Given any attempted list of all subsets of a type, form the subset that reverses membership at each element's own listed position. That diagonal subset cannot appear anywhere in the list.
power set
surjectivity
diagonal argument
fixed point
complementation
Exact theorem
Exact Mathlib statement
theorem Function.cantor_surjective {α : Type*} (f : α → Set α) : ¬Function.Surjective f
The theorem at a glance
Cantor's Theorem at a glance
A visual guide to the theorem's hypotheses, structure, and conclusion; the exact statement gives the formal detail.
No mapping from a type reaches every subset of that same type. Explanatory diagram.Detailed visual description
The poster makes the hypothetical enumeration, the diagonal subset, and the complement fixed-point contradiction explicit while keeping the formal endpoint at non-surjectivity onto Set α.
This map summarizes the statement's structure; the exact Mathlib declaration remains authoritative.
Cantor's Theorem schematic
Loading full-resolution image…
The diagonal subset reverses membership at each proposed preimage, so no enumeration reaches every subset.Open original image in a new tab
The diagonal subset reverses membership at each proposed preimage, so no enumeration reaches every subset. Explanatory scientific diagram.Detailed visual description
A single mapping tapestry connects source elements to candidate subsets. The gold diagonal construction follows those assignments and reverses each self-membership decision, making its own subset unavailable as an image of the function.
Why it matters
A mathematical landmark
Cantor's diagonal argument transformed the study of infinity and became a reusable template across logic, computability, and mathematics. The selected Mathlib theorem captures the exact non-surjectivity statement.
Proof architecture
Cantor's diagonal contradiction
2 curated stages
Mathlib proves that no function from a type to its power set is surjective by first showing that a hypothetical surjective family would force every endofunction to have a fixed point, then applying that bridge to complementation, which has no fixed point.
These source-anchored stages explain the retained Mathlib proof route. They are generated explanations, not proof evidence or an extracted Lean proof-term dependency graph.
01
A surjection would force every endofunction to have a fixed point
A surjection would force every endofunction to have a fixed point
Loading full-resolution image…
Evaluating a surjective family on its own index constructs an element fixed by any chosen endofunction.Open original image in a new tab
Evaluating a surjective family on its own index constructs an element fixed by any chosen endofunction.
Surjective f → ∀ g : β → β, ∃ x, g x = x
The checked helper exists_fixed_point_of_surjective assumes that a family f : α → α → β is surjective. For an endofunction g : β → β, surjectivity selects an index for the diagonal function a ↦ g (f a a); evaluating at that index produces a fixed point of g.
The diagonal proposition would have to be fixed by negation, yielding q↔¬q.
∀ (f : α → Set α), ¬ Function.Surjective f
The scientific panel shows the typed Lawvere route from f:α→(α→Prop) through q=f(a)(a) to a proposition fixed point under negation, which is impossible.
Accepted Atlas resultNot recorded for the preferred artifact
Mathlib is the source of the theorem; the local Lean replay and page review are separate.
Claim boundary
No new theorem is claimed
This target indexes Mathlib's diagonal theorem that no function from a type to its power set is surjective. It does not separately state the cardinal inequality or claim a new proof.
Proof Atlas did not originate Cantor's Theorem or Mathlib's declaration.
The selected declaration is non-surjectivity onto Set α, not a separately stated cardinal inequality or an assertion that no functions exist.
The generated explanation and visuals are not proof evidence.
