Existence of a bijection $f:ω_1×ω_1→ω_1$ for the first uncountable ordinal $ω_1$?

Question

May I ask why "Let $ω_1$ be the first uncountable ordinal. There's a bijection $f:ω_1×ω_1→ω_1$. " Thanks!

Answer 1

In http://caicedoteaching.wordpress.com/2009/01/27/580-some-choiceless-results-3/ (see section 6) I show more generally that there is a canonical bijection between $\alpha$ and $\alpha\times\alpha$ for any infinite ordinal $\alpha$. This does not use choice, and does not require that $\alpha$ is a cardinal or even a limit ordinal, so in particular is more general than the argument using Goedel pairings (The ordering indicated by t.b.).

(I believe this can be found in a book by Levy, but don't know who it is due to.)

Some additional details are in the link above, but the idea is to use Cantor's normal form: Any ordinal $\alpha$ can be written in the form $\omega^{\beta_1}n_1+\dots+\omega^{\beta_k}n_k$ where the $n_i$ are positive integers and the $\beta_i$ are strictly decreasing, with $\beta_1>0$ as long as $\alpha$ is infinite.

Fixing a bijection $p:\omega\times\omega\to\omega$ with $p(0,0)=0$ (and $p$ recursive, if you want), we use the normal form to define an injection $G:ORD\times ORD\to ORD$, where $ORD$ is the class of all ordinals:

Given $\alpha,\beta$, write them as $$ \alpha=\omega^{a_1}m_1+\dots+\omega^{a_k}m_k $$ and $$ \beta=\omega^{a_1}l_1+\dots+\omega^{a_k}l_k $$ where the $a_i$ are strictly decreasing and the $m_i$ and $l_i$ are natural numbers (with 0 allowed). Then set $$G(\alpha,\beta)=\omega^{a_1}p(m_1,l_1)+\dots+\omega^{a_k}p(m_k,l_k).$$ Note that $G$ restricts to an injection of $\alpha\times\alpha$ to $\alpha$ whenever $\alpha$ is indecomposable, i.e., of the form $\omega^\gamma$ for some $\gamma$.

The Schroeder-Bernstein theorem has an explicit proof: From bijections $f:A\to B$ and $g:B\to A$ we can exhibit a bijection between $A$ and $B$. In particular, since obviously there is an injection from $\alpha$ into $\alpha\times\alpha$, we now have an explicit bijection between any indecomposable $\alpha$ and $\alpha\times\alpha$.

For an arbitrary infinite ordinal $\beta$, note that $\beta$ can be uniquely written as $\omega^\gamma\cdot n+\delta$ for some positive integer $n$ and ordinals $\delta<\omega^\gamma$.

From the above (and induction on $n$), there is an explicit bijection between $\omega^\gamma$ and $\omega^\gamma\cdot n$, and there is also an obvious bijection between $\omega^\gamma +\delta$ and $\delta+\omega^\gamma=\omega^\gamma$.

From this, we can easily get a bijection betwen $\beta$ and $\beta\times\beta$.