Axiom of determinacy
   HOME

TheInfoList



OR:

In
mathematics Mathematics is an area of knowledge that includes the topics of numbers, formulas and related structures, shapes and the spaces in which they are contained, and quantities and their changes. These topics are represented in modern mathematics ...
, the axiom of determinacy (abbreviated as AD) is a possible
axiom An axiom, postulate, or assumption is a statement that is taken to be true, to serve as a premise or starting point for further reasoning and arguments. The word comes from the Ancient Greek word (), meaning 'that which is thought worthy or ...
for
set theory Set theory is the branch of mathematical logic that studies sets, which can be informally described as collections of objects. Although objects of any kind can be collected into a set, set theory, as a branch of mathematics, is mostly concern ...
introduced by Jan Mycielski and Hugo Steinhaus in 1962. It refers to certain two-person
topological game In mathematics, a topological game is an infinite game of perfect information played between two players on a topological space. Players choose objects with topological properties such as points, open sets, closed sets and open coverings. Time is ...
s of length ω. AD states that every game of a certain type is determined; that is, one of the two players has a
winning strategy Determinacy is a subfield of set theory, a branch of mathematics, that examines the conditions under which one or the other player of a game has a winning strategy, and the consequences of the existence of such strategies. Alternatively and si ...
. Steinhaus and Mycielski's motivation for AD was its interesting consequences, and suggested that AD could be true in the smallest natural model
L(R) In set theory, L(R) (pronounced L of R) is the smallest transitive class, transitive inner model of Zermelo–Fraenkel set theory, ZF containing all the ordinal number, ordinals and all the real number, reals. Construction It can be constructed i ...
of a set theory, which accepts only a weak form of the
axiom of choice In mathematics, the axiom of choice, or AC, is an axiom of set theory equivalent to the statement that ''a Cartesian product of a collection of non-empty sets is non-empty''. Informally put, the axiom of choice says that given any collection ...
(AC) but contains all real and all
ordinal number In set theory, an ordinal number, or ordinal, is a generalization of ordinal numerals (first, second, th, etc.) aimed to extend enumeration to infinite sets. A finite set can be enumerated by successively labeling each element with the leas ...
s. Some consequences of AD followed from theorems proved earlier by Stefan Banach and Stanisław Mazur, and Morton Davis.
Mycielski Mycielski is a Polish surname. Notable people with the surname include: * Jan Mycielski (born 1932), Polish-American mathematician **The Mycielskian, a construction in graph theory **The Grötzsch graph, sometimes called the Mycielski graph or the ...
and Stanisław Świerczkowski contributed another one: AD implies that all sets of
real number In mathematics, a real number is a number that can be used to measure a ''continuous'' one-dimensional quantity such as a distance, duration or temperature. Here, ''continuous'' means that values can have arbitrarily small variations. Every ...
s are Lebesgue measurable. Later
Donald A. Martin Donald Anthony Martin (born December 24, 1940), also known as Tony Martin, is an American set theorist and philosopher of mathematics at UCLA, where he is an emeritus professor of mathematics and philosophy. Education and career Martin receiv ...
and others proved more important consequences, especially in
descriptive set theory In mathematical logic, descriptive set theory (DST) is the study of certain classes of " well-behaved" subsets of the real line and other Polish spaces. As well as being one of the primary areas of research in set theory, it has applications to ot ...
. In 1988, John R. Steel and
W. Hugh Woodin William Hugh Woodin (born April 23, 1955) is an American mathematician and set theorist at Harvard University. He has made many notable contributions to the theory of inner models and determinacy. A type of large cardinals, the Woodin cardinals, ...
concluded a long line of research. Assuming the existence of some uncountable
cardinal number In mathematics, cardinal numbers, or cardinals for short, are a generalization of the natural numbers used to measure the cardinality (size) of sets. The cardinality of a finite set is a natural number: the number of elements in the set. ...
s analogous to \alef_0, they proved the original conjecture of Mycielski and Steinhaus that AD is true in L(R).


Types of game that are determined

The axiom of determinacy refers to games of the following specific form: Consider a subset ''A'' of the Baire space ''ωω'' of all
infinite sequence In mathematics, a sequence is an enumerated collection of objects in which repetitions are allowed and order matters. Like a set, it contains members (also called ''elements'', or ''terms''). The number of elements (possibly infinite) is called t ...
s of
natural number In mathematics, the natural numbers are those numbers used for counting (as in "there are ''six'' coins on the table") and ordering (as in "this is the ''third'' largest city in the country"). Numbers used for counting are called '' cardinal ...
s. Two players, I and II, alternately pick natural numbers :''n''0, ''n''1, ''n''2, ''n''3, ... After infinitely many moves, a sequence (n_i)_ is generated. Player I wins the game if and only if the sequence generated is an element of ''A''. The axiom of determinacy is the statement that all such games are determined. Not all games require the axiom of determinacy to prove them determined. If the set ''A'' is clopen, the game is essentially a finite game, and is therefore determined. Similarly, if ''A'' is a
closed set In geometry, topology, and related branches of mathematics, a closed set is a set whose complement is an open set. In a topological space, a closed set can be defined as a set which contains all its limit points. In a complete metric space, a ...
, then the game is determined. It was shown in 1975 by
Donald A. Martin Donald Anthony Martin (born December 24, 1940), also known as Tony Martin, is an American set theorist and philosopher of mathematics at UCLA, where he is an emeritus professor of mathematics and philosophy. Education and career Martin receiv ...
that games whose winning set is a
Borel set In mathematics, a Borel set is any set in a topological space that can be formed from open sets (or, equivalently, from closed sets) through the operations of countable union, countable intersection, and relative complement. Borel sets are na ...
are determined. It follows from the existence of sufficiently
large cardinal In the mathematical field of set theory, a large cardinal property is a certain kind of property of transfinite cardinal numbers. Cardinals with such properties are, as the name suggests, generally very "large" (for example, bigger than the least ...
s that all games with winning set a
projective set In the mathematical field of descriptive set theory, a subset A of a Polish space X is projective if it is \boldsymbol^1_n for some positive integer n. Here A is * \boldsymbol^1_1 if A is analytic * \boldsymbol^1_n if the complement of A, X\se ...
are determined (see
Projective determinacy In mathematical logic, projective determinacy is the special case of the axiom of determinacy applying only to projective sets. The axiom of projective determinacy, abbreviated PD, states that for any two-player infinite game of perfect informatio ...
), and that AD holds in
L(R) In set theory, L(R) (pronounced L of R) is the smallest transitive class, transitive inner model of Zermelo–Fraenkel set theory, ZF containing all the ordinal number, ordinals and all the real number, reals. Construction It can be constructed i ...
. The axiom of determinacy implies that for every subspace ''X'' of the
real numbers In mathematics, a real number is a number that can be used to measure a ''continuous'' one-dimensional quantity such as a distance, duration or temperature. Here, ''continuous'' means that values can have arbitrarily small variations. Every re ...
, the
Banach–Mazur game In general topology, set theory and game theory, a Banach– Mazur game is a topological game played by two players, trying to pin down elements in a set (space). The concept of a Banach–Mazur game is closely related to the concept of Baire spa ...
''BM''(''X'') is determined (and therefore that every set of reals has the property of Baire).


Incompatibility of the axiom of determinacy with the axiom of choice

Under assumption of the axiom of choice, we create a counterexample to the axiom of determinacy. The set S1 of all first player strategies in an ω-game ''G'' has the same
cardinality In mathematics, the cardinality of a set is a measure of the number of elements of the set. For example, the set A = \ contains 3 elements, and therefore A has a cardinality of 3. Beginning in the late 19th century, this concept was generalized ...
as the continuum. The same is true for the set S2 of all second player strategies. Let ''SG'' be the set of all possible sequences in ''G'', and A be the subset of sequences of ''SG'' that make the first player win. With the axiom of choice we can well order the continuum, and we can do so in such a way that any proper initial portion has lower cardinality than the continuum. We use the obtained well ordered set J to index both S1 and S2, and construct A such that it will be a counterexample. We start with empty sets A and B. Let α \in J be the index of the strategies in S1 and S2. We need to consider all strategies S1 = of the first player and all strategies S2 = of the second player to make sure that for every strategy there is a strategy of the other player that wins against it. For every strategy of the player considered we will generate a sequence that gives the other player a win. Let t be the time whose axis has length ℵ0 and which is used during each game sequence. We create the counterexample A by
transfinite recursion Transfinite induction is an extension of mathematical induction to well-ordered sets, for example to sets of ordinal numbers or cardinal numbers. Its correctness is a theorem of ZFC. Induction by cases Let P(\alpha) be a property defined for a ...
on α: # Consider the strategy s1(α) of the first player. #Apply this strategy on an ω-game, generating (together with the first player's strategy s1(α)) a sequence , which does not belong to A. This is possible, because the number of choices for has the same cardinality as the continuum, which is larger than the cardinality of the proper initial portion of J. #Add this sequence to B (if it is not already in B), to indicate that s1(α) loses (on ). #Consider the strategy s2(α) of the second player. #Apply this strategy on an ω-game, generating (together with the second player's strategy s2(α)) a sequence , which does not belong to B. This is possible, because the number of choices for has the same cardinality as the continuum, which is larger than the cardinality of the proper initial portion of J. #Add this sequence to A (if it is not already in A), to indicate that s2(α) loses (on ). #Process all possible strategies of S1 and S2 with
transfinite induction Transfinite induction is an extension of mathematical induction to well-ordered sets, for example to sets of ordinal numbers or cardinal numbers. Its correctness is a theorem of ZFC. Induction by cases Let P(\alpha) be a property defined for ...
on α. For all sequences that are not in A or B after that, decide arbitrarily whether they belong to A or to B. So B is the complement of A. Once this has been done, prepare for an ω-game ''G''. If you give me a strategy s1 of the first player, then there is an α \in J such that s1 = s1(α), and we constructed A such that s1(α) fails (on certain choices of the second player). Hence s1 fails. Similarly, any other strategy of either player fails. Hence the axiom of determinacy and the axiom of choice are incompatible.


Infinitary logic and the axiom of determinacy

Many different versions of infinitary logic were proposed in the late 20th century. One reason that has been given for believing in the axiom of determinacy is that it can be written as follows (in a version of infinite logic): \forall G \subseteq Seq(S): \forall a \in S: \exists a' \in S: \forall b \in S: \exists b' \in S: \forall c \in S: \exists c' \in S ... : (a,a',b,b',c,c'...) \in G OR \exists a \in S: \forall a' \in S: \exists b \in S: \forall b' \in S: \exists c \in S: \forall c' \in S ... :(a,a',b,b',c,c'...) \notin G Note: Seq(''S'') is the set of all \omega-sequences of ''S''. The sentences here are infinitely long with a countably infinite list of quantifiers where the ellipses appear.


Large cardinals and the axiom of determinacy

The consistency of the axiom of determinacy is closely related to the question of the consistency of
large cardinal In the mathematical field of set theory, a large cardinal property is a certain kind of property of transfinite cardinal numbers. Cardinals with such properties are, as the name suggests, generally very "large" (for example, bigger than the least ...
axioms. By a theorem of Woodin, the consistency of Zermelo–Fraenkel set theory without choice (ZF) together with the axiom of determinacy is equivalent to the consistency of Zermelo–Fraenkel set theory with choice (ZFC) together with the existence of infinitely many
Woodin cardinal In set theory, a Woodin cardinal (named for W. Hugh Woodin) is a cardinal number \lambda such that for all functions :f : \lambda \to \lambda there exists a cardinal \kappa < \lambda with : \ \subseteq \kappa and an
s. Since Woodin cardinals are
strongly inaccessible In set theory, an uncountable cardinal is inaccessible if it cannot be obtained from smaller cardinals by the usual operations of cardinal arithmetic. More precisely, a cardinal is strongly inaccessible if it is uncountable, it is not a sum of f ...
, if AD is consistent, then so are an infinity of inaccessible cardinals. Moreover, if to the hypothesis of an infinite set of Woodin cardinals is added the existence of a
measurable cardinal In mathematics, a measurable cardinal is a certain kind of large cardinal number. In order to define the concept, one introduces a two-valued measure on a cardinal , or more generally on any set. For a cardinal , it can be described as a subdivisi ...
larger than all of them, a very strong theory of Lebesgue measurable sets of reals emerges, as it is then provable that the axiom of determinacy is true in
L(R) In set theory, L(R) (pronounced L of R) is the smallest transitive class, transitive inner model of Zermelo–Fraenkel set theory, ZF containing all the ordinal number, ordinals and all the real number, reals. Construction It can be constructed i ...
, and therefore that ''every'' set of real numbers in L(R) is determined.


See also

* Axiom of real determinacy (ADR) *
Borel determinacy theorem In descriptive set theory, the Borel determinacy theorem states that any Gale–Stewart game whose payoff set is a Borel set is determined, meaning that one of the two players will have a winning strategy for the game. A Gale-Stewart game is a poss ...
* Martin measure *
Topological game In mathematics, a topological game is an infinite game of perfect information played between two players on a topological space. Players choose objects with topological properties such as points, open sets, closed sets and open coverings. Time is ...


References

* * * * * * *


Further reading

* Philipp Rohde, ''On Extensions of the Axiom of Determinacy'', Thesis, Department of Mathematics, University of Bonn, Germany, 2001 * Telgársky, R.J.br>''Topological Games: On the 50th Anniversary of the Banach-Mazur Game''
Rocky Mountain J. Math. 17 (1987), pp. 227–276. (3.19 MB)
"Large Cardinals and Determinacy"
at the
Stanford Encyclopedia of Philosophy The ''Stanford Encyclopedia of Philosophy'' (''SEP'') combines an online encyclopedia of philosophy with peer-reviewed publication of original papers in philosophy, freely accessible to Internet users. It is maintained by Stanford University. E ...
{{Set theory Axioms of set theory Determinacy Large cardinals