Advanced Topics in Set Theory 2006/2007; 1st Semester Institute for Logic, Language & Computation Universiteit van Amsterdam

In this course, we shall discuss connections between set theory and game theory. We investigate infinite perfect information games, their connection to the Axiom of Choice, the Mycielski-Steinhaus Axiom of Determinacy and its consequences for infinitary combinatorics.

Literature: Preprint version of Alessandro Andretta's book on Descriptive Set Theory. If you are interested in getting a copy, please contact Brian by e-mail before Friday, Sep 8.

Classes:

• First lecture (September 4th, 2006). Literature (Jech, Kechris, Kanamori, Andretta). History of game theory with a focus on the relationship with set theory. Determinacy of games. Two applications: choice games (game theoretic characterization of AC) and asymmetric games (game theoretic characterization of the perfect set property).
  No homework.
• Second lecture (September 11th, 2006). Another application: Solovay games (game theoretic characterization of the existence of a nontrivial ultrafilter on an uncountable set). Coding of relations as real numbers. A surjection from the reals onto ω₁. Trees. Games on a set X. Different notions of strategies.
  Homework:
  • HW#1. Read Andretta's section I.1A.
  • HW#2. Read and understand the proof of Andretta's Proposition 1.11.
  • HW#3. Consider the three definitions of a strategy in Andretta's book (p.104-106). Prove that they are "equivalent". Formulate carefully what this is supposed to mean, state a theorem, and then prove it. (4 points)
  Note: Only HW#3 is due to be handed in on September 18th.
• Third lecture (September 18th, 2006). Games with rules. Axioms of determinacy. AD₂ implies AD. AD implies fragments of choice. Topology of product spaces.
  Homework:
  • HW#4. Exercise 2.2 in Andretta's book. (5 points)
• Fourth lecture (September 25th, 2006). The tree representation theorem for closed sets. Tree representations for perfect sets. Cantor's theorem on the cardinality of perfect sets. Bernstein sets. PSP and uncountable wellordered sequences of reals. The inconsistency of AD_ω1.
  Homework:
  • HW#5. Prove that a function is continuous on Baire space if and only if it is the lifting of a monotone and continuous function on the set of finite sequences. Prove that a function is Lipschitz if and only if it is the lifting of a monotone and length-preserving function on the set of finite sequences. (4 points)
  • HW#6. Exercise 2.19 in Andretta's book. (3 points)
• Fifth Lecture (October 2nd, 2006). Inconsistency of AD_P(R). AD implies PSP. Ultrafilters. Completeness of ultrafilters. Existence of nonprincipal ultrafilters on ω and σ-complete ultrafilters. AD implies that all ultrafilters on ω are principal.
  Homework:
  • HW#7. Prove that AC implies the existence of a nondetermined set without using PSP. (Hint. Redo the proof of the existence of a Bernstein set, but diagonalize against strategies as opposed to perfect trees.) (3 points)
  • HW#8. In class we proved that in the 'ultrafilter game' (U is a nonprincipal ultrafilter on ω, players play disjoint finite sets of natural numbers, if I's set is in U then I wins), if player I has a winning strategy then player II has a winning strategy. Keep in mind that we already proved a lemma that said that if player II has a winning strategy, then player II has a strategy that can enforce that his move is in U. Prove that if player II has a winning strategy, then player I has one. (This completes the proof of the theorem "AD implies that no ultrafilter on ω is nonprincipal".) (3 points)
• Sixth Lecture (October 9th, 2006). Inaccessible cardinals. Measurable cardinals. The Martin measure on the Turing degrees. Martin's theorem ("AD implies that the Martin measure is an ultrafilter.") AD implies that ω₁ is measurable. Flip sets. AD implies that there is no flip set.
  Homework:
  • HW #9. Prove (in ZF) that if there is a κ-complete nonprincipal ultrafilter on κ, then κ is regular (3 points).
  • HW #10. Read Chapter 4 in Drake, Set Theory (p.107-125).
  • HW #11. In the proof of the measurability of ω₁, we took the Martin measure on D and the function that maps x to ω₁^x, and formed the image filter of that map on ω₁. Show that this image filter is nonprincipal (3 points).
  Note: Only HW#9 and #11 are to be handed in.
• Seventh Lecture (October 16th, 2006). Descriptive set theory. σ-algebras. Borel sets. Pointclasses. Analytic sets. Coanalytic sets. Universal sets. Pointclasses with universal sets can not be ambiguous.
  Homework:
  • HW #12. Read Section 12 in Kanamori's book.
  • HW #13. Read Section 3A in Andretta's book (p.26-31).
  • HW #14. Exercise 3.3 in Andretta's book (7 points).
  • HW #15. Exercise 4.10 in Andretta's book (6 points).
  Note: Only HW#14 and #15 are to be handed in.
• Eighth Lecture (October 30th, 2006). Tree representation of analytic sets. Tree representation of coanalytic sets. Coanalytic sets as codes of subsets of ω₁. The coanalytic set WO. The Boundedness Lemma. Application of the boundedness lemma: Player I cannot win in Solovay games.
  Homework:
  • HW #16. Exercise 4.23 in Andretta's book (4 points).
  • HW #17. Try to formulate and prove an abstract form of the boundedness lemma. More precisely, let Γ be a pointclass, X be a Γ-complete set, and φ a function assigning ordinals to elements of X. An abstract version of the boundedness lemma would say: "For every subset A of X that is in the dual of Γ there is some α such that the φ-image of A is bounded by α." Find conditions on Γ, X, and α such that you can prove such a theorem and prove it under these assumptions (5 points).
• Ninth Lecture (November 6th, 2006; Brian Semmes). Solovay's Lemma: AD implies that every subset of ω₁ is definable from a real; a second proof that ω₁ is measurable (the original proof).
  Homework:
  • HW #18. Exercise 8.24 (i) in Andretta's book (3 points).
  • HW #19. Exercise 8.70 in Andretta's book (5 points).
• Tenth Lecture (November 13th, 2006). AD implies that ω₂ is measurable. Θ. Moschovakis Coding Lemma. AD implies that Θ is a limit cardinal.
  
  • HW #20. If you know forcing, read the proof that the pullback filter of the Martin measure onto ω₂ is ω₂-complete (p.388/389 in Kanamori).
• Eleventh Lecture (November 20th, 2006). Prewellorderings. The prewellordering property. PWO(Π¹₁). Propagation of the prewellordering property from Γ to the existential closure. The periodicity phenomenon. The First Periodicity Theorem (without proof).
  Homework:
  • HW #21. Exercise 29.6 in Kanamori's book (3 points).
  • HW #22. In the proof of the prewellordering property of the class Π¹₁, we used HW #21. Show that the relations R(x,y) iff x in A and (if y in A, then the height T_x is less than or equal to the height of T_y), and
    S(x,y) iff x in A and (if y in A, then the height T_x is less than the height of T_y) are Π¹₁ (2 points).
  • HW #23. Read Martin's proof of the First Periodicity Theorem (p.411/412 in Kanamori's book).
• Twelfth Lecture (November 27th, 2006). Proof of the First Periodicity Theorem. Scales. The scale property. The Second Periodicity Theorem (without proof). Erdős arrow notation. 6→(3)²₂.
  Homework:
  • HW #24. Fix an ordinal α and define Φ as the set of functions from Baire space into α. For two such functions φ and ψ, we define the game G_φψ as follows: Player I plays x, player II plays y, and player II wins if φ(x) ≤ ψ(y). We define a relation φ ≤ ψ if and only if player II has a winning strategy in the game G_φψ. As usual, define φ ≈ ψ as &phi ≤ ψ and ψ ≤ φ. Prove that 〈Φ/≈,≤〉 is a wellorder (4 points).
  • HW #25. Read the introductory section on scales in Kanamori's book (Chapter 30 up to "Projective Ordinals").
  • HW #26. Exercise 30.11 in Kanamori's book (4 points).
• Thirteenth Lecture (December 4th, 2006).