Russell's shoes and socks

Question

In a Wikipedia article, I'm reading the following (emphasis is mine):

Informally put, the axiom of choice says that given any collection of bins, each containing at least one object, it is possible to make a selection of exactly one object from each bin. In many cases such a selection can be made without invoking the axiom of choice; this is in particular the case if the number of bins is finite, or if a selection rule is available: a distinguishing property that happens to hold for exactly one object in each bin. To give an informal example, for any (even infinite) collection of pairs of shoes, one can pick out the left shoe from each pair to obtain an appropriate selection, but for an infinite collection of pairs of socks (assumed to have no distinguishing features), such a selection can be obtained only by invoking the axiom of choice.

I don't understand why we can pick out shoes but cannot pick out indistinguishable socks from an infinite collection. Can't we, out of a pair of socks, pick out a random sock? Can someone please clarify what this excerpt above is trying to say?

The whole concept of the axiom of choice seems "artificial" to me.

Answer 1

The first thing to remember is that you are always in the context of a proof of something. You want to prove that something exists. Be it a choice function, or a set, or whatever.

And proofs are finite. So if you have an infinite family of sets, and you've managed to prove that they are all non-empty, you still can't go "one by one" and choose from it, as you would have done if you only had five sets to choose from. This is what the axiom of choice comes to formalize, it is an apparatus for making infinitely many choices at once.

But sometimes, as luck would have it, you can specify which element you want to choose from each set. If all the sets are sets of natural numbers, you can specify the least element; or the least even element if it exists, and the third smallest odd element if there are no even numbers, and the least odd numbers if that doesn't work either. There are many ways to actually specify choices here, and many more which you cannot even fathom in their complexity.

This is the situation with the family of pairs of shoes. We have a rule, to specify, choose the left shoe of all the pairs; or choose the left shoe from this pair, and the right shoe from any other pair; or choose the left shoe if the shoes are black, and otherwise choose the right shoe. And so on and so on.

Sometimes, however, there is no reason to prefer one element of the set over another. This is what happens with socks. While they are different, socks have no inherent properties to set them apart from one another (for posterity, assume plain white socks that have never been worn). So the only way to specify a choice is indeed by an arbitrary choice. But an arbitrary choice is "a line in the proof". Because it is utilizing something called "existential instantiation". And the finiteness of the proof means that we can only apply that rule finitely many times before we need to resort to something better.

---

Two remarks:

1. I'm slightly bending the truth here, in favor of clarity of intuition. There is an issue with internal finiteness and meta-finiteness, which $\sf ZF$ itself can bypass, but that can be ignored until a better grasp of choice and set theory is developed.

2. You can't choose "randomly". You need to prove there is a choice function, and choosing "randomly" is exactly postulating the existence of a choice function. If you do not assume the axiom of choice, then there is no reason for such a function to even exist.

   (And "random" is something which implies some probability distribution to it, the correct word to use would be "arbitrary".)

Answer 2

The thing you are trying to invoke here is the principle of finite choice. (this is not a standard name)

In most forms of logic, one of the basic things you can do with a nonempty set¹ $S$ is that you can introduce a variable $s$ that denotes an element of $S$.

For example, this is invoked if you say "Let $s \in S$..."

Note that no actual "choice" is performed here; $s$ is just a formal symbol. And this is fine; sometimes we don't care what element is chosen, sometimes we can't make an explicit choice, and yet other times we want to exhibit an argument that works with every possible choice. And those times we actually get around to making a "choice", we can substitute that choice in for $s$.

Now, you can do this repeatedly: e.g. "Let $a \in A$. Let $b \in B$. Let $c \in C$. Let $d \in D$." The thing is, logic is finitary; any thread of reasoning has finite length, and thus we only have room to work with finitely many sets and introduce finitely many symbols.

Now, we might solve this by having some family of sets $S_n$. The same limitation applies; we can say "Let $s_1 \in S_1$. Let $s_2 \in S_2$. Let $s_3 \in S_3$." But still, we only have space to do this finitely many times.

I hope I've belabored this point enough that you can recognize "Let $s_n \in S_n$ for all $n$" is a qualitatively different thing from the above. It's something new, that cannot be justified from finite choice alone!

Let's call this the principle of infinite choice.

Now, some people think the principle of infinite choice is an obviously acceptable logical principle. Others think it's obviously nonsensical.

Modern logic tends to be conservative on this — it does not include the principle of infinite choice, instead preferring to defer the issue to set theory, where the axiom of choice lets you emulate this form of reasoning, by the device:

Let $s$ be an element of the set of choice functions on the family of sets $\{ S_n \}_n$. For all $n$, define $s_n$ to be the $n$-th component of $s$.

So, if the set of choice functions is nonempty, we can emulate the principle of infinite choice by making a single choice from the set of choice functions.

And that is why set theory has the axiom of choice: to ensure the set of choice functions is nonempty.

---

Addendum: I stated the above in the language of "families" of things since that's usually easier to read. But if you're unfamiliar, families can be formalized in terms of functions:

• A family of things indexed by the set $I$ is simply a thing-valued function whose domain is $I$
• The $i$-th component of a family given by the function $f$ is simply $f(i)$

Notationally, if $X$ is a family, we tend to write $X_i$ for the $i$-th component. And to introduce the family itself, we mimic a notation from sequences; e.g. the notation $\{ X_i \}_{i \in I}$ to indicate that $I$ is the index set and that $X_i$ is the $i$-th component. $\in I$ can be dropped if the domain is clear or irrelevant.

_{1: or type or class or whatever similar thing is relevant}

Answer 3

I think the idea of the shoes vs. socks is that shoes can have a rule.

If you have an uncountable number of {0,1} sets you can say "always pick 1" or "always pick 0" or (I think; I could be wrong) "take a 1-1 function between the reals and the sets and take the sixth digit of the real numbers decimal expansion".

What you can't do is say "arbitrarily pick one number from one set, one after another". You can't say this because there are uncountably many sets and we can't choose them one after another.

Therefore, although it seem intuitive that we should, we can not say "arbitrarily choose a number from each of the uncountably many sets". We can arbitrarily choose a discrete number of times, and we can, via induction, arbitrarily do it a countable number of times (I think), but we can't say "arbitrarily choice from each set individually despite the fact that the sets themselves are stacked infinitely dense and we can't individually list them all".

However if the items in the sets are distinguishable, we can make one arbitrary decision and apply it to all the sets. Such as "always pick 1".