I want to share a way to construct the order type of the Church-Kleene ordinal ω1CK. 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: {<0, <1, <2, <3, …}. 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 ω1CK. 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 ω2. 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 ω1CK. 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 ω1CK?
Your semantics are vague. “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." What you've done in essence is define an algorithm that resembles infinite descent, therefore countable and of order omega. Treating each set "as if" it's N (set of natural numbers) only works if you treat each set as N, in other words you have a single set, namely N! On the other hand, I could also relabel the numbers to anything I want ("what they started as" has no definition provided), in which case I can reach any ordinal I arbitrarily chose, including omega, epsilon, C-K, empty set, whatever. What am I missing?
Maybe I worded things unclearly. Let me try to express it more precisely. Let’s consider a specific set for concreteness. We’ll look at the first set of naturals that we worked with, {0,2,4,…}. Call this set X. We want to define an ordering < on it so that its order type is <0. We do this by first constructing a bijection from X to N (any bijection will do; a simple one that will work is f(n) = n/2). Now define < on X as follows: i < j if and only if f(i) <0 f(j). This guarantees us that the order type of < is the same as the order type of <0. The same applies for each computable ordering. For each
Loading...
Your reply wasn’t published in its entirety on the website, so I still am unable to follow your logic. My major hurdle is “any bijection will do”. No, it won’t. You still need to map N –> N. In which case, you’re back to infinite descent-types of algorithms, of which there are countably many. Perhaps the portions of your reply which WordPress truncated provide more reasoning.
Your example of bijecting via division by 2, for example, is not closed under N. Wouldn’t matter anyway, as the cardinality of algebraic numbers is still aleph-null, and again: countable.
Huh, I’m not sure what happened with the original reply. Let me try again.
Define X = {0,2,4,…}.We want to define an order < on this set with the same order type as <0. First construct a bijection from X to N (f(n) = n/2 works). Now define < on X as follows: i < j if and only if f(i) <0 f(j). This guarantees us that the order type of < is the same as the order type of <0.
The same applies for each computable ordering. For each computable order type, we take our subset of the naturals and define the order < on this set by labelling each element with a unique natural number and applying the computable order to the labels.
As to your comment: Yes, any bijection from X to N will work. By definition, two sets are said to have the same order type if there is an order-preserving bijection from one to the other. We want to construct an order < on X such that it has the same order type as some other pre-determined order <_n on N. So all we need is a bijection that preserves order, and we do this by defining < so that x < y if and only if f(x) <_n f(y).
The choice of function f(n) = n/2 IS a valid bijection from X to N. Remember: X is the set {0,2,4,6,…}, NOT the set N. And I don’t understand why you’re bringing up countability: yes, every set we’re working with here is countable. (Including the Church-Kleene ordinal!) By definition, any order type that can be placed on a set of naturals is going to be a countable order type.
I think you’re confusing cardinality with order type. Two sets can both have cardinality aleph-null and still have different order types. X and Y have the same cardinality = there’s a bijection from X to Y. X and Y have the same order type = there’s an ORDER-PRESERVING bijection from X to Y.
For example: Suppose that <_0 is the following order on the naturals: {1 < 2 < 3 < 4 < … < 0}. This has order type ω+1. We want to construct an order on the set X = {0, 2, 4, 6, 8, …} that also has order type ω+1. How do we do this? By mapping this set to N, and then ordering it according to <0. Define our mapping f(n) to be n/2, so 0 —> 0, 2 —> 1, 4 —> 2, 6 —> 3, and so on. Then order X according to how <0 orders N. This will give us the following order on X: {2 < 4 < 6 < 8 < … < 0}. Order type ω+1, just as we wanted! This is a simple example, but the exact same principle applies for ANY countable order type we choose.
Thanks for the added info, but I keep getting lost. Is 0 a von Neuman ordinal in your mapping? Or put another way, how would you employ the identity function (also bijective).
I suppose a third colloquial way of putting it, is “0” the space bar on your keyboard, or is it the return key?
No, 0 isn’t necessarily a von Neumann ordinal. There’s a distinction between *order types*, which are equivalence classes of order-isomorphic sets and *Von Neumann ordinals*, which are specific sets that are chosen as representatives of each order type for convenience. So, for example, look at the following sets:
{1,2,3,4,…, 0}
{triangle, square, pentagon, hexagon, …, line}
{0,1,2,3,…, ω}
{∅, {∅}, {∅,{∅}}, {∅,{∅},{∅,{∅}}}, …, {∅, {∅}, {∅,{∅}}, …}}
These three sets all have the same order type, despite containing different elements. The last of these is the Von Neumann ordinal ω+1. The third could potentially be a Von Neumann ordinal, depending on whether 0, 1, 2, and so on are understood to represent sets, or not – it’s left vague. But that’s okay! For the purpose of determining the order type of a set, it doesn’t MATTER what exactly the elements are. All that matters is (1) the amount of elements and (2) the way they are ordered. Any set that has an order structure that looks like {a countable infinity of items, after which comes one single item} is in the same equivalence class as the Von Neumann ordinal ω+1. And for a convenient shorthand, we say that this set “has order type ω+1”.
So there’s a bit of equivocating that can be confusing: ω+1 is sometimes understood to mean the Von Neumann ordinal, and otherwise often understood to mean the equivalence class of all sets that have the particular order type of that Von Neumann ordinal. In this post, I constructed a set with the same order type as the Church-Kleene ordinal, but this set is not a Von Neumann ordinal.
And the identity map from {0,2,4,6,…} to {0,1,2,3,…} is NOT bijective. It is one-to-one but not onto.
The noncomputable part is the assumption that there exists a computable enumeration of exactly and only the well-orderings on N. Intuitively, this can’t be true because being a computable well-ordering on N isn’t a finitely observable property. The proof of this is a simple diagonalization argument.
Assume we have a computable function
f : N -> W(N)
where W(N) is the type of well-orderings on N. By the definition of a well-ordering, all elements have unique successors, if such successors exist. In particular, it’s decidable if applying the successor n times to 0 reaches a particular element. We will construct a new well-ordering, call it O, s.t. if 2n+3 is n steps from 0 in f(n) it isn’t in O, and vice versa.
Let all the even numbers in O form an infinite tower with 0 as the least element.
Start a second tower with 1 ordered above all even numbers.
If the nth successor of 0 in f(n) exists and is 2n+3, add it to the second tower.
If the nth successor of 0 in f(n) either doesn’t exist or does and is not 2n+3, insert it into the nth place in the first tower.
For every well-ordering f(n), 2n+3 is either the nth successor of 0 in f(n) and not in O, or the other way around. In this way, O differs from all well-orderings in f(n). O is also computable, meaning that f is incomplete over computable well-orderings.