A Lean 4 Formalization of Scott's Continuous Lattices (1972)
Lars Warren Ericson
cs.LO
Jun 29, 2026 · v1
math.LO
TL;DR
Complete sorry-free Lean 4 formalization against Mathlib of Scott's 1972 Continuous Lattices, including 43 numbered results and the D∞ λ-calculus model.
Abstract
We present a complete machine-checked formalization of Dana Scott's landmark 1972 paper Continuous Lattices [Sco72], carried out in Lean 4 against mathlib and including the March 1972 Milner correction in [Sco72] (pp. 135–136). Scott's paper develops a model for \(λ\)-calculus from a topological starting point. He defines injective \(T_0\)-spaces – those with a strong extension property for continuous maps – and shows that they are exactly the continuous lattices: complete lattices whose Scott topology is determined by the order via the way-below relation (\(\ll\)). On this foundation he studies projections, retractions, products, function spaces, and inverse limits. The capstone (Theorem 4.4) constructs an inverse limit \(D_\infty\) of function-space approximants and proves \(D_\infty \cong [D_\infty \to D_\infty]\), yielding a purely mathematical model for Church's untyped \(λ\)-calculus. Our development formalizes 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_\infty\)/\(j_\infty\) pair). The formalization is classical (uses 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 \(\texttt{[propext, Classical.choice, Quot.sound]}\).
Problem
Dana Scott's 1972 paper Continuous Lattices develops a topological model for the untyped λ-calculus but its many results had not been machine-checked. Providing a verified formalization requires reconstructing proofs and resolving gaps or corrections.
Approach
The development formalizes 43 numbered results from Sections 1–4 of Scott's paper in Lean 4 against Mathlib, following Scott's proof dependency order. It includes the March 1972 Milner correction and supporting infrastructure such as step functions, the way-below relation, the ⇑a basis of Scott opens, the function-space tower, and the i∞/j∞ pair. Proofs are classical, using Classical.choice transitively.
Results
All 43 results are stated and proved as sorry-free Lean theorems, with the capstone constructing the inverse limit D∞ and proving D∞ ≅ [D∞ → D∞]. All proofs check with the standard footprint [propext, Classical.choice, Quot.sound], with notes recording proof choices and dead ends.