Skip to main content
added 9 characters in body
Source Link
Andrés E. Caicedo
  • 32.5k
  • 5
  • 133
  • 240

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)$$\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.

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)$ 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.

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.

Source Link
Andrés E. Caicedo
  • 32.5k
  • 5
  • 133
  • 240

Martin's cone theorem and recursion theory

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)$ 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.