May I ask why "Let $ω_1$ be the first uncountable ordinal. There's a bijection $f:ω_1×ω_1→ω_1$. " Thanks!
-
4$\begingroup$ Because "the following relation well-orders $\omega_1\times\omega_1$ in type $\omega_1$ and thus indirectly provides the desired bijection. For $\langle\alpha,\beta\rangle,\langle\gamma,\delta\rangle\in\omega_1\times\omega_1$ define $\langle \alpha,\beta\rangle \preceq\langle\gamma,\delta\rangle$ iff one of the following holds: (1) $\max\{\alpha,\beta\}\lt\max\{\gamma,\delta\}$; (2) $\alpha=\gamma$ and $\beta\le\delta\lt\alpha$; (3) $\beta\lt\alpha=\delta\ge\gamma$; or (4) $\beta=\delta$ and $\alpha\le\gamma\le\beta$." $\endgroup$– t.b.Jan 9, 2012 at 15:03
-
3$\begingroup$ See my answer here: math.stackexchange.com/questions/54892/about-a-paper-of-zermelo/… $\endgroup$– Asaf Karagila ♦Jan 9, 2012 at 15:13
-
$\begingroup$ @t.b.: This might be a stupid question. But, does that implies $\omega_1\times\omega_1=\omega_1$ ? $\endgroup$– BumblebeeJul 6, 2017 at 23:26
1 Answer
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$.