76
$\begingroup$

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.

$\endgroup$
15
  • 8
    $\begingroup$ How can you flip a coin uncountably many times? $\endgroup$
    – Umberto P.
    Mar 17, 2014 at 15:41
  • 30
    $\begingroup$ Immediate upvote for the question title $\endgroup$
    – user132181
    Mar 17, 2014 at 15:42
  • 4
    $\begingroup$ @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. $\endgroup$
    – Santiago Canez
    Mar 17, 2014 at 15:44
  • 8
    $\begingroup$ I first read this as "why can't you pick stocks using coin flips?" $\endgroup$
    – CoderDennis
    Mar 17, 2014 at 18:07
  • 2
    $\begingroup$ @CoderDennis But of course you can pick stocks that way, and probably better than any Expert Advisor can do for you :-) $\endgroup$
    – Carl Witthoft
    Mar 17, 2014 at 18:37

6 Answers 6

Reset to default
61
$\begingroup$

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.

$\endgroup$
4
  • $\begingroup$ 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). $\endgroup$
    – The Ugly
    Mar 18, 2014 at 18:08
  • 5
    $\begingroup$ The problem is that how do you "randomly" choose which sock is heads? It's like Zeno's dichotomy paradox. $\endgroup$
    – vadim123
    Mar 18, 2014 at 18:29
  • $\begingroup$ What about if you use a nonrandom method to assign heads and tails? $\endgroup$
    – hippietrail
    Mar 19, 2014 at 2:12
  • 4
    $\begingroup$ @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. $\endgroup$
    – Asaf Karagila ♦
    Mar 19, 2014 at 2:18
14
$\begingroup$

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.

$\endgroup$
15
  • 4
    $\begingroup$ If you assume the axiom of choice, sure. If not, then no. $\endgroup$
    – Asaf Karagila ♦
    Mar 17, 2014 at 19:46
  • 1
    $\begingroup$ @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. $\endgroup$
    – Asaf Karagila ♦
    Mar 18, 2014 at 10:23
  • 2
    $\begingroup$ @phs: Then you are wrong. You do need some part of the axiom of choice in order to prove that the countable union of countable sets, or even the countable union of finite sets, is countable. And the axiom of choice gets into the game exactly at the stage where you wrote "etc." in your first comment. $\endgroup$
    – Asaf Karagila ♦
    Mar 18, 2014 at 18:26
  • 3
    $\begingroup$ @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. $\endgroup$
    – Asaf Karagila ♦
    Mar 18, 2014 at 18:29
  • 1
    $\begingroup$ @phs: Maybe your confusion comes from the meaning of the term "countable". It gives you the existence of a bijection with the natural numbers (an enumeration of the set), but it does not give you (choose for you) such a bijection. For one set (or finitely many) existential elimination will hand you a concrete enumeration, but not so for infinitely many sets at a times. $\endgroup$
    – Marc van Leeuwen
    Mar 19, 2014 at 13:11
8
$\begingroup$

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.

$\endgroup$
5
  • $\begingroup$ +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. $\endgroup$
    – Kyle Strand
    Mar 18, 2014 at 21:23
  • 2
    $\begingroup$ Also, Wiki claims that the originator of this quote is Jerry Bona. Credit where credit is due. $\endgroup$
    – Kyle Strand
    Mar 18, 2014 at 21:24
  • $\begingroup$ @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 :-) $\endgroup$
    – Steve Jessop
    Mar 19, 2014 at 11:24
  • 2
    $\begingroup$ And perhaps also credit to Paul Cohen for proving that it's undecidable in ZF anyway, which helps the joke work :-) $\endgroup$
    – Steve Jessop
    Mar 19, 2014 at 11:27
  • $\begingroup$ To be fair, mathematicians frequently say that things are "obvious" or "clear" when (to the reader) they are not! $\endgroup$
    – Kyle Strand
    Mar 19, 2014 at 16:20
7
$\begingroup$

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.

$\endgroup$
1
  • $\begingroup$ 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. $\endgroup$
    – Dustan Levenstein
    Mar 17, 2014 at 18:51
2
$\begingroup$

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.

$\endgroup$
6
  • 2
    $\begingroup$ 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. $\endgroup$
    – Asaf Karagila ♦
    Mar 17, 2014 at 16:35
  • 2
    $\begingroup$ 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. $\endgroup$
    – cody
    Mar 17, 2014 at 17:28
  • $\begingroup$ Please share concrete examples of this, but the Hahn-Banach theorem does not depend on the AoC according to the wikipedia page. $\endgroup$
    – Matt Phillips
    Mar 17, 2014 at 17:32
  • 1
    $\begingroup$ 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 ;-) $\endgroup$
    – Steve Jessop
    Mar 17, 2014 at 18:38
  • 3
    $\begingroup$ The Hahn-Banach theorem is not provable without some fragment of the axiom of choice. Arzela-Ascoli too. $\endgroup$
    – Asaf Karagila ♦
    Mar 17, 2014 at 18:53
0
$\begingroup$

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.

$\endgroup$
1
  • 1
    $\begingroup$ 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). $\endgroup$
    – Steve Jessop
    Nov 16, 2014 at 14:02

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .