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

Solution 1:

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.

Solution 2:

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.