[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
More information about the FOM
mailing list