axiom of dependent choices
The axiom of dependent choices (DC), or the principle of dependent choices, is the following statement:
Here, is the set of all natural numbers.
ZF+AC implies ZF+DC.
We prove this by using one of the equivalents of AC: Zorn’s lemma. For this proof, we define , the initial segment of with the greatest element . Before starting the proof, we need a fact about initial segments:
The union of initial segments of is either or an initial segment.
Let be a set of initial segments of . If , then , so has a least element . As a result, none of is in , and . If some is in , then there is an initial segment with , so that , contradicting . ∎
Remark. The fact that in the proof above has a least element is a direct result of ZF, so the well-ordering principle (and hence AC) is not needed.
We are now ready for the proof of proposition 1.
Let be a non-empty binary relation on a set (of course non-empty). We want to find a function such that .
Let be the set of all partial functions such that is either an initial segment of , or itself, such that , whenever . Since , some . Additionally, . Define function by and . Then , so that , or is non-empty.
Now, suppose , then for some , so as well. Therefore . Since for any , we see that . This shows that , or that has an upper bound in .
ZF+DC implies ZF+CC.
Since there is a bijection , index each element in by its image in , so that . Let . We want to find a function such that for every .
Define a binary relation on as follows: iff there is an such that and . Since each , . Furthermore, if , then for some . Pick any (since ), so that , and therefore . This shows that .
By DC, there is a function such that for every . Now, for some . Define a function as follows, for each , pick and set (this can be done by induction), and for , set (arithmetic of finite cardinals is possible in ZF). Then for all .
Finally, define as follows: for each , set . Then has the desired property , and the proof is complete. ∎
However, the converses of both of these implications are false. Jensen proved the independence of DC from ZF+CC, and Mostowski and Jech proved the independence of AC from ZF+DC. In fact, it was shown that the weaker version of AC, which states that every set with cardinality at most has a choice function, is independent from ZF+DC.
Remark. DC is related to Baire spaces in point-set topology. It can be shown that DC is equivalent to each of the following statements in ZF:
- 1 T. Jech, Interdependence of weakened forms of the axiom of choice, Comment. Math. Univ. Carolinae 7, pp. 359-371, (1966).
- 2 R. B. Jensen Independence of the axiom of dependent choices from the countable axiom of choice (abstract), Jour. Symbolic Logic 31, 294, (1966).
- 3 A. Levy, Basic Set Theory, Dover Publications Inc., (2002).
- 4 A. Mostowski On the principle of dependent choices, Fund. Math. 35, pp 127-130 (1948).
|Title||axiom of dependent choices|
|Date of creation||2013-03-22 18:46:39|
|Last modified on||2013-03-22 18:46:39|
|Last modified by||CWoo (3771)|