Let $\omega^{CK}_1$ denote the least non-recursive ordinal. Suppose we have an unknown well-ordering of $\mathbb{N}$ of the order type $\omega^{CK}_1+1$ as an oracle. Is it possible to write an algorithm using this oracle that implements a well-ordering of $\mathbb{N}$ of the order type $\omega^{CK}_1$?
Can we implement $\omega^{CK}_1$ using $\omega^{CK}_1+1$ as an oracle?
2 Answers
Colin provided an answer showing that for any particular oracle coding a relation of order type $\omega_1^{ck}+1$, we can produce an ordering of type $\omega_1^{ck}$, simply by moving the top ordinal to the bottom. In the comments, you objected that it might not be possible to find the top element. Colin answered that for any particular oracle, there is a particular algorithm that knows which is the top element.
So let me treat the general case, where we want an algorithm that doesn't depend on the oracle, but works with any oracle coding a relation of order type $\omega_1^{ck}+1$.
Suppose we are given an oracle for a relation $\prec$ on $\mathbb{N}$ having order type $\omega_1^{ck}+1$. We shall compute a relation $\lhd$ having order type $\omega_1^{ck}$. The idea is that we will use essentially the same order as $\prec$, but allow in as elements only those nodes for which we have also found a successor node. This will in effect strip off the top element of $\prec$. And since you want your relation to be on $\mathbb{N}$, we shall also re-index the relation so as to use up all of $\mathbb{N}$. Specifically, given an oracle for a relation $\prec$ on $\mathbb{N}$ of order type $\omega_1^{ck}+1$, we define a relation $\lhd$ on $\mathbb{N}$ as follows: if $k_n$ if the $n^{th}$ element of $\mathbb{N}$ found to have a successor with respect to $\prec$, then we define $n\lhd m$ just in case $k_n\prec k_m$. This is uniformly computable in the oracle for $\prec$. Further, the order $\langle\mathbb{N},\lhd\rangle$ is isomorphic to the collection of elements of $\langle\mathbb{N},\prec\rangle$ having successors, and this has order type precisely $\omega_1^{ck}$, as desired.
What the argument shows, is that we may uniformly compute a relation isomorphic to chopping the maximal element off any given linear order relation on $\mathbb{N}$ that has one. That is, the algorithm computes a relation of order type $\alpha$ uniformly from any oracle coding a relation of order type $\alpha+1$.
-
2Yes, that is an interesting queston. Offhand, I would guess that it is impossible to compute uniformly $\alpha$ from $\alpha+\omega$. (If there were an algorithm, couldn't we trick it somehow by inserting more than $\omega$ on top?) – 2012-02-12
Can we just stick the last element onto the beginning? Let $<$ be an ordering of $\mathbb{N}$ with order type $\alpha+1$ for some ordinal $\alpha$. Let $n$ be the $<$-maximum element. For all $x,y\neq n$ let x<'y\iff x
-
1Colin and Carl are correct; but meanwhile, my answer shows that a uniform algorithm also is possible. – 2012-02-12