[FOM] Determinacy and Sequences of Turing Degrees

[Dmytro Taranovsky]

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