upvote
OK, but if I write code, I can verify it in a few simple steps. What about 250k pages of proof? How can I verify that page 133,432 has the correct assumptions and that it isn't reward hacked just to make lean code pass? How it's done?
reply
You don't need to! That is the beauty of Lean. You only need to check the problem definition (which is no where near 250k pages) and then Lean checks the proofs it self by checking whether each next line can be derived from previous lines. And for this problem, there are many validated problem definitions in Lean. So it is probably true.
reply
> and then Lean checks the proofs it self by checking whether each next line can be derived from previous lines

Ah, so it's similar to something like Merkle trees, where each leaf must be cryptographically valid up to the root otherwise the whole branch is invalid?

So you start with a simple definition that then evolves?

reply
The core idea is that you can map the types and terms of a type theory to the propositions and proofs of a formal logic

Different type theories correspond to different systems of formal logic with different levels of power and expression.

Simply Typed Lambda Calculus corresponds to intuitionistic propositional logic. If you lay out the typing judgements of STLC in natural deduction style and then physically erase the terms (leaving the types) then you literally have the rules of intuitionistic propositional logic.

So if you can write a term that typechecks at a type, that term is a proof of the corresponding proposition.

The easiest example is modus ponens, which is exactly the typing rule for function application:

  G |- M : A -> B     G |- N : A
  -------------------------------- (App)
            G |- M N : B
"Given a function from A to B and a value of A, you get a value of B."

So then in a proof checker you prove the proposition P => (P => Q) => Q by writing a program of that type:

  apply :: a -> (a -> b) -> b
  apply x f = f x
`apply` is demonstrated in haskell which does not have a rich enough type theory to give you more then an intuition (no pun intended) for how this all works. Things like `undefined` and general recursion let you "prove" any type, so it isn't a consistent logic. Languages like Lean and Agda are built on richer dependent type theories that give you far more expressive power for writing proofs (quantifiers, induction, etc.), and they won't let you cheat the type theory.

So to answer your question, no not a merkle tree but a tree none-the-less. You end up with a literal computer program which is a tree of expressions all of which must type check. If they type check then program itself is a proof for whatever proposition is encoded in the type of the program.

reply
You must write very small programs.
reply
You can personally verify every binary digit of your code in a few simple steps?
reply
So Lean itself is proved? With what... Lean?

A 250k pages proof is massive, even if correct, there is almost certainly something extremely inefficient or weird in there.

I cannot imagine that a fundamental proof like this will require hundred of thousand of logic steps.

Unless some part of the proof is about brute-force checking that something holds for a huge number of literal cases.

reply
> I cannot imagine that a fundamental proof like this will require hundred of thousand of logic steps.

It's pretty easy to imagine that, given a starting language, there are facts that require an arbitrary minimum number of words to prove. The only reason the proofs most people learn are short is because:

- There isn't time in a math course to teach arbitrarily long proofs

- Humans don't live long enough to construct arbitrarily long proofs.

- Human minds are turning out to be pretty feeble and they probably couldn't reliably construct and verify anything more than trivially short proofs in the era before computer assistance.

reply
> So Lean itself is proved? With what... Lean?

Yes, actually! Well, one of the kernels is, con-leche: https://github.com/leanprover/con-leche

"This is an external checker for the Lean theorem prover that is proven (in Lean) to be consistent in that it does not accept a proof of False."

reply
You are proving something with the same thing you set out to prove?

Or you mean one implementation is used to prove another? In that case, you have a mutual (or circular) recursion of proofs

reply