# Extensive Definition

In set theory, a
branch of mathematics, determinacy is
the study of under what circumstances one or the other player of a
game must
have a winning
strategy, and
the consequences of the existence of such strategies.

## Basic notions

### Games

The first sort of game we shall consider is the
two-player game of perfect information of length ω, in
which the players play natural
numbers.

In this sort of game we consider two players,
often imaginatively named I and II, who take turns playing natural
numbers, with I going first. They play "forever"; that is, their
plays are indexed by the natural numbers. When they're finished, a
predetermined condition decides which player won. 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. Then in the game GA, I
plays a natural number a0, then II plays a1, then I plays a2, and
so on. Then I wins the game if and only if

- \in A

It is assumed that each player can see all moves
preceding each of his moves, and also knows the winning
condition.

### Strategies

Informally, a strategy for a player is a way of
playing in which his plays are entirely determined by the foregoing
plays. 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. If σ is such a
strategy and <a0,…,a2n-1> is a sequence of plays,
then σ(<a0,…,a2n-1>) is the next play I
will make, if he is following the strategy σ. Strategies
for II are just the same, substituting "odd" for "even".

Note that we have said nothing, as yet, about
whether a strategy is in any way good. A strategy might direct a
player to make aggressively bad moves, and it would still be a
strategy. In fact it is not necessary even to know the winning
condition for a game, to know what strategies exist for the
game.

### Winning strategies

A strategy is winning if the player following it
must necessarily win, no matter what his opponent plays. For
example if σ is a strategy for I, then σ is a
winning strategy for I in the game GA if, for any sequence of
natural numbers to be played by II, say <a1,a3,a5,…>,
the sequence of plays produced by σ when II plays thus,
namely

- ),a_1,\sigma(),a_1>),a_3,\ldots>

### Determined games

A (class of) game(s) is determined if for all
instance of the game there is a winning strategy for one of the
players (not necessarily the same player for each instance). Note
that there cannot be a winning strategy for both players for the
same game, for if there were, the two strategies could be played
against each other. The resulting outcome would then, by
hypothesis, be a win for both players, which is impossible.

## Determinacy from elementary considerations

All finite games of perfect information in which draws do not occur are determined.Familiar real-world games of perfect information,
such as chess or tic-tac-toe,
are always finished in a finite number of moves. If such a game is
modified so that a particular player wins under any condition where
the game would have been called a draw, then it is always
determined. The condition that the game is always over (i.e. all
possible extensions of the finite position result in a win for the
same player) in a finite number of moves corresponds to the
topological condition that the set A giving the winning condition
for GA is clopen in the
topology of Baire
space.

For example, modifying the rules of chess to make
drawn games a win for Black makes chess a determined game. 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.

It is an instructive exercise to figure out how
to represent such games as games in the context of this
article.

The proof that such games are determined is
rather simple: Player I simply plays not to lose; that is, he plays
to make sure that player II does not have a winning strategy after
Is move. If player I cannot do this, then it means player II had a
winning strategy from the beginning. On the other hand, if player I
can play in this way, then he must win, because the game will be
over after some finite number of moves, and he can't have lost at
that point.

This proof does not actually require that the
game always be over in a finite number of moves, only that it be
over in a finite number of moves whenever II wins. That condition,
topologically, is that the set A is closed. This fact--that all
closed games are determined--is called the Gale-Stewart theorem.
Note that by symmetry, all open games are determined as well. (A
game is open if I can win only by winning in a finite number of
moves.)

## Determinacy from ZFC

In 1975, Donald A. Martin proved that all Borel games are determined; that is, if A is a Borel subset of Baire space, then GA is determined. This is the best result possible using ZFC alone, in the sense that the determinacy of the next higher Wadge class is not provable in ZFC.Martin's proof uses the powerset
axiom in an essential way. There is a level-by-level result
detailing what fragment of the powerset axiom is necessary to
guarantee determinacy through what level of the Borel
hierarchy.

Historically, determinacy for second level of the
Borel
hierarchy games was shown by Wolfe in 1955.

## Determinacy and large cardinals

There is an intimate relationship between
determinacy and large
cardinals. 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.

### Measurable cardinals

It follows from the existence of a measurable cardinal that every analytic game (also called a Σ11 game) is determined, or equivalently that every coanalytic (or Π11) game is determined. (See Projective hierarchy for definitions.)Actually an apparently stronger result follows:
If there is a measurable cardinal, then every game in the first
ω2 levels of the difference
hierarchy over Π11 is determined. This is only
apparently stronger; ω2-Π11 determinacy turns out
to be equivalent to Π11 determinacy.

From the existence of more measurable cardinals,
one can prove the determinacy of more levels of the difference
hierarchy over Π11.

### Woodin cardinals

If there is a Woodin cardinal with a measurable cardinal above it, then Π12 determinacy holds. More generally, if there are n Woodin cardinals with a measurable cardinal above them all, then Π1n+1 determinacy holds. From Π1n+1 determinacy, it follows that there is a transitive inner model containing n Woodin cardinals.### Projective determinacy

If there are infinitely many Woodin cardinals, then projective determinacy holds; that is, every game whose winning condition is a projective set is determined. From projective determinacy it follows that, for every natural number n, there is a transitive inner model which satisfies that there are n Woodin cardinals.### Axiom of determinacy

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.

## Consequences of determinacy

### Regularity properties for sets of reals

If A is a subset of Baire space such that the Banach-Mazur game for A is determined, then either II has a winning strategy, in which case A is meager, or I has a winning strategy, in which case A is comeager on some open neighborhoodref usage.This does not quite imply that A has the property
of Baire, but it comes close: A simple modification of the
argument shows that if Γ is an adequate
pointclass such that every game in Γ is determined,
then every set of reals in Γ has the property of
Baire.

In fact this result is not optimal; by
considering the unfolded
Banach-Mazur game we can show that determinacy of Γ
(for Γ with sufficient closure properties) implies that
every set of reals that is the projection of a set in Γ
has the property of Baire. So for example the existence of a
measurable cardinal implies Π11 determinacy, which in turn
implies that every Σ12 set of reals has the property of
Baire.

By considering other games, we can show that
Π1n determinacy implies that every Σ1n+1 set of
reals has the property of Baire, is Lebesgue
measurable (in fact universally
measurable) and has the perfect
set property.

### Periodicity theorems

- The first periodicity theorem implies that, for every natural number n, if Δ12n+1 determinacy holds, then Π12n+1 and Σ12n+2 have the prewellordering property (and that Σ12n+1 and Π12n+2 do not have the prewellordering property, but rather have the separation property).
- The second periodicity theorem implies that, for every natural number n, if Δ12n+1 determinacy holds, then Π12n+1 and Σ12n+2 have the scale property. In particular, if projective determinacy holds, then every projective relation has a projective uniformization.
- The third periodicity theorem gives a sufficient condition for a game to have a definable winning strategy.

### Applications to decidability of certain second-order theories

In 1969, Michael O. Rabin proved that the second-order theory of n successors is decidable. A key component of the proof requires showing determinacy of parity games, which lie in the third level of the Borel hierarchy.### Wadge determinacy

Wadge determinacy is the statement that for all
pairs A,B of subsets of Baire
space, the Wadge
game G(A,B) is determined. Similarly for a pointclass Γ,
Γ Wadge determinacy is the statement that for all sets
A,B in Γ, the Wadge game G(A,B) is determined.

Wadge determinacy implies the semilinear
ordering principle for the Wadge
order. Another consequence of Wadge determinacy is the perfect
set property.

In general, Γ Wadge determinacy is a
consequence of the determinacy of Boolean combinations of sets in
Γ. In the projective
hierarchy, Π11 Wadge determinacy is equivalent to
Π11 determinacy, as proved by Harrington. This result was
extendend by Hjorth to prove that Π12 Wadge determinacy (and
in fact the semilinear ordering principle for Π12) already
implies Π12 determinacy.

- This subsection is still incomplete

## More general games

- This section is still to be written

### Games in which the objects played are not natural numbers

- This subsection is still to be written

### Games played on trees

- This subsection is still to be written

### Long games

- This subsection is still to be written

### Games of imperfect information (Blackwell games)

- This subsection is still to be written

## Quasistrategies and quasideterminacy

- This section is still to be written

## Footnotes

- note usage This assumes that I is trying to get the intersection of neighborhoods played to be a singleton whose unique element is an element of A. Some authors make that the goal instead for player II; that usage requires modifying the above remarks accordingly.

## References

- Set theory, third millennium edition (revised and expanded)
- Descriptive Set Theory
- (PDF)

determinacy in German: Determiniertheit
(Mengenlehre)

determinacy in Polish: Gry nieskończone

determinacy in Swedish: Vinnande
strategi