10
$\begingroup$

Martin's remarkable cone theorem in the theory of determinacy says the following:

Suppose $A\subseteq \omega^\omega$ is Turing invariant and determined. If $\forall x\exists y(x\le_T y\& y\in A)$ then $A$ contains a cone.

Let me explain what this means: $A$ is Turing invariant iff $\forall x\in A\forall y(x\equiv_T y\Rightarrow y\in A)$. Here, $\le_T$ is the relation of Turing reducibility and $\equiv_T$ is the corresponding equivalence relation.

"Determined" is in the usual sense of infinite games on integers.

A cone is a set of the form $$C_y=\{x\mid y\le_T x\}.$$ Clearly, cones are Turing invariant. We say that $y$ is the base of the cone $C_y$.

If $\forall x\exists y(x\le_T y\& y\in A)$ we say that $A$ is cofinal.

When Martin proved his theorem, he thought that it would be a quick way of showing determinacy fails (in ZF), by considering explicit sets coming from recursion theory. Instead, he found several results in recursion theory as a consequence.

Here are some examples:

  • For every $x$ we have $x<_T x'$, where $x'$ is the Turing jump of $x$. This means that the set of jumps is cofinal. By Borel determinacy, it follows that there is a $y$ such that if $y\le_T x$, then $x\equiv_T z'$ for some $z$. Well known recursion theoretic results show that in fact we can take $y=0'$.
  • Again by Borel determinacy, there is a real $x$ such that any $y$ with $x\le_T y$ is a minimal cover above some $z$. Again, recursion theoretic arguments show that we can take $x=0^{(\omega)}$.

I do not know many examples coming from recursion theory, but maybe somebody here does.

Are there (natural) examples of sets $A$ defined recursive theoretically that we know need to contain a cone, but for which we do not know of a (natural) base?

"Need to contain a cone" could be taken to mean, say, that they are Turing invariant and cofinal and Borel.

Naively, a negative answer would mean we have very strong abstract basis results. But I would be interested in natural candidates for a positive answer as well.

$\endgroup$
6
  • $\begingroup$ I heard Martin say at a talk once that when he proved his theorem, it was easy to think at first that perhaps it might be used to refute AD, since after all, he knew lots of sets of Turing degrees, and all that was required was to find one such set that neither contained nor omitted a cone. But of course, it didn't turn out that way... $\endgroup$ Nov 10, 2010 at 17:43
  • 1
    $\begingroup$ Slaman and Reimann have some results on random reals (arxiv.org/abs/0707.1390) which use the cone theorem, where it looks like they have some information about the cones, but not an exact base. $\endgroup$ Nov 10, 2010 at 18:31
  • $\begingroup$ @Henry: Thanks! That's a good place to start. $\endgroup$ Nov 10, 2010 at 19:05
  • 1
    $\begingroup$ Reimann and Slaman show that there is a cone consisting of continuously random reals. However they then show that every non-$\Delta^1_1$ real is continuously random. So Kleene's $\mathcal O$ is a fairly natural base for such a cone. $\endgroup$ Nov 18, 2010 at 18:31
  • 1
    $\begingroup$ If we just want a set that contains no largest cone (i.e., no smallest base) then we can take the nonzero degrees, i.e., those $\mathbf a$ with $\mathbf a>\mathbf 0$. $\endgroup$ Nov 18, 2010 at 20:24

2 Answers 2

8
$\begingroup$

I would like to add another example.

Given a sentence $\phi$ from partial order language, then for any Turing degree $x$, either $D(\leq x)\models \phi$ or $D(\leq x)\models \neg\phi$. By the BD, there is a Turing degree $x_{\phi}$ so that either for all $y\geq_T x_{\phi}$, $D(\leq y)\models \phi$ or for all $y\geq_T x$, $D(\leq y)\models \neg \phi$.

Let $z$ be a Turing degree above all the $x_{\phi}$'s, then for every $y\geq_T z$, $D(\leq y)$ is elementary equivalent to $D(\leq z)$.

I don't know a natural base for this.

$\endgroup$
2
  • $\begingroup$ Nice, much better than my example. $\endgroup$ Apr 13, 2011 at 14:48
  • $\begingroup$ I would like to add a remark that it can be shown that the base is not second order arithmetic definable. $\endgroup$
    – 喻 良
    May 26, 2014 at 23:03
4
$\begingroup$

Let $$ A=\{x \mid x\ \equiv_T\ j(y)\quad \text{for some set } y\}, $$ where $j(y)$ is the $\Delta^1_{2n+1}$-jump of $y$, for $n\ge 1$.

Since $x\ <_T\ j(x)$ for all $x$, $A$ is cofinal in the Turing degrees. Hence assuming Projective Determinacy, $A$ must contain a cone in the Turing degrees.

Kechris showed a restriction on possible jump inversion theorems in the $\Delta^1_{2n+1}$-degrees (see Kastanas, The jump inversion theorem for $Q_{2n+1}$ degrees, Proc. AMS 1984). So I am guessing that no base for a cone contained in $A$ is known. But I guess this is closer to set theory than recursion theory.

EDITS: Changed the example since the $\omega$-jump or hyperjump do not work, by MacIntyre, Transfinite extensions of Friedberg's completeness theorem, J. Symbolic Logic, 1977; and added the assumption PD.

$\endgroup$
2
  • $\begingroup$ Hi Bjørn, thanks for this new example! I'll try to find Kastanas paper. $\endgroup$ Nov 18, 2010 at 18:16
  • 1
    $\begingroup$ As a remark, this example is not strictly what I am hoping for, since the $\Delta^1_{2n+1}$-jump is not definable in a Borel way. (There are other examples of the phenomenon I'm looking for if we allow large cardinals, so I'm specifically looking for a Borel set, see for example this answer: mathoverflow.net/questions/45257/when-can-we-detect-forcing/…) Anyway, Kechris's result certainly gives a very natural projective example that definitely involves set theory under PD, I'll have to think about it. $\endgroup$ Nov 19, 2010 at 5:45

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.