Dmytro Taranovsky
February 26, 2012
Small change: December 12, 2016

Determinacy and Fast-growing Sequences of Turing Degrees

Abstract: We discuss sufficiently fast-growing sequences of Turing degrees. The key result is that, assuming sufficient determinacy, if $φ$ is a formula with one free variable, and $S$ and $T$ are sufficiently fast-growing sequences of Turing degrees of length $ω_1$, then $φ(S)⇔φ(T)$. In the second part (below), we define degrees for subsets of $ω_1$ analogous to Turing degrees, and prove that under sufficient determinacy and CH, all sufficiently high degrees are also effectively indistinguishable.

Fast-growing Sequences of Turing Degrees

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)$. Here, "definable" depends on determinacy assumed; for projective determinacy "definable" is "definable in second order arithmetic". (Recall that projective determinacy asserts that every two-player perfect information game of length $ω$ on integers (that is with moves being integers) and projective payoff set is determined, that is one of the players has a winning strategy.) We can ask whether the analogous property holds for infinite sufficiently fast-growing sequences of Turing degrees, and the answer turns out to be yes in a very strong way.

Theorem 1 (ZFC + determinacy for games on integers of length $ω_1$ and ordinal definable payoff):
Let $δ>ω_1$ be an ordinal and $r$ a real number. There is a function $f$ from countable sequences of Turing degrees to Turing degrees such that for all formulas $φ$ with two free variables, for every sequence of Turing degrees $S$ of length $ω_1$ with $∀α<ω_1 \, f(S|α) ≤ S(α)$, the truth of $φ(r,S)$ in $V_δ$ is independent of $S$.

Proof: Determinacy in the theorem also implies determinacy for payoff ordinal definable from a real. Pick a formula $φ$ and consider the game of length $ω_1$ with the payoff set $\{x: φ_δ(r, S(x))\}$ where $φ_δ$ is relativization of $φ$ to $V_δ$ and $S(x)(α)$ is the Turing degree of $[x_{ω⋅α}, x_{ω⋅α+ω})$ ($x$ is a sequence of integers of length $ω_1$). By determinacy, one of the players has a winning strategy. Because the payoff depends only on the Turing degrees (and with the help of a well-ordering of real numbers), there is a winning strategy that depends only on the last finite set of moves and the Turing degrees of the previous ω-sequences of moves. Pick such a strategy, and let $f_φ$ be such that $f_φ(S|α)$ is the Turing degree for the strategy for moves $ω⋅α$ up to $ω⋅α+ω$ where $S|α$ is the sequence of Turing degrees generated by the moves before $ω⋅α$. Since the other player can force the resulting sequence of Turing degrees to be any $S$ with $f_φ(S|α) ≤ S(α)$, the truth of $φ(r,S)$ in $V_δ$ is independent of $S$ for all such $S$. Finally, pick $f$ with $∀S ∈ w^{<ω_1} ∀\hat φ f(S)≥f_φ(S)$, and $f$ satisfies the theorem.

Notes:

Definition: We say that $φ$ holds for every sufficiently fast-growing sequence of Turing degrees (of a particular length $≤ω_1$) if there is $f$ (from countable sequences of Turing degrees to Turing degrees) such that $φ$ holds for all $S$ with $∀α<|S| \, f(S|α) ≤ S(α)$ ($|S|$ is the order type of $S$).

For $|S| > ω$, the notion of sufficiently fast-growing is not closed under subsequences. Every infinite sequence has an uncountable number of subsequences, so for example, for every $S$, there are subsequences of $S|ω$ that are not recursive in $S(ω)$. However, the notion of 'sufficiently fast-growing' is well-behaved in that for every countable set of conditions (each represented by $f_n$), there is a sequence that satisfies all of them.

In general, a notion of sufficiently fast-growing sequences of Turing degrees is a function that maps each countable sequence of Turing degrees into a nonempty upwards-closed set of Turing degrees (which are the permissible degrees for the next element of the sequence).

Proposition 2: Given a notion of sufficiently fast-growing sequences of Turing degrees, there is a stricter notion $f$ such that (1) for successor $|S|$, $f(S)$ depends only on on the last element of $S$ provided that $∀α<|S| \, S(α)∈f(S|α)$, and (2) (strong monotonicity) if $T∈L_{δ}(S)$ for the least $δ$ for which $L_{δ}(S)$ satisfies ZF\P, then $f(S)⊂f(T)$.
Proof: Let $f_1$ be the initial notion strengthened so that each element of $f_1(S)$ can enumerate $S$, which reduces (1) to (2). $f$ defined by $f(S) = ∩f_1(T)$, where $T$ is obtained from $S$ by zero or more (actually, exactly one suffices) applications of (2), satisfies the proposition.

For reference, $\text{HOD}^A_B(C)$ consists of hereditarily ordinal definable sets as computed in $A$ (or if $A$ is omitted, in $V$) allowing $B$, $C$, and elements of $C$ as parameters.

Corollary 3 (to Theorem 1) (ZFC + determinacy for games on integers of length $ω_1$ and ordinal definable payoff):
   (a) If $S$ is a sufficiently fast-growing sequence of Turing degrees of length $ω_1$, then all reals in $\mathrm{HOD}_S$ are ordinal definable, and hence $\mathbb{R}∩\mathrm{HOD}_S$ is countable.
   (b) If $δ$ is a countable ordinal and (relative to $δ$) $S$ is a sufficiently fast-growing sequence of Turing degrees of length $ω_1$, then $\mathrm{HOD}∩V_δ = \mathrm{HOD}_S∩V_δ$.

Proof: (a) Assume contrary, and let α be the least ordinal such that (under the canonical well-ordering of $\mathrm{HOD}_S$), $α$-th real is not in $\mathrm{HOD}$, and let $r(S)$ denote that real. From the theorem, $r(S)$ is independent from $S$, which contradicts $r(S)$ not being ordinal definable.
   (b) Assume contrary, and let $W$ be a canonical well-ordering of $\mathrm{HOD}_S$ (mapping ordinals to sets) such that sets of lower rank come before sets of higher rank and $W$ agrees with a canonical well-ordering of $\mathrm{HOD}$ up to the least set not in $\mathrm{HOD}$. Let $α$ be the least ordinal such that $W(α)$ is in $\mathrm{HOD}_S ∩ V_δ$ but not in $\mathrm{HOD}$. Under the determinacy assumption, $ω_1$ is inaccessible (and even measurable) in $\mathrm{HOD}$. Because $α≤f(δ)$ for some definable function $f$ (specifically, the order of $\mathrm{HOD} ∩ V_δ$ under the canonical well-ordering of $\mathrm{HOD}$) from countable ordinals to countable ordinals, $α$ is independent of $S$ (to prove, apply the theorem to each $α≤f(δ)$ and take upper bound for the rate of growth). $W(α)$ must depend on $S$, so there is the least ordinal $β$ (with $β≤f(δ)$) such that the truth of $W(β) ∈ W(α)$ depends on $S$, which contradicts the theorem.

The theorem is surprising since the freedom to pick $ω_1$ parameters would ordinarily allow coding in an arbitrary subset of $ω_1$. It is also surprising that even though $S$ is a sequence of $ω_1$ disjoint countable sets of reals, the set of reals ordinal definable from $S$ is countable.

It seems reasonable that the least disagreement between $\mathrm{HOD}$ and $\mathrm{HOD}_S$ corresponds to a measurable cardinal in $\mathrm{HOD}_S$ and an associated elementary embedding. For each s∈S, the least definable from S ordinal corresponding to $s$ appears to be the supremum of $s$-recursive well-orderings, and a reasonable conjecture is that it is measurable in $\mathrm{HOD}_S$. Also, based on results in "Large Cardinals from Determinacy" chapter of the Handbook of Set Theory, it seems reasonable that each element of $S$ leads to a Woodin cardinal in $\mathrm{HOD}_S$.

An interesting project would be to work out the theory of definability from a sufficiently fast-growing sequence of Turing degrees $S$. Here are some partial results.

Proposition 4:
   (a) If $S$ is a sufficiently fast-growing sequence of $n<ω$ Turing degrees, then $\mathrm{HOD}_S^{L(S)}$ contains all $Δ^1_{n+2}$ (and $Σ^1_{n+2}$) reals, and assuming projective determinacy (or just absence of a projective sequence of $ω_1$ distinct reals), all reals that are $Δ^1_{n+2}$ in a countable ordinal.
   (b) Let $δ$ be an ordinal. If $S$ is a sufficiently fast-growing sequence of $ω$ Turing degrees, then $\mathrm{HOD}_S^{L(S)}$ contains (the real number coding) the truth predicate of $L_δ(\mathbb{R})$. If $\mathrm{HOD}^{L(\mathbb{R})}∩\mathbb{R}$ is countable (for example if the axiom of determinacy holds in $L(\mathbb{R})$), then $S$ can be chosen independent of $δ$.

Proof: (a) $S$ can be coded by a real number, and provably in ZFC and uniformly in the code for $S$, $S$ can be used to convert $n$ real quantifiers into $n$ arithmetic quantifiers. For example, $∃X \in \mathbb{R} \, ∀Y \in \mathbb{R} \, φ(X,Y) ⇔ ∃X ≤_\mathrm{T} r_0 \, ∀Y ≤_\mathrm{T} r_1 \, φ(X,Y)$ ($φ$ has no other free variables; $r_i$ can be any real number with Turing degree $S_i$). Combined with $Σ^1_2(S)$ correctness of $L(S)$, this allows $\mathrm{HOD}_S^{L(S)}$ to compute $Σ^1_{n+2}$ truth and hence include all $Δ^1_{n+2}$ (and $Σ^1_{n+2}$) reals. Furthermore, the proof relativizes to any particular countable ordinal (and appropriate $S$). Under projective determinacy, only countably many reals are $Δ^1_{n+2}$ in a countable ordinal, so a sufficiently fast-growing $S$ will cover all of them.
   (b) Let $S$ be such that for every $n<ω$, there is an elementary substructure of $L_δ(\mathbb{R})$ containing $S_n$ and with all reals having a lower Turing degree than $S_{n+1}$, and let M be the union of an $ω$ chain of these substructures. Clearly, $\mathbb{R}^M = \mathbb{R}_S$ where $\mathbb{R}_S$ is the closure of $⋃S$ under Turing reducibility, so $M$ condenses to some $L_λ(\mathbb{R}_S)$ and hence its truth predicate is in $\mathrm{HOD}_S^{L(S)}$. Finally, if $\mathrm{HOD}^{L(\mathbb{R})}∩\mathbb{R}$ is countable, then by existence of upper bounds for countable sets of notions of sufficiently fast-growing, we can pick $S$ independent of $δ$.

Note: Proposition 4 and Corollary 3 can also be relativized on top of an arbitrary real $r$ (using $\mathrm{HOD}_{r,S}$ and $S$ dependent on $r$).

Proposition 5 (ZFC + determinacy for games on integers of length $ω_1$ and ordinal definable payoff):
   (a) Let $S$ be a sufficiently fast-growing sequence of Turing degrees of length $ω_1$ and $T$ an initial segment of $S$ of limit length. Then $\mathbb{R}^{\mathrm{HOD}_S(T)} = \mathbb{R}_T$ where $\mathbb{R}_T$ is the closure of $∪T$ under Turing reducibility. Furthermore, there is an elementary embedding of $L(\mathbb{R}_T)$ into $L(\mathbb{R})$.
   (b) $\mathrm{HOD}(\mathbb{R}_T)$ agrees with $\mathrm{HOD}(\mathbb{R})$ about statements in third-order arithmetic with parameters in $\mathbb{R}_T$ (and hence it satisfies AD).

Proof: (a) Every real in $\mathrm{HOD_S}(T)$ is ordinal definable from $r$ and $S$ for some $r$ belonging to some T(α). Above $α$, $S$ is sufficiently fast-growing relative to $r$, so all reals ordinal definable from $r$ and $S$ have Turing degree below $S_{α+1}$. Because $|T|$ is a limit ordinal, it follows that $\mathbb{R}^{\mathrm{HOD}_S(T)} = \mathbb{R}_T$.
For each $T(α)$, there is a canonical elementary substructure of $L(\mathbb{R})$ containing $T(α)$ and with all reals being in $T(α+1)$. The union of these substructures condenses/collapses to $L(\mathbb{R}_T)$, and the inverse of the collapse is the desired elementary embedding. Also, while $L(\mathbb{R})$ is a proper class, $\mathbb{R}^\#$ exists, so the notions of elementary substructures, etc. are well-defined.
   (b) To avoid issues with undefinability of truth, work in $V_δ$ where $δ$ is the least ordinal such that $V_δ≺_{Σ_2}V$. Let $M$ consist of sets in $\mathrm{HOD}(\mathbb{R})$ that are definable from an element of $\mathbb{R}_T$, and $N$ consist of sets in $\mathrm{HOD}(\mathbb{R}_T)$ that are definable from $\mathbb{R}_T$ and an element of $\mathbb{R}_T$. $N$ is an elementary substructure of $\mathrm{HOD}(\mathbb{R}_T)$, and by the closure of $\mathbb{R}_T$, $M$ is an elementary substructure of $\mathrm{HOD}(\mathbb{R})$. Let $M_1$ be the transitive collapse of $M$. $\mathbb{R}^{M_1}=\mathbb{R}_T$ and $\mathrm{P}(\mathbb{R})^{M_1}⊂\mathrm{P}(\mathbb{R})^N$, so to complete the proof it suffices to show that every set of reals in $N$ is in $M_1$. Every set of reals in $N$ has the form $\{x: φ(r,x)\}$ for some formula φ (with two free variables) and some $r$ in $\mathbb{R}_T$. Using Theorem 1, we can show that the truth of $φ(r,x)$ is independent of $T$ (for all sufficiently fast-growing $T$ of the same limit length with $r$ and $x$ in $\mathbb{R}_T$), so the set is the intersection of $\mathbb{R}_T$ with a set of reals definable from $r$, and hence is present in $M_1$.

One consequence of the proposition is that (under the determinacy assumption), for limit $|T|$ that are not sufficiently closed (including $ω$), in $L(T)$ (or $\mathrm{HOD}_S(T)$), the continuum is a countable union of countable sets. For all limit $|T|$, $\mathrm{HOD}_S(T)$ (and hence $L(T)$) satisfies "there are no uncountable sequences of distinct reals". Also, as before, restricted forms of determinacy translate into restricted forms of the proposition.

We end with some conjectures.
Conjectures: For finite length $n$ (with $S$ being a sufficiently fast-growing sequence of Turing degrees of length $n$), the reals in $\mathrm{HOD}_S^{L(S)}$ are the ones $Δ^1_{n+2}$ in a countable ordinal, equivalently, those that are in the minimal iterable inner model with $n$ Woodin cardinals. If $α = |S|$ is countable in $M_α$ (the minimal iterable inner model with $α$ Woodin cardinals), then the reals in $\mathrm{HOD}_S^{L(S)}$ are those in $M_α$, and perhaps, $\mathrm{HOD}_S^{L(S)}$ itself is an iterate of $M_α$ (or an iterate of $M_α$ augmented with certain iteration strategies).
We can also consider definability in $L(\mathbb{R})$. One conjecture is that for $α = |S|$ countable in $M_α$, the reals in $\mathrm{\mathrm{HOD}}_S^{L(\mathbb{R})}$ are precisely those in $M_{α+ω}$. Finally, an interesting question is the nature of $L(S)$ and $\mathrm{HOD}_S^{L(S)}$ for $|S| = ω_1$.

Degrees of Subsets of $ω_1$

For subsets of $ω_1$, we can define several notions of degrees:

For each of these notions of reducibility, there is a corresponding degree notion generated by equivalence classes of subsets of $ω_1$. Boldface recursive reducibility is finer than constructible reducibility and boldface projective reducibility. Under CH, sets of reals can be coded as subsets of $ω_1$, but constructible reducibility (using $L(Y)$ in place of $L[Y]$) and both of projective reducibilities make sense for sets of reals directly.

Clearly, lightface recursive reducibility is the strictest notion, but it is sufficiently robust for our purposes. It turns out that under appropriate assumptions (specifically, CH and sufficient determinacy), all sufficiently high lightface recursive reducibility degrees are effectively indistinguishable.

Theorem 6 (ZFC + determinacy for games on integers of length $ω_1$ and ordinal definable payoff + Continuum Hypothesis):
Let $δ>ω_1$ be an ordinal and $r$ a real number. There is a degree $S$ for lightface recursive reducibility of subsets of $ω_1$ such that for all formulas $φ$ with two free variables and all $T≥S$, $V_δ$ satisfies $φ(r,S)⇔φ(r,T)$. Furthermore, for boldface recursive reducibility, $S$ can be chosen independent of $r$.

Proof: Consider a game on integers of length $ω_1$ and payoff $\{X: φ(r, \mathrm{degree}(X))\}$ as computed in $V_δ$. If one player has a winning strategy, then by CH, it can be coded into a subset of $ω_1$. Let $S$ be the degree of one such code (under any reasonable coding). Because application of the code for a strategy to a partial play is recursive in the required sense, the other player can force the degree of the play to be any degree $T≥S$, so $φ(r,S)⇔φ(r,T)$. Because every countable set of of degrees has an upper bound, we can pick a degree that works for all $φ$. For boldface recursive reducibility, every set of $ω_1$ degrees has an upper bound, so we can a pick a degree that works for all $φ$ and $r$.

Notes:


REFERENCES

"Determinacy Maximum" by Dmytro Taranovsky (2003), arXiv:math/0311095.
The determinacy of long games by Itay Neeman. Walter De Gruyter Inc, 2004.
"Large Cardinals from Determinacy" by Peter Koellner and Hugh Woodin in Handbook of Set Theory. Springer, 2010.