As a field of study, it’s the study of two-player games of perfect information (so think chess, not football or poker) in which each player may make countably many moves (you can also look at uncountable-length games but it’s not common). I’ll give you more detail than I would a child :P
Each player takes turns to move. You can encode the moves they make as coming from some set - for example they might just play numbers. The rules of the game are imposed by a winning set, which is a set of countable-length sequences of moves, and we say that player I wins if the infinite sequence of her first move followed by player II’s first move followed by her second move, etc, is in the winning set. Otherwise player II wins. (There are no draws, which technically means chess falls outside the scope of this setup, but it turns out not to be a big deal)
(This allows you to encode what moves are allowed by the rules - you just say that any sequence which contains a move where that player broke a rule is a loss for that player, regardless of what comes afterwards.)
Each winning set defines a different game. The property of determinacy is a property of sets of infinite sequences which says that there is a winning strategy for either player. A strategy is just a function which takes the finite sequence of moves up to that point in the game and tells the player (the player for whom the strategy is) what to do. A winning strategy is one which, if followed, always results in a win for that player.
If we modify the rules of noughts and crosses (tic-tac-toe) so that draws are arbitrarily decided to give a win to player I, we know that this (finite) game has a winning strategy. In fact, any finite game has a winning strategy (or, if there are draws, this means there is a non-losing strategy). The outline of the proof is that if player I does not have a strategy to get to one of the (finitely many) winning states, then we can find a strategy for player II which avoids those winning states. (Remember, winning states are winning for I).
So, which games are determined? Are all games determined? Well, it’s actually easy (through a diagonalisation argument, same as proving uncountability of the reals) that not all infinite (countable-length, that is) games played with natural numbers (as moves) are determined. But you can create a way of categorising the sets of countable sequences of natural numbers (i.e. the possible winning sets) by a kind of complexity. This is the basis of descriptive set theory. It starts with topology: you can define basic open sets in this space as those sets consist of all infinite sequences which share a common finite prefix. Closed sets are the complements of open sets, as usual. But then you can define a hierarchy of complexity where the next level are countable unions of closed sets, then the next level are countable unions of complements of countable unions of complements of open sets. (An introduction to descriptive set theory will say more about this).
It’s quite easy to prove that all open sets and all closed sets in this hierarchy of complexity are determined. It’s a little harder to prove that the second level is determined, and harder still to prove that the third level is. Eventually a guy named Tony Martin (D. A. Martin) proved that all Borel sets in this hierarchy are determined. If you know your analysis, the Borel sets are exactly what you’re thinking: they’re the sets formed by all arbitrary countable unions, intersections and complements of open sets.
The interesting thing about this proof was that it needed a huge amount of set theoretic “power”. Most ordinary mathematics like analysis doesn’t need all the axioms of set theory, but this needed a massive chunk of them. This makes it interesting to set theorists because it tells us something about the relationship between something quite concrete: complexity of sets and strategies for easily-defined games on the one hand, and something quite abstract: the axioms of set theory. This pattern continues higher up: more determinacy can be proved if you assume even stronger axioms, going beyond what is typically included in set theory.
Thank you, that was very interesting. I was surprised at the definition of the basic open sets because they felt quite closed to my intuition, so the topology feels discrete to me. It’s definitely Hausdorff, I guess, but that’s no big deal. I’m guessing if you’re saying it uses a lot of the axioms, it uses the axiom of choice. It feels like that kind of arena, but I’m no set theorist. Having been taught by ring theorists, I always found the axiom of choice no big deal and totally uncontroversial, but I’m aware of the existence of mathematicians who feel otherwise, intuitionists (confusing name) and constructivists and the like. Do set theorists have a lot of debate about axioms, is it largely led by consensus, or deeply controversial, or just a case of making clear which you’re using and no one gets excited about it?
As a field of study, it’s the study of two-player games of perfect information (so think chess, not football or poker) in which each player may make countably many moves (you can also look at uncountable-length games but it’s not common). I’ll give you more detail than I would a child :P
Each player takes turns to move. You can encode the moves they make as coming from some set - for example they might just play numbers. The rules of the game are imposed by a winning set, which is a set of countable-length sequences of moves, and we say that player I wins if the infinite sequence of her first move followed by player II’s first move followed by her second move, etc, is in the winning set. Otherwise player II wins. (There are no draws, which technically means chess falls outside the scope of this setup, but it turns out not to be a big deal)
(This allows you to encode what moves are allowed by the rules - you just say that any sequence which contains a move where that player broke a rule is a loss for that player, regardless of what comes afterwards.)
Each winning set defines a different game. The property of determinacy is a property of sets of infinite sequences which says that there is a winning strategy for either player. A strategy is just a function which takes the finite sequence of moves up to that point in the game and tells the player (the player for whom the strategy is) what to do. A winning strategy is one which, if followed, always results in a win for that player.
If we modify the rules of noughts and crosses (tic-tac-toe) so that draws are arbitrarily decided to give a win to player I, we know that this (finite) game has a winning strategy. In fact, any finite game has a winning strategy (or, if there are draws, this means there is a non-losing strategy). The outline of the proof is that if player I does not have a strategy to get to one of the (finitely many) winning states, then we can find a strategy for player II which avoids those winning states. (Remember, winning states are winning for I).
So, which games are determined? Are all games determined? Well, it’s actually easy (through a diagonalisation argument, same as proving uncountability of the reals) that not all infinite (countable-length, that is) games played with natural numbers (as moves) are determined. But you can create a way of categorising the sets of countable sequences of natural numbers (i.e. the possible winning sets) by a kind of complexity. This is the basis of descriptive set theory. It starts with topology: you can define basic open sets in this space as those sets consist of all infinite sequences which share a common finite prefix. Closed sets are the complements of open sets, as usual. But then you can define a hierarchy of complexity where the next level are countable unions of closed sets, then the next level are countable unions of complements of countable unions of complements of open sets. (An introduction to descriptive set theory will say more about this).
It’s quite easy to prove that all open sets and all closed sets in this hierarchy of complexity are determined. It’s a little harder to prove that the second level is determined, and harder still to prove that the third level is. Eventually a guy named Tony Martin (D. A. Martin) proved that all Borel sets in this hierarchy are determined. If you know your analysis, the Borel sets are exactly what you’re thinking: they’re the sets formed by all arbitrary countable unions, intersections and complements of open sets.
The interesting thing about this proof was that it needed a huge amount of set theoretic “power”. Most ordinary mathematics like analysis doesn’t need all the axioms of set theory, but this needed a massive chunk of them. This makes it interesting to set theorists because it tells us something about the relationship between something quite concrete: complexity of sets and strategies for easily-defined games on the one hand, and something quite abstract: the axioms of set theory. This pattern continues higher up: more determinacy can be proved if you assume even stronger axioms, going beyond what is typically included in set theory.
Thank you, that was very interesting. I was surprised at the definition of the basic open sets because they felt quite closed to my intuition, so the topology feels discrete to me. It’s definitely Hausdorff, I guess, but that’s no big deal. I’m guessing if you’re saying it uses a lot of the axioms, it uses the axiom of choice. It feels like that kind of arena, but I’m no set theorist. Having been taught by ring theorists, I always found the axiom of choice no big deal and totally uncontroversial, but I’m aware of the existence of mathematicians who feel otherwise, intuitionists (confusing name) and constructivists and the like. Do set theorists have a lot of debate about axioms, is it largely led by consensus, or deeply controversial, or just a case of making clear which you’re using and no one gets excited about it?