What follows from Axiom of Dependent Choice (DC) and what doesn't?

Question

As most of us, I struggled a lot when I first heard about Axiom of Choice (AC) and its consequences. Some things that can be derived from AC don't agree with my intuition. Consider for instance Zermelo's theorem applied to $\mathbb{R}.$

For many years I wished to abandon this evil axiom, but I was powerless. I mistakenly thought that assuming $\neg AC$ implies that all classical results using AC are then lost. Equivalence of Cauchy and Haine continuity for example. I wasn't aware that there are alternatives to AC.

Finally when dealing with the characterization of Noetherian rings I came across Axiom of Dependent Choice (DC). It sounded so right to me. I loved it since I read it for the very first time.

Since that day I try to re-examine all results that use AC to find out whether DC is enough.

Question. What results follows from DC and what results require full AC?

I am interested in the results form all mathematics. Set theory, topology, algebra, logic, etc.

Obviously all the results that are equivalent to AC fall to the latter group.

Answer 1

Kurt Godel in the 1930's showed that Con(ZF) implies Con(ZFC). Paul Cohen in the 1960's showed that Con(ZF) implies Con(ZF$+\;\neg$AC). So you have your choice, so to speak.

DC implies CC (Countable Choice). CC is: If $f$ is a set-valued function with dom($f)= \omega,$ and $f(n)\ne \phi$ for all $n,$ then $\prod_{n\in \omega}f(n)\ne \phi.$

CC implies that a countable union of countable sets is countable, and hence that $\omega_1$ is a regular cardinal, which matters in the theory of Borel sets, among other things.

In ZF the words finite and infinite must be used with caution. A Tarski-finite set is a bijective image (or any functional image) of a member of $\omega.$ A set $S$ is Dedekind-infinite iff there is an injection from $S$ to a proper subset of S. It is an elementary exercise to show that $S$ is Dedekind-infinite iff $S$ has a countably infinite subset.

It has been shown that it is equi-consistent with ZF that there is a set which is neither Tarski-finite nor Dedekind-infinite.

We can use DC to prove that a set $S$ that is not Tarski-finite is Dedekind infinite, as follows: For $n\in \omega$ let $F_n$ be the set of injective functions from $n$ into $S.$ Let $F=\cup_{n\in \omega}F_n.$ For $f,g \in F,$ let $f<^*g$ iff dom($f)\subsetneqq$ dom($g)$ and $g|_{\text {dom}(f)}=f.$

Then $<^*$ is a binary relation on $F$ and dom$(<^*)=F.$ Now $\phi$ (the empty function) belongs to $F.$ So DC implies there is a sequence $(f_n)_{n\in \omega}$ in $F$ with $f_0=\phi$ and $f_n<^*f_{n+1}$ for all $n\in \omega.$ Then $\cup_{n\in \omega}f_n$ is an injection from $\omega$ into $S.$

I dk whether that can be proved using only CC.

Answer 2

Fallen, there is one result that I can reassure you concerning the validity thereof in ZF+ACC (countable choice) namely the $\sigma$-additivity of the Lebesgue measure. On the other hand, it is consistent with ZF alone that there exists a strictly positive real function with zero Lebesgue integral; see this recent article.

Another interesting pair of facts is that

(1) the transfer principle in Robinson's framework for analysis with infinitesimals for a definable extension $\mathbb{R}\hookrightarrow{}^\ast\mathbb{R}$ can be proved in ZF+ACC. The catch is that

(2) the properness of that particular extension requires stronger foundational material such as the existence of maximal ideals.

So in your announced scheme of things (2) would classify as "a horrible lie" as you put it, but perhaps (1) can assuage your concerns.

Answer 3

Of course, a complete answer is impossible to give here, since it would have to cover so many details about $\sf DC$, other choice principles, and modern mathematics.

Let me give, in a nutshell, a few examples from every category of interest.

$\bf 1.$ What is equivalent to $\sf DC$

• Every tree of height $\omega$ without maximal nodes has a branch; or in a more Zorn-like manner, every partial order where every finite chain has an upper bound, has a maximal element or a countable chain. (Since all finite chains have upper bounds, this translates to "Every partial order has a maximal element or a countable chain.)

• Baire's Category Theorem. The intersection of a countable family of dense open sets in a complete metric space is dense.

• The downwards Lowenheim-Skolem theorem for countable languages: if $\cal L$ is a countable language and $M$ is a structure for $\cal L$, then there is an elementary submodel $N\subseteq M$ which is countable.

• A partial order without infinite descending chains is well-founded, i.e. every non-empty set has a minimal element.

$\bf 2.$ What is weaker than $\sf DC$

• The axiom of choice for countable families.

• Every infinite set has a countably infinite subset.

• The countable union of countable sets is countable.

• The real numbers are not a countable union of countable sets.

• There is a nontrivial measure on Borel sets which is $\sigma$-additive.

• There is no $\alpha$ such that $\aleph_{\alpha+1}$ has countable cofinality.

$\bf 3.$ What does not follow from $\sf DC$

• The Hahn–Banach theorem.

• The existence of irregular sets of reals (e.g. sets which are not measurable, sets which do not have the Baire property, sets which do not have a perfect subset).

• Every set can be linearly ordered.

• The existence of free ultrafilters on $\Bbb N$

• The Krein–Milman theorem.

• The existence of a discontinuous linear functional on $\ell^1$; or even the existence of a non-zero linear functional on $\ell^\infty/c_0$.

• The compactness theorem (for first-order logic), which itself is equivalent to Tychonoff's theorem restricted to Hausdorff spaces.

• The axiom of choice for arbitrary families of finite sets (or really, anything which requires more than countably many choices).

These lists can be extended ad infinitum. Since $\sf DC$ is one of the most useful choice principles out there, its uses can be implicit (or explicit) in many works of modern mathematics. Even those things which do not follow from $\sf DC$ might have weak instances that do, that turn out to be as good and as useful to things like analysis and number theory as the full axiom of choice.