Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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

share|cite|improve this question
up vote 9 down vote accepted

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

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

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

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