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


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:

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

  • $\begingroup$ Thank you very much for your answer and reference. $\endgroup$ – Metta World Peace Jan 27 '13 at 10:24
  • $\begingroup$ No problem. It was nice waking up to find this question posted! $\endgroup$ – Asaf Karagila Jan 27 '13 at 10:25
  • $\begingroup$ I found the reference... $\endgroup$ – Asaf Karagila Jan 28 '13 at 0:26
  • $\begingroup$ not related to this question. But just for reference in defining Bn are we using axiom of replacement $\endgroup$ – Sushil Aug 20 '15 at 13:42
  • $\begingroup$ Yes.${}{}{}{}{}$ $\endgroup$ – Asaf Karagila Aug 20 '15 at 13:55

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.