Borel determinacy theorem
In
The theorem is a far reaching generalization of Zermelo's theorem about the determinacy of finite games. It was proved by Donald A. Martin in 1975, and is applied in descriptive set theory to show that Borel sets in Polish spaces have regularity properties such as the perfect set property.
The theorem is also known for its
Background
Gale–Stewart games
A Gale–Stewart game is a two-player game of perfect information. The game is defined using a set A, and is denoted GA. The two players alternate turns, and each player is aware of all moves before making the next one. On each turn, each player chooses a single element of A to play. The same element may be chosen more than once without restriction. The game can be visualized through the following diagram, in which the moves are made from left to right, with the moves of player I above and the moves of player II below.
The play continues without end, so that a single play of the game determines an infinite sequence of elements of A. The set of all such sequences is denoted Aω. The players are aware, from the beginning of the game, of a fixed payoff set (a.k.a. winning set) that will determine who wins. The payoff set is a subset of Aω. If the infinite sequence created by a play of the game is in the payoff set, then player I wins. Otherwise, player II wins; there are no ties.
This definition initially does not seem to include traditional perfect information games such as chess, since the set of moves available in such games changes every turn. However, this sort of case can be handled by declaring that a player who makes an illegal move loses immediately, so that the Gale–Stewart notion of a game does in fact generalize the concept of a game defined by a game tree.
Winning strategies
A winning strategy for a player is a function that tells the player what move to make from any position in the game, such that if the player follows the function they will surely win. More specifically, a winning strategy for player I is a function f that takes as input sequences of elements of A of even length and returns an element of A, such that player I will win every play of the form
A winning strategy for player II is a function g that takes odd-length sequences of elements of A and returns elements of A, such that player II will win every play of the form
At most one player can have a winning strategy; if both players had winning strategies, and played the strategies against each other, only one of the two strategies could win that play of the game. If one of the players has a winning strategy for a particular payoff set, that payoff set is said to be determined.
Topology
For a given set A, whether a subset of Aω will be determined depends to some extent on its topological structure. For the purposes of Gale–Stewart games, the set A is endowed with the
The set Aω can be viewed as the set of paths through a certain
The
Previous results
Gale and Stewart (1953) proved that if the payoff set is an open or closed subset of Aω then the Gale–Stewart game with that payoff set is always determined. Over the next twenty years, this was extended to slightly higher levels of the Borel hierarchy through ever more complicated proofs. This led to the question of whether the game must be determined whenever the payoff set is a Borel subset of Aω. It was known that, using the axiom of choice, it is possible to construct a subset of {0,1}ω that is not determined (Kechris 1995, p. 139).
Borel determinacy
Donald A. Martin (1975) proved that for any set A, all Borel subsets of Aω are determined. Because the original proof was quite complicated, Martin published a shorter proof in 1982 that did not require as much technical machinery. In his review of Martin's paper, Drake describes the second proof as "surprisingly straightforward."
The field of
Set-theoretic aspects
The Borel determinacy theorem is of interest for its metamathematical properties as well as its consequences in descriptive set theory.
Determinacy of closed sets of Aω for arbitrary A is equivalent to the axiom of choice over ZF (Kechris 1995, p. 139). When working in set-theoretical systems where the axiom of choice is not assumed, this can be circumvented by considering generalized strategies known as quasistrategies (Kechris 1995, p. 139) or by only considering games where A is the set of natural numbers, as in the axiom of determinacy.
Zermelo set theory (Z) is
The existence of all
Stronger forms of determinacy
Several set-theoretic principles about determinacy stronger than Borel determinacy are studied in descriptive set theory. They are closely related to
The
The axiom of determinacy states that all subsets of all Polish spaces are determined. It is inconsistent with ZFC but in ZF + DC (Zermelo–Fraenkel set theory plus the axiom of dependent choice) it is equiconsistent with certain large cardinal axioms.
References
- ^ H. Friedman, "Higher set theory and mathematical practice", Annals of Mathematical Logic 2 (1971). pp.326--357.
- ^ Leinster, Tom (23 July 2021). "Borel Determinacy Does Not Require Replacement". The n-Category Café. The University of Texas at Austin. Retrieved 25 August 2021.
- Friedman, Harvey (1971). "Higher set theory and mathematical practice". Annals of Mathematical Logic. 2 (3): 325–357. .
- L. Bukovský, reviewer, MR284327.
- L. Bukovský, reviewer,
- Gale, D. and F. M. Stewart (1953). "Infinite games with perfect information". Contributions to the theory of games, vol. 2. Annals of Mathematical Studies, vol. 28. Vol. 28. Princeton University Press. pp. 245–266.
- S. Sherman, reviewer, MR54922.
- S. Sherman, reviewer,
- ISBN 0-387-94374-9.
- Martin, Donald A. (1975). "Borel determinacy". doi:10.2307/1971035.
- John Burgess, reviewer. MR403976.
- John Burgess, reviewer.
- Martin, Donald A. (1982). "A purely inductive proof of Borel determinacy". Recursion theory. Proc. Sympos. Pure Math (Proceedings of the AMS–ASL summer institute held in Ithaca, New York ed.). pp. 303–308.
- F. R. Drake, reviewer, MR791065.
- F. R. Drake, reviewer,
External links
- Borel determinacy and metamathematics. Ross Bryant. Master's thesis, University of North Texas, 2001.
- "Large Cardinals and Determinacy" at the Stanford Encyclopedia of Philosophy