Expressing computable ordinals as programs

I loved John Baez’s three-part system on large countable ordinals (1, 2, 3) but something nagged at me. It felt like a description of an algorithm in prose, and I feel like I don’t really understand an algorithm until I’ve implemented it. But what does it mean to implement an ordinal?

I found a couple of answers to that online. One is the definition of a recursive ordinal, and the other is Kleene’s O. However both seemed pretty unsatisfactory to me; I wanted something that could naturally express operations like addition/multiplication/exponentiation, as well as expressing finite ordinals.

Here’s where I ended up: we express an ordinal as a set of lexicographically-sorted and well-ordered binary strings with the “prefix property” that no string in the set is a prefix of any other. If $\mathrm{ord}(A)$ is the ordinal represented by set $A$ , we have

$0 = \mathrm{ord}(\{\})$
$1 = \mathrm{ord}(\{\epsilon\})$ ( $\epsilon$ is the empty string)
$2 = \mathrm{ord}(\{0, 1\})$
$3 = \mathrm{ord}(\{0, 10, 11\})$
$4 = \mathrm{ord}(\{0, 10, 110, 111\})$
$\omega = \mathrm{ord}(\{0, 10, 110, 1110, 11110, \ldots\})$
$\omega + 1 = \mathrm{ord}(\{00, 010, 0110, 01110, 011110, \ldots , 1\})$
$\omega^2 = \mathrm{ord}(\{00, 010, 0110, 01110, \ldots , 100, 1010, 10110, \ldots, 1100, 11010, \ldots, 1110, 111010, \ldots\})$

These are just samples: for every ordinal, there are infinitely many sets that could represent it.

Addition and multiplication are easy here:

$\mathrm{ord}(A) + \mathrm{ord}(B) = \mathrm{ord}(\{0 \cdot a | a \in A\} \cup \{1 \cdot b | b \in B\})$
$\mathrm{ord}(A)\mathrm{ord}(B) = \mathrm{ord}(\{b \cdot a | a \in A, b \in B\})$

Exponentiation is a bit harder, I use this idea: consider a function $f: B \rightarrow A$ with finite support. Let $\{b_1, b_2, ... b_n\} = \mathop{\mathrm{supp}}(f)$ where $b_1 > b_2 > ... > b_n$ . Then we represent this function as $1 \cdot b_1 \cdot f(b_1) \cdot 1 \cdot b_2 \cdot f(b_2) \cdot \ldots \cdot 1 \cdot b_n \cdot f(b_n) \cdot 0$ . If $C$ is the set of all such representations for all such functions $f$ , then $\mathrm{ord}(A)^{\mathrm{ord}(B)} = \mathrm{ord}(C)$

Instead of limits, I define an infinite sum function. Given a function $f: \mathbb{N} \rightarrow \mathcal{P}(\{0,1\}^{*})$ we have

$\sum_{i=0}^\infty \mathrm{ord}(f(i)) = \mathrm{ord}(\{1^i \cdot 0 \cdot x| i \in \mathbb{N}, x \in f(i)\})$

The obvious way to represent these sets as programs would be as functions that test for membership of the set. It should be clear how to implement addition and infinite sum with this representation, and multiplication is only a little more complicated. Unfortunately I don’t see how to do exponentiation, because of one small wrinkle: if we’re to get the right answer for finite exponents, we must ensure that every one of our $f(b_i)$ entries are non-zero, ie not the smallest elements of B, and we have no way to find that. So instead I propose a slight wrinkle: we implement instead a function which tells us whether a string is a prefix of any string in the set.

I’ll try to share code implementing all this ASAP, but I wanted to put the ideas out there first. Thanks!

Expressing computable ordinals as programs

Rate this:

Published by Paul Crowley

Leave a Reply Cancel reply