# Uncountable sets and Naturals

Just a question on uncountable sets.Is there a definition for uncountability which does not rely on bijections from $\mathbb{N}$ ? .Because,whenever we are talking about $\mathbb{N}$,we are not talking about just a set,we are also talking about the algebraic structure inherent to them.The reason I ask this question is that I thought uncountablity was a purely set theoritic idea and now I am thinking maybe it has to do with sets which can't be completely defined by a specific algebra i.e any set which can't be completely defined by a closure of a succesor-like(or maybe an finite) operation.(As an aside,do all uncountable sets support algebras which have a limit operation defined on them ? I know that the reals and the ordinals do and those are the only uncountable sets I know.Are there any uncountable sets which don't support any algebraic structure?).

• Uncountability is a purely set-theoretic concept, and any definition of it is going to boil down to the non-existence of an injection into $\omega$, $\mathbb{N}$, or some other countably infinite set. Your second sentence is false: $\mathbb{N}$ is just a set. It is possible to define various algebraic structures on it, but it’s possible to do that with any set. – Brian M. Scott Dec 3 '11 at 3:47
• Any theory over a finite or countable language, that has an infinite model, has models of every infinite cardinality. So any uncountable set supports an ordered field structure, for example. When $\mathbb{N}$ is used for comparison, it is as a pure set. – André Nicolas Dec 3 '11 at 3:54
• I'm not sure I entirely agree with the other posters here. The consensus has been that countability must be defined in terms of the natural numbers. However, it seems to me that a countable set can be defined very simply as a minimal infinite set. That is, a set $S$ is countable if, for every infinite set $T$, there exists an injection $S \to T$. This definition makes no explicit mention of the natural numbers, and indeed the fact that the natural numbers are countable would have to be proven from this definition using an induction argument. – Jim Belk Dec 3 '11 at 8:29

"Is there a definition for uncountability which does not rely on bijections from $\mathbb{N}$?"

No there is not. Countability is defined specifically to make the cardinality of $\mathbb{N}$ special.

"Because,whenever we are talking about N,we are not talking about just a set,we are also talking about the algebraic structure inherent to them. The reason I ask this question is that I thought uncountability was a purely set theoretic idea and now I am thinking maybe it has to do with sets which can't be completely defined by a specific algebra..."

In set theory, it is standard to define $0=\emptyset$ (that's the emptyset) and the successor function as $S(n) = n \cup \{ n \}$ so that $1 = \{ 0 \} = \{ \emptyset \}$, $2 = \{0,1\} = \{ \emptyset, \{ \emptyset \} \}$, and so forth.

Also in set theory we assume the Axiom of Infinity which can be stated as "There is at least one infinite set". This axiom yields to us that the set $\mathbb{N} = \{ n \colon n = S(k)$ where $k$ is some successor of $\emptyset \}$ actually exists. (If you choose not to assume the axiom of infinity, then uncountable sets don't even exist in the first place, so this is not a "cheat" assumption.)

Now as far as our definition goes, we have not defined arithmetical or algebraic operations on the set $\mathbb{N}$, but we certainly could using the successor function.

"I know that the reals and the ordinals do and those are the only uncountable sets I know.Are there any uncountable sets which don't support any algebraic structure?)."

Careful! You mentioned "the set of ordinals" which is not actually a set, it is a "proper class" (this is the Burali-Forti paradox).

The real numbers are indeed an uncountable set, and so are most subsets of them. For example, $[0,1]$ is uncountable, $(0,1)$ is uncountable, and so forth. However we don't have to restrict ourselves to real numbers.

However, to get away from reals, we can use the standard way to get new uncountable sets through "Cantor's theorem", which says "For any set $X$, the power set of $X$ (written $\mathscr{P}(X)$ has a strictly larger cardinality. This translates directly to mean "given any set $X$, the $\mathscr{P}(X)$ cannot be put into a bijection with $X$".

This means once you have constructed $\mathbb{N}$, you can take $\mathscr{P}(\mathbb{N})$ as an uncountable set that's not the real numbers (or $\mathscr{P}(\mathscr{P}(\mathbb{N}))$, or ....)

• Ok.That cleared some things up for me.The thing I have been trying to understand is what makes these concrete uncountable sets(like reals) uncountable.In case of the reals,I guess it is because of the LUB axiom which i like to think of as a "machine" which takes in a set and spits out a real number.So,somehow we have a way to take in a infinite set and spit out a point and we can use to show that there are no bijections from N to R.I was just wondering whether all concrete examples of uncountable sets have such operations similar to suprememum defined on them.Maybe,I phrased my question badly. – Thiagarajan Dec 3 '11 at 4:19
• To show that the real numbers are uncountable is Cantor's well-known diagonal argument. See this page for more information: en.wikipedia.org/wiki/Cantor%27s_diagonal_argument ------- a generalization of this proof can prove Cantor's theorem that I mentioned in my answer. – tomcuchta Dec 3 '11 at 4:46

I think part of the answer to the question (I'm not completely sure what you are asking, but this may help) is that simply saying that a given set admits a structure of some kind (e.g. that it can be made into a group, ring, etc.) is usually very unnatural: for instance, it's not hard to check that every (nonempty) set can be made into a group. (For finite sets, you can use cyclic groups; for infinite ones, appropriate free groups on a set of the same cardinality.) One has to fix the structure itself (or say that it is somehow canonically determined in terms of other structure that you may impose on your set) to get anything interesting, because there are usually a lot of ways of choosing the structure!

Here is a definition of countable which doesn't rely on the natural numbers.

$A$ is countable, if it is infinite, and whenever $B\subseteq A$ is infinite then there is a bijection between $A$ and $B$.

And uncountable means infinite and not countable. Therefore we have the following definition,

$A$ is uncountable, if it is infinite, and there exists $B\subseteq A$ which is infinite and there is no bijection between $A$ and $B$.

Where we define infinite by either of the following definitions,

1. (Dedekind) $X$ is infinite if there exists an injective function $f\colon X\to X$ which is not surjective.
2. (Tarski) $X$ is infinite if there is a non-empty family $U\subseteq\mathcal P(X)$ without a $\subseteq$-maximal element.

(It should be noted that in the absence of the axiom of choice it is consistent that there is an infinite set satisfying Tarski's definition and not Dedekind's definition.)

Let us see why the above definition of uncountability is provably equivalent to "there is no bijection with $\Bbb N$" (I will assume Tarski's definition of infinite for broader generality):

If $A$ is infinite, and not in bijection with $\Bbb N$, then either there is an injection from $\Bbb N$ into $A$, in which case its range is $B$ a subset of $A$ which is infinite, but there is no bijection between $A$ and $B$; or there is no injection from $\Bbb N$ into $A$ in which case we can show that it is Dedekind-finite, so there is no bijection between $A$ and its proper subsets, but removing one element from an infinite set is still infinite.

In either case there is a subset $B$ of $A$ which is infinite, and there is no bijection between $A$ and $B$.

And if $A$ is infinite and there is a bijection between $A$ and $\Bbb N$, and $B$ is an infinite subset of $A$, then we can construct a bijection between $B$ and an infinite subset of $\Bbb N$ (by restriction any given bijection of $A$ and $\Bbb N$).

Since there is always a bijection between $\Bbb N$ and an infinite subset of $\Bbb N$, it follows that there is a bijection between $A$ and $B$.

So $A$ is countable by the new definition, or in other words, no uncountable. $\qquad\square$

But what about the rest of your post? Well, an arbitrary bijection between two sets is exactly the lack of structure (algebraic or otherwise). Note that there are many bijections between $\Bbb N$ and $\Bbb Q$, but neither respects the algebraic structure of either sets, or its order structure.

The point is that if there is a bijection between $A$ and $B$ and we have certain structure on $A$, then we can transport it to $B$. And if this structure is very useful, as in the case of $\Bbb N$, then it's perhaps a good thing to distinguish it by a special definition.