A Lean 4 Formalization of Scott's Continuous Lattices (1972)
Abstract
We present a complete machine-checked formalization of Dana Scott's landmark 1972 paper \emph{Continuous Lattices} \textbf{[Sco72]}, carried out in Lean 4 against mathlib and including the March 1972 Milner correction in \textbf{[Sco72]} (pp.~135--136). Scott's paper develops a model for λ-calculus from a topological starting point. He defines \emph{injective} T0-spaces -- those with a strong extension property for continuous maps -- and shows that they are exactly the \emph{continuous lattices}: complete lattices whose Scott topology is determined by the order via the way-below relation (≪). On this foundation he studies projections, retractions, products, function spaces, and inverse limits. The capstone (Theorem 4.4) constructs an inverse limit D∞ of function-space approximants and proves D∞ ≅ [D∞ → D∞], yielding a purely mathematical model for Church's untyped λ-calculus. Our development formalizes \textbf{43 numbered results} from Scott's Sections 1--4 (Propositions, Corollaries, Lemmas, and Theorems), each as a sorry-free Lean theorem, together with supporting infrastructure (step functions, the Uparrow a basis of Scott opens, Milner's coarser-than-Scott hypothesis, the function-space tower, and the i∞/j∞ pair). The formalization is \textbf{classical} (uses \texttt{Classical.choice} transitively) and follows Scott's proof dependency order. Where the Lean proof required choices not visible in the original -- or where dead ends were encountered -- we record detailed notes in Section 5. All proofs check with the standard footprint [propext, Classical.choice, Quot.sound]. The formalization has been accepted into the Palomar registry.
Related
- The product of two Scott sober complete lattices is not always Scott sober
- Global Regularity for the 3D Incompressible Navier–Stokes Equations via the Frohmanian Symplectic Tether: Lean 4 Formalization and Conditional Cubic Comparison Framework (v2.1)
- Formalization of Landau damping in the Vlasov--Poisson equations in Lean
- A Lean Formalization of the Hamilton--Perelman Proof of the Three-Dimensional Poincaré Conjecture
- A Lean Formalization of the Hamilton--Perelman Proof of Thurston's Geometrization Conjecture
BibTeX
@misc{ericson2026lean,
title = {{A Lean 4 Formalization of Scott's Continuous Lattices (1972)}},
author = {Lars Warren Ericson},
howpublished = {arXiv},
year = {2026},
month = sep,
doi = {10.48550/arxiv.2606.30782},
eprint = {2606.30782},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2606.30782},
note = {CC BY 4.0},
}
RIS
TY - UNPB
TI - A Lean 4 Formalization of Scott's Continuous Lattices (1972)
AU - Lars Warren Ericson
PY - 2026
DA - 2026/09/06
PB - arXiv
DO - 10.48550/arxiv.2606.30782
UR - https://arxiv.org/abs/2606.30782
AB - We present a complete machine-checked formalization of Dana Scott's landmark 1972 paper \emph{Continuous Lattices} \textbf{[Sco72]}, carried out in Lean 4 against mathlib and including the March 1972 Milner correction in \textbf{[Sco72]} (pp.~135--136). Scott's paper develops a model for λ-calculus from a topological starting point. He defines \emph{injective} T_0-spaces -- those with a strong extension property for continuous maps -- and shows that they are exactly the \emph{continuous lattices}: complete lattices whose Scott topology is determined by the order via the way-below relation (≪). On this foundation he studies projections, retractions, products, function spaces, and inverse limits. The capstone (Theorem 4.4) constructs an inverse limit D_∞ of function-space approximants and proves D_∞ ≅ [D_∞ → D_∞], yielding a purely mathematical model for Church's untyped λ-calculus. Our development formalizes \textbf{43 numbered results} from Scott's Sections 1--4 (Propositions, Corollaries, Lemmas, and Theorems), each as a sorry-free Lean theorem, together with supporting infrastructure (step functions, the Uparrow a basis of Scott opens, Milner's coarser-than-Scott hypothesis, the function-space tower, and the i_∞/j_∞ pair). The formalization is \textbf{classical} (uses \texttt{Classical.choice} transitively) and follows Scott's proof dependency order. Where the Lean proof required choices not visible in the original -- or where dead ends were encountered -- we record detailed notes in Section 5. All proofs check with the standard footprint [propext, Classical.choice, Quot.sound]. The formalization has been accepted into the Palomar registry.
ER -