Difference between revisions of "Zorn's Lemma"

Latest revision as of 18:02, 1 August 2018

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 intersection 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 $x$ 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 \}_{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 $T$ . 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. ∎

References

Lang, S. Algebra, Revised Third Edition. Springer (2002), ISBN 0-387-95385-X.

@@ Line 22: / Line 22: @@
 * <math>a\in B</math>
 * <math>f(B) \subseteq B</math>
-* For every totally ordered subset <math>T \subeteq B</math>, the least upper bound of <math>T</math> in <math>A'</math> is an element of <math>B</math>.
+* For every totally ordered subset <math>T \subseteq B</math>, the least upper bound of <math>T</math> in <math>A'</math> is an element of <math>B</math>.
-Let <math>M</math> be the union of all admissable subsets of <math>A'</math>.  We note that <math>M</math> is not empty, as <math>A'</math> is an admissable subset of itself, and all admissable sets contain <math>a</math>.  Then <math>M</math> is the least admissable set, under order by inclusion.
+Let <math>M</math> be the intersection of all admissable subsets of <math>A'</math>.  We note that <math>M</math> is not empty, as <math>A'</math> is an admissable subset of itself, and all admissable sets contain <math>a</math>.  Then <math>M</math> is the least admissable set, under order by inclusion.
 We say that an element <math>c \in M</math> is an ''extreme point'' if <math>x\in M</math>, <math>x < c</math> together imply <math>f(x) \le c</math>.  For an extreme point <math>c</math> denote by <math>M_c</math> the set of <math>x\in M</math> such that <math>x \le c</math> or <math>f(c) \le x</math>.
@@ Line 42: / Line 42: @@
 ''Proof.'' Let <math>E</math> be the set of extreme points of <math>M</math>.  As before, it suffices to show that <math>E</math> is an admissable set.  Evidently, <math>a</math> is an extreme point of <math>M</math>, as no element of <math>M</math> is less than <math>a</math>, so every element less than <math>a</math> is also less than or equal to <math>f(a)</math>.  Now, suppose <math>c</math> is an extreme point of <math>M</math>.  Then for any <math>x\in M</math>, if <math>x < f(c)</math>, then by Lemma 1, <math>x\le c</math>.  If <math>x=c</math>, then <math>f(x) = f(c)</math>, so <math>f(x) \le f(c)</math>; if <math>x<c</math>, then since <math>c</math> is an extreme point, <math>f(x) \le c \le f(c)</math>.  Therefore <math>f(c)</math> is an extreme point, so <math>f(E) \subseteq E</math>.
-Now, let <math>T</math> be a totally ordered set of extreme points.  Consider the least upper bound <math>s</math> of <math>T</math> in <math>M</math>.  If <math>x</math> is an element of <math>M</math> strictly less than <math>s</math>, then <math>s</math> must be strictly less than some element <math>c \in T</math>.  But <math>c</math> is an extreme point, so <math>f(x) \le c \le s</math>.  Therefore <math>s</math> is an extreme point, i.e., an element of <math>E</math>.  It follows that <math>E</math> is an admissable set, so as before, <math>E=M</math>.  {{halmos}}
+Now, let <math>T</math> be a totally ordered set of extreme points.  Consider the least upper bound <math>s</math> of <math>T</math> in <math>M</math>.  If <math>x</math> is an element of <math>M</math> strictly less than <math>s</math>, then <math>x</math> must be strictly less than some element <math>c \in T</math>.  But <math>c</math> is an extreme point, so <math>f(x) \le c \le s</math>.  Therefore <math>s</math> is an extreme point, i.e., an element of <math>E</math>.  It follows that <math>E</math> is an admissable set, so as before, <math>E=M</math>.  {{halmos}}
 === Theorem 3 (Bourbaki). ===
@@ Line 64: / Line 64: @@
 ''Proof.''  Let <math>T</math> be the family of totally ordered subsets of <math>A</math>.
-We claim that under the order relation <math>\subseteq</math>, <math>T</math> is a strictly inductively ordered set.  Indeed, if <math> \{ X_ \}_{i\in I}</math> is a totally ordered subset of <math>T</math>, then
+We claim that under the order relation <math>\subseteq</math>, <math>T</math> is a strictly inductively ordered set.  Indeed, if <math> \{ X_i \}_{i\in I}</math> is a totally ordered subset of <math>T</math>, then
 <cmath> Z = \bigcup_{i\in I} X_i </cmath>
 is evidently the least upper bound of the <math>X_i</math>, and if <math>a,b \in Z</math>, then for some <math>i,j \in I</math>, <math>a \in X_i</math> and <math>b \in X_j</math>; one of <math>X_i</math> and <math>X_j</math> is a subset of the other, by assumption, so <math>a</math> and <math>b</math> are comparable.  It follows that <math>Z</math> is totally ordered, i.e., <math>Z \in T</math>.
-Now, by Corollary 4, there exists a maximal element <math>P</math> of <math>Z</math>.  This set <math>P</math> is totally ordered, so it has an upper bound <math>x_0</math> in <math>A</math>.  Then <math>P \cup \{x_0\}</math> is a totally ordered set, so by the maximality of <math>P</math>, <math>x_0 \in P</math>.  Now, if <math>y\ge x_0</math>, then <math>P \cup \{y\}</math> is a totally ordered set, so <math>y \in P</math> and <math>y\le x_0</math>, so <math>y=x_0</math>.  Therefore <math>x_0</math> is a maximal element, as desired.  {{halmos}}
+Now, by Corollary 4, there exists a maximal element <math>P</math> of <math>T</math>.  This set <math>P</math> is totally ordered, so it has an upper bound <math>x_0</math> in <math>A</math>.  Then <math>P \cup \{x_0\}</math> is a totally ordered set, so by the maximality of <math>P</math>, <math>x_0 \in P</math>.  Now, if <math>y\ge x_0</math>, then <math>P \cup \{y\}</math> is a totally ordered set, so <math>y \in P</math> and <math>y\le x_0</math>, so <math>y=x_0</math>.  Therefore <math>x_0</math> is a maximal element, as desired.  {{halmos}}
 == References ==

Page

Toolbox

Search