Ordinals and axioms · Definition

Zorn's lemma

set theoryordinals and axioms

Before you start you need to know

Zorn's lemma allows proving the existence of maximal objects where an explicit construction is impossible. It is frequently used in algebra and functional analysis.

Definition

Zorn's lemma is a principle equivalent to the axiom of choice stating that every nonempty partially ordered set in which every chain has an upper bound contains a maximal element.

\[\\forall P\\neq\\varnothing\\,\\Big[\\Big(\\forall C\\subseteq P\\,\\big(\\text{cadena}(C)\\Rightarrow\\\\\exists u\\in P\\,\\forall c\\in C\\,c\\le u\\big)\\Big)\\Rightarrow\\\\\exists m\\in P\\ \\text{maximal}\\Big]\]

If \((P,\le)\) is a nonempty partially ordered set and every chain in \(P\) has an upper bound in \(P\), then there exists a maximal element \(m\in P\), that is, no \(x\in P\) satisfies \(m<x\). A chain is a totally ordered subset of \(P\), and the empty chain is bounded by any element of \(P\).

Let \(P\) be the family of finite subsets of \(\mathbb{N}\) ordered by inclusion. Every finite chain has a maximum, but infinite chains such as \(\{\{1,\dots,n\}: n\in\mathbb{N}\}\) have upper bound \(\mathbb{N}\), which is not in \(P\). So the hypothesis fails and the lemma does not guarantee a maximal element.

A typical error is confusing maximal with maximum: \(m\) being maximal does not imply \(x\le m\) for all \(x\in P\). For example, in \(\{a,b\}\) with the discrete order, both elements are maximal and neither is a maximum.

Think about it

Why do infinite chains matter when applying the lemma?

Because the hypothesis requires an upper bound for every chain, including infinite ones.

Exercises 10

  1. What does Zorn's lemma state?
  2. Which axiom is Zorn's lemma equivalent to?
  3. What is a chain in a partially ordered set?
  4. What does it mean for \(m\) to be a maximal element of \(P\)?
  5. What condition must every chain satisfy to apply Zorn's lemma?
  6. In \(\mathcal{P}(\{1,2\})\) ordered by inclusion, how many maximal elements are there?
  7. Let \(P=\{\{1\},\{2\},\{1,2\}\}\) ordered by inclusion. What is a maximal chain of \(P\)?
  8. Let \(P=\{1,2,3,\dots\}\) with the divisibility order. Does \(P\) have a maximal element?
  9. What is the upper bound of the chain \(\{\{1,\dots,n\}: n\in\mathbb{N}\}\) among the finite subsets of \(\mathbb{N}\)?
  10. Let \(P\) be the family of partial injective functions from \(A\) to \(A\) ordered by extension, with \(A\) infinite. If a chain \(C\) has union \(f=\bigcup C\), what conclusion follows when applying Zorn's lemma?

References

  • Herbert B. Enderton, Elements of Set Theory, 1st edition, Academic Press, 1977.
  • Thomas Jech, Set Theory (The Third Millennium Edition), 3rd millennium edition, Springer, 2003.