FANDOM


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!

Ad blocker interference detected!


Wikia is a free-to-use site that makes money from advertising. We have a modified experience for viewers using ad blockers

Wikia is not accessible if you’ve made further modifications. Remove the custom ad blocker rule(s) and the page will load as expected.