At the moment I am studying several questions about the arithmetical degree of some index-sets in relation to the standard-ordering on $\mathbb{Q}$. The situation is as follows: I fix some enumeration $r_0, r_1, \ldots$ of $\mathbb{Q}$ such that $<$ is decidable. Then I take $R_e=\{r_n \mid n \in W_e\}$, where $W_e=dom(\varphi_e)$ (the domain of the $e^{th}$ partial recursive function, refering to Kleene's Normal Form Theorem). Now $R_e$ inherits the ordering from $\mathbb{Q}$.

$\textbf{Question 1}$
Define $$ A = \{ e \mid (R_e,<) \cong (\mathbb{Z},<)+(\mathbb{Z},<) \}. $$ I try to prove that every $\Sigma_3$-set $m$-reduces to $A$ but I don't have a good idea. Does somebody see something useful I can do?

$\textbf{Question 2}$ I want to show that there exists $d$ such that the sets $\{e \mid (R_e,<) \cong (R_d,<)\}$ and $\{e \mid (R_e,<) \equiv (R_d,<)\}$ are not arithmetical at all. Does somebody has a good idea for this?

  • 1
    $\begingroup$ What is the definition of $W_e$? $\endgroup$
    – plop
    Apr 17, 2021 at 17:02
  • 2
    $\begingroup$ @plop That's the standard notation for the $e$th c.e. set in some fixed "reasonable" enumeration. Basically, $(R_e)_{e\in\mathbb{N}}$ enumerates the "c.e. linear orders" (including the empty order); placing everything inside $\mathbb{Q}$ is just a convenience (think about how every countable linear order can be "greedily" embedded into $\mathbb{Q}$). $\endgroup$ Apr 17, 2021 at 20:33
  • 2
    $\begingroup$ To the OP, question 2 is not true for every $d$ (e.g. think about what happens if $W_d$ has exactly $17$ elements). Do you want to show that some $d$ has that property? $\endgroup$ Apr 17, 2021 at 20:36
  • $\begingroup$ Indeed, sorry you are right . The question was phrased wrong. It should be stated like: for arbitrary $d$ those two sets are not arithmetical. And I should have mentioned that $W_e=dom(\varphi_e)$ (the domain of the $e^{th}$ partial recursive function. $\endgroup$
    – Kasper
    Apr 17, 2021 at 22:16
  • 2
    $\begingroup$ @Dmitry "$e$th" refers to the $e$th element of an "appropriate" enumeration of partial computable functions (which is tacitly fixed ahead of time), and "$\varphi_e$" is the standard notation for that. $\endgroup$ Apr 17, 2021 at 22:30

1 Answer 1


Talking about suborders of $\mathbb{Q}$ explicitly makes things a bit harder to think about than is necessary, in my opinion. Really we should be talking about general computable (or rather, c.e.) linear orders - the point is that $\mathbb{Q}$ is "big enough" that we can WLOG construe these as suborders of $\mathbb{Q}$ for concreteness. This does make some definitions snappier, but I think obscures the intuition; instead, I think it's best to think of linear orders being built by progressively "laying down points" (or refraining from doing so of course).

For example, suppose I have a Turing machine $\Psi$ and I want to tell whether $\Psi(0)$ halts. Consider the following process for building a linear order: I start building a descending sequence until I see $\Psi(0)$ halt, at which point I build an ascending sequence starting from the very first point I laid down. For example, if $\Psi(0)$ halts at step $5$, the linear order I build is $$\color{red}{a_4<a_3<a_2<a_1<a_0}\color{green}{<a_5<a_6<a_7<a_8<...,}$$ the red part corresponding to the points added before I saw the computation halt and the green part corresponding to the points added after I saw the computation halt. It should be clear that if $\Psi(0)$ halts then I wind up building something isomorphic to $\mathbb{N}$, whereas if $\Psi(0)$ doesn't halt I build something isomorphic to $\mathbb{N}^*$ (= the "reverse order" of $\mathbb{N}$); thinking along these lines, you should be able to prove that $0'\le_T \{ e: (R_e,<)\cong (\mathbb{N},<)\}$.

Now thinking towards Question $2$, we want to generalize the above idea to higher jumps: e.g. find some "analogue of $\mathbb{N}$" which gets $0''$, and another which reduces $0'''$, and so on ... until we get an idea for one which gets every (finite) iterate of the jump all at once. At this point ordinals become useful for organizing ideas; I recommend thinking about $\omega^2$ in particular, and how we can think about this ordinal as $\omega$-many copies of $\mathbb{N}$ (keeping in mind how a single copy of $\mathbb{N}$ can encode a specific question about the halting problem).

OK, what about Question $1$?

Well, let's think about how hard it is to tell whether a computable linear order $L$ looks like $\mathbb{Z}+\mathbb{Z}$. This amounts to the following:

  • $L$ is nonempty. This is $\Sigma_1$: "At some stage we lay down a point."

  • Every point in $L$ has both an immediate successor and an immediate predecessor. This is $\Pi_3$: "For every point $a$ in $L$ there are $b,c\in L$ such that $b<a<c$ and at no stage do we add a point other than $a$ to $(b,c)$."

Note that these two conditions alone ensure that $L$ is a sum of copies of $\mathbb{Z}$. We now need to do the hard bit: ensure that we have exactly two copies of $\mathbb{Z}$ in $L$. This leads to our third and fourth conditions:

  • There are two points which are infinitely far from each other. This is $\Sigma_3$: "There are $a<b$ such that at every stage there is some later stage at which we add a new point to $(a,b)$."

  • There are no three points which are each infinitely far from each other. This is $\Pi_3$: "For every $a<b<c$ we either stop adding points to $(a,b)$ at some stage or we stop adding points to $(b,c)$ at some stage."

Once appropriately formalized, this shows that $A$ is $\Pi_3\wedge\Sigma_3$; it's now natural to hope that every $\Pi_3\wedge\Sigma_3$ set $m$-reduces to $A$, and Question $1$ is a step towards this. If we want to reduce an arbitrary $\Sigma_3$ set to $A$ we probably want to focus on the "$\Sigma_3$-part" of the characterization of $A$; in the above, this was the "There are two points infinitely far apart from each other" bit.

Here's a construction which starts us off in the right direction:

Suppose I have a $\Sigma_3$ sentence $\varphi\equiv\exists x\forall y\exists z(\theta(x,y,z))$ with $\theta\in\Delta_0$; I want to "computably build" a linear order which has a pair of points infinitely far from each other iff $\varphi$ is true. To do this, I work in "blocks:"

  • For each $i\in\mathbb{N}$ I have a block $B_i$. Every point in $B_i$ will be above every point in each $B_j$ with $j<i$ and below every point in $B_k$ with $k>i$, and each $B_i$ starts off with a single point.

  • I add points to $B_i$ in such a way that $B_i$ is isomorphic to $\mathbb{N}$ iff $\forall y\exists z(\theta(i,y,z))$ and is finite otherwise. For example, add an element to the "end" of $B_i$ each time I see $\{y: \forall y'<y\exists z(\theta(i,y',z))\}$ gain an element.

If $\varphi$ is true then at least one $B_i$ is infinite, and this forces a pair of points to be infinitely far apart (consider a point in $B_i$ and a point in $B_{i+1}$). Conversely, if $\varphi$ is false then each $B_i$ is finite and we wind up building a copy of $\mathbb{N}$.

Now (even ignoring the formalization) there are two issues with this, as far as Question $1$ goes. First, there's the problem that the "blocks" look like $\mathbb{N}$ instead of $\mathbb{Z}$; this is easily fixed, though. More serious is the issue that if $\varphi$ is true we might wind up with too many infinite blocks; fixing this will require some thought (and ultimately some injury).

  • $\begingroup$ @ Noah Thanks very much for this elaborate answer. These 'mechanical' thoughts about turing machines are very clarifying, although I think I need some time to digest this and trying to work it out for myself. For now I have some small questions related to the use of this $n^{th}$ Turing Jump $0^{(n)}$ (I am relatively new in computability theory, so I hope I won't bother you too much with trivialities). My question is whether I have to think about $0^{(n)}$ just as an arbitrary $\Sigma_n$-complete set, or is there something particular about it that could help me visualizing? $\endgroup$
    – Kasper
    Apr 18, 2021 at 22:46
  • $\begingroup$ Concerning your answer to my first question: is it correct that studying some proofs related to priority-method could help me solving the issue? $\endgroup$
    – Kasper
    Apr 18, 2021 at 22:50
  • 1
    $\begingroup$ @Kasper Re: your first question, yes, for this purpose (and the vast majority of others) you can think of $0^{(n)}$ as just some $\Sigma_n$-complete set. Re: your second question, sort of - they aren't all relevant here, but some are. Specifically, when proving $\Sigma_n$ completeness (or similar) for "large" $n$ (say, $n>2$) we often want to organize things with injury and priority; I think some related arguments appear in Soare's book around when he introduces moveable marker constructions, although I don't have my copy handy. $\endgroup$ Apr 18, 2021 at 22:53

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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