[Math] Finite choice without AC

axiom-of-choiceset-theory

Can anyone explain how we choose one sock from each of finitely many pairs without the axiom of choice? I mean the following quote:
To choose one sock from each of infinitely many pairs of socks requires the Axiom of Choice, but for shoes the Axiom is not needed.
The idea is that the two socks in a pair are identical in appearance, and so we must make an arbitrary choice if we wish to choose one of them. For shoes, we can use an explicit algorithm — e.g., "always choose the left shoe." Why does Russell's statement mention infinitely many pairs? Well, if we only have finitely many pairs of socks, then AC is not needed — we can choose one member of each pair using the definition of "nonempty," and we can repeat an operation finitely many times using the rules of formal logic (not discussed here).

Best Answer

The main challenge here is explaining the precise set-theoretic statement which is meant by "we can make finitely many choices without the axiom of choice"; the proof is then relatively easy. I am going to write in a sort of semi-formal way, which I hope will be clear enough that you can see how to translate into statements of ZF.

By CHOICE, I mean the statement:

Let $X$ and $Y$ be sets, with a map $\pi: X \to Y$. Suppose that, for every $y \in Y$, there is an $x \in X$ with $\pi(x) = y$. Then there is a subset $K$ of $X$ such that, for every $y \in Y$, there is a unique $x \in K$ with $\pi(x) = y$

So $X$ is the set we are choosing from (the set of all socks in the universe), $Y$ is the number of choices we're making, and $K$ is the set of choices we make.

Now, I want to show that this statement is true if $Y$ is finite. So we must discuss the definition of finite.

For any set $Z$, define $s(Z) = Z \cup \{ Z \}$. A set $I$ is called inductive if $\emptyset \in I$ and if, for all $Z \in I$, we also have $s(Z) \in I$. One can show (see any intro set theory book) that there is a unique set $\mathbb{N}$ such that (1) $\mathbb{N}$ is inductive and (2) every inductive set contains $\mathbb{N}$. A set $Y$ is called finite if it can be put in bijection with some member of $\mathbb{N}$.

We have now finished the definitions, and can move to the proof. We are going to show that, if $A \in \mathbb{N}$, if there is a bijection $Y \to A$, and if we have any map $\pi: X \to Y$ satisfying the hypotheses of CHOICE, then the conclusion of CHOICE holds.

First of all, composing $\pi: X \to Y$ with the bijection $Y \to A$, we may assume that $Y$ is an element of $\mathbb{N}$. (Exercise!)

Let's say that "we may make $Y$ choices" if CHOICE is true for $Y$, for all $\pi$ and $X$. Let $T \subseteq \mathbb{N}$ be the set of those elements $Y$ of $\mathbb{N}$ for which we can make $Y$ choices. (Exercise: Actually write out the definition of $T$ set theory notation.) We will show that $T$ is inductive.

First of all, we can make $\emptyset$ choices. Take $K = \emptyset$.

Now, suppose that we can make $Z$ choices. We must show that we can make $s(Z)$ choices. Consider any map $\pi: X \to s(Z)$. Let $X' = \pi^{-1}(Z)$, using the inclusion $Z \subseteq s(Z)$. So, by hypothesis, there is a subset $K' \subseteq X'$ such that, for every $y \in Z$, there is a unique element $x \in K'$ with $\pi(x) = y$. Also, by the hypotheses of AC, there is an element $x \in X$ such that $\pi(x) = \{ Z \}$. Take $K = K' \cup \{ x \}$.

We have now shown that $T$ is inductive, so $\mathbb{N} \subseteq T$. But also $T \subseteq \mathbb{N}$, by construction. So $T = \mathbb{N}$. We have shown that we can make $Y$ choices for every $Y \in \mathbb{N}$, as desired.

By the way, you may notice that this proof looks a lot like a proof by induction. This is how you write a proof by induction in ZF. Set theorists writing for a more experienced audience would just say "do it by induction", without all the explanation I've given.

Related Question