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
- Bauer maximum principle Corollary
- Orthonormal eigenbasis for a compact self adjoint operator Corollary
- 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
- A prime containing an ideal and avoiding a multiplicative set Lemma
- 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
- Boolean ultrafilter extension Lemma
- Extension from subobjects of a generator detects injectivity Lemma
- If some ideal is not finitely generated, there is one maximal among the ideals that are not Lemma
- Maximal orthogonal family of cyclic reducing subspaces Lemma
- Maximal residue-injective subfields exist Lemma
- Minimal primes over a proper ideal exist Lemma
- Normal Suslin-tree forcing is countably distributive Lemma
- Nowhere-separable quotient of a Suslin line Lemma
- Sweet density transfers along complete suborders Lemma
- The first-difference order on branches Lemma
- Under choice, the uncountable Δ-system lemma for finite sets Lemma
- The proved choice ledger: hypotheses, equivalences, and upper bounds Remark
- The quasicompact convention, why compactness of a subset is read intrinsically here, and what each result on this page costs in choice Remark
- A countably closed forcing adds a normal Suslin tree Theorem
- AC implies BPI Theorem
- 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
- Assuming Choice, a base-field embedding extends across every algebraic extension Theorem
- Assuming Choice, every field has an algebraic extension containing roots of all nonconstant base polynomials Theorem
- Baer's criterion for injective modules Theorem
- Diamond constructs a normal splitting Suslin tree Theorem
- Equivalent characterizations of semisimple modules Theorem
- Existence of a maximal orthonormal family, and maximality as completeness Theorem
- Hahn-Banach dominated extension theorem for real vector spaces Theorem
- In a nonzero commutative ring, every proper ideal is contained in a maximal ideal Theorem
- Krein–Milman existence of extreme points Theorem
- L two kernels give Hilbert–Schmidt operators Theorem
- Local structure of distributions as derivatives of continuous functions Theorem
…and 9 more results.
Dependency tree · two levels
10 results within two dependency steps of this one, each drawn at its shortest distance from it. An arrow runs from a result to what uses it, so the chart reads left to right and ends at this result, which carries a heavier outline. Every node is a link to that result. Click elsewhere on 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)