 Advanced Topics in Set Theory 2006/2007; 1st Semester Institute for Logic, Language & Computation Universiteit van Amsterdam
Instructor: Dr Benedikt Löwe
Vakcode: MolATST6
Time: Monday 18-20
Place: P.017
Course language: English
Teaching Assistant: Brian Semmes
Intended Audience: M.Sc. students of Logic and Mathematics
Prerequisites: This course assumes knowledge comparable to the course "Axiomatic Set Theory".

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 ω1. 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. AD2 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 ADP(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 ω1 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 ω1, we took the Martin measure on D and the function that maps x to ω1x, and formed the image filter of that map on ω1. 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 ω1. 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 ω1 is definable from a real; a second proof that ω1 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 ω2 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 ω2 is ω2-complete (p.388/389 in Kanamori).
• Eleventh Lecture (November 20th, 2006). Prewellorderings. The prewellordering property. PWO(Π11). 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 Π11, we used HW #21. Show that the relations
R(x,y) iff x in A and (if y in A, then the height Tx is less than or equal to the height of Ty), and
S(x,y) iff x in A and (if y in A, then the height Tx is less than the height of Ty)
are Π11 (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)22.
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).

Last update : December 1st, 2006