9
$\begingroup$

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?

$\endgroup$
  • 3
    $\begingroup$ You don't need choice to pick socks from a single pair. This kind of fashion decision gets difficult with infinitly many pairs of socks. - It is not really simpler by picking one of two possible well-orders for infinitely many pairs instead of picking a sock for infinitely many pairs. $\endgroup$ – Hagen von Eitzen Nov 28 '14 at 20:30
  • $\begingroup$ Since pairs of socks where the left and right sock are marked as such become more common, it is perhaps time to think of a different example. $\endgroup$ – Daniel Fischer Nov 28 '14 at 20:39
  • 2
    $\begingroup$ @Daniel: I have never seen such a pair in my entire life. At best, I've seen people whose socks lie in a puddle of mess, and they choose arbitrary pairs each time. In that case these people don't even have a well-defined "pair of socks", so choosing becomes impossible. $\endgroup$ – Asaf Karagila Nov 28 '14 at 20:42
  • $\begingroup$ @Asaf A picture of a trekking sock with indication that it's a Right sock, also Toe socks. $\endgroup$ – Daniel Fischer Nov 28 '14 at 20:52
  • 3
    $\begingroup$ @Jessica: Thankfully, I'm not a five year old girl. I do have a niece, but I don't rummage through her socks drawer. So I couldn't tell. $\endgroup$ – Asaf Karagila Nov 29 '14 at 11:19
19
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ But if the statement that every set can be well-ordered is equivalent to Choice, and if we can well-order a set of two elements, doesn't that mean we don't need Choice for this case? Or are my assumptions incorrect? $\endgroup$ – Nishant Nov 28 '14 at 22:08
  • 1
    $\begingroup$ But you don't order the set of two elements. You order all the set of two elements, at the same time, which is equivalent to saying to that you order the union of all these sets of two elements, which is no longer a finite set at all. It's an infinite set. $\endgroup$ – Asaf Karagila Nov 28 '14 at 22:12
  • $\begingroup$ Hmm, so the thing that's equivalent to choice is not "Every set can be well-ordered" but "Given any collection of sets, each set in the collection can be well ordered"? $\endgroup$ – Nishant Nov 28 '14 at 22:19
  • 2
    $\begingroup$ No, that is equivalent to choice, because just take $\{X\}$ as a collection, and it implies $X$ can be well-ordered. $\endgroup$ – Asaf Karagila Nov 28 '14 at 22:21
  • $\begingroup$ @Nishant If you're still confused, you could ask another question to not invalidate any of the answers to this one and make it so good that this one will get marked as a duplicate instead of that one. It can be shown that the axiom of choice is equivalent to the well ordering theorem. It can also be shown that each set satisfies the axiom of choice if and only if it can be well ordered. To show that a set of pairs has a choice function, you have to assume that the union can be well ordered and not just that each pair can be well ordered as described in my answer. $\endgroup$ – Timothy Apr 12 '18 at 18:39
12
$\begingroup$

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.

$\endgroup$
  • 2
    $\begingroup$ The second sentence is excellent. (I have no qualms about the first sentence either. :-)) $\endgroup$ – Asaf Karagila Nov 29 '14 at 11:20
1
$\begingroup$

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.

$\endgroup$
-1
$\begingroup$

Yes you do need the axiom of choice to show that for any set of pairs of socks, there is a choice function that picks one sock from each pair. Each sock from one of those pairs can either function as a left sock or as a right sock so that doesn't give us a way to define in terms of each pair of socks in that set of pairs one sock from that pair. The fact that each pair of socks in that set of pairs can be well ordered is not enough to show that there is a function that assigns to each pair of socks one sock in that pair. To show that such a function exists, you have to assume that the union of all pairs of socks in that set of pairs can be well ordered.

Suppose you have a set of infinitely many pairs of socks. If all those socks were instead shoes and any two socks in a pair were instead a left shoe and a right shoe, then a choice function would exist so how could such a function not exist just because they're socks instead of shoes? That's because to show that the set of pairs of socks has a choice function, you have to assume that that set is a set that can be gotten by turning each shoe in the union of a set of pairs of shoes into a sock and that assumption can't be proven without using the axiom of choice.

$\endgroup$
  • $\begingroup$ It's better for people to give a reason for downvoting an answer if they think it's possible to improve it enough to not be worthy of deletion. If it would have been better to write this answer than no answer at the time when this question did not yet have an answer, I'm not sure it's worth downvoting it instead of writing a comment explaining why another answer renders this answer useless. I think this answer is the only answer that actually answers the question by pointing out the flaw in thinking the ability to well order each pair shows that you can pick one sock from each pair. $\endgroup$ – Timothy Apr 10 '18 at 21:32
  • 1
    $\begingroup$ I wouldn't consider this bad enough to need a downvote -- but perhaps someone thought it doesn't add much to the answers that are already present? $\endgroup$ – hmakholm left over Monica Apr 10 '18 at 21:57
  • $\begingroup$ I think all the other answers are missing the thing my answer didn't miss but my answer is also missing something so maybe we could pick one answer to improve then delete some of the other answers. I think sometimes, a question should have more than one answer because sometimes two of its answer are needed because for some people, one of those two answers is not good enough and for other people, the other one of those two answers is not good enough. $\endgroup$ – Timothy Apr 10 '18 at 23:27

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.