Using existence of Hartogs number in proving uncountability of reals, and whether the approach is equivalent to diagonal method This will be my last question in a series regarding uncountability of reals. My knowledge of set theory is limited, but I read somewhere that existence of Hartogs number can be used to prove Cantor theorem. I will limit the scope to uncountability of the set of real numbers here.
My question:


*

*How does existence of Hartogs number lead to uncountability? (asking for proof)

*Is this proof basically diagonalization approach?

 A: Let $\omega_1$ be the least uncountable ordinal (guaranteed by Hartogs' result and the well-orderedness of the ordinals), and suppose $\mathbb{R}$ were countable. Then we get a surjection $\sigma$ from $\mathbb{N}$ to $\omega_1$, since countable ordinals can be coded by real numbers (see below for details). But for each $n\in\mathbb{N}$, the ordinal $\sigma(n)$ is countable since $\omega_1$ is the least uncountable ordinal, which means that $\omega_1$ can be written as a countable union of countable sets - and this implies that $\omega_1$ is countable, via the Axiom of Choice.
This is not a diagonalization argument; however, it is absolutely terrible, as it requires both Replacement (much stronger than Separation, which is enough for the uncountability of $\mathbb{R}$ via the usual argument) and Choice (since without Choice it is consistent that $\omega_1$ is a countable union of countable sets).

Here's how to code countable ordinals as reals:


*

*A countable ordinal has the same ordertype as some binary relation $R$ on $\mathbb{N}$ (exercise).

*Any binary relation $R$ on $\mathbb{N}$ can be coded as a set of natural numbers - namely, as $S_R=\{\langle a, b\rangle: aRb\}$, where "$\langle\cdot,\cdot\rangle$" is your favorite pairing function on $\mathbb{N}$ (say, the Cantor pairing function).

*Finally, use any of the usual injections $i$ from $\mathcal{P}(\mathbb{N})$ to $\mathbb{R}$, and we say a real $r$ codes a countable ordinal $\alpha$ if $r$ is the $i$-image of the set coding $R$ for some $R$ of ordertype $\alpha$.
A: Here's a proof which doesn't use the axiom of choice.
Assume $\mathbb{R}$ were countable. Then $\mathscr{P}(\omega\times\omega)$ would be countable, by a simple coding argument.  It follows that the set $W$ of well-orderings of $\omega$ would be countable, since $W\subseteq\mathscr{P}(\omega\times\omega).$
Let $\langle w_n \mid n\lt\omega\rangle$ be an enumeration of $W.$ Construct a well-ordering $w$ by starting with $w_0,$ appending $w_1,$ then appending $w_2,$ etc.  Then $w$ is a well-ordering of $\omega$ of order type greater than every countable ordinal, which is a contradiction.  [Strictly speaking, you would construct $w$ as a well-ordering of $\omega\times\omega,$ where $\langle\langle m,a\rangle,\langle n,b\rangle\rangle\in w$ iff $m\lt n$ or $(m=n\text{ and }\langle a,b\rangle\in w_m).$ But $w$ can then easily be coded as a well-ordering of $\omega.]$
What is the connection with Hartogs' theorem? You could view the contradiction above as a contradiction to Hartogs' theorem (since $w$ would be a well-ordering of $\omega$ of order type at least $\omega_1,$ which is guaranteed to exist by Hartogs' theorem), or, maybe better, you could view it as a proof inspired by Hartogs' theorem.
To answer your second question also, this really is different from diagonalization and cannot be rephrased in that guise.
Edit: I see that this is similar in spirit to @NoahSchweber's answer, but it's set up to avoid using the axiom of choice (since I don't take a detour through a countable union of countable ordinals, but simply handle the well-orderings directly).
