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

Posted on by

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:

  1. ALL is not a full list of computable ordinals, which means it is not computable, or
  2. <_{\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.

Leave a comment