Set Theory/Zorn's Lemma and the Axiom of Choice

Two dual ideas in set theory have to do with finding the "largest" possible objects in some set under a given ordering and with making a simultaneous selection of objects from many sets. These notions are phrased in terms of Zorn's Lemma, and the Axiom of Choice; and though they sound very different, they are equivalent to one another. That is, given Zorn's Lemma one can derive the Axiom of Choice, and vice versa. The Axiom of Choice is named as such because it is independent from Zermelo-Fraenkel set theory axioms. Thus, the addition of Choice to ZF enables work not previously possible.

Zorn's Lemma

Zorn's Lemma, as usually stated, takes the form:

1) If every chain in a partially ordered set S has an upper bound, then S has a maximal element.

As Zorn's Lemma (ZL) has no proof or disproof from the axioms of Zermelo-Fraenkel set theory (ZF) (by famous work of Kurt Gödel and Paul Cohen), it makes sense to speak of certain propositions P logically equivalent to Zorn's Lemma (over ZF). "Logically equivalent" means the existence of implications, provable in ZF, that say ZL ==> P and P ==> ZL. "Provable," here, means provable in classical logic; often classically equivalent forms turn out independent with respect to, say, intuitionistic logic. (Topos theory provides a context for separating, via counterexamples, classically equivalent but intuitionistically inequivalent statements.)

We immediately establish the logical equivalence of ZL with two similar propositions.

2) Let S be a set with partial order ≤. If every chain has a least upper bound, then a maximal element exists in S.

3) (Hausdorff Maximality Principle) Let S be a set with partial order ≤ such that every chain of S has an upper bound. Then S contains a maximal chain (maximal with respect to set inclusion).

(1 => 2) If every chain has a least upper bound, a fortiori every chain has an upper bound, so the conclusion of 1) follows, and so that of 2).

(2 => 3) Write Chains(S) for the partially ordered set of chains contained in S, ordered by set inclusion. (We shall apply 2) to Chains(S), not to S itself!) Since every chain in Chains(S) has a least upper bound, namely its union, 2) grants us a maximal element in Chains(S), i.e. a maximal chain.

Some details

The union U of a chain (C_i) in Chains(S) itself has the form of a chain. For given x and y in U, we must have x in C_j and y in C_k, say, and j < k without loss of generality. But having x and y both in C_k makes them comparable.

U, as a chain, then constitutes the least upper bound for (C_i) because it does as a set!

(3 => 1) If a maximal chain C in a partially ordered set S has an upper bound u, then u belongs to C and constitutes a maximal element for S. (If u does not belong to C, then C+{u} gives a larger chain; if u does belong to C but v>u, then C+{v} gives a larger chain.

Though one might expect no content from the tautology 1) ==> 1) that results from combining the three implications above, actually, combining the proofs, we see that whenever Zorn's Lemma fails for a partially ordered set S, it must also fail for Chains(S), the chains of S ordered by inclusion. Thus if Zorn's Lemma holds for partial orders based on set inclusion, then it holds in general!

The Axiom of Choice

Often, Choice is stated "For every nonempty set S, there exists a function f from the set ${\mathcal {S}}$ of all nonempty subsets of S to S such that f(A) is in A". Parsing this, we assert that given a set, there is a way to simultaneously pick an element from each subset of the set. This function is usually referred to as a "choice function".

Further Equivalents of the Axiom of Choice

There are literally hundreds of mathematical statements that are known to be logically equivalent to the Axiom of Choice. Some of these statements are pure set-theoretic statements, such as Zorn's Lemma, above, while others are grounded in other mathematical disciplines.

In this section we will present some of these, mostly without proof.

Zermelo's Well-Ordering Theorem

Perhaps the most important equivalent of the Axiom of Choice (at least from the viewpoint of pure set theory) is Zermelo's Well-Ordering Theorem.

Before we state it, we must introduce some terminology:

A binary relation $R$ on a set $X$ is said to be well-founded if there is no infinite sequence $\langle x_{n}\rangle _{n=0}^{\infty }$ of elements of $X$ satisfying the following:

1. $x_{n}\neq x_{n+1}$ for each $n$, and
2. $\langle x_{n+1},x_{n}\rangle \in R$ for each $n$.

A partial order relation $R$ on a set $X$ is called a well-order relation if

1. for each $x,y\in X$ either $\langle x,y\rangle \in R$, or $\langle y,x\rangle \in R$, and
2. $R$ is well-founded.

Zermelo's Well-Ordering Theorem is then the following simple statement: Every set $X$ can be well-ordered.

Tychonoff's Theorem

States that the cartesian product of any arbitrary family of compact topological spaces is itself compact.

Existence of Non-Lebesgue Measurable Sets

Consider the unit interval $[0,1]$ and the equivalence relation defined the interval by $a\sim b\ {\mbox{if}}\ a-b\in \mathbb {Q}$. Certainly, this is an equivalence relation:

• $a\sim a$ because $a-a=0$, which is rational.
• $a\sim b$ implies $a-b$ is rational. Then $b-a=-(a-b)$ is rational, and so $b\sim a$.
• $a\sim b\ {\mbox{and}}\ b\sim c$ implies that $a-b\ {\mbox{and}}\ b-c$ are rational. Then, $a-c=(a-b)+(b-c)$ is rational too. This implies $a\sim c$.

Now, choose one representative from each equivalence class. Call this set $S$. Can $S$ be Lebesgue measurable? The answer is no.

To prove this, we note that any element of $x\in [0,1]$ differs by the chosen representative of its equivalence class $s_{x}\in S$ by a rational number in $(-1,1)$, However, there are only countably many rational numbers in $(-1,1)$; enumerate them as $\left\{r_{k}\right\}_{1\leq k<\infty }$. Define the set $S+r=\left\{s+r\mid s\in S\right\}$, the translate of $S$ by $r$.

Suppose $S$ is Lebesgue measurable. Then, by translation independence, $S_{k}=S+r_{k}$ is also measurable, and has the same measure. Note that by the choice procedure, the sets $S_{k}$ are all distinct. Take the union of all the translates:

${\mathcal {S}}=\bigcup _{k=1}^{\infty }S_{k}$.

If $S$ has measure zero, then ${\mathcal {S}}$ has measure zero too, by countable additivity.

If $S$ has positive measure, then ${\mathcal {S}}$ has measure $\infty$, by countable additivity. However,

$[0,1]\subset {\mathcal {S}}\subset [-1,2]$, and so $1\leq \mu ({\mathcal {S}})\leq 3$. But $\mu ({\mathcal {S}})$ cannot fall within this range, and so $S$ is nonmeasurable.

Exercises

1. Show that any partially ordered set contains a maximal antichain (a subset in which no two elements are comparable).