If you’ve ever used Lean, Coq, or Agda, you know the feeling. You write a proof, hit “check,” and the type checker returns a green checkmark. A quiet confidence settles in: your reasoning is formally verified, mathematically sound, bulletproof. But here’s the uncomfortable truth that almost nobody talks about: that type checker is just software. And software has bugs.
This isn’t a theoretical edge case. It’s a fundamental paradox buried at the heart of formal verification. The Curry-Howard correspondence tells us that programs are proofs and types are theorems. It’s a beautiful, elegant mapping between computation and logic. But the type checker that enforces this correspondence is itself a program—a concrete, bug-prone implementation of an abstract mathematical ideal. So when you trust your proof assistant, you are really trusting a chain of code that could be wrong. And that chain includes the type checker itself.
Let me be blunt: the type checker is not the final arbiter of truth. It’s a fallible interpreter of a mathematical ideal. This isn’t an attack on the brilliant people building these systems. It’s a reality check for anyone who has ever treated a green checkmark as an infallible seal of correctness.
Consider the concept of the trusted computing base (TCB). In a proof assistant, the TCB is the smallest set of code that must be correct for all proofs to be trusted. Ideally, the TCB is tiny—a minimal kernel that implements the logic. But even that kernel is written by humans, reviewed by humans, and deployed on hardware that can have its own bugs. The moment you extend the system with macros, tactics, or automation, your TCB grows. And with it, the chance of a subtle error that undermines every proof you’ve ever built.
I’ve seen researchers spend months formalizing a complex theorem, only to discover that a rarely-used feature of the type checker had a corner-case bug. The proof was correct in the ideal world of the Curry-Howard correspondence, but the implementation failed to recognize it. The green checkmark was a lie—not because the math was wrong, but because the software was.
This is the uncomfortable paradox: the very tool we designed to guarantee mathematical certainty is itself a source of uncertainty. We rely on type checkers to catch our mistakes, but who catches the type checker’s mistakes? The answer is: more code, more reviews, more testing. But at some point, you hit a recursive trust problem. You can’t formally verify the verifier without an even larger verifier, ad infinitum.
So what does this mean for you, the user of Lean, Coq, or Agda? It means understanding the difference between the logical guarantee (the Curry-Howard ideal) and the implementation guarantee (the actual software). The real guarantee lies in the semantic model underlying the logic, not in the type checker’s execution. That’s why the TCB is a critical concept that is often overlooked in tutorials and blog posts.
Take a side: pretending type checkers are infallible is dangerous. It fosters a false sense of security that can lead to catastrophic errors in safety-critical systems—avionics, medical devices, cryptographic protocols. The most honest approach is to acknowledge the gap, shrink the TCB as much as possible, and treat the type checker as a fallible assistant, not an oracle.
Here’s the twist that might change how you think about formal verification: the fallibility of type checkers doesn’t invalidate the entire enterprise; it makes it more human. We are not building perfect machines. We are building tools that help us reason more carefully, with the understanding that the tools themselves are part of the messy, imperfect world. The real breakthrough is not the green checkmark—it’s the process of formalizing your reasoning, which exposes assumptions you didn’t know you had. The type checker might be wrong, but it still forces you to think more clearly than you would without it.
So next time you see that green checkmark, pause. Ask yourself: what is the trusted computing base here? Which parts of the system am I implicitly trusting? And then get back to work. Because the alternative—not using formal verification at all—is far worse.
FAQ
Q: If type checkers can be wrong, how can we trust any formal proof?
A: You can't trust them absolutely—you can only trust them up to the correctness of the trusted computing base (TCB). The goal is to minimize the TCB and formally verify it when possible. But ultimately, formal verification reduces the risk of error; it doesn't eliminate it. The alternative (no verification) is far riskier.
Q: What should I do differently when using proof assistants?
A: Be aware of the TCB size. Use proof assistants with a small, well-audited kernel (like Lean's kernel). Avoid relying on opaque tactics or automation without understanding their correctness. And always cross-check critical proofs with a different method or tool when possible.
Q: What's the contrarian take?
A: The fallibility of type checkers actually makes formal verification more honest. It forces us to acknowledge that all human reasoning—even with computers—is provisional. The real value of proof assistants is not the infallible stamp, but the discipline of formalizing thought. That discipline catches far more errors than it misses.