# [FOM] Determinacy and Sequences of Turing Degrees

Dmytro Taranovsky dmytro at mit.edu
Wed Feb 22 17:32:16 EST 2012

```A consequence of definable determinacy is that for every definable
property, either it or its negation holds on a cone of Turing degrees.
In other words, if T is a sufficiently high Turing degree, then its
definable properties are independent of T. Moreover, if T_1 is a
sufficiently high Turing degree and T_2 is sufficiently high above T_1,
then definable properties of (T_1, T_2) are independent of (T_1, T_2),
and similarly for n-tuples of Turing degrees.  Here, "definable" depends
on determinacy assumed; for projective determinacy, "definable" is
"definable in second order arithmetic".

In general, we can consider sufficiently fast-growing infinite sequences
of Turing degrees of any length <=omega_1.  Sufficiently fast-growing
means that for each alpha, the alpha-th Turing degree is sufficiently
high relative to the sequence of the previous Turing degrees.
Surprisingly, under appropriate determinacy assumptions, all
sufficiently fast-growing sequences of Turing degrees of length omega_1
are effectively indistinguishable.

Theorem 1 (determinacy for games on integers of length omega_1 and OD
payoff):  Let phi be a formula with one free variable.  If S and T are
sufficiently fast-growing sequences of Turing degrees of length omega_1,
then phi(S)<-->phi(T).

One consequence of the theorem (under the determinacy assumption) is
that if S is a sufficiently fast-growing sequence of Turing degrees of
length omega_1, then the set of real numbers ordinal definable from S is
countable (and independent of S).

The theorem holds even if Turing degrees are replaced by elementary time
degrees: X is elementary time computable from Y iff there is n such that
X can be computed from Y using time bounded by a stack of n
exponentials.  However, using polynomial time degrees would not work;
relativized P=NP toggles even for arbitrarily high polynomial time degrees.

Analogously to ordinary recursion theory, there is recursion theory for
admissible sets, and in particular a notion of recursive function:
P(omega_1)-->P(omega_1).  This can be used to define degrees of subsets
of omega_1 under recursive reducibility.

Theorem 2 (determinacy for games on integers of length omega_1 and OD
payoff; Continuum Hypothesis):  Let phi be a formula with one free
variable.  There is a degree S under recursive reducibility for subsets
of omega_1 such that for all T>=S, phi(S)<-->phi(T).

I do not know whether the Continuum Hypothesis is required for Theorem
2.  Continuous functions R->R can be effectively coded as real numbers,
but the analogous statement for subsets of omega_1 depends on the
Continuum Hypothesis.

See my paper for details, formal statements of the results, and the proofs.
http://web.mit.edu/dmytro/www/SequencesOfTuringDegrees.htm

Dmytro Taranovsky
```