It is well-known that there is a computable pairing function $<\ >:\mathbb N^2\to \mathbb N$. Let $X$ be some reasonable class of countable ordinals ($\omega\_1^{CK}$, $\epsilon\_0$, $\omega^\omega$, or etc.). Is there any computable bijection from $X^2$ to $\mathbb N$? I would like to code pairs like $<\omega, 1>$ by some natural number and to recover the corresponding pair from a given natural number.



Is there a pairing function from countable ordinals to $\mathbb N$?
Coding the pairs from a set $X$ of ordinals is exactly as easy (or hard) as coding the individual elements of $X$. That's because there are very easily computable pairing functions on the natural numbers.


If $X$ is small enough, like $\epsilon\_0$, then this can be done computably, in the sense that there are algorithms for deciding whether a natural number is a code, deciding which of two codes represents the smaller ordinal, deciding whether a code represents a successor or limit ordinal, computing a code for the successor of an ordinal $\alpha$ when given a code for $\alpha$, computing the predecessor if $\alpha$ is a successor, and much more. In the case of $\epsilon\_0$, you can just take the Cantor normal form and Gödel number it to get a code. There are similar but more complicated systems for lots of larger ordinals, in fact, for any proper initial segment of $\omega\_1^{CK}$. The key phrase to look up for (lots of) information about such things is "ordinal notations".


If you want to code all the ordinals below $\omega\_1^{CK}$, rather than just a bounded initial segment of them, then you have to go beyond the computable, and even beyond the hyperarithmetical, in order to do the things I listed in the previous paragraph.


