[KongchangAI]
· 2 min read· 1,459 words

Are Lean-Verified Theorems Absolutely Correct? Don't Be Misled by Formalization

Are Lean-Verified Theorems Absolutely …

Passing Lean's check only shows the formalized code is derivable within the logical system—not that the theorem is absolutely true.

The article analyzes the popular argument that "a theorem is correct because Lean checked it," noting that while formal verification offers high rigor, equating "passes Lean's check" with "the theorem is true" skips three key links: the natural-language-to-formal-code translation lacks formal guarantees; Lean verification depends on its own axioms and implementation, ensuring only in-system derivability; and formal proofs may be disconnected from human understanding. It argues Lean verification is strong evidence against human oversight but must be paired with scrutiny of the formalized statement and human understanding of the proof.

Introduction: When "Lean-Verified" Becomes a Correctness Endorsement

In discussions of mathematics and computer science, a new style of argument is gaining popularity: a theorem is correct because it has passed checking in a proof assistant like Lean. A recent discussion on Hacker News (167 points, 60 comments) revolves around exactly this phenomenon, with a title that gets straight to the core—how to interpret claims like "the theorem is correct because it has been checked by Lean."

Formal verification does provide a rigor that traditional mathematical proofs struggle to match, but equating "passes Lean's check" directly with "the theorem is true" skips over several links that deserve careful scrutiny. This article does not intend to deny the value of formalization, but rather to unpack the gaps in this chain of argument that are easily overlooked.

What Exactly Does Lean Verify?

The Translation Problem from Proposition to Code

What Lean checks is a piece of formalized code, not a mathematical proposition written in natural language. Between the two lies a translation step: the author must transcribe a statement like "every even number greater than 2 can be written as the sum of two primes" into a type-theoretic expression that Lean can understand.

The problem is that this translation process itself has no formal guarantee. If the conditions are written incorrectly, or the scope of quantifiers is confused, Lean will still faithfully verify a wrong proposition. Passing the check only shows that the code is consistent with Lean's logical system; it does not show that the code faithfully expresses the original intent.

Type Theory is the formal foundation of modern proof assistants (including Lean). Unlike set theory, type theory takes "types" as the basic concept, with propositions represented as types and the inhabitants of those types serving as proofs. For example, the proposition "A implies B" is represented as the function type (A \to B), and a proof is a function that takes a proof of A and returns a proof of B. This correspondence—"propositions as types, proofs as terms" (the Curry-Howard correspondence)—makes proof checking reducible to type checking.

The dependent type theory adopted by Lean allows types to depend on values, thereby enabling the expression of fine-grained structures such as "a vector of length n." When formalizing, the author must transcribe natural-language propositions into type expressions in dependent type theory, a process that requires an accurate understanding of the syntax and semantics of type theory. Common transcription errors include quantifier scope errors (such as mistakenly writing (\forall x \exists y) as (\exists y \forall x)), implicit assumptions not made explicit, and type mismatches caused by natural-language ambiguity. Since Lean only checks whether the code has the claimed type, transcription errors will not be automatically detected unless there is human review or meta-level formalization.

The Credibility of Axioms and Logical Foundations

Lean's verification rests on its own logical foundation, including the set of axioms and type-theoretic rules it adopts. Passing a proof means "derivable within Lean's logical system," not "true in an absolute sense." If someone has reservations about the axioms Lean relies on (such as the axiom of choice or the law of excluded middle), then the philosophical weight of the verification result changes accordingly.

Moreover, Lean's own implementation may contain bugs. Although such problems are very unlikely and the community has strict review mechanisms, treating "Lean-verified" as an endpoint that requires no further discussion is epistemically overconfident.

The Axiom of Choice asserts that for any family of nonempty sets, there exists a choice function that selects exactly one element from each set. It is widely used in mathematics to prove existence theorems (such as every vector space having a basis), but it has long been controversial because of its non-constructive nature. The Law of Excluded Middle asserts that any proposition is either true or false, i.e., (P \lor \neg P) holds for any proposition. In intuitionistic logic, the law of excluded middle is not accepted, which leads to differences in strength between constructive proofs and classical proofs.

Lean's default mathematical library is based on classical logic and adopts the axiom of choice and the law of excluded middle, which enables it to support the formalization of a large amount of classical mathematics, but also means that its verification results depend on that set of axioms. If the proof of a theorem substantively uses the axiom of choice, then within a constructivist framework that rejects that axiom, the theorem may not hold or may not have the same proof. Therefore, saying "Lean-verified" implicitly accepts the logical foundation adopted by Lean; people with different positions on the logical foundation will interpret the verification result differently.

In addition, the implementation of Lean's kernel itself (written in C++) may also have flaws, although its design goal is to be as small as possible and rigorously tested. The community reduces this risk through multiple implementations (such as checking exported proofs with an independent kernel), but this remains part of the trust chain.

"Verified" Does Not Equal "Understood"

A recurring theme in the Hacker News discussion is that formal verification and human understanding are two different things. A proof can pass checking in Lean, yet be so lengthy and dependent on a large number of automated tactics that no one has truly understood the structure of the proof.

The value of a traditional mathematical proof lies not only in the correctness of the conclusion but also in the fact that the proof process can convey why the conclusion holds. What passing Lean's check provides is only a binary answer; it does not explain the reasoning, nor does it guarantee that the proof is illuminating. For teaching, conceptual understanding, and subsequent research, this "black-box correctness" has limited use.

A more practical issue is maintenance cost: a proof that passes Lean's check may require a large amount of code, and when modifying or extending it later, the burden of understanding that code is no lighter than understanding a traditional proof.

How to Correctly Interpret Such Claims

Distinguish Different Levels of "Correctness"

When someone says "this theorem has been checked by Lean," a more reasonable interpretation is: within Lean's logical framework, given the formalized proposition, there exists a machine-checkable proof. This is a conditional technical statement, not an unconditional declaration of truth.

Some views in the discussion also point out that the greatest value of formal verification lies in eliminating human error—the omissions that easily occur in long handwritten proofs. This is a genuine contribution, but it is not the same thing as "guaranteeing mathematical truth."

Formalization Is a Tool, Not an Authority

Citing Lean as an authority easily degrades a discussion from "whether the reasoning of this proof is sound" to "have you verified it or not." This shift is not necessarily good for mathematical communication. Formalization should be a supplementary means of checking, not a shield that ends discussion.

One tendency toward consensus in the Hacker News comment section is: Lean verification is strong evidence, but it needs to be combined with scrutiny of the formalized statement itself and human understanding of the proof's reasoning in order to constitute a complete argument for correctness.

Conclusion

Proof assistants like Lean are changing the standards of mathematical rigor, and that is beyond doubt. But the sentence "it passes Lean's check, therefore the theorem is correct" omits three dimensions: fidelity of translation, credibility of the logical foundation, and human understanding. Restoring these dimensions is not meant to weaken the value of formalization, but to make discussions around it more honest and more informative. The next time you see such a claim, asking one more question—"what exactly is the formalized proposition?"—will often be more rewarding than simply accepting the conclusion.

One-line Summary

Passing Lean's check only shows that the formalized code is derivable within the logical system; it does not mean the theorem is absolutely true.

Paragraph Summary

The article analyzes the popular argument that "a theorem is correct because it has been checked by Lean," pointing out that although formal verification provides a high degree of rigor, equating "passes Lean's check" with "the theorem is true" omits three key links: the translation from natural-language propositions to formalized code lacks formal guarantees and may contain transcription errors; Lean verification depends on its own logical axioms and implementation, guaranteeing only derivability within the system rather than absolute truth; and formal proofs are disconnected from human understanding, so a proof that passes checking may be lengthy and obscure, with no one truly understanding it. The article argues for treating Lean verification as strong evidence for eliminating human oversight, while also requiring scrutiny of the formalized statement itself and understanding of the proof's reasoning in order to constitute a complete argument for correctness.

#Lean#formal verification#proof assistant#type theory#mathematical truth#logical foundations
Share:

Related articles