Russell's shoes and socks

Russell's illustration. Given infinitely many pairs of shoes and asked for one shoe from each pair, there is a rule: take the left shoe. It selects one member of every pair at once, it is written down once and for all, and it needs no axiom. Given infinitely many pairs of socks the rule is gone. The two socks of a pair are alike, nothing in the data distinguishes one of them, and the assertion that a function selecting one sock from each pair exists is an instance of the Axiom of Choice (The Axiom of Choice).

The difference is not about footwear. It is that the shoe family comes with a distinguished member in each pair, supplied in advance by the data, whereas a family of two element sets in general comes with nothing of the kind. Below, the shoe half is proved: a distinguishing set makes the choice function explicit, whatever the size of the family. The sock half is not proved here and is not provable here: it is the standard independence result that ZF alone, if consistent, does not prove that every countable family of two element sets has a choice function. The library records that result, with sources, as Fraenkel's socks: ZF does not prove choice for countably many pairs ‡, and does not prove it: it is established either by forcing, or by a permutation model of set theory with atoms together with a theorem transferring the conclusion to ZF, and this library develops neither.

• What is proved and what is quoted. Steps 1.1 to 3.1 are a complete ZF argument: a distinguishing set turns infinitely many choices into one formula. Step 5.1 rests on [A1], an external independence result. The honest reading is that the sock half is unavailable in ZF, not that it has been refuted here.

• Where [A1] sits in this library's record of unproved results. [A1] concerns countable families of two element sets, so it is the failure of a choice principle far weaker than the Axiom of Choice, and the library records it in its own right, with sources, as Fraenkel's socks: ZF does not prove choice for countably many pairs ‡. It is stronger than the bare independence of the Axiom of Choice: the Axiom of Choice implies choice for countable families of pairs, so any ZF proof of the Axiom of Choice would yield a ZF proof of that weaker principle, and [A1] denies the latter, so [A1] already gives Cohen 1963: ZF does not prove the Axiom of Choice ‡. Cohen's first model: an infinite Dedekind-finite set of reals ‡, that if ZF is consistent then so is ZF together with an infinite set of reals having no countably infinite subset, records a different failure of choice and is not what [A1] rests on. The standard Fraenkel-Mostowski "socks" model witnesses [A1] in ZFA, set theory with atoms, where the two socks of a pair are atoms and a permutation exchanging them is an automorphism; a permutation model is not a model of ZF, and the passage to ZF is supplied by the Jech-Sochor embedding theorem, whose role is recorded but not proved in Fraenkel's socks: ZF does not prove choice for countably many pairs ‡.

• Boundedly many pairs of socks are free. Whenever the pairs can be listed as the values $F(0), \dots, F(n-1)$ of a function $F$ with domain a natural number $n$, a choice function exists outright by Every natural-number-indexed list of nonempty sets has a choice function on its family of values, with the picks made one at a time. That lemma is stated over such an indexed family and deliberately does not say "finitely many." A finite set is defined later as one equinumerous with a natural number (Finite, countably infinite, countable, uncountable ↗); this example uses only the indexed-family statement and does not identify an arbitrary finite family with a particular enumeration. Russell's contrast is a genuinely infinite phenomenon, which is why he stated it for infinitely many pairs.

• The shoe argument never used that the pairs are pairwise disjoint, or that they are indexed by $\mathbb{N}$, or that they have two elements. All it used is that some formula picks out one element of each member, which is the general reason a concrete family can have an explicit choice function ($\min$ is a choice function on $\mathbb{N}$ is the same phenomenon with "least element" in place of "left shoe").

• Russell's own phrasing concerns a millionaire with denumerably many pairs of boots and of socks. "Shoes" is the usual modern retelling, and the mathematical content is unchanged: what matters is only that one member of each pair is singled out in advance.