2
$\begingroup$

Sorry I asked this question as a comment on other thread. I thought I would better ask it as a separate question since I have seen this notation more than few times now and I am not quite certain what it means (I would just like to be "sure" of whether it corresponds with what I describe below or not .... which I had thought of separately before). Since I have had this confusion for some months now after seeing this notation, I would appreciate an answer and be pretty happy to have it cleared.

First the definition .... for any (countable) ordinal $\alpha$ define $PS[\alpha]$ to be the minimal among the following: "smallest ordinal that can't be computed using an (ordinary) program which has access to some arbitrary well-ordering of $\mathbb{N}$ with order-type $\alpha$."

What I mean is that if you take some specific bijection between $\alpha$ and $\mathbb{N}$ (denote the bijection as $f$).Then if you denote $PS_f[\alpha]$ as the smallest ordinal that can't be computed using an (ordinary) program that has access to well-order relation corresponding to the bijection, we define:

$PS[\alpha]=$minimal value $PS_f[\alpha]$ among all possible bijections $f$

Now define:

$\beta_0=\omega_{CK}$

$\beta_{\alpha+1}=PS[\beta_\alpha]$

When $\alpha$ is a limit, $\beta_\alpha$ is defined as supremum of all smallers $\beta_x$'s (where $x<\beta$).

I hope this wasn't too long-winded.Now my question simply is how does $\beta_n$ correspond to notation $\omega^{CK}_n$. I mean obviously $\beta_0=\omega^{CK}_1$, what about beyond this?

$\endgroup$
  • $\begingroup$ Bumped to correct the somewhat misleading phrase "some arbitrary well-ordering of $\alpha$ (in terms of $\mathbb{N}$)." $\endgroup$ – SSequence Sep 8 '18 at 16:08
3
$\begingroup$

Let me first rephrase your question a bit more clearly (if this isn't what you're asking, let me know). It sounds like you are asking about Muchnik (weak) reducibility of ordinals: if $\alpha,\beta$ are countable ordinals, we say $\alpha\le_w\beta$ if any copy of $\beta$ computes a copy of $\alpha$, where by "copy" we mean a relation on the naturals which is isomorphic to $\beta$ (resp. $\alpha$).

It's a theorem of Sacks that the following are equivalent, for a countable ordinal $\theta$:

  • $\theta$ is admissible.

  • For some real $r$, $\theta$ is the least ordinal with no $r$-computable copy.

This immediately shows that $\beta_n=\omega_{n+1}^{CK}$ for finite $n$. At transfinite levels, though, interesting things happen: your $\beta_\omega$ is just $\sup_{n\in\omega}(\omega_n^{CK})$, but this ordinal is not admissible (being an admissible limit of admissibles is stronger than just being admissible) - this is because the map sending $\eta$ to the $\eta$th admissible is $\Sigma_1$, and in particular any admissible limit of admissibles $\alpha$ satisfies $\alpha=\omega_\alpha^{CK}$. So in fact we get the opposite pattern: $$\beta_\omega<\beta_{\omega+1}=\omega_\omega^{CK}<\beta_{\omega+2}=\omega_{\omega+1}^{CK}<...$$ Basically, what we're seeing here is that the "obvious" limit stage definition actually plays badly with the concepts at hand.

EDIT: Addressing the comments below:

  • The definition of $\omega_\alpha^{CK}$ that I'm using is "the $\alpha$th admissible" - that is, the unique ordinal $\gamma$ such that $L_\gamma\models KP$ and $\{\beta<\gamma: L_\beta\models KP\}$ has ordertype $\alpha$. Note that $L_\omega\models KP$, so $\omega_0^{CK}=\omega$ and $\omega_1^{CK}$ is what it should be under this definition.

  • The "higher off-by-one" pattern above goes always thus, except at admissible limits of admissibles (also called "recursively inaccessibles"). When $\theta$ is an admissible limit of admissibles, we get $\beta_\theta=\omega_\theta^{CK}$.


Let me end by mentioning a couple hopefully interesting facts. In the interest of full disclosure, this is part of my work - see respectively this paper (which was partly motivated by this work of Hamkins and Li) and this paper.

  • Muchnik reducibility is nonuniform - this is really what "weak" is referring to. We could also ask about Medvedev (strong) reducibility, $\le_s$: for countable ordinals $\alpha,\beta$ we write $\alpha\le_s\beta$ iff there is some single Turing functional $\Phi_e$ such that whenever $B$ is a copy of $\beta$, $\Phi_e^B$ is a copy of $\alpha$. This is extremely different; for example, we always have $\alpha\le\beta\implies\alpha\le_w\beta$, so Muchnik reducibility linearly (pre)orders the countable ordinals, but there is a club of countable ordinals which are pairwise $\le_s$-incomparable! Similarly, in general the set of ordinals Medvedev reducible to a given one is not closed downwards.

  • Muchnik (and Medvedev) reducibility makes sense in a broader context: it's really about countable structures, not just ordinals per se, and as such is part of computable structure theory. And even the countability restriction can be dropped, by looking at computations in generic extensions. While on the face of things this looks like a horrible intrusion of set theory, Shoenfield's absoluteness theorem then implies that we actually get something not too terrible; in particular, for all countable structures $\mathcal{A},\mathcal{B}$, the following are equivalent:

    • There is a generic extension of the universe in which $\mathcal{A}\le_w\mathcal{B}$.

    • In every generic extension of the universe in which $\mathcal{A},\mathcal{B}$ are each countable, we have $\mathcal{A}\le_w\mathcal{B}$.

    This lets us continue Sacks' theorem into the uncountable: an ordinal $\alpha$ is admissible iff there is some real $r$ in some generic extension of the universe such that $\alpha$ is the least ordinal with no $r$-computable copy. And in fact the Medvedev version of this picture - which, by Shoenfield again, is similarly well-behaved - is a necessary (so far as I know) tool in proving the result mentioned in the previous bulletpoint.

$\endgroup$
  • $\begingroup$ Yes, I think you have understood rightly what I was asking. In the terminology of the question, I was defining $PS[\alpha]$ to be the smallest ordinal such that $PS[\alpha] \nleq_w \alpha$. Just a couple of more questions though. (1) What exactly is the precise (and general) definition of $\omega^{CK}_\alpha$ then (sorry I just haven't seen it anywhere)? And is there a generally used phrase such as $\alpha$-th "this" for $\omega^{CK}_\alpha$? (2) Secondly, you mentioned that $\beta_\omega<\beta_{\omega+1}=\omega_\omega^{CK}<\beta_{\omega+2}=\omega_{\omega+1}^{CK}<...$ (continued) $\endgroup$ – SSequence Sep 6 '18 at 22:45
  • $\begingroup$ Does that carry over for higher values? I mean is the following true or not(??): $\beta_{\omega \cdot 2+1}=\omega_{\omega \cdot 2}^{CK}<\beta_{\omega \cdot 2+2}=\omega_{\omega \cdot 2+1}^{CK}<...$ And does that carry over to limit values after that? $\endgroup$ – SSequence Sep 6 '18 at 22:45
  • $\begingroup$ Also, regarding the second part of your answer, obviously some of this is too advanced for me. But I have seen Prof. Joel's paper (I mean just seen it, not read/understood it). Anyway, if the notion mention there is same as one here (math.stackexchange.com/questions/108348/…) then I think I do understand the definition at least (since I do understand the construction in linked answer). Anyway, thanks for the answer. It was quite useful. $\endgroup$ – SSequence Sep 6 '18 at 22:59
  • $\begingroup$ @SSequence See my edits. $\endgroup$ – Noah Schweber Sep 6 '18 at 23:22
  • $\begingroup$ One last question (in case you want to answer). In the definition of $\beta_1$ in terms of $\beta_0=\omega_{CK}$, $\beta_1$ was defined as smallest ordinal such that $\beta_1 \nleq_w \beta_0 $. However, if we take an actual well-order of $\omega_{CK}$ in terms of $\mathbb{N}$ (say in most obvious way by adjusting indexes of smallest programs that calculate ordinals less than $\omega_{CK}$), it seems plausible that using that specific well-order an (ordinary) program wouldn't be able to calculate $\beta_1$. I mean I wouldn't bet on it but it seems plausible. If it is true, good ref. for this? $\endgroup$ – SSequence Sep 7 '18 at 1:59

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.