Instructor: Dr Benedikt Löwe
Time: Monday 18-20
Course language: English
Teaching Assistant: Brian
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.
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.
- 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).
- 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.
Note: Only HW#3 is due to be handed in on September 18th.
- 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)
- Third lecture (September 18th, 2006).
Games with rules. Axioms of determinacy. AD2 implies
AD. AD implies fragments of choice. Topology of product
- 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.
- 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 implies PSP. Ultrafilters. Completeness of
ultrafilters. Existence of nonprincipal ultrafilters on
ω and σ-complete ultrafilters. AD implies that all
ultrafilters on ω are principal.
- 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.
Note: Only HW#9 and #11 are to be handed in.
- HW #9. Prove (in ZF) that if there is a
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).
- 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
Note: Only HW#14 and #15 are to be handed in.
- 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).
- 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.
- 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).
- 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
- 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
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
S(x,y) iff x in A and (if y in A, then
the height Tx is less than the height of
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.
- 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
- Thirteenth Lecture (December 4th, 2006).
Last update : December 1st, 2006