Am a real beginner in set-theory. I read that the Axiom of Choice (AoC) implies the Well-Ordering Theorem…
From what I understand, the gist of the proof is that given any set $X$, we can use AoC to well-order $X$ using induction. Namely, given any element $a_i \in X$ in the ordering, we can use the choice function $c$ (implied by AoC) to select $a_{i+1}=c(X-\bigcup_{j \leq i} a_j)$, and then extend the ordering to include $a_i \leq a_{i+1}$, and so on and so forth …
But suppose that $X=\mathbb{R}$ … if we try to well-order $\mathbb{R}$ using the proof above, up to what extent should we do the induction ? Can we do the induction an uncountable number of times? — up to say … $2^{\omega}+1$ (where $\omega$ is the cardinal number of $\mathbb{N}$) i.e. to "exhaust" all of $\mathbb{R}$)
Best Answer
Firstly, we're using recursion, rather than induction.
Secondly, the recursion can go as long as any ordinal $\alpha$ such that $|\alpha|=|\Bbb R|$, and there are a lot of these, at least $\aleph_2$, and in fact $(2^{\aleph_0})^+$ of them.
To see this in action, fix a well-ordering of $\Bbb N$ which is not of order type $\omega$, e.g., $\omega+1$. Then use this to define a choice function: $c(A)=\min A\setminus\{0\}$ or $0$ if $A=\{0\}$. If we use this as our choice function to well-order $\Bbb N$, we will end up with an order of type $\omega+1$. And the same happens with any other countably infinite ordinal.
So "how long"? Well, some ordinal of cardinality $2^{\aleph_0}$, but there's a lot of them, so it's not possible to pre-determine which one. But that is exactly what makes transfinite recursion trans-finite. The ability to do it over very long well-orders.
(And as a side note, especially when we're dealing with recursion over the ordinals, it's better to use $\aleph$ notation to discuss cardinals, so you should write $2^{\aleph_0}$ rather than $2^\omega$. This way there is no chance of mistaking $2^\omega$ for ordinal exponentiation, which is just $\omega$ again.)