# Strength of "Cofinite Choice"

Let $$A$$ be a set of sets such that $$(\bigcup A) \setminus x$$ is finite for every $$x \in A$$.

How strong is the variant of AC asserting that such an $$A$$ has a choice function? I'd assume it to be weaker than countable choice, but ZF doesn't seem to prove it either.

## 1 Answer

The axiom of cofinite choice is equivalent to the principle that every Dedekind-finite set is finite. Equivalently, for every infinite set $$X$$, there is an injective function $$\omega\to X$$. So as you suspected, it is (strictly) weaker than countable choice, but not provable in ZF.

Assume cofinite choice and let $$X$$ be an infinite set. Let $$A$$ be the set of all cofinite subsets of $$X$$, and let $$g$$ be a choice function for $$A$$. Then we can construct an injective function $$\omega\to X$$ by recursion. Let $$f_0\colon 0\to X$$ be the empty function. Given an injective function $$f_n\colon n\to X$$, the set $$X_n = X\setminus \text{im}(f_n)$$ is cofinite, and we can extend $$f_n$$ to $$f_{n+1}\colon (n+1)\to X$$ by defining $$f_{n+1}(n) = g(X_n)$$. Then $$f = \bigcup_{n\in \omega} f_n$$ is an injective function $$\omega\to X$$.

Conversely, assume that every Dedekind-finite set is finite. Let $$A$$ be a set of nonempty sets such that $$(\bigcup A)\setminus x$$ is finite for all $$x\in A$$. If $$\bigcup A$$ is finite, then $$A$$ is finite, and ZF proves that every finite set has a choice function. If $$\bigcup A$$ is infinite, let $$f\colon \omega\to \bigcup A$$ be an injective function. Then for any $$x\in A$$, since $$(\bigcup A)\setminus x$$ is finite, $$x\cap \text{im}(f)$$ is nonempty. So we can define a choice function $$g$$ on $$A$$ by defining $$g(x) = f(n)$$ for the minimal $$n\in \omega$$ such that $$f(n)\in x$$.

• Somewhat interestingly, an approach similar to the definition of the $f_n$ was how I stumbled upon this question, thanks! Commented Jan 14, 2021 at 21:07
• Perhaps a bit clearly: ZF proves that "the cofinite subsets of $x$ admit a choice function" if and only if $x$ is not infinite Dedekind-finite. Commented Jan 14, 2021 at 21:18
• @Asaf it feels like one needs a DC-like version, since the subsequent choice of $f_{n+1}(n)$ depends on the previous choices of extensions. Thoughts? Commented Feb 3 at 0:26
• @theHigherGeometer: Well, it's an illusion. :) Commented Feb 3 at 7:53
• @theHigherGeometer: Yeah. This is exactly why DC is needed for branches in a tree, but not for branches in a countable tree. Commented Feb 3 at 9:00