Dmytro Taranovsky
February 26, 2012
Update with new conjectures and other changes: April 25, 2020

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

Symmetry is fundamental to infinity, and we often have that all sufficiently closed (in some sense) structures of a given type satisfy the same properties. Foundationally, this can be used to extend the language of set theory [Taranovsky 2012], or we can use sufficiently closed finite structures as a 'replacement' for countable infinity [Taranovsky 2017]. Remarkably, assuming determinacy, for sequences of Turing degrees, 'sufficiently fast-growing' implies 'sufficiently closed'. In this paper, we discuss sufficiently fast-growing sequences of Turing degrees, prove key results, state a number of interesting conjectures, and then discuss degrees of subsets of $ω_1$.

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.

1. By varying $δ$, we can code-in an arbitrary ordinal as a parameter. Also, $δ>ω_1$ so that $ω_1$ (and hence $S$) is in $V_δ$.
2. The determinacy assumption in the theorem is consistent relative to a Woodin limit of Woodin cardinals and (but that should be unnecessary) a measurable cardinal above them [Neeman 2004]. A leisurely introduction to a similar determinacy hypothesis can be found in "Determinacy Maximum" [Taranovsky 2003].
3. "Ordinal definable payoff" can be replaced with another sufficiently robust notion of definability such as definability in third order arithmetic provided that $φ$ is restricted to that class of definability. Also, if we allow any payoff ordinal definable from a countable sequence of ordinals, then we can allow $r$ in $φ$ to be any countable sequence of ordinals.
4. Weaker forms of determinacy translate into weaker forms of the theorem. For example, the theorem holds with $ω_1$ replaced by a countable ordinal α and determinacy for games of length $ω⋅α$ and OD(R) payoff.
5. Projective determinacy suffices for the theorem restricted to the set of all $φ$ expressible in second order arithmetic and finite sequences of Turing degrees (of the same length). For that set of $φ$, the minimum notion of sufficiently high that suffices for finite sequences is: $r_2$ has a sufficiently high Turing degree above that of $r_1$ iff for every natural number $n$, $Σ^1_n(r_1)$ truth is computable from $r_2$.
6. 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. Using polynomial time degrees would not work since coding the opponent's strategy into the play is exponential (for games on {0,1} of length $ω$); relativized P=NP toggles even for arbitrarily high polynomial time degrees. However, the theorem holds for sufficiently closed polynomial time degrees (for every sufficiently high $A$, $\text{EXP}^A$ is sufficiently closed), and even holds for sufficient closed prefix degrees (https://mathoverflow.net/questions/285991/determinacy-and-polynomial-time-degrees).

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 the transitive closure 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 described in [KW 2010], it seems reasonable that each element of $S$ leads to a Woodin cardinal in $\mathrm{HOD}_S$. More conjectures are below.

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.

Conjectures

We end this section with some conjectures.

(1) 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 $M_n$ (the minimal iterable inner model with $n$ Woodin cardinals).
(2) If $α = \mathrm{ot}(S)$ is countable and $S$ is sufficiently fast-growing relative to $α$, then the reals in $\mathrm{HOD}_S^{L(S)}$ are those in $M_α$, and $\mathrm{HOD}_S^{L(S)}$ is itself an iterate of $M_α$, perhaps equipped for with certain iteration strategies. The conjecture is especially likely if $α$ is countable in $M_α$. $\mathrm{HOD}^{L(S)}$ is an iterate of $M_{α'}$ together with a fragment of the iteration strategy, where $α'$ is the largest additively indecomposable ordinal with $α=...+α'$. Also, under large cardinal axioms, the least countable mouse that coiterates past every $M_α$ appears to be the least mouse with a measurable cardinal $κ$, and $κ$ Woodin cardinals.
(3) In $\mathrm{HOD}^{L(S)}$, $ω_1^{L(S)}$ is the least measurable, and $ω_2^{L(S)}$ is the least and only Woodin cardinal.
(4) In $\mathrm{HOD}_S^{L(S)}$, for $s∈S$, $ω_1^{\text{CK},s}$ is the least measurable corresponding to $s$, and $ω_1^{HOD_S(s)}$ is the least Woodin cardinal above it, and with no more measurables until the next $s$. This also applies to other similar degrees, for example using $ω_1^{L(s)}$ and $\max(ω_1^{\mathrm{HOD}_S(s)},ω_2^{L(s)})$ (for the measurable and Woodin resp.) if $s$ is constructibility degree. We can even mix and match different kinds of degrees in $S$ as long as it is done sufficiently uniformly to prevent coding.
(5) In place of Turing degrees, we can use a sufficiently fast growing sequence $S'$ of sufficiently closed countable sets of reals (so each set corresponds to the union of a sufficiently fast-growing sequence of $ω$ Turing degrees). $S$ of length $ωα$ corresponds to $S'$ of length $α$. Likely, $\mathrm{HOD}^{L(S')}=\mathrm{HOD}^{L(S)}$, and $\mathrm{HOD}_{S'}^{L(S')}$ has a Woodin cardinal corresponding to each element $s$ of $S'$, with $ω_1^{L(s)}$ being measurable and $ω_1^{\mathrm{HOD}_{S'}^{L(S')}(s)}$ being Woodin.
(6) Games of length $ω_1$ often correspond to indiscernible Woodin cardinals, but here (i.e. for $L(S)$) we have sufficient uniformity, so more likely, the correspondence is with the minimum iterable inner model $M$ with a proper class of Woodin cardinals. Given an indiscernible $δ$ that is a limit of Woodin cardinals in $M$, let $G$ be a generic filter for $\mathrm{Col}(ω,<\!δ)$. For the $α$th Turing degree, we can use $G|(λ_α^{+}+1)$ and the induced enumeration of the reals in $M[G|λ_α^{+}]$ where $λ_α$ is the $α$th Woodin cardinal in the model. The forcing is sufficiently uniform that the theory of the resulting sequence of Turing degrees is independent of $G$. Moreover, if $β<λ_α$, then for every choice of $G|β$, we can make the $α$th Turing degree arbitrarily high using an iteration above $β$ and some choice of $G$. It is unclear (at least to me) whether 'arbitrarily high' generalizes to arbitrarily fast-growing sequence as a whole.
(7) If the construction in (6) works, then using an iterable inner model with a proper class of measurable limits of Woodin cardinals (and its sharp), we can even add a club $C⊂ω_1$ corresponding to those limits (and their limits) in the iterate of the model. The result should give a fast-growing sequence of Turing degrees $S$ together with a club $C$ that is sufficiently thin in that every $α∈C$ has sufficiently strong reflection properties relative to $S|α$ (with $S_α$ in turn sufficiently high relative to $S|α$ and $C|α$). To go further (using a stronger model), we can use nested clubs, or go even further in the style of reflective sequences in [Taranovsky 2012].

Also, the constructions likely relativize to a universally Baire set $A$ (and its extension as a mouse operator $A'$) using models closed under $A'$ and uniformity with respect to questions in $(L^{A'}(S),∈,A',S)$. Also, for countable $S$ with length $α$ ($S_0$ sufficiently high above $α$), the reals in $\mathrm{\mathrm{HOD}}_S^{L(\mathbb{R})}$ are perhaps precisely those in $M_{α+ω}$

Degrees of Subsets of $ω_1$

• Constructible reducibility: $X≤Y$ iff $X∈L[Y]$.
• Lightface projective reducibility: $X≤Y$ iff $X$ is definable in second order arithmetic augmented with a predicate for $Y$. Boldface projective reducibility is the same, except that it allows a real number as a parameter.
• Lightface recursive reducibility: $X≤Y$ iff $X$ is $Δ_1$ in $Y$ in the following sense: There are formulas $φ$ and $ψ$ with one free variable such that $∀α<ω_1 (α∈X ⇔ ∃β<ω_1 ((L_β[Y],∈,Y)⊨φ(α)) ⇔ $$¬∃β<ω_1 ((L_β[Y],∈,Y)⊨ψ(α)))$. Boldface recursive reducibility is the same, except that it allows a countable ordinal as a parameter.

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

• Weaker forms of determinacy for games of length $ω_1$ translate into weaker forms of the theorem (corresponding to restricted classes of φ).
• The Continuum Hypothesis is needed to be able to code the opponent's strategy into the play. We do not know what happens if CH fails.
• The theorem also applies to coarser degrees like constructible or projective reducibility.
• We do not know whether the conclusion of the theorem holds for sufficiently fast-growing pairs or sequences of degrees of subsets of $ω_1$. We also do not know what happens (alternatively, what can consistently happen) for degrees of subsets of larger ordinals.
• Likely, the reals in $\mathrm{HOD}_S^{L(S)}$ and $\mathrm{HOD}^{L(S)}$ are precisely those that are $Δ^2_1$ in a countable ordinal.

A stricter reduction

A variation on the theorem also holds for a very strict reduction, which subsumes the use of fast-growing sequences of Turing degrees.

For subsets of $ω_1$, define the prefix reduction (with the corresponding notion of prefix degrees) as $X≤Y ⇔ ∃a∈ℕ \, ∀s \, (X_s ⇔ Y_{a⌢s})$ (subscript indicates membership). Here, $⌢$ is string concatenation (using little-endian encoding of numbers): For an ordinal $s$, $a⌢s = 2^{\mathrm{len}(a)}s+a$ where $\mathrm{len}(a) =\min(i∈ℕ: 2^i>a)$. There are many variations on this (including simply using $(a+1)s$), but for our purposes they are essentially the same.

For a boolean function $f$, define a prefix degree to be $f$-closed iff any (equivalently, every) representative $X$ is $f$-closed in the following sense: $∃a ∀s \, f(X_t:t<s) = X_{a⌢s}$ ($s$ and $t$ are ordinals). This choice of $f$-closed is somewhat arbitrary if $f$ is not sufficiently universal, but if it is, this is the strongest natural nonrestrictive notion of $f$-closed. Computational complexity commonly uses weaker versions (that are insufficient here).

Assuming determinacy and given a countable set of properties, there is $f$ such that every $f$-closed prefix degree for subsets of $ω_1$ has the same properties. Moreover, assuming CH, every large enough (dependent on $f$) degree for lightface recursive reducibility has an $f$-closed representative.

For a sufficiently strong $f$, an $f$-closed prefix degree for subsets of $ω_1$ gives a sufficiently fast-growing sequence of Turing degrees of length of $ω_1$ (and conversely, but the converse is non-unique). Moreover, given an $X$ of such a degree, each representative $Y$ can be obtained by using a single $a$ (dependent on $Y$), as opposed to a separate choice for each of the Turing degrees, which accounts for the likely increased large cardinal strength.

REFERENCES