Date/Time
Date(s) - 04/10/2024
3:30 pm - 4:20 pm

Location: HH – 305

Title:  Back-and-forth games to characterize countable structures

Speaker: Matthew Harrison-Trainor

Abstract:
Given two countable structures $A$ and $B$ of the same type, such as graphs, linear orders, or groups, two players Spoiler and Copier can play a back-and-forth games as follows. Spoiler begins by playing a tuple from $A$, to which Copier responds by playing a tuple of the same size from $B$. Spoiler then plays a tuple from $B$ (adding it to the tuple from $B$ already played by Copier), and Copier responds by playing a tuple from $B$ (adding it to the tuple already played by Spoiler). They continue in this way, alternating between the two structures. Copier loses if at any point the tuples from $A$ and $B$ look different, e.g., if $A$ and $B$ are linear orders then the two tuples must be ordered in the same way. If Copier can keep copying forever, they win. $A$ and $B$ are isomorphic if and only if Copier has a winning strategy for this game.
Even if Copier does not have a winning strategy, they may be able to avoid losing for some (ordinal) amount of time. This gives a measure of similarity between $A$ and $B$. A classical theorem of Scott says that for every structure $A$, there is an $\alpha$ such that if $B$ is any countable structure, $A$ is isomorphic to $B$ if and only if Copier can avoid losing for $\alpha$ steps of the back-and-forth game, that is, when $A$ is involved we only need to play the back-and-forth game for $\alpha$ many steps rather than the full infinite game. This gives a measure of complexity for $A$, called the Scott rank. I will introduce these ideas and talk about some recent results.

Coffee will be served in the same room – HH 305 at 3pm – all are welcome.