# Axiom of Choice Examples

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)?

-
The point is that left and right socks are indistinguishable, while left and right shoes are distinguishable. –  Jason DeVito Dec 27 '10 at 20:05
@Jason DeVito: I have checked this experimentally. –  Andrey Rekalo Dec 27 '10 at 20:11
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. –  Arturo Magidin Dec 27 '10 at 21:51
What is an infinite pair? –  Mariano Suárez-Alvarez Dec 28 '10 at 3:33

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.

-
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. –  Andres Caicedo Dec 28 '10 at 0:10
+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? –  alancalvitti Feb 20 '13 at 21:24
@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. –  Andres Caicedo Jul 4 '14 at 16:04

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.

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.
+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") –  alancalvitti Feb 20 '13 at 21:30
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? –  alancalvitti Feb 20 '13 at 21:49