# Bijection between countable ordinals and reals

The set of all countable ordinals is $\omega_1$, which has a cardinality of $\aleph_1$. When accepting the continuum hypothesis, $2^{\aleph_0} = \aleph_1$, so a bijection between countable ordinals and real numbers exists. Is there any known bijection of this type?

• I am not sure I understand your question. Are you asking whether, from the mere knowledge that there is a bijection, we can actually define one? In general, this depends on what notion of definability you are working with. There are models of set theory where there are (very) explicitly definable such bijections, and there are other models where no bijection is definable in quite a general sense. – Andrés E. Caicedo Dec 21 '13 at 7:01
• I don't understand either, but for a different reason. If there was a "known bijection of this type" then the continuum hypothesis would no longer have to be accepted, right? It would be proven? – Jeff Dec 21 '13 at 8:12
• I think that an answer with involves forcing arguments might merit this question with a [set-theory] tag, rather than an [elementary-set-theory] tag after all. – Asaf Karagila Dec 22 '13 at 16:29

The use of the term "known bijection" is unclear. If you mean an explicit formula in the language of set theory that $\sf ZFC$ proves it to be a bijection, then the answer is no. If that would have existed then the continuum hypothesis would have been a theorem, rather than a consistent sentence.

Under certain assumptions, for example $V=L$, there is a definable bijection, and one can say, if so, that there is a statement in the language of set theory which under the additional axiom $V=L$, defines a bijection between $\omega_1$ and $\mathcal P(\omega)$.

However, in general there is no parameter free $\varphi$ such that $\sf ZFC+CH$ proves that $\varphi$ defines a bijection. Assume by contradiction that $\varphi(x,y)$ defines such a bijection (so $x\subseteq\omega$ and $y<\omega_1$). $\newcommand{\forces}{\mathrel{\Vdash}}$

Now consider $V\models\sf ZFC+CH$, and let $\Bbb P=2^{<\omega}$ in $V$ be the Cohen forcing adding a single real, whose canonical name is $\dot r$. Let $G$ is a generic filter, then $V[G]$ is also a model of $\sf ZFC+CH$.

Therefore in $V[G]$ the formula $\varphi(x,y)$ still defines a bijection, therefore there is some $\alpha<\omega_1$ and $p\in G$ such that $p\forces\varphi(\dot r,\check\alpha)$. Let $m,n$ two integers not in the domain of $p$ (recall that a condition is a partial function from $\omega$ into $2$ with a finite domain) and consider the $2$-cycle $(m\ n)$ as a permutation of $\omega$. By standard arguments this permutation extends to the forcing and the names, and we have, $$p\forces\varphi(\dot r,\check\alpha)\iff\pi p\forces\varphi(\pi\dot r,\pi\check\alpha)=p\forces\varphi(\pi\dot r,\check\alpha).$$ Therefore $p$ forces that $\varphi$ does not define a bijection. This is a contradiction to the assumption that it does.

Note: If we allow parameters, then of course that such formula exists, since we just need to write as a formula in $\varphi(x,y,u)$ that $u$ is a bijection between $\mathcal P(\omega)$ and $\omega_1$ and that $u(x)=y$. That clearly creates circularity in the question, so I only treated the parameter free case.

Of course one can define a whole wide spectrum of allowed parameters, real numbers, countable sets of real numbers, and so on and so forth. I have only dealt with the simplest case in my above answer, and there might be a positive answer if we use strong enough parameterization; but my suspicion is that any such answer would amount to encoding the bijection in one way or another.

• Re your first paragraph: Well, that's not quite clear. We could have an explicit formula that only works under $\mathsf{CH}$. For example, there is an explicit formula defining a well-ordering of a set of reals, but the formula only gives us a well-ordering of $\mathbb R$ iff $\mathbb R=\mathbb R^L$. – Andrés E. Caicedo Dec 22 '13 at 16:48
• Re your closing note: But there is much in between no parameters and alloing the bijection as a parameter. There are formulas with reals as parameters, or with ordinals, or with stationary sets. There is a whole subfield of set theory that works on defining well-orderings from such parameters under specific situations. – Andrés E. Caicedo Dec 22 '13 at 16:51
• @Andres: Yes, I meant that it is provable from $\sf ZFC+CH$, not from a stronger theory (as I mention in the second paragraph). – Asaf Karagila Dec 22 '13 at 16:52
• As for the second comment, yes. I agree with that as well. But the spectrum becomes too large for an answer on MSE, I believe. On an answer on MO, I'd feel comfortable giving this answer and the needed variants for various parameters (I had to think about the parameter free proof a few minutes to begin with, going further would require more work, of course). But on MSE my preference is to try and give either hints or relatively full explanations. So doing all that seemed like too much for just an answer. I'll edit your comment in, by the way. – Asaf Karagila Dec 22 '13 at 16:54