Existence of how many sets is asserted by the axiom of choice in this case?

Question

Applying the axiom of choice to $\{\{1,2\}, \{3,4\}, \{5,6\},\ldots\}$, does only one choice set necessarily exist, or all of the $2^{\aleph_0}$ I "could have" chosen? Or something in between? It seems if only one, then I didn't really have much of a choice; I just had to take what the universe gave me. But letting them all exist has its own problems.

Answer 1

In this case you don’t need the axiom of choice to get a choice function: just pick the smaller member of each pair. Various other choice functions are explicitly definable: we could just as well pick the larger member of each pair, for instance. Or we could pick the member that is divisible by $3$ if there is one, and the smaller one otherwise.

In general the axiom of choice gives you more than one choice function. Let $\{A_i:i\in I\}$ be a family of non-empty sets, and let $\varphi:I\to\bigcup_{i\in I}A_i$ be a choice function. For each $i\in I$ let

$$B_i=\begin{cases} A_i,&\text{if }|A_i|=1\\ A_i\setminus\{\varphi(i)\},&\text{otherwise}\;; \end{cases}$$

then the axiom of choice gives us a choice function $\psi:I\to\bigcup_{i\in I}B_i$ for the family $\{B_i:i\in I\}$. This $\psi$ is clearly also a choice function for the original family, and it’s different from $\varphi$ unless every $A_i$ was a singleton. Eventually, once the appropriate cardinal arithmetic has been developed, one can prove that it gives us

$$\prod_{i\in I}|A_i|$$

choice functions.

Answer 2

The axiom of choice asserts there exists one choice function. However, like the problem with many vermin and pests, we usually have that if there is one then there are many (unless, all sets are singletons).

Specifically for sets of natural numbers you don't need the axiom of choice in order to prove that there are continuum many choice functions.

But generally speaking, if you know that $\{A_i\mid i\in I\}$ admits a choice function, and say all the sets have at least two elements, then for every $a\in A_i$ there is a choice function such that $f(i)=a$. How? Simply fix one choice function, and change it on one coordinate at a time. This means that there are plenty of choice functions indeed.

Without the axiom of choice we can sometimes manufacture examples where there are a few choice functions, in the sense that the number of them is exactly what you'd get by one fixed choice function and finitely many changes to it. That's odd.