Axiom of dependent choice

Axiom of dependent choice

Discussion
Ask a question about 'Axiom of dependent choice'
Start a new discussion about 'Axiom of dependent choice'
Answer questions from other users
Full Discussion Forum
 
Encyclopedia
In mathematics
Mathematics
Mathematics is the study of quantity, space, structure, and change. Mathematicians seek out patterns and formulate new conjectures. Mathematicians resolve the truth or falsity of conjectures by mathematical proofs, which are arguments sufficient to convince other mathematicians of their validity...

, the axiom of dependent choices, denoted DC, is a weak form of the axiom of choice (AC) which is still sufficient to develop most of real analysis
Real analysis
Real analysis, is a branch of mathematical analysis dealing with the set of real numbers and functions of a real variable. In particular, it deals with the analytic properties of real functions and sequences, including convergence and limits of sequences of real numbers, the calculus of the real...

. Unlike full AC, DC is insufficient to prove (given ZF) that there is a nonmeasurable set of real
Real number
In mathematics, a real number is a value that represents a quantity along a continuum, such as -5 , 4/3 , 8.6 , √2 and π...

s, or that there is a set of reals without the property of Baire or without the perfect set property
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...

.

The axiom can be stated as follows: For any nonempty set X and any entire binary relation
Binary relation
In mathematics, a binary relation on a set A is a collection of ordered pairs of elements of A. In other words, it is a subset of the Cartesian product A2 = . More generally, a binary relation between two sets A and B is a subset of...

 R on X, there is a sequence
Sequence
In mathematics, a sequence is an ordered list of objects . Like a set, it contains members , and the number of terms is called the length of the sequence. Unlike a set, order matters, and exactly the same elements can appear multiple times at different positions in the sequence...

 (xn) in X such that xnRxn+1 for each n in N. (Here an entire binary relation on X is one such that for each a in X there is a b in X such that aRb.) Note that even without such an axiom we could form the first n terms of such a sequence, for any natural number n; the axiom of dependent choices merely says that we can form a whole sequence this way.

If the set X above is restricted to be the set of all real number
Real number
In mathematics, a real number is a value that represents a quantity along a continuum, such as -5 , 4/3 , 8.6 , √2 and π...

s, the resulting axiom is called DCR.

DC is the fragment of AC required to show the existence of a sequence constructed by transfinite recursion of countable
Countable set
In mathematics, a countable set is a set with the same cardinality as some subset of the set of natural numbers. A set that is not countable is called uncountable. The term was originated by Georg Cantor...

 length, if it is necessary to make a choice at each step.

DC is (over the theory ZF) equivalent to the statement that every (nonempty) pruned tree has a branch. It is also equivalent
to the Baire category theorem
Baire category theorem
The Baire category theorem is an important tool 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....

 for complete metric spaces.

The axiom of dependent choice implies the Axiom of countable choice
Axiom of countable choice
The axiom of countable choice or axiom of denumerable choice, denoted ACω, is an axiom of set theory, similar to the axiom of choice. It states that any countable collection of non-empty sets must have a choice function...

, and is strictly stronger.