# 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 quite digested it properly yet.

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?

-
How can you flip a coin uncountably many times? –  Umberto P. Mar 17 '14 at 15:41
Immediate upvote for the question title –  user132181 Mar 17 '14 at 15:42
@MGA, the axiom of choice applies to any family of sets, no matter the size. Moreover, it's not the statement (which is pretty intuitive as you've noticed) that is contentious, it's the things you can derive as a result and the fact that it does not follow from the other standard axioms of set theory that cause people to question it. –  Santiago Canez Mar 17 '14 at 15:44
I first read this as "why can't you pick stocks using coin flips?" –  CoderDennis Mar 17 '14 at 18:07
@CoderDennis But of course you can pick stocks that way, and probably better than any Expert Advisor can do for you :-) –  Carl Witthoft Mar 17 '14 at 18:37

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.

-
Ah, because assuming you randomly choose which pair is heads, adding a coin flip is unnecessary, because it would randomly choose a randomly designated object (50% chance to be assigned heads in the first place). –  The Ugly Mar 18 '14 at 18:08
The problem is that how do you "randomly" choose which sock is heads? It's like Zeno's dichotomy paradox. –  vadim123 Mar 18 '14 at 18:29
What about if you use a nonrandom method to assign heads and tails? –  hippietrail Mar 19 '14 at 2:12
@hippietrail: Since random is not well-defined, what is not random? And why would such process exist anyway? If you can make these assignments, random or otherwise, then you can choose from the pairs. But the point is that you can't really do that in the general case without using the axiom of choice. –  Asaf Karagila Mar 19 '14 at 2:18

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.

-
Every union of countably many countable sets (and even more for finite ones) is countable. –  Paŭlo Ebermann Mar 17 '14 at 19:40
If you assume the axiom of choice, sure. If not, then no. –  Asaf Karagila Mar 17 '14 at 19:46
Really? It seems like I can take the first of the first set (first stripe), 1st of 2nd & 2nd of 1st (2nd stripe), 1st of 3rd, 2nd of 2nd, 3rd of 1st (3rd stripe), etc. –  phs Mar 18 '14 at 0:01
@phs: But that "etc." is exactly where the axiom of choice gets involved in the process. And if you are dealing with "pairs of socks", then the axiom of choice fails. So the process eventually fails. –  Asaf Karagila Mar 18 '14 at 10:23
@phs: In order to write the sets in a matrix you need to be able and say which is the first, second, and so on, in each of the sets. If you have that, then yes the union is countable. But the point of the socks example is that you can't have that without assuming the axiom of choice. Because you have to choose for every given set which element of that set is the first, the second, and so on. And indeed there are many examples of models where the axiom of choice fails and there are countable families of countable sets (finite, of bounded size, infinite, what have you) whose union is not. –  Asaf Karagila Mar 18 '14 at 18:29

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: http://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.

-
+1 for "countable vs. uncountable". –  yo' Mar 17 '14 at 21:45
+1 because I was going to put the joke in a comment, but you've obviated that need. Though I'm not sure what you mean by "doesn't entirely stand up to analysis," since the whole point of the joke is that in this case intuition and logic are at odds. –  Kyle Strand Mar 18 '14 at 21:23
Also, Wiki claims that the originator of this quote is Jerry Bona. Credit where credit is due. –  Kyle Strand Mar 18 '14 at 21:24
@KyleStrand: I just meant that if you take it literally you end up with someone saying, "well, the AoC looks false to me, so you can't say it's 'obviously' true". I'm not claiming that standing up to analysis is a desirable property of jokes in general, or that this one suffers the lack :-) –  Steve Jessop Mar 19 '14 at 11:24
And perhaps also credit to Paul Cohen for proving that it's undecidable in ZF anyway, which helps the joke work :-) –  Steve Jessop Mar 19 '14 at 11:27

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.

-
The idea that the axiom of choice "supports the intuitive notion that all sets are available", while great for a superficial intuitive understanding of the axiom, is utterly false when you dig deeper. Gödel's proof that the axiom of choice is consistent with ZF actually starts with a model of ZF and then strips it down, the exact opposite of what you would intuitively think the axiom of choice would require. –  Dustan Levenstein Mar 17 '14 at 18:51

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.

-
This is not quite true. There are some nice examples of theorems often used in physics (including quantum mechanics related theorems) which consistently fail without the axiom of choice. –  Asaf Karagila Mar 17 '14 at 16:35
As a more concrete example, the Hahn-Banach theorem is a powerful and useful theorem of Hilbert spaces which is commonly used in QM and operator theory. –  cody Mar 17 '14 at 17:28
Please share concrete examples of this, but the Hahn-Banach theorem does not depend on the AoC according to the wikipedia page. –  Matt Phillips Mar 17 '14 at 17:32
Specifically, the Wikipedia page says that Hahn-Banach is proved by the ultrafilter lemma. Which sounds like the kind of thing I might have known 15 years ago, but my memory isn't good enough to agree or disagree with Wikipedia's claim ;-) –  Steve Jessop Mar 17 '14 at 18:38
The Hahn-Banach theorem is not provable without some fragment of the axiom of choice. Arzela-Ascoli too. –  Asaf Karagila Mar 17 '14 at 18:53

May I add to Andreas Blass' answer? The axiom of choice is a statement that the set-theoretic universe contains lots of sets. In terms of your example with socks, the question is: If you have a countable number of pairwise disjoint 2-element sets does there exist a set which contains exactly one element from each of these 2-element sets. The axiom of choice says yes, such a set does exists, but there are models of set theory in which the axiom of choice fails and in which no set meets each of the 2-element sets in exactly one element.

-
Contrariwise you can say that AoC asserts the universe doesn't contain "too many" sets ;-) Goedel's constructible universe satisfies AoC, and doesn't have any sets that aren't part of the set theoretic universe you construct it in, but it excludes any sets that are so complex they don't have choice sets (or can't be well-ordered). –  Steve Jessop Nov 16 '14 at 14:02