Work in ZF unless an additional choice principle is explicitly named. We use elementary complete-metric-space analysis, not a theorem asserting the equivalence or independence of choice principles.
Motivation
A finite succession of existential choices can be justified by induction. An infinite succession requires more care. If the next decision depends on all previous decisions, knowing that every finite stage can be extended does not yet hand us an infinite sequence. A recursion theorem constructs values from a specified rule; it does not turn an unspecified nonempty set of possible successors into such a rule.
Countable choice concerns one selection from each of a fixed sequence of sets. Dependent choice permits each new selection to depend on the preceding state. Trees make that difference visible: a node records the finite decisions already made, and an infinite branch is a compatible completion. The nested-ball proof of Baire's theorem is a useful analytical example, because the next ball must fit inside the ball just chosen.
Definitions
Definition 4.2.1
(Countable and dependent choice)
Countable choice, written , says that for every sequence of nonempty sets there is a function with for every . The sets need not be finite or countable. The index set is what is countable.
A relation is serial if every has some successor with . We use the pointed form of dependent choice, DC: for every nonempty , serial and specified , there is a sequence with initial term and for all .
Definition 4.2.2
(Trees, pruned trees and branches)
A tree of finite sequences on a set is a nonempty closed under taking prefixes. Its root is the empty sequence. It is pruned if every node has an immediate extension . A branch is with for every . The tree and function spaces are sets in ZF; no enumeration of is assumed.
Definition 4.2.3
(Nowhere dense sets and Baire spaces)
In a metric space, a set is nowhere dense when its closure has empty interior. A space is Baire when every countable intersection of open dense sets is dense. Completeness means that every Cauchy sequence converges to a point of the same space.
Theorem/proposition
Theorem 4.2.4
(The implications we actually prove)
Over ZF,
Countable choice also implies that a countable union of countable sets is countable. The latter proof must choose a family of encodings, not merely observe their individual existence.
Theorem 4.2.5
(DC is the pruned-tree branch principle)
Over ZF, DC is equivalent to the assertion that every pruned tree of finite sequences on any set has an infinite branch. The word “pruned” cannot simply be replaced by “has nodes of arbitrarily large finite length” for arbitrary branching.
Theorem 4.2.6
(Baire's theorem under DC)
Assume DC. Every complete metric space is Baire. In particular a nonempty complete metric space is not the union of countably many nowhere dense sets.
Proof sketch or proof idea
Proof
(Successor functions, pruned trees and partial choices)
Under AC, the successor sets have a choice function . Ordinary recursion on now defines from the specified . This proves AC implies DC and identifies exactly where the selection rule came from.
Assume DC and let be pruned. Use its nodes as states and immediate extension as the serial relation, starting at the empty node. DC gives with and compatible extensions. Their union is a function on and is the desired branch. Conversely, given serial on and , form the tree consisting of the empty sequence and all finite -chains beginning at . The root extends to and any nonempty node extends by seriality. A branch therefore starts at and follows , proving DC.
To derive , take the tree of all finite partial choices: a node of length has for . Every node extends because the single next set is nonempty. No simultaneous choices were used to verify this existential assertion for one node. The branch principle supplies an infinite compatible choice function.
Finally suppose each is countable. The set of injections is nonempty, including the unique empty injection if is empty. Countable choice selects simultaneously. Map a union element to , where is its least membership index. This is injective into , which is countable by the explicit pairing construction. An existential encoding at each index has thus become an actual sequence of encodings using the stated principle.
Proof X-ray
Recursion needs a rule, not merely possible next moves
The successor relation can have many outputs. Recursion applies after a single successor function has been supplied, as AC does in the first proof. DC instead asserts a compatible chain directly. The finite-choice tree is pruned before we know a branch exists; checking one extension at a time does not secretly establish the conclusion we seek.
Proof
(Nested closed balls chosen dependently)
For Baire, let be open dense sets in a complete metric space, and let be any nonempty open set. We construct closed balls
with and . Here denotes the closed metric ball , which is closed by the triangle inequality; it is not being asserted equal to the closure of the corresponding open ball in an arbitrary metric space.
The first ball exists because is nonempty open: choose a point and a sufficiently small positive radius. Given a ball at level , the open ball meets . At a point of that intersection, openness permits a sufficiently small closed ball inside it, with radius at most .
To justify doing this indefinitely, take as states all admissible triples with and . Relate a triple to a level- triple whose closed ball lies in its open ball. The preceding observation proves this relation serial. DC, starting at one admissible level-zero triple, gives the required sequence. Keeping the level in the state ensures that the next requirement is rather than an unspecified dense set.
If , nestedness puts . Thus for , , so the centers are Cauchy. Let their limit be . Every is closed and contains a tail of centers, hence contains . Therefore . Since was arbitrary nonempty open, the intersection is dense. The empty complete space satisfies the density statement trivially.
If with each nowhere dense, the complements are open dense. Their intersection would be nonempty when is nonempty, by the proved density, yet disjoint from the asserted union. This contradiction gives the final conclusion. Neither compactness of the balls nor a convergent-subsequence theorem was used; completeness and shrinking radii were the convergence mechanism.
Worked examples
Worked example 4.2.7
(Arbitrarily long finite paths without an infinite path)
Let consist of the empty sequence and finite strictly decreasing sequences of natural numbers. Prefixes remain in . For every there is a length- node, for example when . There is no infinite branch, since a decreasing sequence starting at has length at most . Nodes ending in zero have no extension, so this tree is not pruned. It does not contradict DC and shows why unbounded finite height alone is insufficient when branching is unrestricted.
Worked example 4.2.8
(A binary tree has a canonical next step)
For a pruned tree on , extend by zero if the zero-extension belongs to the tree, and otherwise extend by one. Prunedness guarantees the latter exists when needed. This specifies a successor function, so ordinary recursion gives a branch in ZF. The general branch principle concerns arbitrary sets of labels, without a canonical order. Its strength cannot be read from this special binary case.
Worked example 4.2.9
(The rational line fails completeness)
In the usual metric on , each singleton is closed and has empty interior. The countable set is therefore a countable union of nowhere dense sets and is not Baire. Completeness fails: dyadic rational approximations to form a Cauchy sequence with no rational limit. The Baire proof would still make Cauchy centers, but would have no point in the space at which to finish.
Worked example 4.2.10
(Specified countable data can remove a choice step)
Suppose a complete metric space comes with a specified countable dense sequence. Enumerate all balls with those centers and positive rational radii. Inside any nonempty open set there is such a ball whose closed ball also lies there: choose a small ambient ball, then a nearby dense center and a still smaller rational radius. At each nested-ball stage, select the least index meeting the required containments and radius bound. This is a uniquely specified rule, so the resulting Baire construction uses recursion in ZF. The least admissible index need not be computable: testing a set-containment condition was not assumed decidable. A canonical mathematical selection and an effective algorithm are different assertions.
Common mistakes
Common mistake
(Countable choice counts the index set, not the members)
The sets in countable choice are not themselves assumed countable. Conversely, finite choice is provable in ZF by induction and does not justify passage to infinitely many coordinated choices. Writing “continue this way” must either identify a successor rule or name the principle producing the sequence.
Common mistake
(Special trees do not yield full DC)
The branch principle uses every pruned tree on arbitrary sets. Special trees with a well-ordered alphabet permit canonical choices and do not by themselves imply full DC. We have proved forward implications and a particular equivalence; no model-theoretic nonimplication or independence result has been established here.
Neither arrow reverses in ZF, while Baire’s theorem turns out to be as strong as DC itself.
A natural next question
Do the implications reverse?
Neither arrow reverses in ZF, while Baire’s theorem turns out to be as strong as DC itself.
Neither forward implication reverses. If ZF is consistent, it has models in which countable choice holds while DC fails, and models in which DC holds while AC fails; these are built by forcing and symmetric-model methods beyond this course. In the other direction, Baire’s theorem for complete metric spaces is known to imply DC over ZF, so the use of DC in the nested-ball proof cannot be avoided in general.
Common mistake
(Completeness, not compactness, finishes the Baire argument)
In Baire's proof, dense sets must be open to fit the next closed ball, and the limit must lie in a complete domain. Closed balls need not be compact. Their radii tend to zero, but without completeness their intersection may still be empty.
Counterexample mode
Dense sets that are not open can be disjoint
Claim: in a complete metric space, every countable intersection of dense sets is dense. In with the usual complete metric, take
Both are dense: an interval contains a rational, and contains a rational , so . If , then and with , so would be rational. Hence . The nested-ball proof breaks at its first step: no closed ball of positive radius fits inside , which contains no interval. The theorem requires the dense sets to be open, which is exactly what lets each new closed ball sit inside the next .
Summary
AC supplies a successor function and hence DC; DC is precisely the arbitrary pruned-tree branch principle and supplies countable simultaneous choices. Countable choice makes separate countable encodings available as a family. Nested-ball Baire proofs reveal a dependent choice step, while specified countable bases can sometimes replace that step by a canonical rule.
Exercises
Quick check
(Prove finite choice in ZF. If a countable family of nonempty countable sets has a countable union, show directly that it has a choice function, without selecting an enumeration of each member.)
Solution · Answer
For zero sets use the empty function. If a finite family already has a choice function and one new nonempty set is added, take one of its elements and extend the finite function. Existential induction proves each finite assertion without choosing an infinite family. For the countable family, fix one injection , supplied by countability of the union. Choose from the unique element whose -value is least in the nonempty subset . Replacement collects this uniquely defined selection function. No family of separate enumerations is needed.
Quick check
(Let already be well-ordered and serial. Construct a chain from any prescribed start in ZF. If and is decidable, explain why the resulting chain is computable.)
Solution · Answer
Define to be the least -successor of in the given well-order. Seriality guarantees it exists, and recursion gives . On with decidable , search until . The search terminates by seriality, so iterating it computes each term. An arbitrary abstract well-order does not supply an algorithm for its least-element operation.
Quick check
(Show that a countable intersection of dense subsets of need not be dense when openness is removed. Use only two distinct dense sets.)
Solution · Answer
Take and for every . Both rationals and irrationals are dense: every interval contains a rational and, by shifting a sufficiently small irrational multiple, an irrational. Their intersection is empty. Neither of these two sets is open in the usual real topology, so this does not violate Baire's theorem.
Quick check
(Construct a nested sequence of nonempty closed balls in with radii tending to zero and empty intersection. Use dyadic intervals containing .)
Solution · Answer
Put and let . These dyadic intervals are nested, contain rational endpoints, and are closed balls in with rational center and radius . Their real intersection is because their diameters tend to zero and they all contain that real number in the corresponding real intervals. Their intersection inside is therefore empty. The missing limit, rather than a failure of nestedness, is the obstruction.
Quick check
(Some definitions of DC require a chain in each nonempty serial relation but do not prescribe its initial term. Prove in ZF that this unpointed form implies the pointed form used here.)
Solution · Answer
Given and , use as states all nonempty finite -chains starting at , with immediate extension as the serial relation. There is at least the one-term state . The unpointed principle gives an infinite chain of these finite states, possibly beginning with a longer one. Their compatible union has domain , starts at , and follows . The domain is all of because the finite lengths increase by one at every step. Thus the missing prescribed start has been encoded into the state space itself. The reverse implication simply forgets the prescribed start.