Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

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.

share|improve this question
    
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... –  Joel David Hamkins Nov 10 '10 at 17:43
1  
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. –  Henry Towsner Nov 10 '10 at 18:31
    
@Henry: Thanks! That's a good place to start. –  Andres Caicedo Nov 10 '10 at 19:05
1  
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. –  Bjørn Kjos-Hanssen Nov 18 '10 at 18:31
    
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$. –  Bjørn Kjos-Hanssen Nov 18 '10 at 20:24
show 1 more comment

2 Answers

up vote 7 down vote accepted

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.

share|improve this answer
    
Nice one. Thanks. –  Andres Caicedo Apr 13 '11 at 14:44
    
Nice, much better than my example. –  Bjørn Kjos-Hanssen Apr 13 '11 at 14:48
add comment

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.

share|improve this answer
    
Hi Bjørn, thanks for this new example! I'll try to find Kastanas paper. –  Andres Caicedo Nov 18 '10 at 18:16
    
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. –  Andres Caicedo Nov 19 '10 at 5:45
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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