Franklin's Notes


Zorn's Lemma

Zorn's Lemma is the following statement:

If every chain in a partially ordered set $A$ has an upper bound, then $A$ has a maximal element (i.e. an element $x\in A$ such that $x\not < y$ for all $y\in A$).

It happens that Zorn's Lemma is equivalent to the Axiom of Choice and the Well-Ordering Principle , and it is often considered the least intuitive of this triad of equivalent statements.

Theorem 1. Zorn's Lemma is equivalent to the Well-Ordering Principle.

Proof. First, we show that AC $\implies$ Zorn's Lemma. Assuming AC, let's suppose to the contrary that there is some poset $(A,\leq)$ with the property that every chain of $A$ has an upper bound, but $A$ has no maximal element, so that for every chain $B\subset A$, there exists an element $a\subset A$ which is strictly greater than the upper bound for $B$, and therefore strictly greater than all elements of $B$. By the General Principle of Choice (equivalent to AC), we may define a function $f$ which maps each chain $B\subset A$ to a strict upper bound of that chain.

Define $x_0=f(\varnothing)$, and consider the set $W$ of all well-ordered chains $B\subset A$ with $x_0$ as their least element that satisfy the additional property for all $x\in B$. Note that $W$ is nonempty, because ${x_0}$ is a well-ordered chain with this property. Notice that if $B_1,B_2\subset A$ are two chains with this property, then one must be an initial segment of the other. First of all, we may claim that either $B_1$ must be a subset of $B_2$ or vice versa: for if neither is a subset of the other, we may let $b_1$ be defined as the smallest element in $B_1$ but not in $B_2$, and $b_2$ be defined as the smallest element in $B_2$ but not in $B_1$ - but this would imply that ${x\in B_1: x<b_1}={x\in B_2: x<b_2}$, meaning that and $b_1=b_2$ contradicts the fact that $b_1\in B_1\backslash B_2$ and $b_2\in B_2\backslash B_1$. Next, we may see that if $B_1\subset B_2$, then $B_1$ is an initial segment of $B_2$: for if $b_2$ is defined as the smallest element of $B_2$ not in $B_1$, and there exists some smallest element $b_1\in B_1$ which is not in $B_2$ but greater than $b_2$, then it would follow again that ${x\in B_1: x<b_1}={x\in B_2: x<b_2}$ and that $b_1=b_2$, producing another contradiction. Hence, for any two chains $B_1,B_2\in W$, one must be an initial segment of the other.

Knowing this, we may consider the union $B^\star = \bigcup W$ of all well-ordered chains satisfying the aforementioned property, and conclude that $B^\star$ is also a well-ordered chain. It is also easy to verify that $B^\star$ satisfies the property for all $x\in B^\star$. This means that $B^\star \in W$. However, notice that the set $B^\star\cup{f(B^\star)}$ is also a well-ordered chain satisfying the aforementioned property, but it contains an element $f(B^\star)$ which is not in $B^\star$, even though $B^\star$ was defined as $B^\star=\bigcup W$! This is a contradiction - hence, we may reject our original assumption that $A$ has no maximal element, and conclude that $AC$\implies Zorn's Lemma.

Now let's prove that Zorn's Lemma $\implies$ AC. Let $Z$ be a nonempty set of disjoint sets, and let $F$ be the set of choice functions on subsets of $Z$ - that is, the set of functions mapping each of the sets in some subset of of $Z$ to one of its elements. We may partially order $F$ by letting $f_1\leq f_2$ whenever $f_1\subset f_2$, or when $f_2$ "extends" $f_1$. Each chain in this ordering has an upper bound, namely the union of all functions in that chain. Thus, by Zorn's Lemma, there exists a maximal function $f^\star\in F$. However, $f^\star$ must be a choice function on all of $Z$, for if there were some set $A\in Z$ not included in the domain of $f^\star$, then the function $f^\star\cup {(A,a)}$ would be greater than $f^\star$, for any choice of $a\in A$. Hence, $f^\star$ is a choice function on all of $Z$, so Zorn's Lemma $\implies$ AC. $\blacksquare$

set-theory

order-theory

back to home page