Is there a direct relation between DC and countable AC?

Question

Working in $\mathbf{ZF}$, let $X$ be a set that's not well-orderable.

Countable AC in X:

• If $F$ is a countable set of non-empty subsets of $X$ there is a choice function $f:F\to X$ such that $f(x)\in x$ for all $x\in F$.

DC in X:

• Let $R\subseteq X\times X$ be a relation such that $\forall a\in X\,\exists b\in X:aRb$. Then there's a sequence $g:\omega\to X$ such that $g(n)Rg(n+1)$ for all $n\in\omega$.

Is there a direct relation between them in the sense that one can prove the other (with $\mathbf{ZF}$ given)?

If either of these hold for $X$ then the same one holds for all non-empty subsets of $X$. Countable AC applies directly. For DC, if $Y\subseteq X$ and $R$ a relation on $Y$, extend $R$ to $X$ by adding $aRb$ for all $a\in X\setminus Y$ and all $b\in Y$.

If either of these hold for $X$, and $Z$ is equinumerous to $X$, then the same one holds for $Z$, because a solution for $X$ can be transferred via bijection between $X$ and $Z$.

So the question is whether one can be used to prove the other.

Clarification: Let $CAC_X$ and $DC_X$ be the above where $X$ represents its cardinality. My question is:

• Is it true that for all non-well-orderable cardinalilty $X$ $DC_X\Rightarrow CAC_X$?
• For any non-well-orderable cardinality $X$ is there guaranteed to be some possibly higher cardinality $Y$ such that $CAC_Y\rightarrow DC_X$?

Answer 1

Suppose that $\mathsf DC(X)$ holds, and let $\{X_n\mid n<\omega\}$ be a countable family of non-empty subsets of $X$.

Without loss of generality, $\bigcup X_n=X$, otherwise we simply add $X_0$ to be the complement of that union. Let's try the naive proof first.

Now define $x\mathrel R y$ if and only if $x\in X_n$ and $y\in X_{n+1}$. By $\sf DC$, there is $f\colon\omega\to X$ such that $f(n)\mathrel R f(n+1)$. But that means that for some $k$, $f(n)\in X_{n+k}$ for all $n<\omega$. So $f$ is a choice function from all but finitely many $X_n$s, which can therefore be completed to a choice function from the whole family. This obviously works if the $X_n$ are pairwise disjoint. But it is not clear otherwise, since it might be that $f(n)$ actually belongs to $X_{n^2}$ as well for all $n$, which means that $f(n+1)$ may actually come from $X_{n^2+1}$, creating gaps. So at best we get a partial choice function here.

If $|X^{<\omega}|=|X|$, we can encode the finite choice functions and diagonalise against them. So this will work in situations such as $X=\Bbb R$. Even better, even if we only have that $|X\times 2|=|X|$, we can still salvage the proof. Note that this implies that $|X\times\omega|=|X|$, and by fixing a bijection we can map each of the $X_n$ to its image in $X\times\{n\}$, generating a pairwise disjoint family.

But what happens if this is not the case? Well. If $X$ does not map onto $\omega$, then it does not have a countable sequence of subsets to begin with. So it has to map onto $\omega$, but then by the above proof it must be Dedekind-infinite. So any infinite Dedekind-finite set cannot serve as a counterexample. It needs to satisfy that $|X\times 2|>|X|$, and it needs to have a sequence of sets $A_n$ such that every point appears in infinitely many and also is omitted from infinitely many different sets in the sequence. It might be possible to concoct a counterexample, I just don't see an immediate way at the moment.

In either case, the result here is that ${\sf DC}(X^{<\omega})$ implies ${\sf AC}_\omega(X)$; and that if $|X\times 2|=|X|$, then ${\sf DC}(X)\to{\sf AC}_\omega(X)$. Moreover, if ${\sf DC}(X)$ holds, then either $X$ does not map onto $\omega$, in which case ${\sf AC}_\omega(X)$ holds vacuously, or $X$ is Dedekind-infinite.

---

As for the reverse direction, it is consistent with $\sf ZF$ that $\sf AC_\omega$ holds, but $\sf DC$ fails. Moreover, we can arrange for that failure of $\sf DC$ to happen at the level of the real numbers. This, on its own, is not enough to argue that there is no nice characterisation, but it does tell you that there is no obvious way to get around $\sf DC$ in this situation.

Of course, being a mathematician, I am obligated to point out the annoying thing that if $X$ is any set for which ${\sf AC}_\omega(X)$ fails, then ${\sf AC}_\omega(X)\to{\sf DC}(X)$ is a true implication for vacuous reasons.

Answer 2

To add to Asaf Karagila's answer, if there exists a counterexample $X$ such that $\text{DC}(X)\land\neg\text{AC}_\omega(X)$, there must exist such a counterexample with $\aleph_0 < |X| < 2^{\aleph_0}$.

Claim: If for all $X$ with $|X|\le 2^{\aleph_0}$ we know that $\text{DC}(X)\Rightarrow\text{AC}_\omega(X)$ then it follows that for all $X$ $\text{DC}(X)\Rightarrow\text{AC}_\omega(X)$.

Proof: Fix $X$. If $\neg\text{DC}(X)$ then $\text{DC}(X)\Rightarrow\text{AC}_\omega(X)$ is true vacuously. So assume $\text{DC}(X)$.

Let $\tau:\omega\to\mathcal{P}(X)\setminus\emptyset$ be injective and denote $A_n=\tau(n)$. We have to construct a choice function for the $A_n$. Define $q:X\to\mathcal{P}(\omega)$ by $q(x)=\{n\in\omega:x\in A_n\}$. Let $Z=\text{Image}(q)$. Then $|Z|\le|\mathcal{P}(\omega)|=2^{\aleph_0}$. The function $q$ induces an equivalence relation on $X$ via $x\equiv_q y\iff q(x)=q(y)$. By the definition of $q$, each $A_n$ is a (mutually disjoint) union of equivalence classes of $\equiv_q$. Let $B_n=q(A_n)$. The $B_n$ are a countable collection of non-empty subsets of $Z$ and they are distinct because of the property of $A_n$ being a union of equivalence classes.

Lemma: $\text{DC}(Z)$ holds.

Proof of lemma: Let $R\subseteq Z\times Z$ be an entire relation. Lift $R$ to $R^\prime\subseteq X\times X$ defined by $x R^\prime y \iff q(x) R q(y)$. $R^\prime$ is entire. Since $\text{DC}(X)$ there is a sequence $a_n$ such that $a_n R^\prime a_{n+1}$. Then $q(a_n) R q(a_{n+1})$.

We now have $\text{DC}(Z)$, $|Z|\le 2^{\aleph_0}$, by assumption $\text{DC}(Z)\Rightarrow\text{AC}_\omega(Z)$, so $\text{AC}_\omega(Z)$ follows.

Applying $\text{AC}_\omega(Z)$ to the $B_n$ we get a sequence $c_n\in B_n$. Now let $d_n=q^{-1}(\{c_n\})$. Each $d_n$ is a $\equiv_q$ equivalence class and by the stuff said earlier about $A_n$, $d_n\subseteq A_n$. But each pair $d_n,d_m$ of equivalence classes is either equal or disjoint. Eliminating duplicates, the family $\{d_n: n\in\omega\}$ is a finite or countable family of mutually disjoint sets. We are also assuming $\text{DC}(X)$ so as in Asaf Karagila's proof for mutually disjoint sets there is a choice function for $\{d_n: n\in\omega\}$. Then, since each $A_n$ is a superset of a unique member of $\{d_n: n\in\omega\}$, we can transfer the choice function to the $A_n$.