The Well-Ordering Theorem and Uncountably Infinite Sets So, I've been doing some reading regarding the Well-Ordering Theorem, and I've come across something that doesn't quite make sense. Per Wikipedia, the Well-Ordering Theorem states that any set $X$ is well-ordered, and thus that any non-empty subset of $X$ has a least element. It is also shown to be equivalent to the axiom of choice, and thus independent from the axioms of ZF. The truth of the theorem seems trivial for a finite set, and it also makes sense for a countably infinite set by way of putting that set in bijection with the natural numbers. I'm running into some confusion trying to play with it for uncountably infinite sets, which have strictly greater cardinality than $\mathbb{N}$. Here's my line of logic, assuming the Well-Ordering Theorem:

Let $X$ be an uncountably infinite set. $X$ is well-ordered; denote this order by $\prec$. Now, define a mapping $\sigma:X\rightarrow X$ as follows. For any $k \in X$, let $G_k = \{m\in X \mid \lnot(m\prec k)\}$. Then let $\sigma(k)$ be the least element of $G_k\setminus\{k\}$. Thanks to the Well-Ordering Theorem, $\sigma(k)$ is well-defined except in the case where $G_k\setminus \{k\}=\emptyset$. That is only possible in the case that $k$ is the greatest element of $X$ under $\prec$. Assume that no such maximal element exists; this must be true for at least some possible sets $X$. Then $\sigma$ is a successor function on $X$, mapping each element of $X$ to the next-greatest element. Let $l$ be the least element of $X$ under $\prec$. Then define a new mapping $\theta:X\rightarrow \mathbb{N}$, such that $\theta(l) = 1$ and $\theta(\sigma(k)) = \theta(k)+1$ for all $k \in X$. It is clear that $\sigma$ is an injection, which implies that $\lvert X \rvert \leq \lvert \mathbb{N} \rvert$. However, this contradicts the assertion that $X$ is uncountably infinite.

I clearly have to have some sort of mistake in my logic here, but I can't for the life of me figure out where I've gone wrong. My only thoughts are either that I've somehow taken some step in my logic which cannot be taken for uncountably infinite sets, or that the Well-Ordering Theorem asserts the existence of a least element in any subset of $X$, but does not allow you to pick out and identify that element. That last one seems a bit unlikely to me, so my bet is I've messed something up. I'd love to hear the thoughts of anyone who wants to point out my mistakes so that I can understand this a little better. Cheers!
 A: Your function $\theta$ is not defined for every element of $X$. In fact, it is only defined on a very small subset of $X$. Think about the following example:
Suppose we order the natural numbers in the following way:
$$1 \prec 3 \prec 5 \prec \cdots \prec 0 \prec 2 \prec 4 \prec \cdots$$
It is a well order because for any $S \subset \mathbb{N}$, the smallest element is the smallest odd number in $S$, if there is one, and the smallest even number in $S$ if it doesn't have odd numbers.
Now your $\theta$ would map 1 to 0, 3 to 1, 5 to 2, and so on. The question is, what is 0 mapped to? It is not the successor of any element in this ordering.
So your $\theta$ function is only defined for a very small initial segment in the ordering. It cannot be used to show that $|X| \leq |\mathbb{N}|$.
A: As Noah's comment and user224...'s answer shows, defining functions recursively on well-ordered sets is more subtle than this; you've assumed implicitly that every element other than the least element has a predecessor but this fails for every infinite well-ordered set other than those isomorphic to $\mathbb{N}$.
Instead you have to recursively define functions $f$ on well-ordered sets like this:

*

*First describe what $f$ does to the least element.

*Then describe what $f$ does to an element with a predecessor, as a function of that predecessor.

*Then describe what $f$ does to an element $x$ without a predecessor, as a function of the initial segment $\{ y : y < x \}$.

This is called transfinite recursion. You can learn more by looking up ordinals and seeing how, for example, ordinal arithmetic operations are defined.
It may also help to see an explicit (well, "explicit") example of an uncountable well-ordered set; for that see the first uncountable ordinal.
