Matthew Harrison-Trainor, University of Illinois at Chicago
Back-and-forth games to characterize countable structures
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 α such that if B is any countable structure, A is isomorphic to B if and only if Copier can avoid losing for α steps of the back-and-forth game, that is, when A is involved we only need to play the back-and-forth game for α 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.
MC 5501