Why is the Axiom of Choice not needed when the collection of sets is finite?

Question

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?

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

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

Answer 3

This is a good question; the main answer is that making a single choice out of a single bin is a matter of logic.

Specialized to this particular situation, if $S$ is a set and you have proven $\exists x : x \in S$, then logic allows you to introduce a new constant symbol (say, $a$) along with the corresponding an axiom $a \in S$.

The usual interpretation of this mechanic is that $a$ represents a 'choice' of an element of $S$, although this is by no means the only way to interpret this sort of thing:

• We might instead interpret $a$ as simply being a dummy variable, so that what we're doing is defining a function of $S$
• We might interpret $a$ as some sort of 'generic' element of $S$ rather than a choice of a specific element
• Some forms of logic allow you to introduce $a \in S$ even when $S$ is an empty set; naturally this does not lend itself well to interpreting $a$ as a choice of an element!

Whatever way we look at it, we can use it to prove we can make a choice from a single bin in set theory; the main steps are

• Introduce $a \in S$
• Show $\{ (S, a) \}$ is a choice function on $\{ S \}$

Whatever our philosophical opinions on logic are, this construction defines a function

$$ S \to \operatorname{ChoiceFunctions}(\{ S \}) $$

where $\operatorname{ChoiceFunctions}(X)$ means the collection of all choice functions on $X$. This, together with the hypothesis that $S$ is nonempty, implies that $\operatorname{ChoiceFunctions}(\{ S \}) $ is nonempty as well.

---

Finite choice is basically the same. In an ad-hoc fashion you could repeat this sort of argument by repeatedly introducing one variable at a time. Alternatively (in set theory) you can set up a recursive definition and show finite choices can be made by induction; IIRC the proof is straightforward, but complicated.

Answer 4

This isn't a direct answer to the question, but a way to think about the axiom of choice.

The axiom of choice is a generalization of finiteness. It's related (by, for instance, the compactness theorem in logic, and Tychonoff's theorem in topology) to topological compactness, which is another generalization of finiteness.

Without the axiom of choice, you can sometimes specify a choice: "Pick the left shoe from each pair." If you can make (read: define) such a specification, you don't need the axiom of choice, because you can point to that specification as your choice.

Consider how each equivalent definition of Choice is true in the finite setting:

• "Every finite product of non-empty sets has at least one element." If you're given a few sets, you can select one from each, one step at a time. (If you have an infinite number of sets, you'd need an infinite number of steps.)
• "Every finite set can be well-ordered." If you pull elements out one at a time, that's a well-ordering. (Again, you'd need an infinite number of steps for an infinite set.)
• "Every finite vector space has a basis." Choose a non-zero vector. Then take a vector not in the linear subspace generated by the first vector. Then take a vector not in the span of the first two vectors. Eventually, you'll run out of vectors.
• "Every two finite cardinals are comparable." Count up from 0 until you get to the first one. That's the smaller one. If you get to both at once, they're equal.

In an informal sense, the axiom of choice says you can always take an infinite number of (certain kinds of) steps in finite time. And you can only follow a statement/proof that takes finite time to read. The axiom of choice is also non-constructive: you can't use it to make a "real" example, because you'd need infinite construction time.

---

More on finiteness and statements:

Let $X = X_0 \times X_1 \times X_2 \times \dots$ be a product of sets. Then the axiom of choice says

$$\exists x_0 \in X_0 \ \exists x_1 \in X_1 \ \exists x_2 \in X_2 \ \exists \dots \ \text{s.t.} (x_0, x_1,x_2, \dots) \in X$$

But the first ellipsis doesn't actually make sense in logic. No mathematical logic rules allow an infinite number of quantifiers. The axiom of choice sort of says, "That's okay, it still works."

On the other hand, you can define the "left shoe" choice with only a finite number of quantifiers. Let $I$ be the index set for the product. Then

$$\{\text{left}_i \in X_i | i \in I\} \in X$$

is a choice of all the left shoes, with one implicit quantifier over the index set.

Answer 5

This is essentially just the power of the pairing axiom. Consider the case $n=3$: If $A,B,C$ are nonempty, then so is $A\times B\times C$. The proof of this is easy: if $x\in A,y\in B,z\in C$, then $(x,y,z)\in A\times B\times C$.

We can write this schematically as:

$$\exists x\exists y\exists z\,((x,y,z)\in A\times B\times C)\implies \exists w\,(w\in A\times B\times C),$$

where we can see the pairing axiom (which asserts that $(x,y,z)$ is a set) doing the work of compressing $n$ existence quantifiers into one.

I want to make it clear that there is no actual choosing going on here. It is not required that there be any rule to find a particular element of $A$ - they might be "indistinguishable socks" for all we care. It doesn't matter, because the ambiguity of the original choices has been off-loaded to ambiguity in the output element of $A\times B\times C$.

The problem with this method is that pairing only works for $n=2$, or by induction, for finite $n$. Beyond this we must postulate an axiom or use additional structure in the $A_i$ sets in order to produce choice functions.

Answer 6

If I buy a pair of white socks, and I have never worn either of them, then they don't have any distinguishing features. Nevertheless, people make these sort of choices on a daily basis.

You might argue, while indiscernible, the two socks surely have some feature which distinguishes them! And you'd be correct. Although you might not be able to actually point the finger and say "Aha! This is what distinguishes them!", and you might have to resort to something like their particles or some other microscopic-level sort of difference.

But if I now ask you to choose from several pairs at the same time, you first need to inspect each pair under a microscope (or some other more destructive tests) in order to be able to describe a choice process. Maybe in one pair the cotton impurity is higher in one, and maybe in another it is the same. So each pair needs to go under careful checks just so you can tell me what sock was chosen from each pair.

Of course, you can ditch this method, and just go "This sock, that sock, this sock, and that sock". But that is not going to work if you have infinitely many socks.

And indeed, in the formal version of the socks analogy—which is all that it is, an analogy, and we would do well to remember that—we have sets of two elements and we cannot choose from all these pairs simultaneously. Of course, given one pair, we can show there are differences between the two elements of the set, after all they are not the same element, but we cannot point at a single property that will work for all pairs at the same time. Which is why the axiom of choice is needed in such case.

Answer 7

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?

I wish to address a misconception here. The axiom of choice does not concern picking an object from indistinguishable ones, but rather that we do not need a way to distinguish them to be able to pick one of a collection. For example consider any infinite group $G$. There is no way you are going to be able to uniquely identify a non-identity element in $G$, because you know nothing about $G$. But the axiom of choice (applied to the non-identity elements in $G$) states that we can indeed pick one of them. Of course, since we only have one picking to do, we do not need the axiom of choice at all. But this illustration is to make clear what exactly is the issue of picking; the objects in each non-empty set may very well be distinguishable but we do not care.

Answer 8

This is a rider to the excellent answers given by Clive and Dustan. To address the case of a single pair of socks: assume you are given an unordered pair of socks $\{x, y\}$ such that the socks $x$ and $y$ have no distinguishing features. Then $x$ and $y$ are the same sock. In this case, you should take the sock back to the store and claim Leibniz's law of the identify of indiscernibles as an unchallengeable reason for a refund.

Answer 9

Suppose discourse universe is formed by objects. Starting with

Axiom 1 (Empty set). There exists a set $\emptyset$ such which contains no elements, i.e., for every object we have $x\notin\emptyset$.

We can prove by contradiction the folling proposition:

Proposition 2 (Single choice). Let $X$ be a non-empty set. Then there exists an objects $x$ such that $x\in X$.

Now we can show that for any collection of non-empty sets, we can choose a element for each set. (Use induction to prove it.)

Proposition 3 (Finite choice). Let $n\ge1$ be a natural number, and for each natural number $1\le i\le n$, let $X_i$ be a non-empty set. Then there exists an $n$-tuple $(x_i)_{1\le i\le n}$ such that $x_i\in X_i$ for all $1\le i\le n$. In other words, if each $X_i$ is non-empty, then the set $\prod_{1\le i\le n}X_i$ is also non-empty.

The axiom of choice asserts that this proposition is also true for infinite cartesian products.

Axiom 4 (Choice). Let $I$ be a set, and for each $\alpha\in I$, let $X_\alpha$ be a non-empty set. Then $\prod_{\alpha\in I}X_\alpha$ is also non-empty. In other words, there exists a function $(x_\alpha)_{\alpha\in I}$ which assigns to each $\alpha\in I$ an element $x_\alpha\in X_\alpha$.

This is very intuitively appealing axiom; in some sense one one is just apllying Proposition 2 over and over again. But it does not follow from the other axioms of set theory.