Zorn's Lemma
Zorn's Lemma is a set theoretic result which is equivalent to the Axiom of Choice.
Contents
[hide]Background
Let be a partially ordered set.
We say that is inductively ordered if every totally ordered subset of has an upper bound, i.e., an element such that for all , . We say that is strictly inductively ordered if every totally ordered subset of has a least upper bound, i.e., an upper bound so that if is an upper bound of , then .
An element is maximal if the relation implies . (Note that a set may have several maximal elements.)
We say a function is increasing if for all .
Statement
Every inductively ordered set 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 be a strictly inductively ordered set, and let be an increasing function. Pick some . Let be the set of elements such that . Evidently, is stricty inductively ordered, for if is a totally ordered subset of , then it has a least upper bound in , which is evidently greater than , so this least upper bound is an element of . We say that a subset is admissable if it satisfies these conditions:
- For every totally ordered subset , the least upper bound of in is an element of .
Let be the union of all admissable subsets of . We note that is not empty, as is an admissable subset of itself, and all admissable sets contain . Then is the least admissable set, under order by inclusion.
We say that an element is an extreme point if , together imply . For an extreme point denote by the set of such that or .
Lemma 1.
For each extreme point , .
Proof. It suffices to show that is an admissable set. Evidently, , so . Now, let be an element of . If , then evidently, , so . If , then since is an extreme point, , so . On the other hand, if , then , so . Therefore .
Let be a totally ordered subset of . Then has a least upper bound . Since is admissable, . Now, if , then evidently . On the other hand, if , then either , or every element of is less than or equal to , so . Hence the least upper bound of every totally ordered subset of is an element of , so is admissable. Therefore ; since we know , it follows that . ∎
Lemma 2.
Every element of is an extreme point.
Proof. Let be the set of extreme points of . As before, it suffices to show that is an admissable set. Evidently, is an extreme point of , as no element of is less than , so every element less than is also less than or equal to . Now, suppose is an extreme point of . Then for any , if , then by Lemma 1, . If , then , so ; if , then since is an extreme point, . Therefore is an extreme point, so .
Now, let be a totally ordered set of extreme points. Consider the least upper bound of in . If is an element of strictly less than , then must be strictly less than some element . But is an extreme point, so . Therefore is an extreme point, i.e., an element of . It follows that is an admissable set, so as before, . ∎
Theorem 3 (Bourbaki).
For any strictly inductively ordered set and any increasing function , there exists an element of such that .
Proof. Choose an arbitrary , and define as before. Let be the least admissable subset of , as before. By Lemmata 2 and 1, for all elements , either , or . Therefore is totally ordered under the ordering induced by . Then has a least upper bound which is an element of . We note that , so , and since is increasing, . Hence , 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 be a strictly inductively ordered set. Then has a maximal element.
Proof. Suppose the contrary. Then by the Axiom of Choice, for each , we may define to be an element strictly greater than . Then is an increasing function, but for no does , which contradicts the Bourbaki-Witt Theorem. ∎
Corollary 5 (Zorn's Lemma).
Let be an inductively ordered set. Then has a maximal element.
Proof. Let be the family of totally ordered subsets of .
We claim that under the order relation , is a strictly inductively ordered set. Indeed, if $\{ X_ \}_{i\in I}$ (Error compiling LaTeX. Unknown error_msg) is a totally ordered subset of , then is evidently the least upper bound of the , and if , then for some , and ; one of and is a subset of the other, by assumption, so and are comparable. It follows that is totally ordered, i.e., .
Now, by Corollary 4, there exists a maximal element of . This set is totally ordered, so it has an upper bound in . Then is a totally ordered set, so by the maximality of , . Now, if , then is a totally ordered set, so and , so . Therefore is a maximal element, as desired. ∎
References
- Lang, S. Algebra, Revised Third Edition. Springer (2002), ISBN 0-387-95385-X.