Do we really need Choice to pick socks?

Question

It is said that you need the Axiom of Choice to pick one sock from each of infinitely many pairs, but that you don't need it for shoes, since you can just pick all the left shoes.

But Choice is equivalent to the statement that every set can be well-ordered, right? And can't be well-order a two-element (or any finite) set without invoking anything related to Choice? If so, doesn't that mean we don't need Choice to pick socks after all?

Answer 1

The axiom of choice is not needed to choose from one pair of socks. You do that every morning when you put on your socks. In fact, even if you have infinitely many socks, choosing one doesn't require the axiom of choice. Neither does choosing five, or ten socks. That's just existential instantiation and induction.

The axiom of choice is needed in order to choose from infinitely many pairs at once. The reason is that between two socks, there is no "left" or "right", and there is no distinguishing property that we can always say that "given a pair of socks, one of them is such and such". And so the axiom of choice is really needed for that.

More formally, Fraenkel, and later Cohen, showed that this argument is mathematically solid. It is consistent that the axiom of choice fails, and there is a set which is the countable union of pairs, but there is no function which chooses a single element from each pair.

Answer 2

I think Asaf's answer above is generally excellent, but I'll add a few thoughts. I think that this is a place where the metaphors we use to convey mathematics can fail, as there are often several layers of precision that get lost in the metaphor, and become yet more and more clumsy to keep track of. For example: when we say "infinitely many pairs of socks", we do not want to mean "infinitely many copies of the same pair of socks" as in that case, we could have just kept track of where a single sock from the original pair went in each copy (sort of). Instead we want to mean a collection of infinitely many distinct pairs of socks. Now you might object that surely we could just identify all of these together as a single pair. But how exactly? Let's say we have two bins "Sock 1" and "Sock 2". We have to take one of the first pair socks and throw it in "Sock 1" and one of the second pair and ... . You might notice we just used the axiom of choice.

To make some of the above more precise: suppose we have an infinite index set $I$. Then "infinitely many copies of the same pair" corresponds to the set of functions $$f: I \to \{sock_1,sock_2\}$$

while the axiom of choice metaphor corresponds to takeing a collection of two element sets $A_i$, and then finding a function $$I \to \bigcup_{i\in I} A_i$$ Such that $f(i) \in A_i$ for each $i$. This subtle difference is worth meditating on.

Answer 3

You still need axiom of choice to pick a certain order for every pair of socks (this is equivalent to pick a sock for every pair indeed). This does not happen for shoes since shoe pairs come with a predefined order.