View source for Stokes wave

In [[descriptive set theory]], the '''Borel determinacy theorem''' states that any Gale-Stewart game whose winning set is a [[Borel set]] is [[Determinacy|determined]], meaning that one of the two players will have a winning strategy for the game. It was proved by [[Donald A. Martin]] in 1975. The theorem is applied in descriptive set theory to show that Borel sets in Polish spaces have regularity properties such as the [[perfect set property]] and the [[property of Baire]]. 

The theorem is also known for its [[metamathematics|metamathematical]] properties. In 1971, before the theorem was proved, [[Harvey Friedman]] showed that any proof of the theorem in [[Zermelo-Fraenkel set theory]] must make repeated use of the [[axiom of replacement]].  Later results showed that stronger determinacy theorems cannot be proven in Zermelo-Fraenkel set theory, although they are relatively [[consistent]] with it.

== Background ==
=== Gale&ndash;Stewart games ===
{{main|Determinacy}}

A '''Gale&ndash;Stewart''' game is a two-player game of perfect information. The game is defined using a set ''A'', and is denoted ''G''<sub>''A''</sub>. 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. 

<center>
<math>
\begin{matrix}
\mathrm{I} &  a_1 & \quad & a_3 & \quad & a_5 & \quad & \cdots\\
\mathrm{II} &  \quad & a_2 & \quad & a_4 & \quad & a_6 & \cdots
\end{matrix}
</math>
</center>

The play continues without end, so that a single play of the game determines an infinite sequence <math>\langle a_1,a_2,a_3\ldots\rangle</math> of elements of ''A''. The set of all such sequences is denoted ''A''<sup>&omega;</sup>.    The players are aware, from the beginning of the game, of a fixed '''payoff set''' that will determine who wins.   The payoff set is a [[subset]] of ''A''<sup>ω</sup>. 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.

=== 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 he or she 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
<center>
<math>
\begin{matrix}
\mathrm{I} &  a_1 = f(\langle \rangle) & \quad & a_3 = f(\langle a_1, a_2\rangle)& \quad & a_5 = f(\langle a_1, a_2, a_3, a_4\rangle) & \quad & \cdots\\
\mathrm{II} &  \quad & a_2 & \quad & a_4 & \quad & a_6 & \cdots.
\end{matrix}
</math>
</center>
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
<center>
<math>
\begin{matrix}
\mathrm{I} &  a_1 & \quad & a_3 & \quad & a_5 & \quad & \cdots\\
\mathrm{II} &  \quad & a_2 = g(\langle a_1\rangle)& \quad & a_4  = g(\langle a_1,a_2,a_3\rangle) & \quad & a_6 = g(\langle a_1,a_2,a_3,a_4,a_5\rangle) & \cdots .
\end{matrix}
</math>
</center>

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''<sup>&omega;</sup> will be determined depends to some extent on its topological structure. For the purposes of Gale&ndash;Stewart games, the set ''A'' is endowed with the [[discrete topology|discrete]] [[topology]], and ''A''<sup>&omega;</sup> endowed with the resulting [[product topology]], where ''A''<sup>&omega;</sup> is viewed as a [[countably infinite]] [[topological product]] of ''A'' with itself.  In particular, when ''A'' is the set {0,1}, the topology defined on ''A''<sup>&omega;</sup> is exactly the ordinary topology on [[Cantor space]], and when ''A'' is the set of natural numbers, it is the ordinary topology on [[Baire space]].

The set ''A''<sup>&omega;</sup> can be viewed as the set of paths through a certain [[Tree (descriptive set theory)|tree]], which leads to a second characterization of its topology. The tree consists of all finite sequences of elements of ''A'', and the children of a particular node &sigma; of the tree are exactly the sequences that extend &sigma; by one element. Thus if ''A'' = { 0, 1 }, the first level of the tree consists of the sequences &lang; 0 &rang; and &lang; 1 &rang;; the second level consists of the four sequences &lang; 0, 0 &rang;, &lang; 0, 1 &rang;, &lang; 1, 0 &rang;, &lang; 1, 1 &rang;; and so on.  For each of the finite sequences &sigma; in the tree, the set of all elements of ''A''<sup>&omega;</sup> that begin with &sigma; is a [[basis (topology)|basic open set]] in the topology on ''A''. The [[open set]]s of ''A''<sup>ω</sup> are precisely the sets expressible as unions of these basic open sets. The [[closed set]]s, as usual, are those whose complement is open. 

The [[Borel set]]s of ''A''<sup>&omega;</sup> are the smallest class of subsets of ''A''<sup>&omega;</sup> that includes the open sets and is closed under complement and countable union. That is, the Borel sets are the smallest [[sigma-algebra|&sigma;-algebra]] of subsets of ''A''<sup>ω</sup> containing all the open sets. The Borel sets are classified in the [[Borel hierarchy]] based on how many times the operations of complement and countable union are required to produce them from open sets.

== Previous results ==
Gale and Stewart (1953) proved that if the payoff set is an [[open set|open]] or [[closed set|closed]] subset of ''A''<sup>&omega;</sup> then the Gale&ndash;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 set|Borel subset]] of ''A''<sup>ω</sup>.  It was known that, using the [[axiom of choice]], it is possible to construct a subset of {0,1}<sup>ω</sup> that is not determined (Kechris 1995, p.&nbsp;139).

[[Harvey Friedman]] (1971) proved that that any proof that all Borel subsets of Cantor space ({0,1}<sup>ω</sup> ) were determined would require repeated use of the [[axiom of replacement]], an axiom not typically required to prove theorems about "small" objects such as Cantor space.

== Borel determinacy ==
[[Donald A. Martin]] (1975) proved that for any set ''A'', all Borel subsets of ''A''<sup>ω</sup> 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 [[descriptive set theory]] studies properties of [[Polish space]]s (essentially, complete separable metric spaces). The Borel determinacy theorem has been used to establish many properties of Borel subsets of these spaces. For example, all Borel subsets of Polish spaces have the [[perfect set property]] and the [[property of Baire]].

== Set-theoretic aspects ==
The Borel determinacy theorem is of interest for its [[metamathematics|metamethematical]] properties as well as its consequences in descriptive set theory.

Determinacy of closed sets of ''A''<sup>&omega;</sup> for arbitrary ''A'' is equivalent to the [[axiom of choice]] over [[Zermelo-Fraenkel set theory|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 [[Zermelo-Fraenkel set theory]] without the axiom of replacement. It differs from ZF in that Z does not prove that the [[powerset]] operation can be iterated uncountably many times beginning with an arbitrary set.  In particular, ''V''<sub>&omega; + &omega;</sub>, a particular countable level of the [[cumulative hierarchy]], is a model of Zermelo set theory.  The axiom of replacement, on the other hand, is only satisfied by ''V''<sub>κ</sub> for significantly larger values of κ, such as when κ is a [[strongly inaccessible cardinal]]. Friedman's theorem of 1971 showed that there is a model of Zermelo set theory (with the axiom of choice) in which Borel determinacy fails, and thus Zermelo set theory cannot prove the Borel determinacy theorem.

== Stronger forms of determinacy ==
{{main|determinacy}}
Several set-theoretic principles about determinacy stronger than Borel determinacy are studied in descriptive set theory. They are closely related to [[large cardinal axiom]]s. 

The [[axiom of projective determinacy]] states that all [[projective set|projective]] subsets of a Polish space are determined. It is known to be unprovable in ZFC but relatively consistent with it and implied by certain [[large cardinal]] axioms. The existence of a [[measurable cardinal]] is enough to imply over ZFC that all [[analytic set|analytic subsets]] of Polish spaces are determined. 

The [[axiom of determinacy]] states that all subsets of all Polish spaces are determined. It is inconsistent with ZFC but equiconsistent with certain large cardinal axioms.

== References ==
* {{cite journal
  | first = Harvey
  | last = Friedman
  | title = Higher set theory and mathematical practice
  | journal = Annals of Mathematical Logic
  | volume=2
  | year=1971
  | pages=325&ndash;357
  | doi = 10.1016/0003-4843(71)90018-0
  | issue = 3
}}
** L. Bukovský, reviewer, [[Mathematical Reviews]], {{MR|284327}}.
* {{cite book
  | author= Gale, D. and F. M. Stewart
  | chapter=Infinite games with perfect information
  | title=Contributions to the theory of games, vol. 2
  | year=1953
  | series=Annals of Mathematical Studies, vol. 28
  | volume=28 
  | pages=245&ndash;266
  | publisher=Princeton University Press
}}
** S. Sherman, reviewer, [[Mathematical Reviews]], {{MR|54922}}.
*{{cite book
 | author = Alexander Kechris
 | authorlink = Alexander S. Kechris
 | title = Classical descriptive set theory
 | series = [[Graduate texts in mathematics]]
 | volume = 156
 | year = 1995
 | isbn = 0-387-94374-9
}}
* {{cite journal
 | author=Martin, Donald A.
 | title=Borel determinacy
 | journal=[[Annals of Mathematics]]. Second series
 | volume=102 
 | issue=2
 | pages=363–371
 | year=1975
 | doi=10.2307/1971035
}}
** John Burgess, reviewer. [[Mathematical Reviews]], {{MR|403976}}.
* {{cite conference
 | first= Donald A. 
 | last=Martin 
 | title=A purely inductive proof of Borel determinacy
 | booktitle= Recursion theory
 | pages=303&ndash;308 
 | publisher= 
 | date= 1982
 | series=Proc. Sympos. Pure Math
 | edition=Proceedings of the AMS&ndash;ASL summer institute held in Ithaca, New York 
}}
**F. R. Drake, reviewer, [[Mathematical Reviews]], {{MR|791065}}.

== External links ==
* ''[http://www.cas.unt.edu/~rdb0003/thesis/thesis.pdf Borel determinacy and metamathematics]''. Ross Bryant. Master's thesis, University of North Texas, 2001.

[[Category:Determinacy]]
[[Category:Theorems in the foundations of mathematics]]