ar X iv :1 40 1. 18 94 v1 [ m at h. L O ] 9 J an 2 01 4 Submitted on September 3, 2013 to the Notre Dame Journal of Formal Logic Volume ??, Number ??, Guessing, Mind-changing, and the Second Ambiguous Class Samuel Alexander Abstract In his dissertation, Wadge defined a notion of guessability on subsets of the Baire space and gave two characterizations of guessable sets. A set is guessable iff it is in the second ambiguous class (∆02), iff it is eventually annihilated by a certain remainder. We simplify this remainder and give a new proof of the latter equivalence. We then introduce a notion of guessing with an ordinal limit on how often one can change one's mind. We show that for every ordinal α , a guessable set is annihilated by α applications of the simplified remainder if and only if it is guessable with fewer than α mind changes. We use guessability with fewer than α mind changes to give a semi-characterization of the Hausdorff difference hierarchy, and indicate how Wadge's notion of guessability can be generalized to higher-order guessability, providing characterizations of ∆0α for all successor ordinals α > 1. 1 Introduction Let NN be the set of sequences s : N → N and let N<N be the set ∪nNn of finite sequences. If s ∈ N<N, we will write [s] for { f ∈ NN : f extends s}. We equip NN with a second-countable topology by declaring [s] to be a basic open set whenever s ∈ N<N. Throughout the paper, S will denote a subset of NN. We say that S ∈ ∆02 if S is simultaneously a countable intersection of open sets and a countable union of closed sets in the above topology. In classic terminology, S ∈ ∆02 just in case S is both Gδ and Fσ . The following notion was discovered by Wadge [9] (pp. 141–142) and independently by this author [1]. 1 2010 Mathematics Subject Classification: Primary 03E15 Keywords: guessability, difference hierarchy 1 2 S. Alexander Definition 1.1 We say S is guessable if there is a function G : N<N →{0,1} such that for every f ∈ NN, lim n→∞ G( f ↾ n) = χS( f ) = { 1, if f ∈ S, 0, if f 6∈ S. If so, we say G guesses S, or that G is an S-guesser. The intution behind the above notion is captured eloquently by Wadge (p. 142, notation changed): Guessing sets allow us to form an opinion as to whether an element f of NN is in S or Sc, given only a finite initial segment f ↾ n of f . Game theoretically, one envisions an asymmetric game where II (the guesser) has perfect information, I (the sequence chooser) has zero information, and II's winning set consists of all sequences (a0,b0,a1,b1, . . .) such that bi → 1 if (a0,a1, . . .)∈ S and bi → 0 otherwise. The following result was proved in [9] (pp.144–145) by infinite game-theoretical methods. The present author found a second proof [1] using mathematical logical methods. Theorem 1.2 (Wadge) S is guessable if and only if S ∈ ∆02. Wadge defined (pp. 113–114) the following remainder operation. Definition 1.3 For A,B ⊆ NN, define Rm0(A,B) = NN. For μ > 0 an ordinal, define Rmμ(A,B) = ⋂ ν<μ ( Rmν(A,B)∩A∩Rmν(A,B)∩B ) . (Here • denotes topological closure.) Write Rmμ(S) for Rmμ(S,Sc). By countability considerations, there is some (in fact countable) ordinal μ , depending on S, such that Rmμ(S) = Rmμ ′(S) for all μ ′ ≥ μ ; Wadge writes RmΩ(S) for Rmμ(S) for such a μ . He then proves the following theorem: Theorem 1.4 (Wadge, attributed to Hausdorff) S ∈ ∆02 if and only if RmΩ(S) = /0. In Section 2, we introduce a simpler remainder (S,α) 7→ Sα and use it to give a new proof of Theorem 1.4. In Section 3, we introduce the notion of S being guessable while changing one's mind fewer than α many times (α ∈ Ord) and show that this is equivalent to Sα = /0. In Section 4, we show that for α > 0, S is guessable while changing one's mind fewer than α + 1 many times if and only if at least one of S or Sc is in the αth level of the difference hierarchy. In Section 5, we generalize guessability, introducing the notion of μ th-order guessability (1 ≤ μ < ω1). We show that S is μ th-order guessable if and only if S ∈ ∆0μ+1. 2 Guessable Sets and Remainders In this section we give a new proof of Theorem 1.4. We find it easier to work with the following remainder2 which is closely related to the remainder defined by Wadge. For X ⊆ N<N, we will write [X ] to denote the set of infinite sequences all of whose finite initial segments lie in X . Guessing and Mind-changing 3 Definition 2.1 Let S ⊆ NN. We define Sα ⊆ N<N (α ∈ Ord) by transfinite recursion as follows. We define S0 = N<N, and Sλ = ∩β<λ Sβ for every limit ordinal λ . Finally, for every ordinal β , we define Sβ+1 = {x ∈ Sβ : ∃x ′,x′′ ∈ [Sβ ] such that x ⊆ x ′, x ⊆ x′′, x′ ∈ S, x′′ 6∈ S}. We write α(S) for the minimal ordinal α such that Sα = Sα+1, and we write S∞ for Sα(S). Clearly Sα ⊆ Sβ whenever β < α . This remainder notion is related to Wadge's as follows. Lemma 2.2 For each ordinal α , Rmα(S) = [Sα ]. Proof Since Sα ⊆ Sβ whenever β < α , for all α , we have Sα = ∩β<αSβ+1 (with the convention that ∩ /0 = N<N). We will show by induction on α that Rmα(S) = [Sα ] = [∩β<αSβ+1]. Suppose f ∈ [∩β<α Sβ+1]. Let β < α . Let U be an open set around f , we can assume U is basic open, so U = [ f0], f0 a finite initial segment of f . Since f ∈ [∩β<α Sβ+1], f0 ∈ Sβ+1. Thus there are x ′,x′′ ∈ [Sβ ] extending f0 (hence in U ), x′ ∈ S, x′′ 6∈ S. In other words, x′ ∈ [∩γ<β Sγ+1]∩ S and x ′′ ∈ [∩γ<β Sγ+1]∩ S c. By induction, x′ ∈ Rmβ (S) ∩ S and x ′′ ∈ Rmβ (S) ∩ S c. By arbitrariness of U , f ∈ Rmβ (S)∩S∩Rmβ (S)∩Sc. By arbitrariness of β , f ∈ Rmα(S). The reverse inclusion is similar. Note that Lemma 2.2 does not say that Rmα(S) = /0 if and only if Sα = /0. It is (at least a priori) possible that Sα 6= /0 while [Sα ] = /0. Lemma 2.2 does however imply that RmΩ(S) = /0 if and only if S∞ = /0, since it is easy to see that if [Sα ] = /0 then Sα+1 = /0. Thus in order to prove Theorem 1.4 it suffices to show that S is guessable if and only if S∞ = /0. The ⇒ direction requires no additional machinery. Proposition 2.3 If S is guessable then S∞ = /0. Proof Let G : N<N → {0,1} be an S-guesser. Assume (for contradiction) S∞ 6= /0 and let σ0 ∈ S∞. We will build a sequence on whose initial segments G diverges, contrary to Definition 1.1. Inductively suppose we have finite sequences σ0 ⊂ 6= * * * ⊂ 6= σk in S∞ such that ∀0 < i ≤ k, G(σi) ≡ i mod 2. Since σk ∈ S∞ = Sα(S) = Sα(S)+1, there are σ ′,σ ′′ ∈ [S∞], extending σk, with σ ′ ∈ S, σ ′′ 6∈ S. Choose σ ∈ {σ ′,σ ′′} with σ ∈ S iff k is even. Then limn→∞ G(σ ↾ n)≡ k+1 mod 2. Let σk+1 ⊂ σ properly extend σk such that G(σk+1)≡ k+1 mod 2. Note σk+1 ∈ S∞ since σ ∈ [S∞]. By induction, there are σ0 ⊂ 6= σ1 ⊂ 6= * * * such that for i > 0, G(σi) ≡ i mod 2. This contradicts Definition 1.1 since limn→∞ G((∪iσi) ↾ n) ought to converge. The ⇐ direction requires a little machinery. Definition 2.4 If σ ∈ N<N, σ 6∈ S∞, let β (σ) be the least ordinal such that σ 6∈ Sβ (σ). Note that whenever σ 6∈ S∞, β (σ) is a successor ordinal. Lemma 2.5 Suppose σ ⊆ τ are finite sequences. If τ ∈ S∞ then σ ∈ S∞. And if σ 6∈ S∞, then β (τ)≤ β (σ). 4 S. Alexander Proof It is enough to show that ∀β ∈ Ord, if τ ∈ Sβ then σ ∈ Sβ . This is by induction on β , the limit and zero cases being trivial. Assume β is successor. If τ ∈ Sβ , this means τ ∈ Sβ−1 and there are τ ′,τ ′′ ∈ [Sβ−1] extending τ with τ ′ ∈ S, τ ′′ 6∈ S. Since τ ′ and τ ′′ extend τ , and τ extends σ , τ ′ and τ ′′ extend σ ; and since σ ∈ Sβ−1 (by induction), this shows σ ∈ Sβ . Lemma 2.6 Suppose f : N→ N, f 6∈ [S∞]. There is some i such that for all j ≥ i, f ↾ j 6∈ S∞ and β ( f ↾ j) = β ( f ↾ i). Furthermore, f ∈ [Sβ ( f ↾i)−1]. Proof The first part follows from Lemma 2.5 and the well-foundedness of Ord. For the second part we must show f ↾ k ∈ Sβ ( f ↾i)−1 for every k. If k ≤ i, then f ↾ k ∈ Sβ ( f ↾i)−1 by Lemma 2.5. If k ≥ i, then β ( f ↾ k) = β ( f ↾ i) and so f ↾ k ∈ Sβ ( f ↾i)−1 since it is in Sβ ( f ↾k)−1 by definition of β . Definition 2.7 If S∞ = /0 then we define GS : N<N → {0,1} as follows. Let σ ∈ N<N. Since S∞ = /0, σ 6∈ S∞, so σ ∈ Sβ (σ)−1\Sβ (σ). Since σ 6∈ Sβ (σ), this means for every two extensions x′,x′′ of σ in [Sβ (σ)−1], either x′,x′′ ∈ S or x′,x′′ ∈ Sc. So either all extensions of σ in [Sβ (σ)−1] are in S, or all such extensions are in Sc. (i) If there are no extensions of σ in [Sβ (σ)−1], and length(σ) > 0, then let GS(σ) = GS(σ−) where σ− is obtained from σ by removing the last term. (ii) If there are no extensions of σ in [Sβ (σ)−1], and length(σ) = 0, let GS(σ) = 0. (iii) If there are extensions of σ in [Sβ (σ)−1] and they are all in S, define GS(σ) = 1. (iv) If there are extensions of σ in [Sβ (σ)−1] and they are all in Sc, define GS(σ) = 0. Proposition 2.8 If S∞ = /0 then GS guesses S. Proof Assume S∞ = /0. Let f ∈ S. I will show GS( f ↾ n) → 1 as n → ∞. Since f 6∈ [S∞], let i be as in Lemma 2.6. I claim GS( f ↾ j) = 1 whenever j ≥ i. Fix j ≥ i. We have β ( f ↾ j) = β ( f ↾ i) by choice of i, and f ∈ [Sβ ( f ↾i)−1] = [Sβ ( f ↾ j)−1]. Since f ↾ j has one extension (namely f itself) in both [Sβ ( f ↾ j)−1] and S, GS( f ↾ j) = 1. Identical reasoning shows that if f 6∈ S then limn→∞ GS( f ↾ n) = 0. Theorem 2.9 S ∈ ∆02 if and only if S∞ = /0. That is, Theorem 1.4 is true. Proof By combining Propositions 2.3 and 2.8 and Theorem 1.2. 3 Guessing without changing one's Mind too often In this section our goal is to tease out additional information about ∆02 from the operation defined in Definition 2.1. Definition 3.1 For each function G with domainN<N, if G( f ↾ (n+1)) 6=G( f ↾ n) ( f ∈ NN, n ∈ N), we say G changes its mind on f ↾ (n+ 1). Now let α ∈ Ord. We say S is guessable with < α mind changes if there is an S-guesser G along with a function H : N<N → α such that the following hold, where f ∈ NN and n ∈ N. (i) H( f ↾ (n+ 1))≤ H( f ↾ n). (ii) If G changes its mind on f ↾ (n+ 1), then H( f ↾ (n+ 1))< H( f ↾ n). This notion bears some resemblance to the notion of a set Z ⊆ N being f -c.e. in [4], or g-c.a. in [7]. Guessing and Mind-changing 5 Theorem 3.2 For α ∈ Ord, S is guessable with < α mind changes if and only if Sα = /0. Proof (⇒) Assume S is guessable with < α mind changes. Let G,H be as in Definition 3.1. We claim that for all β ∈ Ord, if σ ∈ Sβ then H(σ) ≥ β . This will prove (⇒) because it implies that if Sα 6= /0 then there is some σ with H(σ)≥ α , absurd since codomain(H) = α . We attack the claim by induction on β . The zero and limit cases are trivial. Assume β = γ+1. Suppose σ ∈ Sγ+1. There are x′,x′′ ∈ [Sγ ] extending σ , x′ ∈ S, x′′ 6∈ S. Pick x∈{x′,x′′} so that χS(x) 6=G(σ) and pick σ+ ∈N<N with σ ⊆σ+ ⊆ x such that G(σ+) = χS(x) (some such σ+ exists since G guesses S). Since x ∈ [Sγ ], σ+ ∈ Sγ . By induction, H(σ+)≥ γ . The fact G(σ+) 6= G(σ) implies H(σ+)< H(σ), forcing H(σ)≥ γ + 1. (⇐) Assume Sα = /0. For all σ ∈ N<N, define H(σ) = β (σ)− 1 (by definition of β (σ), since Sα = /0, clearly H(σ) ∈ α). I claim GS,H witness that S is guessable with < α mind changes. By Proposition 2.8, GS guesses S. Let f ∈ NN, n ∈ N. By Lemma 2.5, H( f ↾ (n + 1)) ≤ H( f ↾ n). Now suppose GS changes its mind on f ↾ (n + 1), we must show H( f ↾ (n+ 1)) < H( f ↾ n). Assume, for sake of contradiction, that H( f ↾ (n+ 1)) = H( f ↾ n). Assume GS( f ↾ n) = 0, the other case is similar. By definition of GS, (∗) for every infinite extension f ′ of f ↾ n, if f ′ ∈ [Sβ ( f ↾n)−1] then f ′ ∈ Sc. Since GS changes its mind on f ↾ (n+ 1), GS( f ↾ (n+ 1)) = 1. Thus (∗∗) for every infinite extension f ′′ of f ↾ (n+ 1), if f ′′ ∈ [Sβ ( f ↾(n+1))−1] then f ′′ ∈ S. And f ↾ (n+1) does actually have some such infinite extension f ′′, because if it had none, that would make GS( f ↾ (n+1)) = GS( f ↾ n) by case 1 of the definition of GS (Definition 2.7). Being an extension of f ↾ (n+ 1), f ′′ also extends f ↾ n; and by the assumption that H( f ↾ (n+1)) = H( f ↾ n), f ′′ ∈ [Sβ ( f ↾n)−1]. By (∗), f ′′ ∈ Sc, and by (∗∗), f ′′ ∈ S. Absurd. It is not hard to show S is a Boolean combination of open sets if and only if S is guessable with < ω mind changes, so Theorem 3.2 and Lemma 2.2 give a new proof of a special case of the main theorem (p. 1348) of [3] (see also [2]). 4 Mind Changing and the Difference Hierarchy We recall the following definition from [5] (p. 175, stated in greater generality-we specialize it to the Baire space). In this definition, Σ01(NN) is the set of open subsets of NN, and the parity of an ordinal η is the equivalence class modulo 2 of n, where η = λ + n, λ a limit ordinal (or λ = 0), n ∈ N. Definition 4.1 Let (Aη)η<θ be an increasing sequence of subsets of NN with θ ≥ 1. Define the set Dθ ((Aη)η<θ )⊆ NN by x ∈ Dθ ((Aη )η<θ ) ⇔ x ∈ ⋃ η<θ Aη & the least η < θ with x ∈ Aη has parity opposite to that of θ . Let Dθ (Σ01)(N N) = {Dθ ((Aη)η<θ ) : Aη ∈ Σ01(N N), η < θ}. 6 S. Alexander This hierarchy offers a constructive characterization of ∆02: it turns out that ∆02 = ∪1≤θ<ω1Dθ (Σ 0 1)(N N) (see Theorem 22.27 of [5], p. 176, attributed to Hausdorff and Kuratowski). For brevity, we will write Dα for Dα(Σ01)(NN). Theorem 4.2 (Semi-characterization of the difference hierarchy) Let α > 0. The following are equivalent. (i) S is guessable with < α + 1 mind changes. (ii) S ∈ Dα or Sc ∈ Dα . We will prove Theorem 4.2 by a sequence of smaller results. Definition 4.3 For α,β ∈ Ord, write α ≡ β to indicate that α and β have the same parity (that is, 2|n−m, where α = λ + n and β = κ +m, n,m ∈ N, λ a limit ordinal or 0, κ a limit ordinal or 0). Proposition 4.4 Let α > 0. If S ∈ Dα , say S = Dα((Aη)η<α ) (Aη ⊆ NN open), then S is guessable with < α + 1 mind changes. Proof Define G : N<N → {0,1} and H : N<N → α + 1 as follows. Suppose σ ∈ N<N. If there is no η < α such that [σ ] ⊆ Aη , let G(σ) = 0 and let H(σ) = α . If there is an η < α (we may take η minimal) such that [σ ]⊆ Aη , then let G(σ) = { 0, if η ≡ α; 1, if η 6≡ α , H(σ) = η . Let f : N→N. Claim 1 limn→∞ G( f ↾ n) = χS( f ). If f 6∈ ∪η<α Aη , then f 6∈ Dα((Aη)η<α ) = S, and G( f ↾ n) will always be 0, so limn→∞ G( f ↾ n)= 0= χS( f ). Assume f ∈∪η<α Aη , and let η <α be minimum such that f ∈ Aη . Since Aη is open, there is some n0 so large that ∀n ≥ n0, [ f ↾ n]⊆ Aη . For all n ≥ n0, by minimality of η , [ f ↾ n] 6⊆ Aη ′ for any η ′ < η , so G( f ↾ n) = 0 if and only if η ≡ α . The following are equivalent. f ∈ S iff f ∈ Dα((Aη)η<α ) iff η 6≡ α iff G( f ↾ n) 6= 0 iff G( f ↾ n) = 1. This shows limn→∞ G( f ↾ n) = χS( f ). Claim 2 ∀n ∈ N, H( f ↾ (n+ 1))≤ H( f ↾ n). If H( f ↾ n) = α , there is nothing to prove. If H( f ↾ n) < α , then H( f ↾ n) = η where η is minimal such that [ f ↾ n] ⊆ Aη . Since [ f ↾ (n+ 1)] ⊆ [ f ↾ n], we have [ f ↾ (n+ 1)]⊆ Aη , implying H( f ↾ (n+ 1))≤ η . Claim 3 ∀n ∈ N, if G( f ↾ (n+ 1)) 6= G( f ↾ n), then H( f ↾ (n+ 1))< H( f ↾ n). Assume (for sake of contradiction) H( f ↾ (n + 1)) ≥ H( f ↾ n). By Claim 2, H( f ↾ (n + 1)) = H( f ↾ n). By definition of H this implies that ∀η < α , [ f ↾ (n+1)]⊆ Aη if and only if [ f ↾ n]⊆ Aη . This implies G( f ↾ (n+1)) = G( f ↾ n), contradiction. By Claims 1–3, G and H witness that S is guessable with < α +1 mind changes. Guessing and Mind-changing 7 Corollary 4.5 Let α > 0. If S ∈ Dα or Sc ∈ Dα then S is guessable with < α + 1 mind changes. Proof If S ∈ Dα this is immediate by Proposition 4.4. If Sc ∈ Dα then Proposition 4.4 says Sc is guessable with < α + 1 mind changes, and this clearly implies that S is too. Lemma 4.6 Suppose S is guessable with <α mind changes. Let G :N<N→{0,1}, H : N<N → α be a pair of functions witnessing as much (Definition 3.1). There is an H ′ : N<N → α such that G,H ′ also witness that S is guessable with < α mind changes, with H ′( /0) = H( /0), and with the additional property that for every f : N→ N and every n ∈ N, H( f ↾ (n+1)) ≡ H( f ↾ n) if and only if G( f ↾ (n+1)) = G( f ↾ n). Proof Define H ′(σ) by induction on the length of σ as follows. Let H ′( /0) =H( /0). If σ 6= /0, write σ = σ0 ⌢ n for some n ∈ N (⌢ denotes concatenation). If G(σ) = G(σ0), let H ′(σ) = H ′(σ0). Otherwise, let H ′(σ) be either H(σ) or H(σ)+ 1, whichever has parity opposite to H ′(σ0). By construction H ′ has the desired parity properties. A simple inductive argument shows that (∗) ∀σ ∈ N<N, H(σ) ≤ H ′(σ) < α . I claim that for all f : N→ N and n ∈ N, H ′( f ↾ (n + 1)) ≤ H ′( f ↾ n), and if G( f ↾ (n + 1)) 6= G( f ↾ n) then H ′( f ↾ (n+ 1))< H ′( f ↾ n). If G( f ↾ (n+1))=G( f ↾ n), then by definition H ′( f ↾ (n+1))=H ′( f ↾ n) and the claim is trivial. Now assume G( f ↾ (n+1)) 6=G( f ↾ n). If H ′( f ↾ (n+1))=H( f ↾ (n+1)) then H ′( f ↾ (n+ 1))< H( f ↾ n)≤ H ′( f ↾ n) and we are done. Assume H ′( f ↾ (n+ 1)) 6= H( f ↾ (n+ 1)), which forces that (∗∗) H ′( f ↾ (n+ 1)) = H( f ↾ (n+ 1))+ 1. To see that H ′( f ↾ (n+ 1))< H ′( f ↾ n), assume not (∗ ∗ ∗). By Definition 3.1, H( f ↾ (n+ 1))< H( f ↾ n), so H( f ↾ n)≥ H( f ↾ (n+ 1))+ 1 (Basic arithmetic) = H ′( f ↾ (n+ 1)) (By (∗∗)) ≥ H ′( f ↾ n) (By (∗ ∗ ∗)) ≥ H( f ↾ n). (By (∗)) Equality holds throughout, and H ′( f ↾ (n+1))= H ′( f ↾ n). Contradiction: we chose H ′( f ↾ (n+ 1)) with parity opposite to H ′( f ↾ n). Definition 4.7 For all G,H as in Definition 3.1, f ∈ NN, write G( f ) for limn→∞ G( f ↾ n) (so G( f ) = χS( f )) and write H( f ) for limn→∞ H( f ↾ n). Write G ≡ H to indicate that ∀ f ∈ NN, G( f ) ≡ H( f ); write G 6≡ H to indicate that ∀ f ∈ NN, G( f ) 6≡ H( f ) (we pronounce G 6≡ H as "G is anticongruent to H"). Lemma 4.8 Suppose G : N<N →{0,1} and H : N<N → α witness that S is guessable with < α mind changes. There is an H ′ : N<N → α such that G,H ′ witness that S is guessable with < α mind changes, and such that the following hold. If G( /0)≡ α then H ′ 6≡ G. If G( /0) 6≡ α then H ′ ≡ G. 8 S. Alexander Proof I claim that without loss of generality, we may assume the following (∗): If G( /0)≡ α then H( /0) 6≡ G( /0). If G( /0) 6≡ α then H( /0)≡ G( /0). To see this, suppose not: either G( /0) ≡ α and H( /0) ≡ G( /0), or else G( /0) 6≡ α and H( /0) 6≡G( /0). In either case, H( /0)≡α . If H( /0)≡α then H( /0)+1 6=α , and so, since H( /0)< α , H( /0)+1< α , meaning we may add 1 to H( /0) to enforce the assumption. Having assumed (∗), we may use Lemma 4.6 to construct H ′ : N<N → α such that G,H ′ witness that S is guessable with < α mind changes, H ′( /0) = H( /0), and H ′ changes parity precisely when G changes parity. The latter facts, combined with (∗), prove the lemma. Proposition 4.9 Suppose G : N<N → {0,1} and H : N<N → α + 1 witness that S is guessable with < α + 1 mind changes. If G( /0) = 0 then S ∈ Dα . Proof By Lemma 4.8 we may safely assume the following: If G( /0)≡ α + 1 then H 6≡ G. If G( /0) 6≡ α + 1 then H ≡ G. In other words, (∗) If G( /0)≡ α then H ≡ G. (∗∗) If G( /0) 6≡ α then H 6≡ G. For each η < α , let Aη = { f ∈ N N : H( f )≤ η}. (H( f ) as in Definition 4.7) I claim S = Dα((Aη )η<α), which will prove the proposition since each Aη is clearly open. Suppose f ∈ S, I will show f ∈ Dα((Aη )η<α). Since f ∈ S, H( f ) 6= α , because if H( f ) were = α , this would imply that G never changes its mind on f , forcing limn→∞ G( f ↾ n) = limn→∞ G( /0) = 0, contradicting the fact that G guesses S. Since H( f ) 6= α , H( f ) < α . It follows that for η = H( f ) we have f ∈ Aη and η is minimal with this property. Case 1: G( /0) ≡ α . By (∗), H ≡ G. Since f ∈ S, limn→∞ G( f ↾ n) = 1, so η = limn→∞ H( f ↾ n) ≡ 1. Since α ≡ G( /0) = 0, this shows η 6≡ α , putting f ∈ Dα((Aη )η<α). Case 2: G( /0) 6≡ α . By (∗∗), H 6≡ G. Since f ∈ S, limn→∞ G( f ↾ n) = 1, so η = limn→∞ H( f ↾ n) ≡ 0. Since α 6≡ G( /0) = 0, this shows η 6≡ α , so f ∈ Dα((Aη )η<α). Conversely, suppose f ∈ Dα((Aη)η<α), I will show f ∈ S. Let η be minimal such that f ∈ Aη (by definition of Aη , η = H( f )). By definition of Dα((Aη )η<α), η 6≡ α . Case 1: G( /0)≡α . By (∗), H ≡G. Since limn→∞ H( f ↾ n)=H( f )=η 6≡α ≡G( /0)= 0, we see limn→∞ H( f ↾ n) = 1. Since H ≡ G, limn→∞ G( f ↾ n) = 1, forcing f ∈ S since G guesses S. Case 2: G( /0) 6≡ α . By (∗∗), H 6≡ G. Since lim n→∞ H( f ↾ n) = H( f ) = η 6≡ α 6≡ G( /0) = 0, we see limn→∞ H( f ↾ n) = 0. Since H 6≡ G, limn→∞ G( f ↾ n) = 1, again showing f ∈ S. Corollary 4.10 If S is guessable with < α + 1 mind changes, then S ∈ Dα or Sc ∈ Dα . Guessing and Mind-changing 9 Proof Let G,H witness that S is guessable with <α+1 mind changes. If G( /0) = 0 then S ∈ Dα by Proposition 4.9. If not, then (1−G),H witness that Sc is guessable with < α +1 mind changes, and (1−G)( /0) = 0, so Sc ∈ Dα by Proposition 4.9. Combining Corollaries 4.5 and 4.10 proves Theorem 4.2. 5 Higher-order Guessability In this section we introduce a notion that generalizes guessability to provide a characterization for ∆0μ+1 (1 ≤ μ < ω1). We will show that S ∈ ∆ 0 μ+1 if and only if S is μ th-order guessable. Throughout this section, μ denotes an ordinal in [1,ω1). Definition 5.1 Let S = (S0,S1, . . .) be a countably infinite tuple of subsets Si ⊆ NN. (i) For every f ∈NN, write S ( f ) for the sequence (χS0( f ),χS1( f ), . . .)∈{0,1} N. (ii) We say that S is guessable based on S if there is a function G : {0,1}<N →{0,1} (called an S-guesser based on S ) such that ∀ f ∈ NN, lim n→∞ G(S ( f ) ↾ n) = χS( f ). Game theoretically, we envision a game where I (the sequence chooser) has zero information and II (the guesser) has possibly better-than-perfect information: II is allowed to ask (once per turn) whether I's sequence lies in various Si. For each Si, player I's act (by answering the question) of committing to play a sequence in Si or in Sci is similar to the act (described in [6], p. 366) of choosing a I-imposed subgame. Example 5.2 If S enumerates the sets of the form { f ∈ NN : f (i) = j}, i, j ∈ N then it is not hard to show that S is guessable (in the sense of Definition 1.1) if and only if S is guessable based on S . Definition 5.3 We say S is μ th-order guessable if there is some S = (S0,S1, . . .) as in Definition 5.1 such that the following hold. (i) S is guessable based on S . (ii) ∀i, Si ∈ ∆0μi+1 for some μi < μ . Theorem 5.4 S is μ th-order guessable if and only if S ∈ ∆0μ+1. In order to prove Theorem 5.4 we will assume the following result, which is a specialization and rephrasing of Exercise 22.17 of [5] (pp. 172–173, attributed to Kuratowski). Lemma 5.5 The following are equivalent. (i) S ∈ ∆0μ+1. (ii) There is a sequence (Ai)i∈N, each Ai ∈ ∆0μi+1 for some μi < μ , such that S = ⋃ n ⋂ m≥n Am = ⋂ n ⋃ m≥n Am. Proof of Theorem 5.4 10 S. Alexander (⇒) Let S = (S0,S1, . . .) and G witness that S is μ th-order guessable (so each Si ∈ ∆0μi+1 for some μi < μ). For all a ∈ {0,1} and X ⊆ N N, define Xa = { X , if a = 1; N N\X , if a = 0. For notational convenience, we will write "G(~a) = 1" as an abbreviation for "0 ≤ a0, . . . ,am−1 ≤ 1 and G(a0, . . . ,am−1) = 1," provided m is clear from context. Observe that for all f ∈ NN and m ∈ N, G(S ( f ) ↾ m) = 1 if and only if f ∈ ⋃ G(~a)=1 m−1 ⋂ j=0 S a j j . Now, given f : N→ N, f ∈ S if and only if G(S ( f ) ↾ n)→ 1, which is true if and only if ∃n∀m ≥ n, G(S ( f ) ↾ m) = 1. Thus f ∈ S iff ∃n∀m ≥ n, G(S ( f ) ↾ m) = 1 iff ∃n∀m ≥ n, f ∈ ⋃ G(~a)=1 m−1 ⋂ j=0 S a j j iff f ∈ ⋃ n ⋂ m≥n ⋃ G(~a)=1 m−1 ⋂ j=0 S a j j . So S = ⋃ n ⋂ m≥n ⋃ G(~a)=1 m−1 ⋂ j=0 S a j j . At the same time, since G(S ( f ) ↾ m)→ 0 whenever f 6∈ S, we see f ∈ S if and only if ∀n∃m ≥ n such that G(S ( f ) ↾ m) = 1. Thus by similar reasoning to the above, S = ⋂ n ⋃ m≥n ⋃ G(~a)=1 m−1 ⋂ j=0 S a j j . For each m, ⋃ G(~a)=1 ⋂m−1 j=0 S a j j is a finite union of finite intersections of sets in ∆ 0 μ ′+1 for various μ ′ < μ , thus ⋃ G(~a)=1 ⋂m−1 j=0 S a j j itself is in ∆ 0 μm+1 for some μm < μ . Letting Am = ⋃ G(~a)=1 ⋂m−1 j=0 S a j j , Lemma 5.5 says S ∈ ∆ 0 μ+1. (⇐) Assume S ∈ ∆0μ+1. By Lemma 5.5, there are (Ai)i∈N, each Ai ∈ ∆ 0 μi+1 for some μi < μ , such that S = ⋃ n ⋂ m≥n Am = ⋂ n ⋃ m≥n Am. (∗) I claim that S is guessable based on S = (A0,A1, . . .). Define G : {0,1}<N → {0,1} by G(a0, . . . ,am) = am, I will show that G is an S-guesser based on S . Suppose f ∈ S. By (∗), ∃n s.t. ∀m≥ n, f ∈ Am and thus χAm( f ) = 1. For all m ≥ n, G(S ( f ) ↾ (m+ 1)) = G(χA0( f ), . . . ,χAm( f )) = χAm( f ) = 1, so limn→∞ G(S ( f ) ↾ n) = 1. A similar argument shows that if f 6∈ S then limn→∞ G(S ( f ) ↾ n) = 0. Guessing and Mind-changing 11 Combining Theorems 1.2 and 5.4, we see that S is guessable if and only if S is 1storder guessable. It is also not difficult to give a direct proof of this equivalence, and having done so, Theorem 5.4 provides yet another proof of Theorem 1.2. Notes 1. A third independent usage of the term guessable, with similar but not the same meaning, appears in [8] (p. 1280), where a subset Y ⊆ NN is called guessable if there is a function g ∈ NN such that for each f ∈ Y , g(n) = f (n) for infinitely many n. 2. In general, there seems to be a correspondence between remainders on NN and remainders on N<N that take trees to trees; in the future we might publish more general work based on this observation. References [1] Alexander, S., "On Guessing Whether a Sequence has a Certain Property," Journal of Integer Sequences vol. 14 (2011), 12 pp. [2] Allouche, J., "Note on the constructible sets of a topological space," Annals of the New York Academy of Science vol. 806 (1996), pp. 1–10. [3] Dougherty, R., and C. Miller, "Definable Boolean combinations of open sets are Boolean combinations of open definable sets," Illinois Journal of Mathematics vol. 45 (2001), pp. 1347–1350. [4] Figueira, S., Hirschfeldt, D., Miller, J., Ng, K., and A. Nies, "Counting the changes of random ∆02 sets," to appear in Journal of Logic and Computation, published online 2013, doi: 10.1093/logcom/exs083. [5] Kechris, A., "Classical Descriptive Set Theory," Springer-Verlag, 1995. [6] Martin, D., "Borel determinacy," Annals of Mathematics vol. 102 (1975), pp. 363–371. [7] Nies, A., "Calibrating the complexity of ∆02 sets via their changes," preprint, arXiv: http://arxiv.org/abs/1302.0454. [8] Tsaban, B., and L. Zdomskyy, "Combinatorial Images of Sets of Reals and Semifilter Trichotomy," Journal of Symbolic Logic vol. 73 (2008), pp. 1278–1288. [9] Wadge, W., "Reducibility and Determinateness on the Baire Space," PhD dissertation, UC Berkeley (1983). Acknowledgments We acknowledge Tim Carlson, Chris Miller, Dasmen Teh, and Erik Walsberg for many helpful questions and suggestions. We are gratetful to a referee of an earlier manuscript for making us aware of William Wadge's dissertation. 12 S. Alexander Department of Mathematics The Ohio State University 231 West 18th Ave Columbus OH 43210 USA alexander@math.ohio-state.edu