10,831 Pages

## Encoding ordinal as binary relation

Imagine we have an infinite countable ordinal $$\alpha$$, equipped with standard $$<$$ relation. Because $$\alpha$$ has cardinality of $$\mathbb{N}$$, there is an ordering of $$\mathbb{N}$$ which "resembles" ordering of $$\alpha$$. For example, if we take ordering of $$\omega2+4$$, that is $$0<1<2<3<...<\omega<\omega+1<...<\omega2<\omega2+1<\omega2+2<\omega2+3$$, we can take following ordering of natural numbers: $$4<6<8<10<...<5<7<9<...<0<1<2<3$$.

Technically, this "resemblance" means that they have the same order type, and there is order-preserving mapping between them. Order-preserving mapping is bijection $$f:\alpha\rightarrow\mathbb{N}$$, such that $$\beta<\gamma\Leftrightarrow f(\beta)\triangleleft f(\gamma)$$, where $$\triangleleft$$ is this non-standard ordering of natural numbers. In our example, we have $$f(n)=2(n+2), f(\omega+n)=2(n+2)+1,f(\omega2+m)=m$$ for $$n\in\mathbb{N}$$ and $$m\in\{0,1,2,3\}$$.

We also have to note, that $$\triangleleft$$ relation is transitive, i.e. if $$a\triangleleft b$$ and $$b\triangleleft c$$ then $$a\triangleleft c$$. In above example, we have $$4\triangleleft6$$ and $$6\triangleleft8$$, from which we have $$4\triangleleft8$$.

## Encoding binary relation as subset of $$\mathbb{N}^2$$

Imagine we have an ordering $$\triangleleft$$ of $$\mathbb{N}$$. Actually, it can be any relation. Now we code this relation as a set $$S\subseteq\mathbb{N}^2$$ in a following way: let's take any $$a,b\in\mathbb{N}$$. Then we have $$(a,b)\in S\Leftrightarrow a\triangleleft b$$. Let's look at the examples: we have $$(0,1)\in S$$ because $$0\triangleleft1$$, but we don't have $$(1,0)\in S$$, because in our relation we don't have $$1\triangleleft0$$. We also don't have $$(0,0)\in S$$, or actually for any $$n$$ we don't have $$(n,n)\in S$$. We have, however, things like $$(5,1),(4,5),(4,8)...$$

## Encoding subset of $$\mathbb{N}^2$$ as subset of $$\mathbb{N}$$

For this, we need a bijection $$f:\mathbb{N}^2\rightarrow\mathbb{N}^2$$. There is plenty of possible encodings, but the one I use is $$f(a,b)=2^a(2b+1)-1$$. One can easily verify that this function is bijective. I have choosen this particular one because of computational simplicity.

The encoding of a set $$S\subseteq\mathbb{N}^2$$ is so called image of this set under $$f$$. In simple terms, it's a set $$S'\subseteq\mathbb{N}$$ such that $$(a,b)\in S\Leftrightarrow f(a,b)\in S'$$. For example, if $$S=\{(0,n):n\in\mathbb{N}\}$$, then $$S'$$ is exactly the set of even numbers. If $$S=\{(m,0):n\in\mathbb{N}\}$$, then $$S'=\{0,1,3,7,15,...\}$$ contains exactly the numbers one less than some power of 2.

## Encoding subset of $$\mathbb{N}$$ as binary string

This is an easy part. Given set $$S\in\mathbb{N}$$ we map to a string $$w\in\{0,1\}^\omega$$ such that $$n\in S\Leftrightarrow w(n)=1$$, where $$w(n)$$ means $$n$$th bit of $$w$$. This simply means that n-th bit of string is 1 iff number n is in S. One example could be $$\mathbb{P}=\{n:n\text{ is prime}\}=\{2,3,5,7,11,13,...\}$$, which will map to a string $$0_00_11_21_30_41_50_61_70_80_90_{10}1_{11}0_{12}1_{13}0_{14}...$$ (subscript just show which bit is which).

So here it is! Now we have series of functions $$\omega_1\backslash\omega\rightarrow\{R:R\text{ is ordering on }\mathbb{N}^2\}\rightarrow\mathcal{P}(\mathbb{N}^2)\rightarrow\mathcal{P}(\mathbb{N})\rightarrow\{0,1\}^\omega$$ which codes ordinals into binary strings!