How exactly does the oracle for a well-order of order type $\omega_1^\text{CK}$ operate?

Question

The concept of an oracle for Turing machines assumes that the oracle answers Yes/No to a particular question $Q$, assuming that $Q$ is formulated as a bitstring on the oracle tape (instead of answering Yes/No, the oracle can generate the answer as a bitstring on the oracle tape).

Let $O$ denote an oracle that “encodes a well-order of order type $\omega_1^\text{CK}$” or, in other words, “has access to the well-order relation describing the well-ordering of $\omega_1^\text{CK}$ in terms of $\mathbb{N}$”. Can anyone explain what the set of questions for $O$ is and how a particular $Q$ (from the set of all possible questions) is converted to a bitstring?

Answer 1

You're right that we can't really use a structure as an oracle, per se; instead, we look at copies of the structure, that is, ways of representing the structure as a set of natural numbers. Incidentally, everything I say below applies to general countable structures.

A relation $E\subseteq\omega\times\omega$ is a copy of $\omega_1^{CK}$ if it defines a structure isomorphic to $\omega_1^{CK}$; that is, if $(\omega;E)\cong\omega_1^{CK}$. EDIT: If you prefer, you can think of a copy as a pair $(A; E)$ with $A\subseteq\omega$ and $E\subseteq\omega^2$ which is isomorphic to $\omega_1^{CK}$; for our purposes, this won't make a difference - see the comments below. It might be easier to think about this in a simpler case: consider the relation given by $mEn$ iff

• $m$ is odd and $n$ is even, or

• $m,n$ have the same parity and $m<n$.

This is a copy of the ordinal $\omega+\omega$: it's describing the linear order $$1\prec 3\prec 5\prec 7\prec 9\prec ...\prec 0\prec 2\prec 4\prec 6\prec 8\prec ...$$

Copies can be used as oracles in the obvious way, since a copy is just a set of pairs of natural numbers. Of course, there is no unique copy of $\omega_1^{CK}$, although we may argue that one copy or another is particularly "natural." The types of questions we ask in this context range across all copies of a structure; for example, the statement "$\omega_1^{CK}$ is not computable" is shorthand for "there is no computable copy of $\omega_1^{CK}$."

Answer 2

Since you used my phrase too, let me just mention first that a good way to say the same thing might be "well-ordering of/on $\mathbb{N}$ with order-type $\omega_1^{CK}$". To be fair, I can relate to your question very well because if you don't have a formal math background and have never read either an (i) elementary set theory book cover-to-cover (ii) an introductory formal proof book which also covers various types of "ordering" ..... then I think you might just have never encountered many of these terms. Up until I asked first few questions here, I didn't know how to express properly/formally (for which I could simply use that phrase) what I had been playing around with for few years. And it did cause a lot of difficulty for me in asking questions.

Anyway, here is my "informal/naive" take on this (I think an expert answer might be more authoritative place to look, but this might help you in getting some understanding of things). Informally, you can think of "well-ordering of/on $\mathbb{N}$ with order-type $\omega_1^{CK}$" simply as "inducing" a bijection between $\omega_1^{CK}$ and $\mathbb{N}$ (probably if one has to be more formal, one might word it a little differently?). More generally, you can replace $\omega_1^{CK}$ with any (non-finite) $\alpha$ that satisfies $\alpha <\omega_1$ ($\omega_1$ being first uncountable).

If you denote the corresponding (unique/unambiguous) bijective function as $f:\alpha \rightarrow \mathbb{N}$ then the inverse of this $f^{-1}:\mathbb{N} \rightarrow \alpha$ is also of course a bijective function. Now what is the well-order relation corresponding to this well-ordering? It can be simply defined by the function $lessequals:\mathbb{N}^2 \rightarrow \{0,1\}$ such that:

$lessequals(x,y)=$ truth value of $f^{-1}(x) \le f^{-1}(y)$

Note that $f^{-1}(x) \le f^{-1}(y)$ is an ordinal comparison. You can also define the function $lessthan:\mathbb{N}^2 \rightarrow \{0,1\}$ as:

$lessthan(x,y)=$ truth value of $f^{-1}(x) < f^{-1}(y)$

In the given context, it is the function $lessequals$ that can be called the well-order relation (well I am going by description in the wiki link here honestly). But, at any rate, one can observe that both these functions are computationally reducible to each other (somewhat trivially).

---

One can say that an ordinal $\alpha$ is "computable/recursive" if there exists a well-ordering of $\mathbb{N}$ with order-type $\alpha$ (adding a minor exception for finite ordinals I suppose) such that the corresponding well-order relation is computable. $\omega^{CK}_1$ is defined as the smallest ordinal that is not computable/recursive.

There is one important fact here that, while somewhat trivial, is important to know. If $\alpha$ is a recursive ordinal than so is any ordinal $\beta$ (where $\beta < \alpha$).