Why is the Axiom of Choice not needed when the collection of sets is finite?
According to Wikipedia:
Informally put, the axiom of choice says that given any collection of bins, each containing at least one object, it is possible to make a selection of exactly one object from each bin. In many cases such a selection can be made without invoking the axiom of choice; this is in particular the case if the number of bins is finite...
How do we know that we can make a selection when the number of bins is finite? How do we even know that we can make a selection from a single bin of finite elements?
Then it gives an example:
To give an informal example, for any (even infinite) collection of pairs of shoes, one can pick out the left shoe from each pair to obtain an appropriate selection, but for an infinite collection of pairs of socks (assumed to have no distinguishing features), such a selection can be obtained only by invoking the axiom of choice.
But how can we even make a selection out of a single pair of socks if they don't have any distinguishing features? Is there another axiom being assumed here?
Solution 1:
It's a matter of the basic rules of inference allowed in proofs.
Suppose $\mathcal B$ is a "collection" of bins with only one element, i.e., $\mathcal B = \{S\}$ for some set $S$. The assumption is that $S$ is nonempty. By definition, this means there exists $x \in S$. We can use the existential instantitation rule of inference to fix $x \in S$. Then the association $$\mathcal B \to \bigcup_{T \in \mathcal B} T = S$$ given by $$\{S \mapsto x\}$$ defines a choice function.
Similarly, one can prove by induction that if $\mathcal B$ is a finite collection of nonempty buckets, then a choice function exists - if $\mathcal B_n$ is a collection of $n$ nonempty buckets, then fixing $S \in \mathcal B_n$, it follows that $\mathcal B_n \setminus \{S\}$ is a collection of $n-1$ nonempty buckets.
Solution 2:
The axiom of choice says precisely that if $I$ is a set and, for each $i \in I$, we have a non-empty set $X_i$, then the product $\prod_{i \in I} X_i$ is non-empty. (Elements of products can be identified with choice functions, so non-emptiness of the product is equivalent to existence of a choice function.) When $I$ is finite, this is a statement which can be proved by induction on $|I|$, which does not require choice.