Some Interesting Tidbits

Stuff I didn’t want to squeeze into the axiom of choice article.

Sections

• Russell’s Paradox
• Supertasks
• Axiom of Choice in Linear Algebra
• Avoiding Axiom of Choice in Specific Cases

Russell’s Paradox

The paradox goes like this:

• Let \( P \) be the set of all sets that do not contain itself.

• If \( P \) does not contain itself, then it fits the definition above and should be in \( P \).

• However, if \( P \) contains itself, then the definition would be violated. So, it cannot contain itself.

• We are stuck with the unpleasant situation where \( P \) cannot contain itself, yet must also contain itself.

One particular axiom in Zermelo-Fraenkel set theory stops the construction of such pathological sets \( P \). Wikipedia has a nice explanation about this.

Russell’s paradox is similar to the sentence “this statement is false”, which is also known as the liar paradox. If the sentence is true, then it must be false. If it is false, then it must be true!

Supertasks

The countably infinite collection of sets situation feels very similar to the key issue with Supertasks.

Here is an example of a Supertask: suppose you have a light switch that starts in an “off” state at \( t = 0 \). After waiting for \( \frac{1}{2} \) seconds, you flip it to an “on” state. Then, you wait for \( \frac{1}{4} \) seconds before flipping it again. Keep repeating while waiting half as long to flip the switch again each time. The waiting times is an infinite sequence \( \frac{1}{2}, \frac{1}{4}, \frac{1}{8}, \frac{1}{16}, ...\) that sums to \( 1 \).

Since we started at \( t = 0 \) and the waiting times sum to \( 1 \), this infinite flipping process will end at \( t = 1 \). We can figure out if the light is “on” or “off” at any point in time \( t \in [0,1) \) by just counting the number of finite flips that have happened until that point.

But there is no way to “reach” the end of this process and figure out what state the light switch is in at \( t = 1 \).

Axiom of Choice in Linear Algebra

An interesting example application of the axiom of choice is in linear algebra: it can be used to prove that every vector space has a basis. The key part of the proof applies Zorn’s Lemma, which is equivalent to the Axiom of Choice.

A very brief summary of the proof goes like this.

• Let \( X \) be the set of all linearly independent subsets of a vector space \( V \).

• \( X \) contains the empty set and so is nonempty. It is partially ordered by inclusion \( \subseteq \).

• Every chain (totally ordered subsets) in \( X \) has an upper bound, which is the union of all elements in the chain.

• Every finite subset of this upper bound has to be linearly independent*. Hence, the upper bound is in \( X \).

• Apply Zorn’s Lemma to get a maximal element \( L \in X \).

• \( L \) must span \( X \). If not, there will be a \( y \in X \) so that \( L \subset L \cup \{ y \} \).

• \( L \) is linearly independent and spans \( X \). So, \( L \) is a basis for \( X \).

* This is the definition of linear independence for an infinite set.

Avoiding Axiom of Choice in Specific Cases

Infinite Collection of Singleton Sets

Write our infinite collection of singleton sets as \( X = \{ X_i \, \, | \, \, i \in I \} \) as usual. For all \( i \in I \), let \( x_i \) be the only element in each set \( X_i \).

We can avoid having to use the Axiom of Choice by doing this:

• For a given \( i \), \( X_i \) is a set and \( x_i \) is a set. So, \( (X_i, x_i) \) is a set.

• Define a binary relation \( P(X_i, (X_i, x_i)) \) for all \( i \).

• \( P \) satisfies this condition: \( \forall a, \exists \text{ exactly one } b \text{, s.t. } P(a,b) \text{ is true.} \)

• So, there is a function \( F \) where, \( F(a) = b \iff P(a,b) \).

• Then, we can use the axiom scheme of replacement to say that if \( A \) is any set, the image \( F(A) \) is also a set.

• In our case, the image is \( F(X) = \{ (X_i, x_i) \, \, | \, \, X_i \in X \} \).

• The set \( \{ (X_i, x_i) \} \) gives us the choice function we need, which in turn allows us to prove that the cartesian product is nonempty!

You might have noticed a slight problem with these steps: how do we know that the binary relation in step two is definable?

Unfortunately, proving whether a binary relation is definable or undefinable is a formidable task that requires considerable effort to study, and I have not done the requisite study to be able to do so. This is why most explanations of when we can avoid using the Axiom of Choice tend to feel “vibe-based” and people tend to “just write down a choice function”.

Infinite Collection of Two-Element Sets

What if instead of singletons, we have two elements in each of our sets? Then, it depends on whether we can define a relation \( P \) that meets the condition for the axiom schema of replacement.

This is why Bertrand Russell said that the axiom of choice is required for infinite pairs of socks, but not infinite pairs of shoes. The infinite pairs of socks are an analogy for collections of two-element sets in general.

The infinite pairs of shoes are an analogy for collections of two-element sets, where we are able to write down a binary relation that meets the condition to invoke the axiom schema of replacement. Non-rigorously speaking, there is a binary relation \( P \), so that for \( a = \) each pair of shoes, there exists exactly one \( b = \) left shoe, so that \( P(a,b) \) is true.