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 be a nonempty poset in which every chain has an upper bound. Then 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 in which every chain has an upper bound, and the Axiom of Choice.
, and every chain has an upper bound in .
Every family of nonempty sets has a choice function (The Axiom of Choice).
A progressive map on a chain-complete poset has a fixed point (Bourbaki–Witt fixed point theorem).
is maximal when there is no with (Maximal element and greatest element).
is a strict upper bound of when for every (Upper bound, least upper bound, and strict upper bound).
The empty set is a chain, and a subset is a chain when any two of its elements are comparable (Chain in a poset).
is a partial order, in particular transitive ( and imply ) and antisymmetric ( and imply ); the strict order means and , so is irreflexive (Partial order and partially ordered set).
Inclusion is a partial order on any collection of sets: ; and give by extensionality; and gives (Partial order and partially ordered set).
Proof
Suppose has no maximal element.
Let be the set of all chains of , a subset of the power set of , partially ordered by inclusion.
is a chain-complete poset: if is a chain under inclusion then is a chain of , since any two of its elements lie in a common member of , and it is the least upper bound of under inclusion; the empty chain has least upper bound , which is a chain.
For let be the set of strict upper bounds of in .
Each is nonempty: has an upper bound in by hypothesis, taking any element of the nonempty when ; by assumption is not maximal, so there is with ; then for every transitivity gives from , and , since would give and , hence by antisymmetry, contradicting ; so for every and .
Apply the Axiom of Choice to the family , every member of which is nonempty, obtaining a choice function with for each ; composing with the map , which is a function on , yields a selection defined for every chain , and no injectivity of is needed, since two chains with the same set of strict upper bounds simply receive the same chosen element.
Define for ; this is again a chain, because is a strict upper bound of and so is comparable to every element of .
is progressive for inclusion, since by construction.
By Bourbaki–Witt applied to the chain-complete and the progressive , there is with , that is .
But is a strict upper bound of , so every element of is strictly below it, giving , 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 . So on this library's convention, where is a chain (Chain in a poset), requiring every chain to have an upper bound already forces , 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 is genuinely independent and cannot be dropped. See 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).
Depends on
Used by
- The Axiom of Choice and Zorn's lemma are equivalent Corollary
- (ℕ, ≤) has no maximal element: Zorn's chain hypothesis fails Counterexample
- A progressive map with no fixed point, on a poset that is not chain-complete Counterexample
- Two maximal elements and no greatest element Counterexample
- A bounded function on ℝ with no local maximum and no local minimum at any point, upper semicontinuous at no point and lower semicontinuous at no point: compose the Hamel coefficient with a strictly increasing injection of ℝ into (0,1) Example
- An additive f : ℝ → ℝ that is not x ↦ cx: the coefficient of one fixed Hamel basis vector. It is unbounded above and below on every nondegenerate interval, its graph is dense in ℝ², and every nonempty level set is dense in ℝ Example
- The chains of a poset, ordered by inclusion, form a chain-complete poset Example
- FALSE: every additive f : ℝ → ℝ is of the form x ↦ cx for a single real c False statement
- FALSE: transfinite induction and recursion need the Axiom of Choice False statement
- FALSE: Zorn's lemma is a theorem of ZF False statement
- Assuming the Axiom of Choice, ℝ has a Hamel basis over ℚ: there is B ⊆ ℝ such that every real is a finite ℚ-linear combination of elements of B in exactly one way, and each basis vector carries a well-defined ℚ-linear coefficient map Lemma
- Under choice, the uncountable Δ-system lemma for finite sets Lemma
- The choice ledger: what costs the Axiom of Choice and what does not Remark
- The quasicompact convention, why compactness of a subset is read intrinsically here, and what each result on this page costs in choice Remark
- Alexander's subbase lemma: if every cover by members of a fixed subbasis has a finite subcover then the space is compact; the proof is an application of Zorn's lemma Theorem
- In a nonzero commutative ring, every proper ideal is contained in a maximal ideal Theorem
- The ultrafilter lemma, from the Axiom of Choice: every filter extends to an ultrafilter Theorem
- The well-ordering theorem Theorem
- Tychonoff's theorem: an arbitrary product of compact spaces is compact in the product topology, assuming the Axiom of Choice Theorem
- Zorn's lemma gives a basis between any linearly independent set and any spanning set containing it: if L ⊆ S ⊆ V with L independent and span(S) = V, there is a basis B of V with L ⊆ B ⊆ S Theorem
Dependency tree · next 3 levels
Direct dependencies and their dependencies through the next three levels: 17 results over 8 levels. An arrow runs from a result to what uses it, and this result sits at the bottom with a heavier outline. Click the chart to enlarge it.
Sources
- Encyclopedia of Mathematics, Zorn lemma (standard reference, not scraped)
- Bourbaki–Witt theorem (Wikipedia) (standard reference, not scraped)
- Zorn's lemma (Wikipedia) (standard reference, not scraped)
- Axiom of choice (Wikipedia) (standard reference, not scraped)