4
$\begingroup$

How can one demonstrate there is no sequence $X_i$ of sets such that $X_{i+1}' = X_i$ (this is really equality as sets though Turing equivalence would be interesting too).

I know it fails if I relax equality to simply $X_{i+1}' <_T X_i$ as in this question but I'd think there has to be some kind of simple fixed point style argument in this case. Maybe I'm just sleep deprived but I'm blanking on how to show it and even trying the Martin determinacy stuff didn't immediately give me an answer.

Specifically, the reason I care is I need to show that for any $X$ there is a maximum value of $k \in \omega$ such that $(\exists Y)(X = Y^k)$.

$\endgroup$
0

2 Answers 2

7
$\begingroup$

Let $\Theta(X, n)$ be a uniform process such that $\Theta(Z^{(n)}, n) = Z$, i.e. $\Theta$ undoes jumps. Using the recursion theorem, define a functional $\Phi_e$ such that $\Phi_e^X(e)\downarrow$ iff $\exists n\, \Theta(X, n)(e) = 0$.

Now suppose such a sequence $(X_i)_{i \in \omega}$ existed. Consider the sequence $X_0(e), X_1(e), X_2(e),\dots$. So $X_i(e) = 1$ iff there is a $j \ge i$ with $X_j(e) = 0$. If this sequence contains infinitely many 0s, then it is is entirely 1s, a contradiction. If this sequence contains only finitely many 0s, then it contains only finitely many 1s, again a contradiction.

$\endgroup$
1
  • $\begingroup$ That's really neat. Thanks. $\endgroup$ Dec 11, 2020 at 8:52
6
$\begingroup$

This is a consequence of the main result of John Steel's paper Descending Sequences of Degrees. The main result of that paper is that if $P$ is an arithmetic formula, there is no sequence $\langle A_n \rangle_n$ such that for all $n$, $A_n \ge_T A_{n + 1}'$ and $A_{n + 1}$ is the unique $B$ such that $P(A_n, B)$ holds. In your case, you just need to let $P(X, Y)$ be the formula which says that $X$ is the jump of $Y$ (since the jump, at least in its usual formulation, is injective on the level of sets).

If you ask instead about Turing equivalence, then your statement is false. Here's a proof. Let $\langle A_n \rangle_n$ be a sequence such that $A_n \ge_T A_{n + 1}'$. Then you can use the relativized form of the jump inversion theorem to build a sequence $\langle B_n \rangle_n$ such that for each $n$, $B_n \ge_T A_n$ and $B_n \equiv_T B_{n + 1}'$.

$\endgroup$

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.