Dependent Choice and the Complete-Metric Baire Theorem

Assume prescribed-start DC. Given nonempty $A$ and serial $R$, fix one $a_0\in A$. Its prescribed chain is a chain with unrestricted start, so starting-point-free DC follows. This is a single existential instantiation, not a family of selections.

Conversely assume starting-point-free DC, and fix nonempty $A$, serial $R$ and $a_0\in A$. By Separation in $\omega \times \mathcal{P}(\omega \times A)$, the pairs $(l,p)$ with $l\ge 1$, $p:l\to A$, $p(0)=a_0$, and $p(i)Rp(i+1)$ for every $i+1<l$ form a set $P$. The pair $(1,\{(0,a_0)\})$ belongs to $P$, since there are no adjacent coordinates to check.

Define $S$ on $P$ by $(l,p)S(l+1,q)$ exactly when $q$ extends $p$. This is a subset of $P\times P$. For any $(l,p)\in P$, seriality gives one $b\in A$ with $p(l-1)Rb$; the function $q=p\cup \{(l,b)\}$ has domain $l+1$ and satisfies all required edges, old ones from $p$ and the new last edge by the choice of $b$. Thus $S$ is serial. No simultaneous successor function has been selected.

Apply starting-point-free DC to the nonempty set $P$ and serial $S$. It gives $h(k)=(l_k,p_k)$ with $p_{k+1}$ extending $p_k$ and $l_{k+1}=l_k+1$. Induction gives $l_k=l_0+k$ and, for $j\le k$, $p_j\subseteq p_k$: the zero case is reflexivity, and each successor uses one end extension. In particular the domains are unbounded in $\omega$.

Replacement gives the set $\{p_k:k\in \omega \}$ and Union gives $f={\bigcup }_{k\in \omega }{p}_k$. Two pairs in $f$ with the same first coordinate lie together in $p_{\max (j,k)}$, so have the same second coordinate. Every $n$ lies in $l_{n+1}$, since $l_0\ge 1$, and all domains lie in $\omega$. Consequently $f:\omega \to A$ and $f(0)=a_0$.

For any $n\in \omega$, both $n$ and $n+1$ lie in $l_{n+2}$. That path's edge gives $f(n)=p_{n+2}(n)R{p}_{n+2}(n+1)=f(n+1)$. Hence $f$ is the prescribed chain. Together with the first implication this proves the equivalence, without any additional choice axiom.

From the ball definition of closure, $D$ is dense precisely when every ball about every point meets $D$. This is equivalent to meeting every nonempty open set: a point of such an open set has a ball inside it; conversely each ball is itself nonempty and open. It follows that $D$ is dense exactly when $\mathrm{int}(X\setminus D)=\mathrm{\varnothing }$, since a nonempty open subset of the complement is exactly an open set disjoint from $D$.

If $F$ is closed, $\bar{F}=F$, so $F$ is nowhere dense exactly when $\mathrm{int}(F)=\mathrm{\varnothing }$, exactly when $X\setminus F$ is dense. Its complement is open by closedness. Conversely, if $U$ is open dense, $F=X\setminus U$ is closed and has empty interior by the preceding test, hence is nowhere dense.

Assume (2). If a nonempty open $V$ were meagre, fix its one witness $V\subseteq {\bigcup }_n{N}_n$. Put $F_n=\overline{N_n}$ by the uniquely specified closure operation. Each $F_n$ is closed and has empty interior by nowhere density of $N_n$; by closedness its own closure equals itself. Thus the $F_n$ are closed nowhere dense. But $V\subseteq {\bigcup }_n{F}_n$ makes that union's interior nonempty, contradicting (2). This proves (3). The family of closures is defined from the given witness, without choosing decompositions.

Assume (3), and let $(F_n)$ be closed nowhere dense. If its union had nonempty interior $V$, this open set would be meagre, witnessed by the very sequence $(F_n)$, contrary to (3). Thus (2) follows.

Assume (3), and let $C$ be comeagre. If $C$ were not dense, the open-set test would give a nonempty open $V\subseteq X\setminus C$. A meagre witness for $X\setminus C$ also covers $V$, contradicting (3). Thus (4) follows. Conversely assume (4). If a nonempty open $V$ were meagre, $X\setminus V$ would be comeagre and hence dense, yet disjoint from $V$, a contradiction. Thus (4) implies (3).

Apply these complement correspondences term by term. For each sequence of closed nowhere dense $F_n$, the $U_n=X\setminus F_n$ are open dense and $X\setminus {\bigcup }_n{F}_n={\bigcap }_n{U}_n$. The union has empty interior exactly when this intersection is dense. Conversely, starting with any sequence of open dense $U_n$ and taking its closed nowhere dense complements gives the same identity. Thus (1) and (2) imply each other; the De Morgan index set is $\omega \mathrm{\ne }\mathrm{\varnothing }$.

These implications prove all four equivalences. They also cover $X=\mathrm{\varnothing }$: every set and every union or intersection under consideration is empty, hence dense with empty interior, and there is no nonempty open set. No choice axiom or completeness hypothesis was used.

If $X=\mathrm{\varnothing }$, the intersection is empty and dense. Otherwise it suffices to meet an arbitrary nonempty open $V\subseteq X$. Set $C(c,r)=\bar{B}(c,r)$. For any nonempty open $W$, fix $c\in W$ and $\delta >0$ with $B(c,\delta )\subseteq W$. Given a bound $b>0$, take $t\ge 1$ with $r=1\mathrm{/}t<\min (\delta ,b)$. Then $r$ is positive rational, $r\le b$, and $C(c,r)\subseteq B(c,\delta )\subseteq W$, directly from $d(c,x)\le r<\delta$.

By ZF Separation, let $S$ consist of all triples $(n,c,r)\in \omega \times X\times \mathbb{Q}$ with $0<r\le 1\mathrm{/}(n+1)$ and $C(c,r)\subseteq V\cap U_n$. The set $V\cap U_0$ is nonempty by density and open. The preceding construction with $b=1$ gives an initial state $s_0=(0,c_0,r_0)\in S$.

Relate $(n,c,r)$ to $(n+1,c^{\mathrm{\prime }},r^{\mathrm{\prime }})$ when both lie in $S$ and $C(c^{\mathrm{\prime }},r^{\mathrm{\prime }})\subseteq B(c,r)\cap U_{n+1}$. For each state, $c\in B(c,r)$, so density of $U_{n+1}$ makes $W=B(c,r)\cap U_{n+1}$ nonempty; it is open. The construction with $b=1\mathrm{/}(n+2)$ supplies $c^{\mathrm{\prime }},r^{\mathrm{\prime }}$. Since $B(c,r)\subseteq C(c,r)\subseteq V$, this triple belongs to $S$. Thus the displayed relation is serial on the nonempty set $S$. Only one centre and radius were fixed for this one existence assertion.

Apply prescribed-start DC to $S$ with initial state $s_0$. The resulting chain has stage coordinate $n$ at position $n$: this holds at zero, and each relation step increments that coordinate by one. Write its states $(n,c_n,r_n)$ and $C_n=C(c_n,r_n)$. Then $C_{n+1}\subseteq B(c_n,r_n)\subseteq C_n$, $r_n\le 1\mathrm{/}(n+1)$, and $C_n\subseteq V\cap U_n$. This application is the proof's sequence-selection use of DC; centres are already components of the selected states.

For fixed $n$, induction on $m-n$ gives $C_m\subseteq C_n$ for all $m\ge n$: equality is the base, and the next containment follows from nesting. Since $c_m\in C_m$, for $m,k\ge n$ the triangle inequality gives $d(c_m,c_k)\le d(c_m,c_n)+d(c_n,c_k)\le 2r_n\le 2\mathrm{/}(n+1)$. For any positive rational $\epsilon$, choose $t\ge 1$ with $1\mathrm{/}t<\epsilon \mathrm{/}2$ and take $n=t$; then the displayed bound is less than $\epsilon$. Hence $(c_n)$ is Cauchy. Completeness supplies a single limit $x\in X$.

Fix $n$. If $d(x,c_n)>r_n$, put $\eta =d(x,c_n)-r_n>0$ and fix a positive reciprocal $e<\eta$. Convergence gives $m\ge n$ with $d(x,c_m)<e$. The tail bound and triangle inequality yield $d(x,c_n)\le d(x,c_m)+d(c_m,c_n)<e+r_n<\eta +r_n=d(x,c_n)$, which is impossible. Therefore $d(x,c_n)\le r_n$ and $x\in C_n$. In particular equality on a closed-ball boundary is allowed.

Thus $x\in V\cap {\bigcap }_n{U}_n$. Since $V$ was an arbitrary nonempty open set, the intersection is dense. This proves CM-Baire, and hence also its equivalent category formulations.

By the function-set construction $Y$ is a set. Fix one $a_{\ast }\in A$; the constant function $n\mapsto a_{\ast }$ belongs to $Y$. If $f\mathrm{\ne }g$, their nonempty set of differing coordinates has a least member, so $d$ is a well-defined real-valued function (its graph is obtained by Replacement). Its values are nonnegative, it is symmetric, and it is zero exactly on the diagonal. No selection from a family of different carriers is involved.

For every $t\in \omega$, $d(f,g)<1\mathrm{/}(t+1)$ holds exactly when $f$ and $g$ agree at all coordinates $i\le t$: a first disagreement at $k\le t$ gives distance at least $1\mathrm{/}(t+1)$; a first disagreement at $k>t$ gives a smaller reciprocal, and equality of functions gives zero. Also, agreement at all $i<l$ implies $d(f,g)\le 1\mathrm{/}(l+1)$, including $l=0$.

To prove the strong triangle inequality, equalities $f=g$ or $g=h$ reduce it to equality. Otherwise let $i$ and $j$ be the first disagreements of $(f,g)$ and $(g,h)$ and set $t=\min (i,j)$. All three functions agree below $t$, so either $f=h$ or their first disagreement is at least $t$. Thus $d(f,h)\le 1\mathrm{/}(t+1)=\max (d(f,g),d(g,h))$. Nonnegative numbers have maximum at most their sum, so the ordinary triangle inequality follows as well. Hence $d$ is an ultrametric.

For $s:l\to A$, define $\widehat{s}(i)=s(i)$ for $i<l$ and $\widehat{s}(i)=a_{\ast }$ otherwise. Then $\widehat{s}\in [s]$, including the empty prefix $l=0$, whose cylinder is $Y$. If $l\ge 1$ and $f\in [s]$, the equivalence above gives $B(f,1\mathrm{/}l)=[s]$, so $[s]$ is open. If $g\mathrm{\notin }[s]$, there is $i<l$ with $g(i)\mathrm{\ne }s(i)$, and $B(g,1\mathrm{/}(i+1))$ fixes that coordinate and misses $[s]$. The complement is therefore open. For $l=0$ the complement is empty and open. Thus every cylinder is nonempty and clopen.

Let $(f_j{)}_{j\in \omega }$ be any Cauchy sequence in $Y$. For each $n$, its Cauchy property at the rational tolerance $1\mathrm{/}(n+1)$ makes the set of $K$ satisfying $(\mathrm{\forall }p,q\ge K)d(f_p,f_q)<1\mathrm{/}(n+1)$ nonempty. Let $K_n$ be its least member. Define $f(n)=f_{K_n}(n)$. Leastness makes both $K_n$ and this value unique, so Replacement gives the graph of a function $f:\omega \to A$, without any choice principle. By the prefix equivalence, for $j\ge K_n$ one has $f_j(n)=f_{K_n}(n)=f(n)$.

Given $f\in O$ with $O$ open, take $\epsilon >0$ with $B(f,\epsilon )\subseteq O$ and take $l\ge 1$ with $1\mathrm{/}l<\epsilon$. If $g$ extends $f\upharpoonright l$, its distance to $f$ is at most $1\mathrm{/}(l+1)<\epsilon$. Thus $f\in [f\upharpoonright l]\subseteq O$, proving the basis assertion.

For a finite prefix length $l$, put $H_0=0$ and successively $H_{t+1}=\max (H_t,K_t)$ for $t<l$. This finite deterministic construction uses no selections; induction shows $H_l\ge K_t$ for every $t<l$. Hence every $j\ge H_l$ has $f_j\upharpoonright l=f\upharpoonright l$, and $d(f_j,f)\le 1\mathrm{/}(l+1)$. Given positive rational $\epsilon$, take $l\ge 1$ with $1\mathrm{/}l<\epsilon$; this bound proves $f_j\to f$. The construction works also when $A$ is a singleton, in which case every distance is zero. Thus every Cauchy sequence converges in $Y$, completing the proof.

Each $U_n$ is a set by Separation in $Y$. The graph $\{(n,U)\in \omega \times \mathcal{P}(Y):(\mathrm{\forall }f\in Y)(f\in U\leftrightarrow (\mathrm{\exists }m\in \omega )f(n)Rf(m))\}$ is also a set by Separation. For each $n$ there is exactly one such $U$, so this graph defines an indexed family with domain $\omega$.

If $f\in U_n$, fix one witnessing $m$. Every $g$ in the cylinder $[f\upharpoonright (\max (n,m)+1)]$ has $g(n)=f(n)$ and $g(m)=f(m)$, hence $g(n)Rg(m)$ and $g\in U_n$. This is an open neighbourhood of $f$, so $U_n$ is open.

Fix one $a_{\ast }\in A$, and let $s:l\to A$ be any finite prefix; $l=0$ is allowed. Set $L=\max (l,n+1)$. Extend $s$ to $t:L\to A$ by assigning $a_{\ast }$ at each new coordinate. Thus $t(n)$ is defined and $L>n$. Seriality gives one $b\in A$ with $t(n)Rb$. Define $g(i)=t(i)$ for $i<L$, $g(L)=b$, and $g(i)=a_{\ast }$ for $i>L$. Then $g\in [s]$ and $g(n)Rg(L)$, so $g\in U_n$. This is one explicit extension for a fixed cylinder and fixed $n$, not a choice of extensions for a family of cylinders.

Every nonempty open subset of $Y$ contains a cylinder, and hence meets $U_n$ by the preceding construction. Equivalently every ball meets $U_n$, which is exactly density by the metric closure definition. Thus every $U_n$ is open dense. For singleton $A=\{a_{\ast }\}$ seriality forces $a_{\ast }R{a}_{\ast }$ and the same construction gives $U_n=Y$. No infinite relation-path was assumed in proving nonemptiness of a cylinder.

Since $A\mathrm{\ne }\mathrm{\varnothing }$, $Y=A^{\omega }$ with its specified metric is nonempty complete, and $(U_i)$ is open dense. Apply CM-Baire to this space and family: $D={\bigcap }_i{U}_i$ is dense in $Y$. If $D$ were empty, every ball about a point of the nonempty space $Y$ would miss it, contradicting density. Thus fix a single $f\in D$.

For each $i\in \omega$, Separation gives $W_i=\{j\in \omega :f(i)Rf(j)\}$. Since $f\in U_i$, this set is nonempty and has a unique least element $q(i)$. The graph of $q$ is the subset of $\omega \times \omega$ where $j\in W_i$ and no smaller natural belongs to $W_i$; hence Separation makes $q:\omega \to \omega$ a set function. In particular $f(i)Rf(q(i))$ for every $i$. This defines successors uniquely from the one fixed $f$.

Apply recursion with carrier $\omega$, initial element $0$ and the self-map $q$. It yields $k:\omega \to \omega$ with $k(0)=0$ and $k(n+1)=q(k(n))$. The composite $a(n)=f(k(n))$ has graph obtained by Separation in $\omega \times A$. For every $n$, the preceding relation at $i=k(n)$ says $a(n)=f(k(n))Rf(q(k(n)))=f(k(n+1))=a(n+1)$. Thus $a$ is an $R$-chain.

The construction works for every nonempty $A$ and every serial $R$, so gives the global starting-point-free DC principle. Its ZF equivalence with the prescribed-start principle gives the latter as well. The minimum $q(i)$ can be smaller or larger than $i$, so no increasing-index or distinct-value assumption entered the argument; singleton carriers and self-loops are allowed.

Assume DC. The forward implication applies over ZF to every complete metric space and every $\omega$-indexed sequence of open dense subsets, and says that their intersection is dense. This is exactly CM-Baire, including its empty-space instance.

Assume CM-Baire. The reverse implication applies to every nonempty set and every serial relation on it, and supplies both the unrestricted and prescribed-start chain principles. Thus CM-Baire implies DC. These two implications prove the stated equivalence over ZF.