Why is the Well Ordering Theorem true? I'm having some troubles recently understand why every set can be well ordered.
I mean suppose it's true, then $\mathbb{R}$ can be well orderd, suppose $a\in \mathbb{R}$ is the first, then we will define a function $f:\mathbb{R} \rightarrow \mathbb{N}$ and say $f(a)=1$. Then we will look at $\mathbb{R}\backslash \{a\}$ (it's a subset of $\mathbb{R}$) then there is $b\in \mathbb{R}$ such that he is the first, and we will define $f(b)=2$ and then we can continue like that in contradiction that $\mathbb{R}$ is uncountable.
Can you please tell me where is my mistake? And maybe give me a "feeling" about why we can suppose this axiom is true? Thank you very much.
 A: The construction of your function $f$ can never exhaust all of $\mathbb{R}$. So it will never be defined at all of $\mathbb{R}$. Maybe it is clearer if you try constructing it the other way around. We construct $g: \mathbb{N} \to \mathbb{R}$ as follows. Let $g(0)$ be the least element in the well-order of $\mathbb{R}$. Then let $g(1)$ be the least element in $\mathbb{R} - \{g(0)\}$, and continue this process. This does define a function, but it is just not surjective.
Note that there are more well-ordered sets than just $\mathbb{N}$. For example, we can put two copies of $\mathbb{N}$ after each other. This is a well-order, but it has "infinite" elements. We usually denote this well-order by $\omega + \omega$. We can already create many different well-orders in this way: $\omega + \omega + \omega$ etc. These are all countable, but there are also uncountable ones. Such as for example any well-order we put on $\mathbb{R}$.

This last sentence uses the axiom of choice of course (or the well-ordering theorem, which is equivalent). We can already construct uncountable well-orders without choice using Hartog's lemma.
