Σ_{1}^{1} in every real in a Σ_{1}^{1} class of reals is Σ_{1}^{1}

Leo Harrington Department of Mathematics

University of California, Berkeley Berkeley CA 94270

Richard A. Shore^{∗} Department of Mathematics Cornell University Ithaca NY 14853

Theodore A. Slaman^{†} Department of Mathematics University of California, Berkeley Berkeley CA 94270

July 11, 2016

Abstract

We first prove a theorem about reals (subsets of ℕ) and classes of reals: If a real X is Σ_{1}^{1} in every member G of a nonempty Σ_{1}^{1} class K of reals then X is itself Σ_{1}^{1}. We also explore the relationship between this theorem, various basis results in hyperarithmetic theory and omitting types theorems in ω-logic. We then prove the analog of our first theorem for classes of reals: If a class A of reals is Σ_{1}^{1} in every member of a nonempty Σ_{1}^{1} class B of reals then A is itself Σ_{1}^{1}.

1 Introduction

We work in Cantor space 2^{ℕ} and call its members X ⊆ ℕ, reals. We think of members of Baire space ℕ^{ℕ} as functions F : ℕ → ℕ (coded as real consisting of pairs of numbers). We use the standard normal form theorems for reals and classes of reals as follows: A real X is Σ_{1}^{1} (in a real G) if it is of the form {n|∃F ∀xR(F ↾ x, x, n)} for a recursive (in G) predicate R. A class K of reals is Σ_{1}^{1} (in G) if it is of the form {X|∃F ∀xR(X ↾ x, F ↾ x, x)} for a recursive (in G) predicate R. A real or class of reals is Δ_{1}^{1} (or hyperarithmetic) (in G) if it and its complement are Σ_{1}^{1} (in G). Our first main theorem is the following:

∗Partially supported by NSF GrantDMS-1161175. The last two authors began their work on this paper at a workshop of the Institute for Mathematical Sciences of the National University of Singapore which also partially supported them.

†Partially supported by NSF Grant DMS-1301659 and by the Institute for Mathematical Sciences of the National University of Singapore.

Theorem 2.1. If a real X is Σ_{1}^{1} in every member G of a nonempty Σ_{1}^{1} class K of reals then X is itself Σ_{1}^{1}.

While the statement of this theorem and certainly the proof we provide in the next section seem to have little to do with either results of hyperarithmetic theory or model theory they are all, in fact, connected along a couple of paths. Indeed, we were thinking about related matters when we proved the theorem.

A basis theorem in recursion theory typically says that every nonempty class of some sort contains a member with some property. For example, the classes may be arbitrary Σ_{1}^{1} classes K of reals. One, the Gandy Basis Theorem (see Sacks [1990, III.1.5]), says that every nonempty Σ_{1}^{1} class of reals contains one Z such that ω_{1}^{Z} = ω_{1}^{CK}. (For any Z, ω_{1}^{Z} is the least ordinal not recursive, or equivalently not Δ_{1}^{1} in Z; ω_{1}^{CK} is ω_{1}^{Z} for Z recursive (or Δ_{1}^{1}).) Another, the Kreisel Basis Theorem (see Sacks [1990, III. 7.2]) , says that if a real X is not hyperarithmetic (i.e. Δ_{1}^{1}) then K also contains a real Z in which X is not Δ_{1}^{1}. An equivalent version is that if X is Δ_{1}^{1} in every member of K then X is Δ_{1}^{1}.

Our first theorem is the generalization of the Kreisel basis theorem where Δ_{1}^{1} is replaced by Σ_{1}^{1}. (To see that it implies the result of Kreisel note that it says that if X and X̄ are both Σ_{1}^{1} (i.e. Δ_{1}^{1}) in every member of K then they are both Σ_{1}^{1} (and so Δ_{1}^{1})). Our theorem also implies the basis result of Gandy: As Kleene’s O is not Σ_{1}^{1} there is a Z ∈ K in which O is not Σ_{1}^{1}. By classical results of Spector (see Sacks [1990, II. 7.7]), this implies that ω_{1}^{Z} = ω_{1}^{CK}. (See Theorem 2.9.)

Sacks also provides results of hyperarithmetic theory as corollaries to Kreisel’s theorem and others that, as he points out, can be viewed as omitting types theorems in ω-logic. They are also immediate consequences of our theorem as we indicate in the next section. We discus these and other related results in next section after we prove our theorem.

After his proof, Sacks [1990, p. 75] says of this connection that "The recursion theorist winding his way through a Σ_{1}^{1} set is a brother to the model theorist threading his way through a Henkin tree." Our proof, which requires no knowledge of either hyperarithmetic theory or model theory, shows that there is another sibling traipsing (or perhaps treading carefully) through a forcing construction.

Our theorem should have been a classical one of hyperarithmetic theory. It also has analogs, both recent and classical, in other settings. When we told Stephen Simpson the result he remarked that Andrews and Miller [2015, Proposition 3.6] had recently proven the analogous result for Π_{1}^{0} classes in place of Σ_{1}^{1} classes. We rephrase it in our terminology as follows:

Theorem 1.1 (Andrews and Miller). Let P be a nonempty Π_{1}^{0} class. If X is Π_{1}^{0} in every member of P then X is Π_{1}^{0}. (Or, equivalently, if X is Σ_{1}^{0} in every member of P then X is Σ_{1}^{0}.)

Their proof is a forcing proof similar to ours but using Π_{1}^{0} classes instead of Σ_{1}^{1} ones. At the level of Σ_{2}^{1} classes, a standard basis theorem gives the analogous result (as

pointed out to us by John Steel). The classical result (see Moschovakis [1980, 4E.5]) is that the Δ_{2}^{1} reals are a basis for the Σ_{2}^{1} classes of reals. Thus if K is Σ_{2}^{1} it contains a Δ_{2}^{1} real G and, of course, any real X which is Σ_{2}^{1} in G via Θ is itself Σ_{2}^{1}. (X = {n|∃G(Ψ(G) & Θ(G, n))} where Ψ is the Σ_{2}^{1} formula saying G satisfies its Δ_{2}^{1} definition.) Similar basis results hold at higher levels of the projective hierarchy assuming various set theoretic axioms. (See Moschovakis [1980, 5A.4 and 6C.6].)

About the only facts about Σ_{1}^{1} reals and classes that we use in our proof are the the standard normal form theorems mentioned at the beginning of this Introduction.

Our second main theorem is one analogous to Theorem 2.1 but at the level of classes of real.

Theorem 3.1. If a class A of reals is Σ_{1}^{1} in every member of a nonempty Σ_{1}^{1} class B of reals then it is Σ_{1}^{1}.

Our proof of this theorem requires some familiarity with effective descriptive set theory. We give some of the basic facts needed and the proof in §3.

2 The Proof for Reals

We now give the promised forcing style proof of our main theorem.

Theorem 2.1. If a real X is Σ_{1}^{1} in every member G of a nonempty Σ_{1}^{1} class K of reals then X is itself Σ_{1}^{1}.

Proof. We use the language of Gandy-Harrington forcing. Forcing conditions are nonempty Σ_{1}^{1} classes L of reals with set containment as extension. We view the Σ_{1}^{1} formulas φ(G, n) as of the form ∃F ∀xR(G ↾ x, F ↾ x, x, n) with R recursive. We say that L ⊩ φ(G, n) if (∀Z ∈ L)(φ(Z, n)). If, as usual, we say L ⊩ ¬φ(G, n) if (∀L̂⊆L)(L̂ ⊮ φ(G, n)), this definition is then equivalent to (∀Z ∈ L)(¬φ(Z, n)). The point here is that if there is a Z ∈ L such that φ(Z, n) then L̂ = L ∩ {Z|φ(Z, n)} is a nonempty extension of L which obviously forces φ(G, n).

We now list all the Σ_{1}^{1} formulas Θ_{k}(G, n). These are the formulas that could potentially define the reals Σ_{1}^{1} in any G. We consider an X which is a candidate for being Σ_{1}^{1} in every G ∈ K. We build a sequence L_{k} of conditions beginning with L_{0} = K ={G|∃F_{0}∀xR_{m_{0}}(G ↾ x, F_{0} ↾ x, x)} as well as initial segments γ_{k} (of length at least k) of our intended G and δ_{i,k} of witnesses F_{i} (of length at least k) showing that G ∈ L_{k}. More precisely, each L_{k} will be of the form G ⊃ γ_{k} & ∀i ≤ k∃F_{i} ⊃ δ_{i,k}∀xR_{m_{i}}(G ↾ x, F_{i} ↾ x, x) for some recursive R_{m_{i}} (independent of k). Thus, if we successfully continue our construction keeping L_{k} nonempty for each k then the F_{i} = lim_{k} δ_{i,k} for i ≤ k will witness that G = lim_{k} γ_{k} is in every L_{k} as we guarantee that R_{m_{i}}(γ_{k} ↾ x, δ_{i,k} ↾ x, x) holds for every i, x < k and every k.

We begin with γ_{0} = ∅ = δ_{0,0} and R_{m_{0}} as specified by K. So our G will at least be in K as desired. Suppose we have defined γ_{j} and δ_{i,j} for j, i ≤ k and wish to define L_{k+1}, γ_{k+1} and δ_{i,k+1} for i ≤ k + 1 so as to prevent X from being Σ_{1}^{1} in G via Θ_{k}. We ask if there is an m ∈ ω and a nonempty L ⊆ L_{k} such that

1. m ∉ X and L ⊩ Θ_{k}(G, m) or

2. m ∈ X and L ⊩ ¬Θ_{k}(G, m).

Suppose there is such an L of the form ∃F_{k+1}∀xR_{m_{k+1}}(G ↾ x, F_{k+1} ↾ x, x). As L ⊆ L_{k} is nonempty we can choose γ_{k+1} ⊃ γ_{k} and δ_{i.k+1} ⊃ δ_{i,k} for i ≤ k and some δ_{k+1,k+1} all of length at least k + 1 such that L_{k+1} as given by G ⊃ γ_{k+1} & (∀i ≤ k + 1)(∃F_{i} ⊃ δ_{i,k+1})(∀xR_{m_{i}})(G ↾ x, F_{i} ↾ x, x) is a nonempty subclass of L (and so, in particular, R_{m_{i}}(γ_{k+1} ↾ x, δ_{i,k+1} ↾ x, x) for every i, x ≤ k + 1). We can now continue our induction.

Note that if we can successfully define nonempty L_{k} in this way for every k then we build a G = lim_{k} γ_{k} and F_{i} = lim_{k} δ_{i,k} for each i such that ∀xR_{m_{i}}(G ↾ x, F_{i} ↾ x, x). In particular ∀xR_{m_{0}}(G ↾ x, F_{0} ↾ x, x) and so G ∈ K. Similarly, G ∈ L_{k} for every k > 0. If X is Σ_{1}^{1}(G) as assumed, then X = {n|Θ_{k}(G, n)} for some k. We consider the construction at stage k+1 and the L chosen at that stage. If we were in case (1) then as L ⊩ Θ_{k}(G, m) and G ∈ L_{k+1}, Θ(G, m) is true but m ∉ X for a contradiction. Similarly, if we were in case (2), as L ⊩ ¬Θ_{k}(G, m) and G ∈ L_{k+1}, ¬Θ(G, m) is true but m ∈ X again for a contraction.

Thus we can assume that there is some first stage k + 1 at which there are no m and L ⊆ L_{k} as required in the construction. In this case we claim that X is Σ_{1}^{1} as desired. Indeed, we claim that X is defined as a Σ_{1}^{1} real by m ∈ X ⇔ (∃Z ∈ L_{k})Θ_{k}(Z, m). To see this suppose first that (∃Z ∈ L_{k})Θ_{k}(Z, m). Then L as defined by L_{k} & Θ_{k}(G, m) is a nonempty Σ_{1}^{1} class such that L ⊩ Θ_{k}(G, m) and so we would have m ∈ X as desired by the assumed failure of (1) at stage k + 1 of the construction. On the other hand, if (∀Z ∈ L_{k})(¬Θ_{k}(Z, m) then L_{k} ⊩ ¬Θ_{k}(G, m) and so by the failure of (2) at stage k + 1 of the construction, m ∉ X as desired.

As usual, we may relativize the Theorem to any real C.

Our theorem easily implies several basic results of hyperarithmetic theory without any appeal to the theory of hyperarithmetic sets as used, for example, in Sacks [1990]. Many of them can also be seen as consequences of type omitting theorems for certain classes of generalized logics. These type omitting arguments are also immediate consequences of our Theorem. We presented two basis theorems of this sort in the introduction and note here that the proof of Kreisel’s in Sacks [1990] uses several deep facts about hyperarithmetic reals and Σ_{1}^{1} classes.

Following his proof of the Kreisel basis theorem Sacks [1990] gives as a corollary a result of Kreisel about the intersections of all ω-models of various theories of second order arithmetic from which follow some previous specific results. We state that result now along with some similar ones earlier in Sacks’s presentation. These can all be seen as type omitting arguments. After stating them, we explain a general setting which includes them all and give the relevant type omitting theorems as Corollaries of Theorem 2.1.

Theorem 2.2 (Sacks [1990, III. 4.10]). The intersection of all ω-models of Δ_{1}^{1} comprehension is HYP, the class of all hyperarithmetic sets or equivalently the class of all Δ_{1}^{1} sets.

More generally, we have the following result of Kreisel.

Theorem 2.3 (Sacks [1990, III.7.3]). Let K be a Π_{1}^{1} set of axioms in the language of analysis (i.e. second order arithmetic). If a real X belongs to every countable ω-model of K then X is Δ_{1}^{1}.

A similar result is the following.

Theorem 2.4 (Sacks [1990, III.4.13]). The intersection of all ω-models of Σ_{1}^{1} choice downward closed under many-one reducibility is also HYP.

In all of these results it is easy to see that the class of models described is Σ_{1}^{1} and, of course, every member X of such a model is recursive in it and so any real in every such model is Σ_{1}^{1} but these models are all trivially closed under complementation. So they all follow from our Theorem.

Moving to the type omitting point of view we, somewhat more generally, consider two sorted logics (N , M, …) in the usual sense of having two types of variables one ranging over the elements of N and the other over those of M in addition to the usual apparatus of function, relation and constant symbols of ordinary first order logic. While formally merely a version of first order logic gotten by adding on predicates for N and M, this logic can be turned into a much stronger one (N -logic) by requiring that all models have their first sort (with some functions and relations on it as given in the structure) isomorphic to some given countable first order structure. The most common example of these logics is ω-logic where we require that N be isomorphic to the ordinal ω or the standard model ℕ of arithmetic (depending on the language intended). Again, the most common examples are given by classes of ω-models of fragments T of second order arithmetic as mentioned above. Here, in addition to requiring that N be the standard model of arithmetic we intend that the elements of M are subsets of N and the membership relation ∈ between members of N and those of M is in the language (with the usual axiom of extensionality so that the elements of M may be identified with true subsets of N = ℕ). As being an N model, or even also satisfying some Π_{1}^{1} theory T, is clearly Σ_{1}^{1} in N, we immediately get all the results from Sacks [1990] mentioned above as a corollaries of our theorem. Indeed, we have the following generalization of Kreisel’s result in Sacks [1990, III.7.3]:

Theorem 2.5. If T is a Π_{1}^{1} set of sentences in the two sorted language of (N , M, …) and N is a countable structure for the appropriate sublanguage (restricted to the first sort), T has an N -model and p is a n-type (i.e. a complete consistent set of formulas φ(x) with n free variables in the language of (N , M, …)) which is not Σ_{1}^{1} in N, then there is an N -model of T not realizing p. (Note that, as types are complete sets of formulas, p being Σ_{1}^{1} (in N) is equivalent to its being Δ_{1}^{1} (in N).

Proof. Being an N model of T is a Σ_{1}^{1} in N property and so by our Theorem (relativized to N) there is even an N -model (N , M, …) of T in which p is not even Σ_{1}^{1}. (Of course, any type realized in (N , M, …) is recursive in the complete diagram of (N , M, …) and so hyperarithmetic in (N , M, …).)

Viewing our theorem as a type omitting argument suggests that we should be able to omit any countable sequence of types (reals) of the appropriate sort rather than just one. A simple modification of our proof gives the expected result.

Theorem 2.6. If K is a nonempty Σ_{1}^{1} class reals and X_{n} a countable sequence of reals none of which is Σ_{1}^{1}, then there is a G ∈ K such that no X_{n} is Σ_{1}^{1} in G. Similarly if no X_{n} is Δ_{1}^{1}, then there is a G ∈ K such that no X_{n} is Δ_{1}^{1} in G.

Proof. Repeat the proof of the Theorem but at step k + 1 = ⟨n, j⟩ of the construction replace X by X_{n} and Θ_{k} by Θ_{j}. If we successfully pass through all steps k then the previous argument shows that no X_{n} is Σ_{1}^{1} in G ∈ K. On the other hand, if the construction terminates at step k + 1 = ⟨n, j⟩ then the previous argument shows that X_{n} is defined as a Σ_{1}^{1} real by m ∈ X_{n} ⇔ (∃Z ∈ L_{k})Θ_{j}(Z, m) for a contradiction. For the Δ_{1}^{1} version, simply consider the sequence Y_{n} where Y_{n} = X_{n} if X_{n} is not Σ_{1}^{1} and Y_{n} is the complement if X_{n} otherwise (i.e. X_{n} is not Π_{1}^{1}). As now no Y_{n} is Σ_{1}^{1}(G), no X_{n} is Δ_{1}^{1}(G).

This version of our Theorem also extends the analog of the result actually given by Andrews and Miller [2015, Proposition 3.6].

Of course, we can relativize this theorem as well to any real C. To give a somewhat different example of a such type omitting argument application of this last theorem we provide one for nonstandard models of ZFC for which we have uses elsewhere.

Corollary 2.7. For every real C and reals X_{n} not Δ_{1}^{1} in C, there is a countable ω-model of ZFC containing C but not containing any X_{n} whose well founded part consists of the ordinals less than ω_{1}^{C}, the first ordinal not recursive in C.

Proof. Being a countable ω-model of ZFC containing (a set isomorphic to) C (under the isomorphism taking the ω of the model to true ω) is clearly a Σ_{1}^{1} in C property. Now apply Theorem 2.6 adding on a new real X_{0} = O^{C} (i.e. Kleene’s O relativized to C) to the list. It supplies a countable ω-model of ZFC containing C but not containing any of the X_{n}. As it contains C it contains every ordering recursive in C and so order types for every ordinal less than ω_{1}^{C}. On the other hand, if there were an ordinal in the model isomorphic to ω_{1}^{C} then, by standard results of hyperarithmetic theory, O^{C} would be in the model as well.

Finally, we point out that the complexity of the G of Theorem 2.6 (and hence of Corollary 2.7 as well) can be as low as possible.

Theorem 2.8. If K is a nonempty Σ_{1}^{1} class reals and X_{n} a countable sequence of reals uniformly Δ_{1}^{1} (recursive) in O none of which is Σ_{1}^{1}, then there is a G ∈ K with G Δ_{1}^{1} (recursive) in O such that no X_{n} is Σ_{1}^{1} in G. Indeed, G can be chosen to be of strictly smaller hyperdegree than O, i.e. O is not Δ_{1}^{1} in G. As in Theorem 2.6, if we assume only that the X_{n} are not Δ_{1}^{1} then we may conclude that none are Δ_{1}^{1} in G.

Proof. Suppose we are at step k = ⟨n, j⟩ of the construction. We know that either there is an m ∈ X_{n} such that (∀Z ∈ L_{k})(¬Θ_{k}(Z, m)) or an m ∉ X_{n} such that (∃Z ∈ L_{k})(Θ_{k}(Z, m)). As the X_{n} are uniformly Δ_{1}^{1} (recursive) in O, and the rest of the conditions considered in the construction are either Σ_{1}^{1} or Π_{1}^{1}, O can hyperarithmetically (recursively) decide which case to apply. As choosing the γ_{k+1} ⊃ γ_{k} and δ_{i.k+1} ⊃ δ_{i,k} for i ≤ k and so L_{k+1} now only require finding ones for which the corresponding Σ_{1}^{1} class L_{k+1} is nonempty, this step is also recursive in O. Of course, as we can add O onto the list of X_{n}, we then guarantee that O is not Σ_{1}^{1} in G and so, of course, not Δ_{1}^{1} in G as required.

Note that by a result of Spector’s (see Sacks [1990, Theorem II.7.6(ii)]) ω_{1}^{CK} < ω_{1}^{A} implies that O is Δ_{1}^{1} in A (indeed there is a pair of Σ_{1}^{1} formulas φ(X, n) and θ(X, n) which define O and its complement for any X with ω_{1}^{X} > ω_{1}^{CK}), we have the Kleene and Gandy basis theorem for Σ_{1}^{1} classes as well.

Theorem 2.9 (Kleene and Gandy Basis Theorems). Every nonempty Σ_{1}^{1} class of reals K contains an element A recursive in and of strictly smaller hyperdegree than O. In particular, one with ω_{1}^{A} = ω_{1}^{CK}.

3 The Proof for Classes of Reals

In this section we prove our result for classes of reals.

Theorem 3.1. If a class A of reals is Σ_{1}^{1} in every member of a nonempty Σ_{1}^{1} class B of reals then it is Σ_{1}^{1}.

The proof relies on several basic and important results of effective descriptive set theory. To ease reading the proof, we state the most important ones now. We state lightface versions without parameters. Relativizations to individual real parameters are routine. (Note that, when ordinals or lengths of well-ordered relations are involved, relativization to Z includes replacing ω_{1}^{CK} by ω_{1}^{Z}. ) We don’t need the full boldface versions. These facts can be found in basic books on effective descriptive set theory such as Moschovakis [1980], higher recursion theory such as Sacks [1990] or Hinman [1978] or even reverse mathematics such as Simpson [2009].

Proposition 3.2 (Codes). We can code Δ_{1}^{1} classes of reals V as either Δ_{1}^{1} reals C (Δ_{1}^{1} codes) or as numbers e by coding the Δ_{1}^{1} code C as a number e (hyperarithmetic codes for Δ_{1}^{1} reals). In either case, the property of being a code is Π_{1}^{1} and membership of a real Z in the set coded by C or e is a Δ_{1}^{1} relation given that C and e are codes. Similarly, membership of a number n in a Δ_{1}^{1} real with hyperarithmetic code e is a Δ_{1}^{1} relation. We can pass in a Δ_{1}^{1} way between these types of codes and the syntactic ones given by the formulas required in our definition of Δ_{1}^{1} reals and classes given that all the objects are, in fact, codes. In this situation we often abuse notation by writing Z ∈ C to denote the assertion that Z is in the class coded by C. When C and D are both codes, we use D ⊆ C to denote the assertion that ∀Z( Z ∈ D → Z ∈ C) and similarly for D ⊇ C. These relations are then all Π_{1}^{1}. These facts also imply that the predicate Z is Δ_{1}^{1}(X) is Π_{1}^{1}. (We also use C ⊇ A for an arbitrary class A of reals to mean that every real in the set coded by C is in A.)

Proposition 3.3 (Representation Theorem). If V is a Π_{1}^{1} class then there is a Δ_{1}^{1} function F such that Z ∈ V ⇔ F(Z) ∈ W O where W O is the class of reals Z which, viewed as a set of pairs of numbers, represents a well ordering. If Z ∈ W O, we write |Z| for the ordinal represented by Z.

Proposition 3.4 (Bounding). If V is a Π_{1}^{1} class of reals, F is as in Proposition 3.3 then V is Δ_{1}^{1} if and only if there is a bound < ω_{1}^{CK} on the order types of F(Z) for Z ∈ V. Moreover, if V contains only Δ_{1}^{1} reals and G is a Δ_{1}^{1} subset of V then such a bound (expressed as either a real or a number coding a recursive well-ordering) for {F(Z)|Z ∈ G} (or even any Σ_{1}^{1} subset of the Δ_{1}^{1} well orderings) can be found in a Δ_{1}^{1} way from the codes (or indices) for F, G and V. As a consequence we may, in this case, divide V into an increasing,continuous sequence ⟨V_{i}|i < ω_{1}^{CK}⟩ of uniformly Δ_{1}^{1} sets given by V_{i} = {Z ∈ V| |F(Z)| < i}.

Remark 3.5. While we have not found an explicit statement in our references of the uniformity described in this bounding theorem, it can easily be deduced from the uniform version of the analogous theorem for sets of numbers (as in e.g. Sacks [1990, II.3.4]) by translating the real codes for ordinals < ω_{1}^{CK} to numbers in O of at least as large a rank given by Sacks [1990, I.4.3].

Proposition 3.6 (Gandy-Harrington Forcing). We can define a general notion of forcing whose conditions are Σ_{1}^{1} classes ordered by inclusion as extension. A simplified version of the proof of Theorem 2.1 that leaves out the diagonalization requirements shows that we may construct a generic G in any given Σ_{1}^{1} class meeting any countable collection of dense sets. Thus we may use this forcing notion in any of the common ways. As usual, we will be interested in forcing over countable standard models of fragments of ZFC containing various specified reals. In addition to the typical results about forcing such as forcing equals truth, we note that, by the arguments in the proof of Theorem 2.1, a Π_{1}^{1} sentence φ(G) about the generic G is forced by a condition (Σ_{1}^{1} set) P if and only if ∀Z ∈ P(φ(Z)). We also note that if ⟨G_{0}, G_{1}⟩ is generic then both G_{0} and G_{1} are generic. (See Miller [1995, §30] for more about this forcing notion and Lemma 30.3 there for this last particular fact.) Absoluteness considerations will also play a role in our applications of this forcing.

As a notational convenience in proving our theorem, we can, by the Gandy basis theorem (Theorem 2.9) and the fact that ω_{1}^{B} = ω_{1}^{CK} is a Σ_{1}^{1} predicate (of B), assume without loss of generality that ω_{1}^{B} = ω_{1}^{CK} for every B ∈ B. (Note ω_{1}^{B} = ω_{1}^{CK} ⇔ ∀e({e}^{B} is a well-ordering → ∃i∃f(f is an isomorphism of {i} and {e}^{B}).)

We begin with some crucial approximations to our class A and an analysis of their properties.

Notation 3.7. We let D_{B} = {C|C is a Δ_{1}^{1}(B) code & C ⊇ A} and A_{B} = {A|(∀C ∈ D_{B})(A ∈ C)}. Similarly, we let A_{0} = {A|A is a member of every Δ_{1}^{1} class containing A}. For B ∈ B, we let ψ_{B}(Z) be a Σ_{1}^{1}(B) formula defining A.

Lemma 3.8. For B ∈ B, D_{B} is Π_{1}^{1}(B) and A_{B} is Σ_{1}^{1}(B).

Proof. Fix B ∈ B. For any real C, C ∈ D_{B} if and only if C is a Δ_{1}^{1}(B) code and ∀Z(ψ_{B}(Z) → Z ∈ C). As ψ_{B} is Σ_{1}^{1}(B), both conjuncts here are Π_{1}^{1}(B) by Proposition 3.2 and so D_{B} is Π_{1}^{1}(B) as required. The second claim now follows directly from the definition of A_{B} and Proposition 3.2. (Rephrase the definition of D_{B} in terms of number codes to make the quantifier count work.)

Lemma 3.9. For any reals A and B in B with ω_{1}^{A,B} = ω_{1}^{CK}, A ∈ A ⇔A ∈ A_{B}.

Proof. Clearly A ∈ A implies that A ∈ A_{B} for every B ∈ B by the definition of A_{B}. For the other direction suppose A ∉ A. Let F ∈ Δ_{1}^{1}(B) be as in Proposition 3.3 for the Π_{1}^{1}(B) class V = {Z|¬ψ_{B}(Z)} which is the complement of A. Thus F(A) is a well ordering which is Δ_{1}^{1}(A, B) and so, by hypothesis, less than some i < ω_{1}^{CK}. Thus the (obviously Σ_{1}^{1}) set {Z|F(Z) < i} is equal to the Π_{1}^{1} set {Z|¬ψ_{B}(Z) & (i + 1) ≰ F(Z)} and so is Δ_{1}^{1}(B). It is disjoint from A and has A as a member by our choice of i. The Δ_{1}^{1}(B) code C for its complement is then a member of D_{B} not containing A as a member. This C is then a witness that A ∉ A_{B} as required.

Lemma 3.10. A_{0} is Σ_{1}^{1}.

Proof. Consider the real J = {e|e is a hyperarithmetic index for a Δ_{1}^{1} code of a superset of A} = {e|e is a hyperarithmetic index for a real in D_{B}}. This real J is Π_{1}^{1}(B) in every B ∈ B by Lemma 3.8 and Proposition 3.2. So by Theorem 2.1 (formally applied to the complements) is Π_{1}^{1}. Thus A_{0} which is the intersection of the sets coded by indices in J is Σ_{1}^{1}: Z ∈ A_{0} ⇔ ∀e(e ∈ J → Z is in the set coded by e).

Lemma 3.11. If B, C ∈ B and ω_{1}^{B,C} = ω_{1}^{CK}, then A_{B} = A_{C}.

Proof. If not, then we have, without loss of generality, an A ∈ A_{C} −A_{B}. So there is a code D ∈ D_{B} with A ∉ D and A ∈ A_{C}. Now the nonempty class W ={Z|Z ∈ A_{C} & Z ∉ D} is Σ_{1}^{1}(B, C) by Lemma 3.8 and Proposition 3.2. Thus by the Gandy basis theorem (relative to B, C) (Theorem 2.9) there is a W in W and so in A_{C} −A_{B} with ω_{1}^{W,B,C} = ω_{1}^{CK}. Lemma 3.9, however, tells us that W ∈ A_{B} ⇔ W ∈ A ⇔ W ∈ A_{C} for a contradiction.

Lemma 3.12. If B, C ∈ B and ω_{1}^{B,C} = ω_{1}^{CK}, then for every X ∈ D_{B} there is a Y ∈ D_{B} and a Z ∈ D_{C} such that Y ⊆ X and Z ⊆ Y ⊆ Z, i.e. Y and Z are codes for the same set.

Proof. By Proposition 3.4, there is a uniformly Δ_{1}^{1} continuous increasing sequences D_{B,i} (i < ω_{1}^{CK} = ω_{1}^{B}) with union D_{B}. We can then set A_{B,i} = {A|∀C ∈ D_{B,i}(A ∈ C)}. This sequence is clearly nested and continuous with intersection A_{B}. As D_{B,i} and all its members are Δ_{1}^{1}(B), the A_{B,i} are also uniformly Δ_{1}^{1}(B) by Proposition 3.2 as we can convert to number codes. Similarly, we have D_{C,i} and A_{C,i} (i < ω_{1}^{CK} = ω_{1}^{C}). By Lemma 3.11 we know that for each i < ω_{1}^{CK} and Z ∈ \overline{A_{B,i}} there is a j < ω_{1}^{CK} such that Z ∈ \overline{A_{C,j}}. By Proposition 3.4, there is a k < ω_{1}^{CK} such that for every Z ∈ \overline{A_{B,i}}, Z ∈ \overline{A_{C,k}} and we can get k uniformly Δ_{1}^{1}(B, C). Of course, the analogous fact switching B and C is also true. Iterating and interleaving these Δ_{1}^{1}(B, C) functions starting with any i < ω_{1}^{CK} produces a Δ_{1}^{1}(B, C) increasing sequence of k < ω_{1}^{CK}. By Proposition 3.4, this sequence has a bound and hence a supremum l < ω_{1}^{CK} and A_{B,l} = A_{C,l}.

Now consider any X ∈ D_{B,i} so X ⊇ A_{B,l} for any l > i in ω_{1}^{CK}. We may now choose one such that A_{B,l} = A_{C,l}. As A_{B,l} ∈ Δ_{1}^{1}(B) and contains A, there is a code Y ∈ D_{B} for it. Similarly there is a code Z ∈ D_{C} for A_{C,l}. As A_{B,l} = A_{C,l}, these are then the desired Y and Z.

Lemma 3.13. For every B ∈ B, A_{B} = A_{0}.

Proof. Fix B ∈ B. Clearly, it suffices to prove that ∀X ∈ D_{B}∃Y ∈ D_{B}(X ⊇ Y & V = {Z|Z ∈ Y } ∈ Δ_{1}^{1}). (As this says there is, for each X ∈ D_{B}, a Δ_{1}^{1} code V for a Δ_{1}^{1} class V contained in the class coded by X and containing A (as Y ∈ D_{B}). This code shows that A_{0} ⊆ A_{B} by definition. On the other hand, A_{B} ⊆ A_{0} for every B.)

Fix an X ∈ D_{B}. Consider now the class W = {C ∈ B|(∀Y ∈ D_{B})(X ⊇ Y → {Z|Z ∈ Y } ∉ Δ_{1}^{1}(C)}. By Proposition 3.2, this class is Σ_{1}^{1}(B). If it were nonempty then, by the Gandy basis theorem (relative to B) (Theorem 2.9), it would have a member C with ω_{1}^{B,C} = ω_{1}^{CK}. This would provide a counterexample to Lemma 3.12 and so W is empty.

We now work with a countable standard model which contains B and satisfies a fragment of ZFC sufficient to guarantee the absoluteness of Σ_{1}^{1} formulas. Note, for example, that all reals Δ_{1}^{1} in B (and so all in D_{B}) are in this model.

Let G ∈ B be a Gandy-Harrington generic over this model as in Proposition 3.6. As G ∉ W, there is a Y ∈ D_{B} such that X ⊇ Y and {Z|Z ∈ Y } ∈ Δ_{1}^{1}(G). Fix a specific Δ_{1}^{1} definition of this class from G, i.e. Σ_{1}^{1}(G) formulas φ and θ such that ∀Z(φ(G, Z) ↔ ¬θ(G, Z)), ∀Z(Z ∈ Y → φ(G, Z)) and ∀Z(Z ∉ Y → θ(G, Z)). As G is generic we have a Σ_{1}^{1} P forcing these sentences. Now consider the Σ_{1}^{1} class Q = {⟨C, C′⟩ |C, C′ ∈ P & ∃Z(φ(C, Z) & θ(C′, Z) ∨ φ(C′, Z) & θ(C, Z))}. If Q is nonempty then there is a Gandy-Harrington generic ⟨C, C′⟩ ∈ Q. Each of C and C′ is in P and Gandy-Harrington generic by Proposition 3.6. Thus any Z witnessing that ⟨C, C′⟩ ∈ Q would be a counterexample to one of the sentences above forced by P and hence true of C and C′. Thus Q is empty and so Z ∈ Y ⇔ (∀C ∈ P)(¬θ(C, Z)) and Z ∉ Y ⇔ (∀C ∈ P)(¬φ(C, Z)) and {Z|Z ∈ Y } is Δ_{1}^{1} as required.

We now prove our theorem on Σ_{1}^{1} classes.

Proof of Theorem 3.1: We claim that A ∈ A if and only if A ∈ A_{0} (which is Σ_{1}^{1} by Lemma 3.10) and one of the following two Σ_{1}^{1} statements hold for a Σ_{1}^{1} formula ψ that we will define below:

(1) ω_{1}^{A} = ω_{1}^{CK} or

(2) ω_{1}^{A} > ω_{1}^{CK} → ψ(A).

Now A ∈ A → A ∈ A_{0} by the definition of A_{0}. So we may assume that A ∈ A_{0} and show that A ∈ A ⇔ (1) or (2) holds. If (1) holds then by the Gandy basis theorem (Theorem 2.9) (relative to A) we may choose a B ∈ B with ω_{1}^{A,B} = ω_{1}^{CK}. Now by Lemma 3.9, A ∈ A ⇔ A ∈ A_{B} while A ∈ A_{B} ⇔ A ∈ A_{0} by Lemma 3.13. Thus, in this case, A ∈ A ⇔ A ∈ A_{0} as required.

Assume then that (1) fails and so the hypothesis of (2) holds. We now must argue that we have a Σ_{1}^{1} formula ψ(A) that, under these assumptions, is equivalent to A ∈ A. As mentioned just before Theorem 2.9, there is a pair if Σ_{1}^{1} formulas φ(X, n) and θ(X, n) which define O and its complement for any X with ω_{1}^{X} > ω_{1}^{CK}. By the Kleene basis theorem (Theorem 2.9) there is a recursive index computing a B ∈ B from O. By the hypothesis of our theorem there is a Σ_{1}^{1}(B) formula ψ_{B}(Z) defining A. Thus there is a Σ_{1}^{1} formula ψ̂(X, Z) which defines A from any X with ω_{1}^{X} > ω_{1}^{CK}. We now take our desired ψ to be ψ̂(A, A).

As a final comment, we point out that if we had only wanted to prove Theorem 3.1 in the Δ_{1}^{1} case we would have a simple proof along the lines of the last paragraph of the proof of Lemma 3.13. This argument also gives a proof of the analog for classes of reals of the Δ_{1}^{1} case of Theorem 2.6.

Theorem 3.14. If B is a nonempty Σ_{1}^{1} class of reals and X_{n} a countable sequence of classes of reals none of which is Δ_{1}^{1}, then there is a G ∈ B such that no X_{n} is Δ_{1}^{1} in G.

Proof. Note that if X_{m} ∉ Δ_{1}^{1}(B) for every B ∈ B then any G ∈ B works for X_{m}. Thus we may assume that for every n there is a B_{n} ∈ B and φ_{n} and θ_{n} Σ_{1}^{1} formulas with two free real variables which, with B_{n} for the first variable, define X_{n} and its complement. Let G ∈ B be a Gandy-Harrington generic over a countable standard model of a sufficient fragment of ZFC containing the B_{n}. We claim no X_{n} is Δ_{1}^{1}(G). If not, let φ and θ be Σ_{1}^{1}(G) formulas defining some X_{n} and its complement. Let P be a condition which forces that (∀Z)(φ_{n}(B_{n}, Z) → φ(G, Z)), (∀Z)(θ_{n}(B_{n}, Z) → θ(G, Z)) and (∀Z(φ(G, Z) ↔ ¬θ(G, Z)). Now consider the Σ_{1}^{1} class Q = {⟨C, C′⟩ |C, C′ ∈ P & ∃Z(φ(C, Z) & θ(C′, Z) ∨ φ(C′, Z) & θ(C, Z))}. If Q is nonempty then there is a Gandy-Harrington generic ⟨C, C′⟩ ∈ Q. Each of C and C′ is in P and Gandy-Harrington generic by Proposition 3.6. Thus any Z witnessing that ⟨C, C′⟩ ∈ Q would be a counterexample to one of the sentences above forced by P and hence true of C and C′. Thus Q is empty and so Z ∈ X_{n} ⇔ (∀C ∈ P)(¬θ(C, Z)) and Z ∉ X_{n} ⇔ (∀C ∈ P)(¬φ(C, Z)) and so X_{n} is Δ_{1}^{1} for the desired contradiction.

Corollary 3.15. Any class A of reals which is Δ_{1}^{1} in every member of a Σ_{1}^{1} class B of reals is Δ_{1}^{1}.

We do not know if the full analog of Theorem 2.6 for classes of reals , i.e. Theorem 3.14 with Δ_{1}^{1} replaced by Σ_{1}^{1}, is also true.

4 Bibliography

Andrews, U. and Miller, J. S. [2015], Spectra of theories and structures, Proceedings of the American Mathematical Society 143, 1283-1298.

Hinman, P. G. [1978], Recursion Theoretic Hierarchies, Perspectives in Mathematical Logic, Springer-Verlag, Berlin.

Miller , A. W. [1995], Descriptive Set Theory and Forcing, Lecture Notes in Logic, Springer-Verlag, Berlin.

Moschovakis, Y. N. [1980], Descriptive Set Theory, Studies in Logic and the Foundations of Mathematics 100, North-Holland, Amsterdam.

Sacks, G. E. [1990], Higher Recursion Theory, Perspectives in Mathematical Logic, Springer-Verlag, Berlin.

Simpson, S. G. [2009], Subsystems of Second Order Arithmetic 2^{nd} ed., Perspectives in Logic, ASL and Cambridge University Press, New York.