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. AD_{2} 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 ω_{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 ω_{1}^{x},
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(Π^{1}_{1}). 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 Π^{1}_{1}, 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 Π^{1}_{1} (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)^{2}_{2}.
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