Art of Problem Solving
AoPS Online
Math texts, online classes, and more
for students in grades 5-12.
Visit AoPS Online ‚
Books for Grades 5-12 Online Courses
Beast Academy
Engaging math books and online learning
for students ages 6-13.
Visit Beast Academy ‚
Books for Ages 6-13 Beast Academy Online
AoPS Academy
Small live classes for advanced math
and language arts learners in grades 2-12.
Visit AoPS Academy ‚
Find a Physical Campus Visit the Virtual Campus

Difference between revisions of "Zorn's Lemma"

(Zorn's Lemma! With proof! Yay!)
 
(→‎See Also: category, get rid of red links)
Line 76: Line 76:
 
== See Also ==
 
== See Also ==
  
−
* [[Axiom of Choice]]
 
−
* [[Well-Ordering Theorem]]
 
 
* [[Zermelo-Fraenkel Axioms]]
 
* [[Zermelo-Fraenkel Axioms]]
  
  
 
[[Category:Set theory]]
 
[[Category:Set theory]]
 +
[[Category:Theorems]]

Revision as of 17:24, 25 November 2007

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

Background

Let $A$ be a partially ordered set.

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 \subeteq B$ (Error compiling LaTeX. Unknown error_msg), 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}$ (Error compiling LaTeX. Unknown error_msg) 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. ∎

References

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

See Also

Retrieved from "https://artofproblemsolving.com/wiki/index.php?title=Zorn%27s_Lemma&oldid=20258"