18
$\begingroup$

In the wikipedia article, two examples are given which use/ do not use the axiom of choice. They are:

  • Given an infinite pair of socks, one needs AC to pick one sock out of each pair.

  • Given an infinite collection of pairs of shoes, one shoe can be specified without AC by choosing the left one.

Aren't these equivalent examples (just with different objects)? Why can't one just choose the left sock in (i) (so that AC is not needed)?

|cite|improve this question
$\endgroup$
  • 10
    $\begingroup$ The point is that left and right socks are indistinguishable, while left and right shoes are distinguishable. $\endgroup$ – Jason DeVito Dec 27 '10 at 20:05
  • 19
    $\begingroup$ @Jason DeVito: I have checked this experimentally. $\endgroup$ – Andrey Rekalo Dec 27 '10 at 20:11
  • 2
    $\begingroup$ On the other hand, if you have an infinite number of people each wearing a pair of socks, then you can pick one sock from each pair without having to invoke the Axiom of Choice; by having the socks worn, you don't just have the set of pair of socks, but they now come with an ordering among each pair. $\endgroup$ – Arturo Magidin Dec 27 '10 at 21:51
  • 4
    $\begingroup$ What is an infinite pair? $\endgroup$ – Mariano Suárez-Álvarez Dec 28 '10 at 3:33
  • 1
    $\begingroup$ @newlogic because you need the axiom of choice to pick it $\endgroup$ – Kenny Lau Sep 25 '17 at 17:54
11
$\begingroup$

In both examples you are given an infinite family of sets of size 2, and a choice function picks an element of each family. In the case of the sets of shoes, each set comes with an ordering (left, right), and so we can define a choice function explicitly. In the case of pairs of socks, this is not the case: Of course, given any pair, we can assign an ordering to it so we can select one of the two socks. However, there is no obvious way of uniformly doing this for all pairs at the same time. This means (at least intuitively) that there is no way of defining a choice function. Its existence can only be granted by applying the axiom of choice.

There are several variants of this example. One that may be useful to think about is the following: One can show explicitly that if $A_n$ is a set of reals and $|A_n|=2$ for each $n\in{\mathbb N}$, then $\bigcup_n A_n$ is a (finite or infinite) countable set. However, it is consistent with the axioms of set theory except choice that there is a sequence $(A_n\mid n\in{\mathbb N})$ of sets, each $|A_n|=2$, and yet $\bigcup_n A_n$ is not countable. Although the construction of the model where this happens is technical, the point is that this formalizes the intuition that there is no "explicit" way of choosing a sock from each pair, simultaneously, and that any way of doing so is essentially non-constructive.

For more on the set theoretic versions of these collections of socks (Russell cardinals), see here.

|cite|improve this answer
$\endgroup$
  • $\begingroup$ A reasonably gentle introduction to these ideas is the article on the Axiom of Choice that Thomas Jech wrote for the "Handbook of Mathematical Logic". He also wrote a book on the subject, but it is more technical. $\endgroup$ – Andrés E. Caicedo Dec 28 '10 at 0:10
  • $\begingroup$ +1 but, Re: "given any pair, we can assign an ordering to it so we can select one of the two socks. However, there is no obvious way of uniformly doing this for all pairs at the same time." Why not? If it's possible to assign an ordering to the first pair and all pairs of socks are pairwise indistinguishable, what's the meaning of uniformly in this context? $\endgroup$ – alancalvitti Feb 20 '13 at 21:24
  • $\begingroup$ @alan What I mean is that there is no "rule" that describes how to choose a sock from a pair. For any given pair, we can of course pick one (we have two ways of doing this), but given an infinite collection of pairs of socks, there is no way to exhibit a "simultaneous" choice of a sock for each pair. It is not that we have been literally given the same pair infinitely many times (if so, we have a way: We make one decision, and copy it on each pair). Indeed, $\prod_n \{0,1\}$ has size $\mathbb R$ without any use of choice, even if (consistently) some $\prod_n A_n$ with each $|A_n|=2$ are empty. $\endgroup$ – Andrés E. Caicedo Jul 4 '14 at 16:04
  • $\begingroup$ Another intuitive way to think about this: I can give a set of instructions so that, any person following them will pick up the same collection of shoes (one from each pair). There is no such ("explicit") set of instructions for socks. $\endgroup$ – Andrés E. Caicedo Dec 15 '17 at 18:13
  • $\begingroup$ go ahead, what is the set of instructions? $\endgroup$ – alancalvitti Jan 1 '18 at 18:52
9
$\begingroup$

The idea behind the axiom of choice is to tell you how to choose when you can't necessarily distinguish between the items.

When you take out a pair of socks from the closet (or drawer, etc) you can't tell which one you had on your left foot and which on your right, or which one is this and which one is that. If you can, well... you need to remember to let someone else make sure you have matching socks :-)

The idea, formally, is that if you take a product of infinitely many non-empty sets then it is not empty, namely there is a function in the product which returns an element in each coordinate.

Formally, given a set $I$ such that $\forall i\in I$ we have $A_i\not=\emptyset$ then there is $F\colon I\to\bigcup_{i\in I} A_i$ for which $F(i)\in A_i$.

If you think about it, this is not a "strange" requirement when you are discussing mathematics, and it might come naturally in many places.

For example, for any two sets $A,B$ if there is $f\colon A\to B$ which is surjective then there is an injective $g\colon B\to A$. What are we doing? In a sense we choose one representative in each equivalence class of $a_1\sim a_2\iff f(a_1) = f(a_2)$. But if we have infinitely many equivalence classes - then we (usually) need to invoke some choice axiom (perhaps the axiom of choice, or countable choice, or dependent choice, etc...)

However, many times the use is not of the axiom of choice, but rather an equivalent principle called "Zorn's Lemma", it states that if you have a partial order in which every chain is bounded from above - then there is some maximal element (that is no one is strictly above it in the order). Again not something that is unreasonable if you want infinitary processes to "act" similar to finitary ones.

Addendum:
After I gave it some extra thought, I came up with something that might clear up the things. There is a concept which is "a definable element", that is that you can write some formula $\psi(x)$ such that $a$ is the only element (suppose in $A$) which satisfies the formula. If you want to choose from infinitely many sets then you need to be able and tell which element you have chosen.

If you have at least one definable element in each set, suppose by some uniform formula $\varphi(x)$, then you can clearly choose the one element defined by $\varphi$. However if there are many definable elements in each set, or infinitely many formulae are needed - then you cannot express it simply, and then you must assume that you can do it.

And as I remarked above, we simply want infinitary processes to behave well, like finitary ones.

|cite|improve this answer
$\endgroup$
  • $\begingroup$ +1 but Re: "If you want to choose from infinitely many sets then you need to be able and tell which element you have chosen." What's a definable element for only 1 set consisting of 2 indistinguishable socks? And if you can choose from 1 pair, why not for 2 pairs, $10^{100}$ pairs or countably many? (See also my comment to Andres above on his "uniformity") $\endgroup$ – alancalvitti Feb 20 '13 at 21:30
  • $\begingroup$ @alan: So you want to tell me that if I hand you a brand new pair of totally white socks, you cannot choose one? That's interesting. I hope that all the pairs of socks that you are buying have labels "Left" and "Right" on them. $\endgroup$ – Asaf Karagila♦ Feb 20 '13 at 21:42
  • $\begingroup$ That's not what I wrote above. I wrote that if you can choose once, why can't you repeat that choice procedure multiple times? $\endgroup$ – alancalvitti Feb 20 '13 at 21:47
  • $\begingroup$ @alan: You can repeat this choice as finitely many times as you want. But when you want to switch from a finite choice to infinite choice then you need the axiom of choice. $\endgroup$ – Asaf Karagila♦ Feb 20 '13 at 21:48
  • $\begingroup$ You're not explaining why the transition. If you can do it $10^{100}$ times (or even once), why can't you put it in an infinite loop? $\endgroup$ – alancalvitti Feb 20 '13 at 21:49

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.