Doesn't well ordering theorem disprove Cantor's argument of uncountable set?

Question

If there is a well ordering principle, can i not use it to define a bi-jection from $\mathbb N \to A$ (where $A$ is an uncountable set)?

If not how does transfinite induction hold true?

Answer 1

The well-ordering principle states that any set can be well-ordered - that is, for any set $X$, there is a binary relation $\preccurlyeq$ on $X$ which

• is a linear order, and

• has no infinite descending chains.

The usual ordering on $\mathbb{N}$ is the simplest example of an infinite well-ordering; but there are lots of others! There are even lots of countable well-orderings.

The key point is that even if $\preccurlyeq$ is a well-ordering, there may be elements of $X$ with infinitely many things $\preccurlyeq$-below them. This is not obvious at first, but a good example is the set $\mathbb{N}\cup\{\infty\}$ ordered in the obvious way. Then $\infty$ has infinitely many things below it; but the order is still a well-order. To see this, try counting down from $\infty$: we start with $\infty$, and then we have to pick something smaller than $\infty$ - but whatever we pick will be finite, and so our descending chain will be finite.

Similarly, consider the set $\mathbb{N}\times\{0, 1\}$, ordered by setting $(a, b)\preccurlyeq (c, d)$ if $c=0, d=1$ or $c=d$ and $a\le b$ in the usual sense. Think of this as "$\mathbb{N}+\mathbb{N}$." It's a good exercise to show that this is a well-ordering.

So when we well-order a set, there's no reason to expect the well-ordering we get to look like $\mathbb{N}$. From here it's a short jump to seeing that there are in fact uncountable well-orderings: the (isomorphism classes of) countable well-orderings are well-ordered by length!

So there is in fact no contradiction here.

Answer 2

If you consider equivalently the axiom of choice, you can start from a collection $(X_i)$ of nonempty sets indexed by the real numbers. Then from each set $X_i$ one can choose an arbitrary element and in this way obtain a collection $(x_i)$ of elements indexed by the real numbers. Per se, there is no bijection with the set of natural numbers.