Greg Restall is way more dedicated and wired than I am. He already has two posts about what’s happening at the Logic Colloquium, and I just made it up the hill in the midday sun. I am so glad I didn’t pack my computer. So thank you, Greg, for blogging from the Logic Colloquium, so I don’t have to. Greg’s slides for his course are up, so you can follow along even if you’re not here with us in Athens.

Games in logic are incredibly fashionable, and there’s lots of exciting work that I could write about. But I won’t. Instead, I’ll give you an exercise that can be solved with just the very basics of logic.

A finite game is a subset W ⊆ M₁, …, M_n, where each M_i is a finite set. M_i is the set of possible moves at step i, and W is the set of winning play for player A. You have two players, A and B. A begins by making a move m₁ ∈ M₁, then B moves by picking m₂ ∈ M₂, etc. The game ends after n moves (that’s why it’s finite). A wins if the sequence m₁, … m_n ∈ W, otherwise B wins (there are no draws).

This framework is pretty general. For instance, this is how tic-tac-toe fints the definition: each M_i = {1, …, 9}, where 1, …, 9 are the numbers assigned to the 9 squares on the tic-tac-toe board, say, like this:

1	2	3
4	5	6
7	8	9

Players A and B alternate in picking squares. The game ends after 9 moves (n = 9). W is the set of those sequences of 9 numbers in which (a) at the end, A has picked 3 squares in a row, column, or a diagonal, and (b) every move by A was legal, i.e., A didn’t pick a square that B had picked previously.

A winning strategy for A is a method by which A can force a win every time, i.e., a prescription which tells A what to pick for m₁, what to pick for m₃ (depending on what B picked for m₂), what to pick for m₅ (depending on what B picked for m₂ and m₄), etc., so that m₁, …, m_n ∈ W. Similarly, a winning strategy for B is a prescription which tells B what to pick for m₂ (depending on what A picked for m₁), what to pick for m₄ (depending on what A picked for m₁ and m₃), etc., so that m₁, …, m_n ∉ W. A game is determined if there’s either a winning strategy for player A or for player B.

Exercise: Show using only principles of ordinary predicate logic that every finite game is determined.