12
$\begingroup$

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.

$\endgroup$

1 Answer 1

14
$\begingroup$

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$.

$\endgroup$
6
  • $\begingroup$ Somewhat interestingly, an approach similar to the definition of the $f_n$ was how I stumbled upon this question, thanks! $\endgroup$
    – univalence
    Commented Jan 14, 2021 at 21:07
  • 3
    $\begingroup$ 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. $\endgroup$
    – Asaf Karagila
    Commented Jan 14, 2021 at 21:18
  • $\begingroup$ @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? $\endgroup$ Commented Feb 3 at 0:26
  • $\begingroup$ @theHigherGeometer: Well, it's an illusion. :) $\endgroup$
    – Asaf Karagila
    Commented Feb 3 at 7:53
  • 1
    $\begingroup$ @theHigherGeometer: Yeah. This is exactly why DC is needed for branches in a tree, but not for branches in a countable tree. $\endgroup$
    – Asaf Karagila
    Commented Feb 3 at 9:00

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .