The seminar studies this semester the general topic
of "games in logic". Sample topics:
Ehrenfeucht-Fraisse games
- finite (for elem. equivalence) and infinite (for isomorphism)
in Chpt.3 of W.Hodges: Shorter model theory (it is in the library
or on the web)
- pebbling version (for the k-variable logic and finite model theory)
in M.Otto's lecture notes (Sec.2.1)
model-theoretic forcing
- the set-up via games
in Hodges, Building models by games (Chpt.2)
or more generally in T.Zhang's notes
related to the Completeness thm
- Hintikka's games or M.Hyland's text on game semantics
related to Herbrand's thm
- witnessing of E-, EU-, EUEU-, ... formulas and the Student-Teacher game
in Sec.1 of
my paper with Pudlak and Takeuti
or in Sec.7.4 in my
book, or in Secs.2 and 3. in my paper with Pudlak
and Sgall or a more general exposition
(Secs.1.1 and 1.2)
Conway's construction of the surreal numbers
- in his book "On numbers and games",
a review for info
on determinacy of games
- determinacy of finite games, the Gale-Stewart thm
and the non-determinacy of infinite games via the Axioms of Choice
- Axiom of determinacy
in A.E.Caicedo's slides (offers other literature)
in proof complexity
- DPLL like games and the Prover - Delayer game for resolution
in a paper by Galesi and Thapen
in complexity theory
- the Karchmer-Wigderson game, the size of propositional
formulas and communication complexity
in Ran Raz's lecture notes