I want to share a way to construct the order type of the Church-Kleene ordinal ω₁^CK. As far as I’m aware, this construction is original to me, and I think it’s much simpler and more elegant than others that I’ve found on the internet. Please let me know if you see any issues with it!

So, we start with the notion of a computable ordinal. A computable ordinal is a computable well-order on the natural numbers. In other words, it’s a well-order < on ℕ such that there exists a Turing machine that, given any two natural numbers n and m, outputs whether n < m according to that order.

There’s an injection from computable well-orders on ℕ to Turing machines, so there are countably many computable well-orders (at most one for each Turing machine). This means that there’s a list of all such computable well-orders. Let’s label the items on this list in order: {<₀, <₁, <₂, <₃, …}. Each <_n stands for a Turing machine which takes in two natural number inputs and returns true or false based on the nth computable well-ordering.

Now, we want to construct a set with order type ω₁^CK. We’re going to have it be an order on the natural numbers, so what we have to work with from the start is the set {0, 1, 2, 3, 4, 5, 6, …}.

We start by splitting up this set into an infinite collection of sets. First, we take every other number, starting with 0: {0, 2, 4, 6, 8, …}. That’ll be our first set. We’ve left behind {1, 3, 5, 7, 9, …}, so next we take every other number from this set starting with 1: {1, 5, 9, 13, …}. Now we’ve left behind {3, 7, 11, 15, …}. Our next set, predictably, will be every other number from this set starting with 3. This is {3, 11, 19, 27, …}. And we keep on like this forever, until we’ve exhausted every natural number.

This gives us the following set of sets:

{{0, 2, 4, 6, …}, {1, 5, 9, 13, …}, {3, 11, 19, 27, …}, {7, 23, 39, 47, …}, …}

Now, we define our order to make everything in the first set less than everything in the second set, and everything in the second set less than everything in the third set, and so on. So far so good, but this only gives us order type ω². Next we define the order WITHIN each set.

To do this, we’ll use our enumeration of computable orders. In particular, within the nth set, the ith number will be less than the jth number exactly in the case that i <_n j. You can think about this as just treating each set “as if” it’s really {0, 1, 2, 3, …}, then ordering it according to <_n, and then relabeling the numbers back to what they started as.

This fully defines our order. Now, what’s the order type of this set? Well, it can’t be any particular computable order type, because every computable order type can be found as a sub-order of it! So it must be some uncomputable order type. And by construction, we know it must be exactly the order type that contains all and only computable order types as suborders. But this is just the order type of the Church-Kleene ordinal!

So there we have it! We’ve constructed ω₁^CK. Now, remember that the Church-Kleene ordinal is uncomputable. But I just described an apparently well-defined process for creating an ordered set with its order! This means that some part of the process I described must be uncomputable. Challenge question for you: Which part is uncomputable, and can you think of a proof of its uncomputability that is independent of the uncomputability of ω₁^CK?