Zorn's Lemma

From AoPSWiki

Revision as of 02:20, 11 April 2009 by Boy Soprano II (Talk | contribs)

(diff) ← Older revision | Current revision (diff) | Newer revision → (diff)

Zorn's Lemma is a set theoretic result which is equivalent to the Axiom of Choice.

Background

We say that $A$ is inductively ordered if every totally ordered subset $T$ of $A$ has an upper bound, i.e., an element $a \in A$ such that for all $x\in T$ , $x \le a$ . We say that $A$ is strictly inductively ordered if every totally ordered subset $T$ of $A$ has a least upper bound, i.e., an upper bound $a$ so that if $b$ is an upper bound of $T$ , then $a \le b$ .

An element $m \in A$ is maximal if the relation $a \ge m$ implies $a=m$ . (Note that a set may have several maximal elements.)

We say a function $f : A \to A$ is increasing if $x \le f(x)$ for all $x\in A$ .

Statement

Every inductively ordered set $A$ has a maximal element.

Proof (using the Axiom of Choice)

We first prove some intermediate results, viz., Bourbaki's Theorem (also known as the Bourbaki-Witt theorem).

Let $A$ be a strictly inductively ordered set, and let $f: A \to A$ be an increasing function. Pick some $a \in A$ . Let $A'$ be the set of elements $x \in A$ such that $a \le A$ . Evidently, $A'$ is stricty inductively ordered, for if $T$ is a totally ordered subset of $A'$ , then it has a least upper bound in $A$ , which is evidently greater than $a$ , so this least upper bound is an element of $A'$ . We say that a subset $B \subseteq A'$ is admissable if it satisfies these conditions:

$a\in B$
$f(B) \subseteq B$
For every totally ordered subset $T \subseteq B$ , the least upper bound of $T$ in $A'$ is an element of $B$ .

Let $M$ be the union of all admissable subsets of $A'$ . We note that $M$ is not empty, as $A'$ is an admissable subset of itself, and all admissable sets contain $a$ . Then $M$ is the least admissable set, under order by inclusion.

We say that an element $c \in M$ is an extreme point if $x\in M$ , $x < c$ together imply $f(x) \le c$ . For an extreme point $c$ denote by $M_c$ the set of $x\in M$ such that $x \le c$ or $f(c) \le x$ .

Lemma 1.

For each extreme point $c$ , $M_c = M$ .

Proof. It suffices to show that $M_c$ is an admissable set. Evidently, $a\le c$ , so $a \in M_c$ . Now, let $x$ be an element of $M_c$ . If $x = c$ , then evidently, $f(c) \le f(x)$ , so $f(x) \in M_c$ . If $x < c$ , then since $c$ is an extreme point, $f(x)\le c$ , so $f(x) \in M_c$ . On the other hand, if $f(c) \le x$ , then $f(c) \le x \le f(x)$ , so $f(x) \in M_c$ . Therefore $f(M_c) \subseteq M_c$ .

Let $T$ be a totally ordered subset of $M_c$ . Then $T$ has a least upper bound $s\in A'$ . Since $M$ is admissable, $s\in M$ . Now, if $s \le c$ , then evidently $s\in M_c$ . On the other hand, if $s\ge c$ , then either $f(c) \le s$ , or every element of $T$ is less than or equal to $c$ , so $s \le c$ . Hence the least upper bound of every totally ordered subset $T$ of $M_c$ is an element of $M_c$ , so $M_c$ is admissable. Therefore $M \subseteq M_c$ ; since we know $M_c \subseteq M$ , it follows that $M= M_c$ . ∎

Lemma 2.

Every element of $M$ is an extreme point.

Proof. Let $E$ be the set of extreme points of $M$ . As before, it suffices to show that $E$ is an admissable set. Evidently, $a$ is an extreme point of $M$ , as no element of $M$ is less than $a$ , so every element less than $a$ is also less than or equal to $f(a)$ . Now, suppose $c$ is an extreme point of $M$ . Then for any $x\in M$ , if $x < f(c)$ , then by Lemma 1, $x\le c$ . If $x=c$ , then $f(x) = f(c)$ , so $f(x) \le f(c)$ ; if $x<c$ , then since $c$ is an extreme point, $f(x) \le c \le f(c)$ . Therefore $f(c)$ is an extreme point, so $f(E) \subseteq E$ .

Now, let $T$ be a totally ordered set of extreme points. Consider the least upper bound $s$ of $T$ in $M$ . If $x$ is an element of $M$ strictly less than $s$ , then $s$ must be strictly less than some element $c \in T$ . But $c$ is an extreme point, so $f(x) \le c \le s$ . Therefore $s$ is an extreme point, i.e., an element of $E$ . It follows that $E$ is an admissable set, so as before, $E=M$ . ∎

Theorem 3 (Bourbaki).

For any strictly inductively ordered set $A$ and any increasing function $f: A \to A$ , there exists an element $x_0$ of $A$ such that $x_0 = f(x_0)$ .

Proof. Choose an arbitrary $a\in A$ , and define $A'$ as before. Let $M$ be the least admissable subset of $A'$ , as before. By Lemmata 2 and 1, for all elements $a,b \in M$ , either $a \le b$ , or $b \le f(b) \le a$ . Therefore $M$ is totally ordered under the ordering induced by $A$ . Then $M$ has a least upper bound $x_0$ which is an element of $M$ . We note that $f(x_0) \in M$ , so $f(x_0) \le x_0$ , and since $f$ is increasing, $x_0 \le f(x_0)$ . Hence $x_0 = f(x_0)$ , as desired. ∎

Note that thus far, we have not used the Axiom of Choice. In the next corollary, however, we will use the Axiom of Choice.

Corollary 4.

Let $A$ be a strictly inductively ordered set. Then $A$ has a maximal element.

Proof. Suppose the contrary. Then by the Axiom of Choice, for each $x \in A$ , we may define $f(x)$ to be an element strictly greater than $x$ . Then $f$ is an increasing function, but for no $x \in A$ does $x = f(x)$ , which contradicts the Bourbaki-Witt Theorem. ∎

Corollary 5 (Zorn's Lemma).

Let $A$ be an inductively ordered set. Then $A$ has a maximal element.

Proof. Let $T$ be the family of totally ordered subsets of $A$ .

We claim that under the order relation $\subseteq$ , $T$ is a strictly inductively ordered set. Indeed, if $\{ X_ \}_{i\in I}$ is a totally ordered subset of $T$ , then $Z = \bigcup_{i\in I} X_i$ is evidently the least upper bound of the $X_i$ , and if $a,b \in Z$ , then for some $i,j \in I$ , $a \in X_i$ and $b \in X_j$ ; one of $X_i$ and $X_j$ is a subset of the other, by assumption, so $a$ and $b$ are comparable. It follows that $Z$ is totally ordered, i.e., $Z \in T$ .

Now, by Corollary 4, there exists a maximal element $P$ of $Z$ . This set $P$ is totally ordered, so it has an upper bound $x_0$ in $A$ . Then $P \cup \{x_0\}$ is a totally ordered set, so by the maximality of $P$ , $x_0 \in P$ . Now, if $y\ge x_0$ , then $P \cup \{y\}$ is a totally ordered set, so $y \in P$ and $y\le x_0$ , so $y=x_0$ . Therefore $x_0$ is a maximal element, as desired. ∎