Unless otherwise indicated, all meetings take place on Tuesdays at 4:30PM at 380-381T
The seminar is led by Professor Thomas Icard
Autumn
The seminar will cover material from the book Models and Games by Jouko Väänänen (Cambridge Studies in Advanced Mathematics 132, Cambridge University Press, 2001).
The focus will be on game-theoretic methods in model theory. A central concern of the seminar is to investigate the interplay between the key logical notions of truth, consistency and equivalence as represented by three special games: the Semantic Game, the Model Existence Game, and Ehrenfeucht-Fraïssé games. We will pay special attention to the proof techniques arising from this game-theoretic approach to model theory.
We will begin by introducing the basic framework and results about general two-player games of perfect information (Gale-Stewart theorem, determinacy), after which we will review classical results in the model theory of first-order logic from the point of view of games (Löwenheim-Skolem theorems, compactness, omitting types theorem). We will then study dynamic Ehrenfeucht-Fraïssé games for infinitary logics and some of their applications to the model theory of infinitary logics. If time permits, we will discuss logics with generalised quantifiers, as studied through the prism of games.
- Oct 4: Francesca Zaffora Blando (Stanford), Two-Player Games and Determinacy
Abstract (+/-):I will begin by introducing the basic framework of two-player zero-sum games of perfect information: in particular, I will define the concept of deteminacy, illustrate it with a few examples, and present Zermelo’s Theorem. I will then discuss infinite games, prove the Gale-Stewart Theorem, and explain in what way Zermelo’s Theorem follows from Gale-Stewart as a special case. I will then briefly discuss the Axiom of Determinacy, and show that it contradicts the Axiom of Choice.
- Oct 11: Alan Aw (Stanford), Ehrenfeucht Games from Scratch
Materials: handout
Abstract (+/-):We will learn about Ehrenfeucht-Fraïssé games with as few logical prerequisites as possible, following the exposition in Väänänen (Chapter 4 and bits of Chapter 5).
- Oct 18: Johan van Benthem (Stanford/UvA), Logic and Games: Some Current Issues
Abstract (+/-):I will talk about some issues in connecting logic and games that I am pursuing in Amsterdam. My main topic is the design of logics for game structure based on modal neighborhood semantics, and some difficulties that we have found with the notion of game equivalence that we would like to impose. If time permits, I'd also like to raise some issues about the general structure of logic games (such as Ehrenfeucht-Fraïssé games), and some open problems surrounding these.
- Oct 25: Declan Thomas (Stanford), Cub Games and the Löwenheim-Skolem Theoem
Abstract (+/-):The Löwenheim-Skolem Theoem holds that if a first order sentence φ is true in a structure M then it is true in a countable substructure of M. In this talk, I will introduce Cub Games, a type of infinite two player game, and show how they can be used to prove the Löwenheim-Skolem Theoem. I will conclude with some interesting features of Cub Games and Cub Sets.
- Nov 1: No seminar this week.
- Nov 8: Chris Mierzewski (Stanford), Model Existence Games and the Omitting Types Theorem
Abstract (+/-):Given a set T of first-order sentences, the Model Existence game MEG(T) characterises checking the consistency of T as a game between two players. I will explain how the Model Existence game provides a method for constructing a Hintikka extension of T, which allows to prove that the consistency of T is equivalent to the existence of a winning strategy for the second player in MEG(T).
I will then use the Model Existence game to prove the Omitting Types theorem. I will contrast this game-theoretic proof of the Omitting Types theorem with the standard proof, and illustrate the usefulness of omitting-types constructions with some examples.
Lastly, I will discuss connections between Model Existence games, omitting types and model-theoretic forcing.
- Nov 15: TBD (TBD), TBD
- Nov 22: TBD (TBD), TBD
- Nov 29: Thanksgiving Break
- Dec 6: TBD (TBD), TBD
Winter
This quarter's topic is algorithmic randomness. We begin with a brief historical introduction to randomness and a review of basic results in computability theory. Then we will cover selections from either Nies' Computability and Randomness (Oxford University Press, 2009) or Downey and Hirschfeldt's Algorithmic Randomness and Complexity (Springer, 2010).
- Jan 17: Francesca Zaffora Blando (Stanford), Introduction to Algorithmic Randomness
- Jan 24: Harvey Friedman (Ohio State), Adventures in Incompleteness
Abstract (+/-):After giving a general discussion and overview of Gödel Incompleteness, we turn to the latest ongoing development: Emulation Theory.
- Jan 31: J.T. Chipman (Stanford), Some Basic Results in Computability Theory
Abstract (+/-):TBD
- Feb 7: TBD (TBD), TBD
- Feb 14: TBD (TBD), TBD
- Feb 21: TBD (TBD), TBD
- Feb 28: TBD (TBD), TBD
- Mar 7: TBD (TBD), TBD
- Mar 14: TBD (TBD), TBD
Last modified