Axiom of Choice/Examples/Russell's Socks and Shoes

Example of Use of Axiom of Choice

Suppose we have an infinite number of pairs of socks.

Using the Axiom of Choice, we can simultaneously pick one sock from each pair.

However, if we also have a infinite number of pairs of shoes, we no longer need the Axiom of Choice to pick one shoe from each pair.

We simply choose the left one.

Proof

This is more formally stated as:

Given an infinite set of unordered pairs, the Axiom of Choice is needed to pick one element from each pair.

Given an infinite set of ordered pairs, the Axiom of Choice is not needed to pick one element from each of the pairs: we may simply pick the first element of each.

This theorem requires a proof. In particular: Needs formalising You can help $\mathsf{Pr} \infty \mathsf{fWiki}$ by crafting such a proof. To discuss this page in more detail, feel free to use the talk page. When this work has been completed, you may remove this instance of {{ProofWanted}} from the code. If you would welcome a second opinion as to whether your work is correct, add a call to {{Proofread}} the page.

Historical Note

This example was devised by Bertrand Russell as a neat illustration of how the Axiom of Choice can be used.

Sources

• 2010: Raymond M. Smullyan and Melvin Fitting: Set Theory and the Continuum Problem (revised ed.) ... (previous) ... (next): Chapter $4$: Superinduction, Well Ordering and Choice: Part $\text I$ -- Superinduction and Well Ordering: $\S 1$ Introduction to well ordering