# Zorn's Lemma

This page has been identified as a candidate for refactoring.Until this has been finished, please leave
`{{Refactor}}` in the code.
Because of the underlying complexity of the work needed, it is recommended that you do not embark on a refactoring task until you have become familiar with the structural nature of pages of $\mathsf{Pr} \infty \mathsf{fWiki}$.To discuss this page in more detail, feel free to use the talk page.When this work has been completed, you may remove this instance of `{{Refactor}}` from the code. |

This article needs to be tidied.Please fix formatting and $\LaTeX$ errors and inconsistencies. It may also need to be brought up to our standard house style.To discuss this page in more detail, feel free to use the talk page.When this work has been completed, you may remove this instance of `{{Tidy}}` from the code. |

## Theorem

Let $\struct {X, \preceq}, X \ne \O$ be a non-empty ordered set such that every non-empty chain in $X$ has an upper bound in $X$.

Then $X$ has at least one maximal element.

### Axiom of Choice Implies Zorn's Lemma

Acceptance of the Axiom of Choice implies the truth of Zorn's Lemma.

### Statement of Axiom of Choice

For every set of non-empty sets, it is possible to provide a mechanism for choosing one element of each element of the set.

- $\ds \forall s: \paren {\O \notin s \implies \exists \paren {f: s \to \bigcup s}: \forall t \in s: \map f t \in t}$

That is, one can always create a choice function for selecting one element from each element of the set.

### Statement of Zorn's Lemma

Let $\struct {X, \preceq}, X \ne \O$ be a non-empty ordered set such that every non-empty chain in $X$ has an upper bound in $X$.

Then $X$ has at least one maximal element.

### Zorn's Lemma Implies Axiom of Choice

If Zorn's Lemma is true, then so must the Axiom of Choice be.

## Note

The statement of Zorn's Lemma supposes the existence of an upper bound **in $X$** for any (non-empty) chain $A$.

It does *not* guarantee the existence of an upper bound for $A$ in $A$ itself.

The conclusion is that:

- $\forall a \in X: a \le x \implies a = x$

## Discussion

It can be shown that this follows from the Axiom of Choice and is in fact equivalent to it.

This quick very rough sketch indicates an appropriate chain of equivalences for others to elaborate.

1. Every partition has a transversal (axiom of choice)

2. For every set of non empty sets S there is a choice function f.

Consider traversal f of partition {{s} X s: s in S}. Partition since each pair of {s} and hence each pair of {s} X S is disjoint. This traversal exists by 1 and is a choice function since range is S from first elements of ordered pairs and each second element of pair has to be in the first element of the pair.

3. Any chain closed poset has a maximal element above any particular element. (Chain closed means every sub-chain has a least upper bound)

If not, every element has a non-empty set of strictly greater elements or strict upper bounds. Choice function exists by 2 since the sets of greater elements are all non empty. This choice function is an increasing map on a chain closed poset with no fixed point since strictly increasing as maps to strictly greater elements. Contradicts Bourbaki-Witt fixed point theorem that every increasing map on a chain closed poset has a fixed point. (Quick separate proof using injective map from class of all ordinals unless there is a fixed point. Start map from ordinals into the poset with ordinal 0 to any particular element. Defined for successor ordinals directly from the increasing map ie the choice function to set of upper bounds, defined for limit ordinals from the least upper bound of chain for elements mapped by previous ordinals. This LUB exists since chain closed poset. Converse relation would be map since injective - from subset onto the ordinals so ordinals as the range of a map from a set would be a set. But ordinals are a proper class.)

Note: Item 3 keeps the transfinite argument to separate proof of Bourbaki-Witt fixed point (which also has a longer proof not using transfinite). Other approaches mix a similar transfinite argument directly into proofs of zorns lemma being equivalent to other forms of choice.

4. Any chain of a poset extends to a maximal chain (Hausdorff). Consider poset of chains ordered by inclusion. This is chain closed since union of chain is a chain that is their least upper bound. Apply 3 so it has a maximal element which is a maximal chain.

5. Any chain bounded poset has a maximal element above any particular element (Zorn). It has a maximal chain which has an upper bound since it is a chain bounded poset. That upper bound of the maximal chain must be a maximal element.

6. Any set has a well-ordering. Consider the partial well orderings of the set ordered by being an initial segment. This is a chain bounded (and also chain closed) poset. So it has a maximal element by 5. If it was properly partial then any of the remaining elements could be added at end to refute maximality. So it must be a complete well ordering.

7. Consider any well ordering of the union of a partition. Define a transversal by choosing the least element of each block of the partition. So 6 implies 1 and all are equivalent to axiom of choice.

This article is incomplete.You can help $\mathsf{Pr} \infty \mathsf{fWiki}$ by expanding it.To discuss this page in more detail, feel free to use the talk page.When this work has been completed, you may remove this instance of `{{Stub}}` from the code.If you would welcome a second opinion as to whether your work is correct, add a call to `{{Proofread}}` the page. |

This article needs to be linked to other articles.You can help $\mathsf{Pr} \infty \mathsf{fWiki}$ by adding these links.To discuss this page in more detail, feel free to use the talk page.When this work has been completed, you may remove this instance of `{{MissingLinks}}` from the code. |

## Also see

## Source of Name

This entry was named for Max August Zorn.

He published it in 1935.

However, it had previously been reported by Kazimierz Kuratowski in 1922, in a slightly different (and simpler) form.

Hence this result is sometimes known as the Kuratowski-Zorn Lemma.

Zorn himself fully acknowledged Kuratowski in his own publication of this result, and was apparently somewhat embarrassed to have had it named after him, rather than Kuratowski. Kuratowski himself had not attached any particular importance to it, considering it a straightforward corollary of the Hausdorff Maximal Principle.

## Sources

- 1922: Kazimierz Kuratowski:
*Une méthode d'élimination des nombres transfinis des raisonnements mathématiques*(*Fund. Math.***Vol. 3**: pp. 76 – 108) - 1935: Max August Zorn:
*A remark on method in transfinite algebra*(*Bull. Amer. Math. Soc.***Vol. 41**: pp. 667 – 670)

- 1960: Paul R. Halmos:
*Naive Set Theory*... (previous) ... (next): $\S 16$: Zorn's Lemma - 1964: Steven A. Gaal:
*Point Set Topology*... (previous) ... (next): Introduction to Set Theory: $3$. The Axiom of Choice and Its Equivalents