# Zorn's Lemma

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

## Contents

## 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 intersection 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 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.