Remix.run Logo
▲ utkuumur 3 hours ago

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.

▲lossolo2 2 hours ago | parent [-]

> 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?

▲solomonb 15 minutes ago | parent [-]

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.