Remix.run Logo
▲ solomonb 10 minutes ago

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.