TheoremStatement: Literature-sourcedProof: AI-adaptedprecheck passjudge pass (z-ai/glm-5.2)verified 2026-07-26 (claude-opus-5)

How statement and proof provenance work

The first chip identifies the source of the statement or construction; the second identifies the source of its local proof or verification.

Literature-sourced: the exact statement appears in a cited source; only wording and notation differ.
AI-adapted: a semantically identical restatement of literature-sourced material, modulo indexing, notation, and boundary cases adopted by the library.
AI-generated: a genuinely novel statement formulated by AI, with no source for the claim itself.

These labels describe origin, not correctness: citations and verification chips remain separate evidence.

Zorn's lemma

Statement

Assume the Axiom of Choice (The Axiom of Choice). Let $(P, \leq)$ be a nonempty poset in which every chain has an upper bound. Then $P$ has a maximal element (Maximal element and greatest element).

Note the hypothesis asks only for an upper bound, not a least upper bound, and the conclusion asserts only that a maximal element exists, never that a greatest one does.

Facts & Assumptions

Given: A nonempty poset $(P, \leq)$ in which every chain has an upper bound, and the Axiom of Choice.

[A1]

$P \neq \emptyset$ , and every chain $C \subseteq P$ has an upper bound in $P$ .

[A2]

Every family of nonempty sets has a choice function (The Axiom of Choice).

[L1]

A progressive map on a chain-complete poset has a fixed point (Bourbaki–Witt fixed point theorem).

[L2]

$m$ is maximal when there is no $x$ with $m < x$ (Maximal element and greatest element).

[L3]

$u$ is a strict upper bound of $S$ when $s < u$ for every $s \in S$ (Upper bound, least upper bound, and strict upper bound).

[L4]

The empty set is a chain, and a subset is a chain when any two of its elements are comparable (Chain in a poset).

[L5]

$\leq$ is a partial order, in particular transitive ( $u \leq v$ and $v \leq w$ imply $u \leq w$ ) and antisymmetric ( $u \leq v$ and $v \leq u$ imply $u = v$ ); the strict order $u < v$ means $u \leq v$ and $u \neq v$ , so $<$ is irreflexive (Partial order and partially ordered set).

[L6]

Inclusion is a partial order on any collection of sets: $A \subseteq A$ ; $A \subseteq B$ and $B \subseteq A$ give $A = B$ by extensionality; and $A \subseteq B \subseteq C$ gives $A \subseteq C$ (Partial order and partially ordered set).

Proof

technique · contradiction

1.1assume-contra

Suppose $P$ has no maximal element.

1.2L4L6construct

Let $C$ be the set of all chains of $P$ , a subset of the power set of $P$ , partially ordered by inclusion.

2.1step 1.2L4L6

$(C, \subseteq)$ is a chain-complete poset: if $D \subseteq C$ is a chain under inclusion then $⋃ D$ is a chain of $P$ , since any two of its elements lie in a common member of $D$ , and it is the least upper bound of $D$ under inclusion; the empty chain has least upper bound $⋃ \emptyset = \emptyset$ , which is a chain.

2.2step 1.2L3construct

For $C \in C$ let $S_{C}$ be the set of strict upper bounds of $C$ in $P$ .

3.1step 2.2step 1.1A1L2L3L5

Each $S_{C}$ is nonempty: $C$ has an upper bound $u$ in $P$ by hypothesis, taking any element of the nonempty $P$ when $C = \emptyset$ ; by assumption $u$ is not maximal, so there is $v$ with $u < v$ ; then for every $c \in C$ transitivity gives $c \leq v$ from $c \leq u \leq v$ , and $c \neq v$ , since $c = v$ would give $v \leq u$ and $u \leq v$ , hence $u = v$ by antisymmetry, contradicting $u < v$ ; so $c < v$ for every $c \in C$ and $v \in S_{C}$ .

4.1step 3.1A2

Apply the Axiom of Choice to the family $S = {S_{C} : C \in C}$ , every member of which is nonempty, obtaining a choice function $g$ with $g (S) \in S$ for each $S \in S$ ; composing with the map $C \mapsto S_{C}$ , which is a function on $C$ , yields a selection $C \mapsto g (S_{C}) \in S_{C}$ defined for every chain $C$ , and no injectivity of $C \mapsto S_{C}$ is needed, since two chains with the same set of strict upper bounds simply receive the same chosen element.

5.1step 4.1step 2.2L3L4L5construct

Define $f (C) = C \cup {g (S_{C})}$ for $C \in C$ ; this is again a chain, because $g (S_{C})$ is a strict upper bound of $C$ and so is comparable to every element of $C$ .

6.1step 5.1

$f$ is progressive for inclusion, since $C \subseteq f (C)$ by construction.

7.1step 2.1step 6.1L1

By Bourbaki–Witt applied to the chain-complete $C$ and the progressive $f$ , there is $C_{0} \in C$ with $f (C_{0}) = C_{0}$ , that is $g (S_{C_{0}}) \in C_{0}$ .

8.1step 7.1step 4.1L3L5discharge-contradiction∎

But $g (S_{C_{0}})$ is a strict upper bound of $C_{0}$ , so every element of $C_{0}$ is strictly below it, giving $g (S_{C_{0}}) < g (S_{C_{0}})$ , which is impossible because $<$ is irreflexive.

Remarks

The Axiom of Choice is used exactly once, at step 4.1, and nowhere else. Everything before it, including Bourbaki–Witt, is a theorem of ZF. That is why the fixed point theorem is kept as a separate item: it marks the boundary between what is free and what is bought.
The hypothesis is about all chains, including the empty one, whose upper bounds are exactly the elements of $P$ . So on this library's convention, where $\emptyset$ is a chain (Chain in a poset), requiring every chain to have an upper bound already forces $P \neq \emptyset$ , and the nonemptiness hypothesis is stated separately for emphasis rather than as an independent assumption. In particular the empty poset does not satisfy the hypothesis: there the empty chain has no upper bound, because there is nothing at all to be one. Under the competing convention, on which chains are required to be nonempty, nonemptiness of $P$ is genuinely independent and cannot be dropped. See $(N, \leq)$ has no maximal element: Zorn's chain hypothesis fails ↗ for the failure when unbounded chains exist.
The conclusion is maximal, not greatest, and conflating the two is the most common error in applying the lemma (FALSE: every maximal element is a greatest element).
The converse holds: Zorn's lemma implies the Axiom of Choice (Zorn's lemma implies the Axiom of Choice), so the two are equivalent over ZF (The Axiom of Choice and Zorn's lemma are equivalent).

Zorn's lemma

Statement

Facts & Assumptions

Proof

Remarks

Depends on

Dependency tree · 2 levels

Sources