Why can't you pick socks using coin flips?

I'm teaching myself axiomatic set theory and I'm having some trouble getting my head around the axiom of choice. I (think I) understand what the axiom says, but I don't get why it is so 'contentious', which probably means I haven't yet digested it properly.

As far as I can make out, one phrasing of the axiom is: for any family of non-empty, pairwise disjoint sets, there exists a set containing exactly one element from each set in the family.

If that's all the axiom states, why is there so much debate around it? If it were stated as there exists a procedure for constructing such a set, that might help me understand (though is that an incorrect statement of the axiom?), but then again:

To use Russell's classic shoes-and-socks example, why won't a coin flip for each pair of socks suffice?

I'm sure this must be a stupid question, but please help me understand why.

Solution 1:

Coin flips don't work because you need to decide which sock goes for "heads" and which one for "tails". Once you've made that assignment you don't need the coin anymore; just assume you always get heads.

Solution 2:

The sets in the "socks example" are such that you cannot possible make a "reasonable distinction" between the two.

It's more than just that. The union of the pairs, while a countable union of pairs, is not countable. It can be made so that it doesn't even have a countably infinite subset (and sometimes it is possible that there is such countably infinite subset).

On the other hand, the union of the pairs $\{H_n,T_n\}$, where $H_n$ and $T_n$ are the possible outcomes of the $n$-th coin flip, is countable. We can simply map $H_n$ to $2n$ and $T_n$ to $2n+1$. This is an easy injection from the possible outcomes into the natural numbers.

To make this slightly more visual, if I will give you countably many sets of pairs of ants, you will be able to examine each pair and discern its elements, but looking for afar, you will not be able to do that for all the pairs at the same time. Similarly here, in this case, you can examine finitely many sets and discern between each set's elements, but you can't do that uniformly for all the pairs.

Solution 3:

Your instinct is basically correct, you can choose socks arbitrarily ("by flipping a coin") without an axiom that lets you. But only because anything you do is necessarily a finite process.

In fact the Axiom of Choice is not needed for finite sets. Various restricted forms of it are theorems of the other axioms: https://mathoverflow.net/questions/32538/finite-axiom-of-choice-how-do-you-prove-it-from-just-zf

AC is controversial when applied to transfinite sets. To over-simplify, you can think of the "controversy" as specifically being related to the fact that it's equivalent to the Well-Ordering Theorem (which my course called the Well-Ordering Principle, but apparently that's ambiguous in other contexts). Nobody ever disputed that finite and countable sets can be well-ordered, it's the rest that are tricky.

There's a joke (that doesn't entirely stand up to analysis, but does reflect the gut instincts of many), that the Axiom of Choice is obviously true, the Well-Ordering Theorem is obviously false, and Zorn's Lemma is obviously incomprehensible. They're all equivalent.

Solution 4:

A point not emphasized in the answers yet is that the axiom of choice is not about what you (or anyone else) can do, like flipping coins) but about the existence of sets. The other ZF axioms ensure the existence of sets defined in various ways, but they do not ensure the existence of random-looking sets. One role of the axiom of choice is to support the intuitive notion that all sets are available, even ones that we can't define.

Solution 5:

It's contentious because it gives you an access to the uncountable infinity of real numbers that hasn't been 'earned' through some constructive process like taking a limit. This results in certain seeming paradoxes, such Banach-Tarski. In addition--though this is a little more of a personal bias--there is nothing in the natural world which seems to motivate it, i.e. no result that I'm aware of which is of interest to physics or any other science depends on it. Math for any practical purpose is 'complete' without it.