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 dependent choice, denoted by
, is 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 collectio ...
(
) that is still sufficient to develop most of
real analysis
In mathematics, the branch of real analysis studies the behavior of real numbers, sequences and series of real numbers, and real functions. Some particular properties of real-valued sequences and functions that real analysis studies include converg ...
. It was introduced by
Paul Bernays
Paul Isaac Bernays (17 October 1888 – 18 September 1977) was a Swiss mathematician who made significant contributions to mathematical logic, axiomatic set theory, and the philosophy of mathematics. He was an assistant and close collaborator of ...
in a 1942 article that
explores which
set-theoretic
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 ...
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 f ...
s are needed to develop analysis.
["The foundation of analysis does not require the full generality of set theory but can be accomplished within a more restricted frame." The axiom of dependent choice is stated on p. 86.]
Formal statement
A
homogeneous relation
In mathematics, a homogeneous relation (also called endorelation) over a set ''X'' is a binary relation over ''X'' and itself, i.e. it is a subset of the Cartesian product . This is commonly phrased as "a relation on ''X''" or "a (binary) relation ...
on
is called a
total relation
In mathematics, a binary relation ''R'' ⊆ ''X''×''Y'' between two sets ''X'' and ''Y'' is total (or left total) if the source set ''X'' equals the domain . Conversely, ''R'' is called right total if ''Y'' equals the range .
When ''f'': ''X'' â ...
if for every
there exists some
such that
is true.
The axiom of dependent choice can be stated as follows:
For every nonempty
set
Set, The Set, SET or SETS may refer to:
Science, technology, and mathematics Mathematics
*Set (mathematics), a collection of elements
*Category of sets, the category whose objects and morphisms are sets and total functions, respectively
Electro ...
and every total relation
on
there exists a
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 calle ...
in
such that
:
for all
''x''
0 may be taken to be any desired element of ''X''.
If the set
above is restricted to be the set of all
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 real ...
s, then the resulting axiom is denoted by
Use
Even without such an axiom, for any
, one can use ordinary mathematical induction to form the first
terms of such a sequence.
The axiom of dependent choice says that we can form a whole (countably infinite) sequence this way.
The axiom
is the fragment of
that is required to show the existence of a sequence constructed 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 ...
of
countable
In mathematics, a set is countable if either it is finite or it can be made in one to one correspondence with the set of natural numbers. Equivalently, a set is ''countable'' if there exists an injective function from it into the natural numbers; ...
length, if it is necessary to make a choice at each step and if some of those choices cannot be made independently of previous choices.
Equivalent statements
Over
Zermelo–Fraenkel set theory
In set theory, Zermelo–Fraenkel set theory, named after mathematicians Ernst Zermelo and Abraham Fraenkel, is an axiomatic system that was proposed in the early twentieth century in order to formulate a theory of sets free of paradoxes such as ...
,
is equivalent to the
Baire category theorem
The Baire category theorem (BCT) is an important result in general topology and functional analysis. The theorem has two forms, each of which gives sufficient conditions for a topological space to be a Baire space (a topological space such that the ...
for complete metric spaces.
It is also equivalent over
to the
Löwenheim–Skolem theorem
In mathematical logic, the Löwenheim–Skolem theorem is a theorem on the existence and cardinality of models, named after Leopold Löwenheim and Thoralf Skolem.
The precise formulation is given below. It implies that if a countable first-order t ...
.
[Moore states that "Principle of Dependent Choices Löwenheim–Skolem theorem" — that is, implies the Löwenheim–Skolem theorem. ''See'' table ]
is also equivalent over
to the statement that every
pruned tree
In descriptive set theory, a tree on a set X is a collection of finite sequences of elements of X such that every prefix of a sequence in the collection also belongs to the collection.
Definitions
Trees
The collection of all finite sequences of ...
with
levels has a
branch
A branch, sometimes called a ramus in botany, is a woody structural member connected to the central trunk (botany), trunk of a tree (or sometimes a shrub). Large branches are known as boughs and small branches are known as twigs. The term '' ...
(''proof below'').
Furthermore,
is equivalent to a weakened form of
Zorn's lemma; specifically
is equivalent to the statement that any partial order such that every well-ordered chain is finite and bounded, must have a maximal element.
Relation with other axioms
Unlike full
,
is insufficient to prove (given
) that there is a
non-measurable
In mathematics, a non-measurable set is a set which cannot be assigned a meaningful "volume". The mathematical existence of such sets is construed to provide information about the notions of length, area and volume in formal set theory. In Ze ...
set of real numbers, or that there is a set of real numbers without the
property of Baire
A subset A of a topological space X has the property of Baire (Baire property, named after René-Louis Baire), or is called an almost open set, if it differs from an open set by a meager set; that is, if there is an open set U\subseteq X such th ...
or without the
perfect set property In descriptive set theory, a subset of a Polish space has the perfect set property if it is either countable or has a nonempty perfect subset (Kechris 1995, p. 150). Note that having the perfect set property is not the same as being a p ...
. This follows because the
Solovay model In the mathematical field of set theory, the Solovay model is a model constructed by in which all of the axioms of Zermelo–Fraenkel set theory (ZF) hold, exclusive of the axiom of choice, but in which all sets of real numbers are Lebesgue measur ...
satisfies
, and every set of real numbers in this model is Lebesgue measurable, has the Baire property and has the perfect set property.
The axiom of dependent choice implies the
axiom of countable choice
The axiom of countable choice or axiom of denumerable choice, denoted ACω, is an axiom of set theory that states that every countable collection of non-empty sets must have a choice function. That is, given a function ''A'' with domain N (where ...
and is strictly stronger.
[For a proof that the Axiom of Countable Choice does not imply the Axiom of Dependent Choice ''see'' ]
It is possible to generalize the axiom to produce transfinite sequences. If these are allowed to be arbitrarily long, then it becomes equivalent to the full axiom of choice.
Notes
References
*
{{Set theory
Axiom of choice