Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

1 Answer 1

up vote 3 down vote accepted

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$.

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.