# Axiom of Choice and the cardinality of the reals

Assuming the Axiom of Choice, (it seems that) there is a bijection between $\mathbb{R}$ and $\mathbb{N}$ that follows from any well-ordering of the reals. That is, given a well-ordering of $\mathbb{R}$, the nth real number in the ordering would correspond to the nth natural number.

On the contrary, if the reals are assumed to be countable, a contradiction can quickly be reached using Cantor's Diagonal Argument.

Where am I mistaken? Is it my understanding of well-ordering?

-
 +1: Good question. Also, I have deleted some tags. – Aryabhata Jan 5 '11 at 1:18 en.wikipedia.org/wiki/Ordinal_number – Qiaochu Yuan Jan 5 '11 at 1:39 @downvoter I would appreciate it if you told my why you down voted my question so that I may ask better questions in the future. – jericson Jan 24 '11 at 2:33

Your error is thinking that "well-ordered and infinite" means "bijectable with $\mathbb{N}$". Your argument is not even enough to give a bijection between $\mathbb{N}$ and the following well-ordering of the integers: order the nonnegative integers in the usual way; make every negative number larger than any nonnegative number, and compare negative numbers by comparing their absolute value. That is, the well ordering $$0, 1, 2, 3,\ldots, n,\ldots ; -1, -2, -3, \ldots, -n, \ldots$$ where ";" means that $-1$ is larger than any nonnegative integer. This type of order is called $\omega+\omega$, because it is essentially two copies of $\mathbb{N}$, one placed after the other ($\omega$ is the ordinal name of the well-order of the natural numbers). This is still countable, of course, but you can probably see already that your argument about well-ordering the reals to get a bijection with $\mathbb{N}$ is already in serious trouble: you have no warrant for assuming that it will actually "hit" every real number (and in fact, it won't).

Added: Just for completeness: to show this is a well ordering of $\mathbb{Z}$, let $A$ be any nonempty subset of $\mathbb{Z}$. If $A\cap\mathbb{N}$ is nonempty, then the least element of $A$ is the least element $\mathbf{a}$ of $A\cap\mathbb{N}$ (my naturals include $0$, by the by), since given any $a\in A$, if $a\in\mathbb{N}$ then by definition of $\mathbf{a}$ we have $\mathbf{a}\leq a$. And if $a$ is negative, then since $\mathbf{a}$ is nonnegative we have $\mathbf{a}\leq a$. Thus, $\mathbf{a}$ is the least element of $A$. If, on the other hand, we have $A\cap\mathbb{N}=\emptyset$, then that means that $A$ consists only of negative numbers. Let $B=\{ |a|\mid a\in A\}$. Then $B\subseteq\mathbb{N}$ and is nonempty, so it has a least element $\mathbf{b}$. Then $\mathbf{a}=-\mathbf{b}\in A$ is the least element of $A$, since given any $a\in A$, we have that $a$ is negative by assumption and so that $|\mathbf{a}| = \mathbf{b}\leq |a|$; since this is how we compare negative numbers in this order, we have that $\mathbf{a}$ is less than or equal to $a$, hence $\mathbf{a}$ is the least element of $A$, as claimed.

-
thank you for the very nice example! I see now where my thinking was wrong. – jericson Jan 5 '11 at 1:25

Well orderings can be much longer than $|\mathbb{N}|$. There certainly is an nth real in the well-order, but there are reals with much higher ordinals as well. One form of AC is that any set can be well-ordered, but that does not imply that all infinite sets have the same cardinality.

-

Given the set of all subsets of the natural numbers and the axiom of choice it does seem that one should be able to form a set by picking an element from each subset. Yet this set will have cardinality of 2^(aleph0). Given that the set of naturals only extend to omega, how could a well ordering be placed upon this set? It's elements will not be unique. I have read that the axiom of choice only applies to collections of sets that have no elements in common. So it seems then that we can only select up to the cardinality of the set that contains this collection. Given this, it seems that the naturals could not be used to order the reals because such an ordering would imply multiple lowest ranking elements.

-
 You have several mistakes here: The set formed by picking elements is not necessarily of cardinality $2^{\aleph_0}$, since nobody is requiring that the elements you pick for different sets are different. In fact, it is impossible in this case that the set of elements you pick is of the size you say because, as you say, there are only countably many natural. You will be picking the same element a lot of times. This has nothing to do with whether you can well-order the collection of subsets of natural numbers. – Andres Caicedo Jan 23 '11 at 19:25 Also, you may be misremembering what you read, because the axiom of choice applies to any non-empty collection of non-empty sets, not just to collections of disjoint sets. If you are skeptical of this claim, note that the axiom of choice is provable for finite collections (in set theory without choice), and there are many finite collections of non-empty sets that have elements in common. A harder problem is whether you can find injective choice functions. Of course, this is highly dependent on the specific family under consideration, but it is a completely different question. – Andres Caicedo Jan 23 '11 at 19:28