6.5 Axiom of determinacy

In this book our focus is mostly on low level definable sets of reals such as those that are or . To go “higher up”, one resorts to the use of games and strategies which lie at the heart of the Axiom of Determinacy. It turns out that this axiom is at its core a large cardinal axiom.

6.5.1 Games and strategies

Let A ⊆ ωω. An infinite game GA with perfect information has two players labeled I and II. The game is played by choosing a natural number alternately between the two players and ends in ω-many steps. Each game generates a real x = (n0, m0,…, ni, mi,…) ∈ ωω where ni and mi are the numbers played by I and II respectively at step i. If x ∈ A, then I wins the game. Otherwise, II wins.

Definition 6.5.1. Given a set A ⊆ ωω, I has a winning strategy : ω<ω → ω for the game GA if for every g ∈ ωω, the real ∗ g = (n0, g(0),…, ni, g(ni),… ) ∈ A where n0 = () and ni = ((n0, g(0),…, ni−1, g(i − 1))) for i > 0. The string (n0, g(0),…, ni) is called a play at step i by I following . II has a winning strategy : ω<ω → ω for the game GA if for every f ∈ ωω, the real f ∗ = (f(0), m0,…, f(i), mi,… ) ∉ A where m0 = (f(0)) and mi = ((f(0), m0,, … , f(i))) for i > 0. The string (f(0), m0,…, mi) is called a play by II at step i following . GA is determined if either of the two players has a winning strategy.

Definition 6.5.2. The Axiom of Determinacy (AD) states that for any A ⊆ ωω, either I or II has a winning strategy for GA.

It is not difficult to see that AC contradicts AD. However, GA is determined whenever A is simply defined.

Proposition 6.5.3. If A is a closed set, then GA is determined.

Proof. Since A is closed, there is a tree T ⊆ ω<ω such that A = [T]. Suppose that II has no winning strategy. We define a I-winning strategy as follows:

Let () be an n0 such that II has no winning strategy on G[T(n0)] where T(n0) = {τ ∈ T | n0 ⪯ τ}, where n0 is the string of length 1 whose value at 0 is n0. Note that n0 exists by the assumption that II has no winning strategy.

By induction assume that is defined for sequences of length up to i − 1, and II has no winning strategy on G[T(n0,m0,…,ni−1)] where

T(n0,m0,…,ni−1) = {τ ∈ T |(n0, m0,…, ni−1) ⪯ τ},

for the sequence (n0, m0,…, mi) played by I following . Then there is an ni such that II has no winning strategy on G[T(n0,m0,…,mi,ni)] where

T(n0,m0,…,mi,ni) = {τ ∈ T |(n0, m0,…, mi−1, ni) ⪯ τ}.

Let

((n0, m0,…, mi−1)) = ni.

Then for any g ∈ ωω and number k, ∗ g ↾ k ∈ T. Hence ∗ g ∈ A since A is closed.

It is not always true that if GA is determined, then so is GωωA (see Exercise 6.5.1). However, the next proposition implies that this complementation property holds when A is closed.

Proposition 6.5.4. Suppose that Γ ⊆ (ωω) so that for any A ∈ Γ and string σ ∈ ω<ω, the set Aσ = {x | σ⌢x ∈ A} ∈ Γ. If GA is determined for every A ∈ Γ, then so is GωωA for every A ∈ Γ.

Proof. Suppose that A ∈ Γ. Note that for any n, An = {x | n⌢x ∈ A} ∈ Γ and so GAn is determined.

Case (1) There exists an n0 such that player II has a winning strategy for GAn0. Let (0) = n0. For any string (n0, m0,…, mi), let ((n0, m0,…, mi)) be (m0,…, mi). Then is a winning strategy for player I for GωωA.

Case (2) Otherwise. Then for every n, player I has a winning strategy n for GAn . Define so that for each n, (n) = n() and for any string (n0, m0,…, ni), (n0, m0 …, ni) = n0((m0,…, ni)). Then is a winning strategy for II for the game GωωA.

The optimal result on determinacy provable in ZF is due to Martin. Optimality here means that any stronger version is essentially a large cardinal axiom. Let DC denote the Axiom of Dependent Choice:

Theorem 6.5.5. (Martin [93]). ZF + DC ⊢ “Every Borel set is determined”.

Theorem 6.5.6. (Martin [92] and Harrington [45]). -determinacy is equivalent to the existence of 0♯.

The status concerning AD is more complex. A detailed discussion would involve the notion of a Woodin cardinal which we will not define. Nonetheless, Woodin, Martin and Steel have shown that ZF + AD is equiconsistent with ZFC+ “There exist infinitely many Woodin cardinals”. Woodin also showed the following:

Theorem 6.5.7. (Woodin). The following are equivalent:

(i)ZF + DC + -Determinacy is consistent;

(ii)ZF + DC + Analytical Determinacy is consistent;

(iii)ZFC + “There exists a Woodin cardinal” is consistent.

Woodin as well as Martin and Steel [95] have also provided a level-by-level analysis of determinacy in the projective hierarchy (known as Projective Determinacy).

6.5.2 Exercise

Exercise 6.5.1. Assume ZFC. Prove that there is a set A such that GA is determined but GωωA is not.

6.6 Recursion-theoretic aspects of determinacy

The investigation of determinacy from the perspective of recursion theory was initiated by Martin. A natural starting point is to analyze the complexity of winning strategies.

6.6.1 Basis theorems for winning strategies

If A is , then both the sets { |(∀g)( ∗ g ∈ A)} and { | (∀f)(f ∗ ∉ A)} are . By Corollary 4.2.7, there is a -winning strategy for either I or II. However, even for -sets, it is not possible to improve the upper bound significantly.

Theorem 6.6.1. (Blass [7]). Suppose that A is Π01. If I has a winning strategy for GA, then I has a winning strategy recursive in ; if II has a winning strategy for GA, the II has a hyperarithmetic winning strategy.

Proof. Since A is , there is a recursive tree T ⊆ ω<ω such that A = [T]. Suppose that I has a winning strategy. Then the set

B = { |(∀i)(∀σ ∈ ωi)((σ is a play at step i by I following )→(∃x)(x ≻ σ ∧ x ∈ A))}

is a nonempty -set. By Gandy’s Basis Theorem (2.5.3), there is a 0 ≤T in B. Obviously 0 is a winning strategy for player I.

Now suppose that I has no winning strategy. Let n ∈ ∗ . Then = {m | m ≤o* n} is an r.e. set with an initial segment of order type under the r.e. linear ordering relation <o*. Define an arithmetical set C of functions from ω<ω into as follows: f ∈ C if and only if for any σ,

(i) if [σ] ⊆ [T], then f(σ) is undefined;

(ii) if [σ] ∩ [T] = , then f(σ) = 1;

(iii) suppose σ satisfies neither (i) nor (ii). (a) If |σ| is even, then f(σ) = 2i if i = sup{k | k = f(σ⌢j)} exists where sup is in the sense of <o*; otherwise, f(σ) is undefined. (b) If |σ| is odd, then f(σ) = 2i if i = inf{k | k = f(σ⌢m)} exists where inf is in the sense of <o*; otherwise, f(σ) is undefined.

Since ∩ is the largest well-ordered segment of , for any f ∈ C and σ, if f(σ) is defined then f(σ) ∈ .

Claim 1. Suppose σ satisfies (iiia). If for any m, there is a hyperarithmetic partial function fm ∈ C such that fm(σ⌢m) is defined, then there is a hyperarithmetic partial function f ∈ C such that f(σ) is defined.

Proof of Claim 1. Define a -relation R ⊆ ω ×(ω × ) as follows: (m, (e, i)) ∈ R if and only if i ∈ and ∈ C so that (σ⌢m) is defined. By Theorem 4.2.1, there is a -function g : ω → ω × uniformizing R. By the assumption, g is total and hence hyperarithmetic.

Define f to be a hyperarithmetic function such that for any m and τ ⪰ σ⌢m, f(τ) = (τ) where g(m) = (m0, m1). Obviously f ∈ C. Moreover, since f is hyperarithmetic, sup{k | k = f(σ⌢m)} exists and so f(σ) is defined.

Claim 2. There exists a hyperarithmetic g ∈ C such that g() is defined.

Proof of Claim 2. Suppose not. We obtain a winning strategy for I playing GA as follows:

By Claim 1, there is an m such that no hyperarithmetic function f ∈ C exists for which f(m) is defined. Let () = m. Note that by (iiib), for any hyperarithmetic f ∈ C and number j, f(m⌢j) is undefined.

By induction on k, for any play (i0, j0,…, ik) at step k by I following , there is no hyperarithmetic f ∈ C such that f((i0, j0, …, ik)) is defined. Then for any jk and any hyperarithmetic f ∈ C, f((i0, j0,…, ik, jk)) is undefined. By Claim 1, there is a ik+1 for which there is no hyperarithmetic function fik+1 ∈ C so that fik+1((i0, j0,…, ik, jk, ik+1)) is defined. Let ((i0, j0,…, ik, jk) = ik+1. Then is a winning strategy for I, contradicting the assumption.

Thus there is a hyperarithmetic function g ∈ C such that g() ∈ . We define a hyperarithmetic strategy g for II as follows: For each n, let g(n) = m where g(m)<o* g(). For each k and σ ∈ ω<ω with even length, let g(σ⌢k) = m where g(σ⌢k⌢m)<o* g(σ) (if it exists).

We claim that g is II’s winning strategy. To see this, for any h ∈ ωω, g(h ∗ g ↾ 2k + 2)<o∗ g(h ∗ g ↾2k) for any k with g(h ∗ g ↾2k) ≠ 1. Since g() ∈ , there is a k such that g(h ∗ g ↾2k) = 1. Thus h ∗ g ∈ ωω A.

A general basis theorem for the analytical hierarchy is the following Third Periodicity Theorem due to Moschovakis.

Theorem 6.6.2. (Moschovakis [107]).

(i)Suppose that every -set is determined. If I has a winning strategy for GA where A is , then I has a -winning strategy.

(ii)Suppose that every -set is determined. If I has a winning strategy for GA where A is , then I has a -winning strategy.

6.6.2 Cones of Turing degrees

A set A of Turing degrees is a cone if there exists a z such that A = {x | x ≥ z}. We say that z is the base of A.

Proposition 6.6.3. Assume ZF + AD. For any set A of Turing degrees, either A or its complement contains a cone of Turing degrees.

Proof. Let A = {x | deg(x) ∈ A}. Suppose that I has a winning strategy for GA. Then for any g ≥T , ∗ g ≡T g. Thus g ∈ A. Hence A contains a cone of Turing degrees.

If II has a winning strategy for GA, then by the same argument, the complement of A contains a cone of Turing degrees.

Although the proof of Proposition 6.6.3 looks straightforward, it reveals the remarkable fact that the global structure of the Turing degrees may be sensitive to set-theoretic assumptions.

Definition 6.6.4.

–A ⊆ ωω is cofinal if for every x there is a y ∈ A such that y ≥T x.

–A tree T ⊆ ω<ω is pointed if T is perfect and for any x ∈[T], x ≥T T.

–A pointed tree T is uniformly pointed if there exists an e such that for any x ∈[T], T = .

Proposition 6.6.5. (Martin [91]). ZF + DC + AD implies that every cofinal set of reals has a uniformly pointed subtree.

Proof. Suppose that A ⊆ ωω is cofinal. Let B ⊆ ωω be such that z = x ⊕ y ∈ B if and only if either

–x ≰T y; or

–x ≤T y and y ∉ A.

By AD, GB is determined. Suppose that I has a winning strategy . Let y ∈ A so that y ≥T. Then ∗ y = y ⊕ x for some x ≤T y. Hence ∗ y ∉ B.

Thus II has a winning strategy . Let T0 ⊆ 2<ω be a uniformly pointed tree such that T0 ≡T (see Exercise 6.6.1). Let T1 be defined such that (n0,…, ni) ∈ T1 if and only if there exists a finite string (m0,…, mi) ∈ T0 such that (m0, n0,…, mi, ni) is a play by II at step i following . Clearly T1 ≤T . Since is II’s winning strategy, for any y ∈ [T1], there is an x ∈ [T0] such that y = x ∗ and ≤T x ≤T y. Moreover T1 is a perfect tree: Every τ = (n0,…, ni) ∈ T1 that is the image of a σ = (m0,…, mi) ∈ T0(i.e. a play by II of (m0, n0,…, mi, ni) at step i following ) has a pair of (immediate) incompatible extensions τ1 and τ2 in T1 so that there exist x1, x2 ≻ σ with x1 ∗ ≻ τ1 and x2 ∗ ≻ τ2, since otherwise there is a unique y such that for any x ≻ σ in [T0], x ≤T x ∗ = y and this would imply that there are uncountably many reals recursive in y, which is a contradiction. We conclude that T1 is a pointed subtree of A.

We follow the idea in [58] to construct a subtree T2 of T1 so that T2 is uniformly pointed. Define a sequence of trees T1 = ⊇ ⊇ … which are recursive in T1 as follows:

Stage e:

Case (1) There is an n such that ≠ T1(n) for some σ ∈ . Let = {τ | τ ∈ ∧ (τ ⪰ σ ∨ τ ⪯ σ)} and proceed to the next stage.

Case (2) Otherwise.

Subcase (i) (∀n)(∀σ ∈ )(∃τ ≻ σ)(τ ∈ ∧ (n)[|τ|] ↓). Then it is not difficult to define a T1-recursive perfect tree ⊆ such that for every x ∈ [], we have = T1. In this case, terminate the construction since ≤T T1 and is a uniformly pointed tree.

Subcase (ii) Otherwise. Then there exist n0 and σ0 ∈ such that for every τ ⪰ σ0 in , (n)[|τ|] ↑. Let = {τ | τ ∈ ∧ (τ ⪰ σ0 ∨ τ ⪯ σ)}. Proceed to the next stage.

If the construction does not terminate at any stage e, then there is a real x ∈ e[]. By the definition of the sequence {}, we have ≠ T1, which contradicts the fact that T1 is a pointed tree. Thus the construction must terminate at some stage e where Subcase (i) holds. Let T2 = .

6.6.3 Exercise

Exercise 6.6.1. Prove that for any real z, there is a uniformly pointed tree T ⊆ 2<ω such that T ≡T z.

6.6.4 Turing determinacy

Definition 6.6.6.

–Turing determinacy (TD) states that any set of Turing degrees either contains or is disjoint from a cone.

–If Γ is a class of sets of Turing degrees, then Γ-Turing determinacy states that every set in Γ either contains or is disjoint from a cone.

Turing determinacy plays a significant role in descriptive set theory, as shown by the following theorems which are stated without proof:

Theorem 6.6.7. (Harrington [45]). ZFC + -determinacy is consistent if and only if ZFC + -Turing determinacy is consistent.

Theorem 6.6.8. (Woodin).

(i)For any n ≥ 2, ZFC + -determinacy is consistent if and only if ZFC + -Turing determinacy is consistent.

(ii)ZF + DC + AD is consistent if and only if ZF + DC + TD is consistent.

6.6.5 Martin’s conjecture

A function F : 2ω → 2ω is degree invariant on a cone (of reals) C = {x | x ≥T z} for some z if any x, y ≥T z in C of the same Turing degree satisfy F(x)≡T F(y). F is increasing on a cone C if F(x)≥T x for x ∈ C. If F and G are degree invariant on a cone, write F ≤M G if F(x)≤T G(x) for all x ∈ C. Martin made the following conjecture.

Conjecture 6.6.9. Assume ZF + AD + DC.

1.Every degree invariant function that is not increasing on a cone is a constant on a cone;

2.≤M prewellorders the degree invariant functions which are increasing on a cone. Furthermore, if the ≤M-rank of F is α, then F′ has ≤M-rank α + 1, where F′(x) = (F(x))′, the Turing jump of F(x).

Martin’s conjecture is one of the deepest conjectures in recursion theory. Essentially it says that the only “natural unsolvable problem” is the halting problem. We will take up this topic in detail in Chapter 7.

6.6.6 Exercises

Exercise 6.6.2 (Blass [7]). Prove that for any hyperarithmetic real x, there is a -set A such that II has a winning strategy for GA but has no winning strategy recursive in x.

Exercise 6.6.3. Suppose that A is a -set such that for any Turing degree x, x ∩ A ≠ . Then there is a pointed tree T so that [T] ⊆ A.

Exercise 6.6.4 (Blass [7]). Prove that there is a -set A such that I has a winning strategy but has no hyperarithmetic winning strategy for GA.

Exercise 6.6.5. Prove that there exists a Turing degree a such that

for any Turing degree b ≥ a, where (≤ a) = {c | c ≤ a}.

Exercise 6.6.6. Assume ZF + PD. Prove that there exists a Turing degree a such that 〈(≥ a), ≤〉 ≡ 〈(≥ b), ≤〉 for any Turing degree b ≥ a, where (≥ a) = {c | c ≥ a}.

Exercise 6.6.7 (Jockusch and Soare [59]). Prove that 〈, ≤〉 ≢ 〈, ≤〉 where is the set of Turing degrees of arithmetical sets.

Exercise 6.6.8. Assume ZFC. Prove that there is a sequence {fn}n<ω of functions such that fn+1 <M fn for all n.

Exercise 6.6.9 (Simpson [138]). Assume ZF + -determinacy. Prove that there is an x such that for any y ≥h x, the hyperdegree of y is a minimal cover.

*Exercise 6.6.10 (Harrington and Kechris [46]). Let P ⊆ 2ω be a -set that is cofinal with respect to the Turing degrees of hyperarithmetic sets, i.e. for any x ∈ HYP there is a y ∈ P such that y ≥T x. Prove then any x ≥T is Turing equivalent to a y ∈ P.