[2] In this sort of game there are two players, often named I and II, who take turns playing natural numbers, with I going first.
This condition need not be specified by any definable rule; it may simply be an arbitrary (infinitely long) lookup table saying who has won given a particular sequence of plays.
More formally, consider a subset A of Baire space; recall that the latter consists of all ω-sequences of natural numbers.
Again, such a "way" does not have to be capable of being captured by any explicable "rule", but may simply be a lookup table.
More formally, a strategy for player I (for a game in the sense of the preceding subsection) is a function that accepts as an argument any finite sequence of natural numbers, of even length, and returns a natural number.
[4] All finite games of perfect information in which draws do not occur are determined.
Real-world games of perfect information, such as tic-tac-toe, chess, or infinite chess, are always finished in a finite number of moves (in infinite chess-games this assumes the 50-move rule is applied).
[5] As it happens, chess has a finite number of positions and a draw-by-repetition rules, so with these modified rules, if play continues long enough without White having won, then Black can eventually force a win (due to the modification of draw = win for black).
David Gale and F. M. Stewart proved the open and closed games are determined.
Determinacy for second level of the Borel hierarchy games was shown by Wolfe in 1955.
Over the following 20 years, additional research using ever-more-complicated arguments established that third and fourth levels of the Borel hierarchy are determined.
In 1971, before Martin obtained his proof, Harvey Friedman showed that any proof of Borel determinacy must use the axiom of replacement in an essential way, in order to iterate the powerset axiom transfinitely often.
Friedman's work gives a level-by-level result detailing how many iterations of the powerset axiom are necessary to guarantee determinacy at each level of the Borel hierarchy.
For every integer n, ZFC\P proves determinacy in the nth level of the difference hierarchy of
See reverse mathematics for other relations between determinacy and subsystems of second-order arithmetic.
In general, stronger large cardinal axioms prove the determinacy of larger pointclasses, higher in the Wadge hierarchy, and the determinacy of such pointclasses, in turn, proves the existence of inner models of slightly weaker large cardinal axioms than those used to prove the determinacy of the pointclass in the first place.
From the existence of more measurable cardinals, one can prove the determinacy of more levels of the difference hierarchy over Π11.
is an initial segment of s. To prove that A is determined, define auxiliary game as follows: In addition to ordinary moves, player 2 must play a mapping of
By indiscernibility, if κ and the ordinals in the auxiliary response are in I, then the moves by player 1 do not depend on the auxiliary moves (or on κ), and so the strategy can be converted into a strategy for the original game (since player 2 can hold out with indiscernibles for any finite number of steps).
determinacy holds, then for a Turing cone of x (that is for every real x of sufficiently high Turing degree), L[x] satisfies OD-determinacy (that is determinacy of games on integers of length ω and ordinal-definable payoff), and in HODL[x]
From projective determinacy it follows that, for every natural number n, there is a transitive inner model that satisfies that there are n Woodin cardinals.
The axiom of determinacy, or AD, asserts that every two-player game of perfect information of length ω, in which the players play naturals, is determined.
AD is provably false from ZFC; using the axiom of choice one may prove the existence of a non-determined game.
However, if there are infinitely many Woodin cardinals with a measurable above them all, then L(R) is a model of ZF that satisfies AD.
In 1969, Michael O. Rabin proved that the monadic second-order theory of n successors (S2S for n = 2) is decidable.
[8] A key component of the proof requires showing determinacy of parity games, which lie in the third level of the Borel hierarchy.
Assuming that a certain iterability conjecture is provable, existence of a measurable Woodin cardinal implies determinacy of open games of length ω1 and projective payoff.
(In these games, a winning condition for the first player is triggered at a countable stage, so the payoff can be coded as a set of reals.)
ω1 is maximal in that there are undetermined games on integers of length ω1+ω and ordinal definable payoff.
Against this definition, all finite two-player zero-sum games are clearly determined.