Equivalent of the countable axiom of choice?

Question

Given $\{A_n\}_{n \in \omega}$ a countable collection of nonempty sets, there is a function $f$ with domain $\omega$ and $f(n) \in A_n$ for each $n \in \omega$. Is it the case that it is equivalent to , there is some infinite subset $I \subseteq \omega$ and $f : I \to \bigcup_{n \in I} A_n$ with $f(n) \in A_n$ for every $n \in I$? If not, could we make them equivalents by imposing an upper bound of cardinality of $A_n$?

Answer 1

This principle is sometimes called $\bf PCC$, Partial Countable Choice. I have seen it dubbed "weak countable choice" as well in other papers. In this spirit I shall denote $\bf CC$ the axiom of countable choice.

The answer is that it is equivalent to countable choice, and some of its restrictions are also equivalent to the analogous restrictions of countable choice.

Clearly $\bf CC\implies PCC$, so it only remains to show the other direction, suppose that $\bf PCC$ holds and let $\{A_n\mid n\in\omega\}$ be a family of non-empty sets. Let $B_n=\prod_{k<n}A_k$, then $\{B_n\mid n\in\omega\}$ is a family of non-empty sets. Let $I\subseteq\omega$ such that we can choose $b_i\in B_i$ for $i\in I$.

Now we define a choice function from $\{A_n\mid n\in\omega\}$ as follows:

$$F(n)=b_i(n)\quad\text{such that}\quad i=\min\{i\in I\mid n<i\}$$

This is a well-defined function, because for every $n$ there is a unique $i$ with this property, and it defines a choice function on all the $A_n$'s.

It is easy to see the the above proof generalizes to the cases where $A_n$ are limited to a family of cardinalities which is closed under finite products (we want that the $B_n$'s would be well-defined). So for example this is true if we limit $A_n$'s to be finite, or countable, or have size $2^{\aleph_0}$.

I am fairly certain that the reverse implication does not work for every family of cardinalities, but I cannot recall an immediate counterexample. Incidentally I was going through some papers looking for something and I came across the following paper which provides a construction of a counterexample in lines of the above suggestion:

• Hall, E. and Shelah, S. Partial choice functions for families of finite sets. ArXiv (2011)

---

You might want to take a look at Herrlich's The Axiom of Choice, and in particular in Section 2.2, Theorem 2.12 and some exercises (in particular the fifth exercise).