ordinals | Martynas M.

Is the Kleene’s set $\mathcal{O}$ of all computable ordinals computable? The answer is, no. It is an old result, but I think trying to prove it yourself is a good exercise to learn some basics when it comes to ordinals.

Note, in the proofs below ordering = well-ordered set.

Proof #1

Suppose $\mathcal{O}$ is computable, then it is listable: $\text{ALL}[i] = <_{i}$ . Using ALL we can construct a new computable ordering: $<_x(m,n)= \neg \text{ALL}[m](m,n)$ . $<_x$ is computable, therefore in the list ALL, so it has some index $j$ : $<_x = \text{ALL}[j]$ . We can now give $j$ as an input to $<_x$ and obtain a contradiction: $<_x(j,n) = \text{ALL}[j](j,n)$ and $<_x(j,n)= \neg \text{ALL}[j](j,n)$ . Therefore, $\mathcal{O}$ is not computable.

Proof #2

Suppose the set of all computable ordinals is computable. Then it is listable: ALL[i] = $(\mathbb{N}, <_i)$ (I will conflate $(\mathbb{N}, <_i)$ with $<_i$ ). We can construct a new computable ordering:

def <_ALL(m,n):
    (b1, x) = unpair(m)
    (b2, y) = unpair(n)
    if b1 == b2:
        b = ALL[b1]
        return b(x, y)
    else:
        return b1 < b2

$B=(\mathbb{N},<_{\text{ALL}})$ is a computable ordering of type $\beta$ . $A_i = (\mathbb{N}, <_i)$ is a computable ordering of type $\alpha_i$ .

If we could prove that $\forall i :\beta > \alpha_i$ , then this would prove that $\beta$ is not in the list ALL. Let’s do that.

For every $i$ we can construct a new computable ordering $<_{ALL'}$ :

ALL' = copy(ALL)
ALL'[0], ALL'[i] = ALL[i], ALL[0]

def <_ALL'(m, n):
    (b1, x) = unpair(m)
    (b2, y) = unpair(n)
    if b1 == b2:
        b = ALL'[b1]
        return b(x, y)
    else:
        if b1 < i and b2 == i:
            return False
        elif b1 == i and b2 < i:
            return True
        else:
            return b1 < b2

For every $<_{\text{ALL'}}$ there exists an order-preserving bijection $g(x)$ s.t. $x <_{\text{ALL}} y \Longleftrightarrow g(x) <_{\text{ALL'}} g(y)$ :

def g(x):
    (k, z) = unpair(x)
    if k != 0 and k != i:
        return x
    else:
        if k == 0:
            return pair(i, z)
        else:
            return pair(0, z)

Therefore ordering $B_i = (\mathbb{N}, <_{\text{ALL'}})$ also has the order type $\beta$ . Next, let’s take the initial segment of $B_i$ , namely $C=({ x \in \mathbb{N} ~ | ~ (k,z) = \text{unpair}(x) \land k < 1 }, <_{\text{ALL'}})$ . $C$ has the order type $\alpha_i$ . Because $C$ is a proper subset of $B_i$ , $\beta > \alpha_i$ . Since we can perform the same procedure for every $i$ , $\forall i : \beta > \alpha_i$ .

So a computable ordering of type $\beta$ is not in the list ALL. Yet, $<_{\text{ALL}}$ is computable. So either:

ALL is not a full list of computable ordinals, which means it is not computable, or
$<_{\text{ALL}}$ is not computable, but unpair(x) and ALL[i](x,y) are computable, which only leaves the list ALL to be not computable.

Thus, ALL is not computable and therefore the set of all computable ordinals is not computable.

Martynas M.

Tag Archives: ordinals

Two Proofs That The Set of All Computable Ordinals Is Not Computable

Proof #1

Proof #2