cantors_diagonalization

What problem does it solve?

Cantor's diagonalization proves that a set has strictly greater cardinality than its power set by constructing a diagonal element that differs from every element of any proposed enumeration, thereby establishing non-enumerability. The technique also generalizes to computability arguments (e.g., no Turing machine can decide the Halting problem) and other diagonal arguments in mathematics and logic. In Lean 4 / mathlib4, Cantor.not_surjective provides the abstract result; the method typically explicitly defines a diagonal function such as d : ℕ → Bool that inverts f(n)(n) at each step.

Core Features & Use Cases

• Formal diagonal construction to refute surjectivity in Lean 4 / mathlib4 proofs.
• Application to uncountability results, Cantor's theorem, and computability arguments (e.g., Halting problem undecidability).
• Lean 4 templates including a concrete diagonal function d(n) = not f(n)(n) used to exhibit a counterexample.

Quick Start

Provide a surjection f : ℕ → S and request the diagonal element that differs from every f(n) at position n.