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.

  • $\begingroup$ Just give me an infinite collection of pairs of socks, and I'm going to show you why the axiom of choice is necessary. $\endgroup$ – Momo Sep 19 '17 at 0:19
  • 3
    $\begingroup$ "Can't we, out of a pair of socks, pick out a random sock?" One way to think about this is that the axiom of choice is exactly the thing that tells us that we can make "random" choices. Remember that the way axiomatic set theory works (roughly) is that we try to express our intuitions about sets through formal axioms; one of those intuitions (arguably) is that we can, in fact, "make unlimited random choices," and the axiom of choice is the axiom which corresponds to this intuition. $\endgroup$ – Noah Schweber Sep 19 '17 at 0:23
  • $\begingroup$ @NoahSchweber What is the principal difference between choosing a sock from a finite collection and an infinite one? I don't get this. $\endgroup$ – sequence Sep 19 '17 at 0:28
  • $\begingroup$ For finite sets you can prove the AC from the other ZF axioms by induction. For infinite sets, it is proved that AC is logically independent of ZF, so you may have a world with AC and a world with the negation of AC. My attempted joke above was trying to tell you that intuition fails us when we deal with infinite sets. (Think for example about a box with an infinite number of apples: you can take out the apples, eat one of them and put them back in the box and nothing will be missing.. how inuitive is that?) $\endgroup$ – Momo Sep 19 '17 at 0:41
  • $\begingroup$ @Momo To me your example with apples is much more intuitive than with socks. If we have an infinite collection of socks and an infinite collection of shoes, then I don't understand why we can pick out distinguishable shoes, but can't do so with indistinguishable socks. I don't get what indistinguishability has to do with picking out socks or other items. $\endgroup$ – sequence Sep 19 '17 at 1:22

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".)

  • $\begingroup$ I'd think of the following analogy to a function choosing socks arbitrarily. Any irrational number has infinitely many digits after the comma. That is, $\pi = 3.1415x_5x_6x_7\dots x_n\dots$. We can think of $f(n) = (x_n)_{n=1}^\infty$ as some choice function that chooses infinitely many digits by some rule. Thus there should exist a choice function to pick out a sock from an infinite set of indistinguishable pairs. $\endgroup$ – sequence Sep 19 '17 at 23:15
  • 1
    $\begingroup$ The digits are distinguishable, so your example falls into the shoes case. $\endgroup$ – Momo Sep 20 '17 at 2:18
  • $\begingroup$ @sequence: I have no idea what you mean in that comment. $\endgroup$ – Asaf Karagila Sep 20 '17 at 4:08
  • $\begingroup$ @sequence: (1) Choice functions should not be thought as some kind of a rule for choosing, since we tend to think in a framework where there are only countably many rules. (2) Your argument amounts to "the identity function is continuous everywhere, therefore we should except every function to be continuous". $\endgroup$ – Asaf Karagila Sep 20 '17 at 5:28

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 set1 $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

  • $\begingroup$ To me, intuitively, I absolutely see no reason how a finite process of choosing $n$ elements form $n$ sets is logically different from the process of choosing infinitely many elements from infinitely many sets, one element from each set. But can you please clarify the following?: (1) What is the $n$-th component of $s$ (i.e. what kind of a component does a function $s$ have?)? (2) "to ensure the set of choice functions is empty" Did you mean "non-empty"? (3) Does $\{S_n\}_n$ mean an $n$-th collection of $n$ sets $S$, $n$ sets per each collection? $\endgroup$ – sequence Sep 20 '17 at 1:30
  • $\begingroup$ @sequence: Since you're unfamiliar, I've explained how to formalize the notion of "family" in terms of functions. $\endgroup$ – user14972 Sep 20 '17 at 8:48

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".

  • $\begingroup$ I think an infinite set of pairs of socks is not an uncountable set. Why would it be such? $\endgroup$ – sequence Sep 20 '17 at 1:08

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.