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?

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.
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.
• 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. – Andrés E. Caicedo Jan 23 '11 at 19:25