Live data from Hacker News

Theorem Proving in Lean [pdf]

leanprover.github.io

21–23 of 23 posts

Re: Theorem Proving in Lean [pdf]

#21

has anybody proved something interesting in Lean? Perhaps not too difficult, but some proposition that might take a couple of days of work done in hours? I'm all for encoding foundations in a programmatic framework, but it seems that the idea here is to make this a useful tool for practicing mathematicians. The documentation didn't seem to have any examples of how that might happen.

Well, there is the entire mathematical components library[0]. It's still fairly elementary, roughly at an advanced undergraduate level.

Right now it actually takes far more time to write lean code than to prove things by hand. What is typically done in a single lecture in an intro Algebraic Number Theory course can take hours upon hours to implement. E.g. the Pell equation [1]. You have to be extremely explicit about everything, and can't handwave the details you do in human proofs.

Right now the overhead of writing proofs in Lean is so large that you'd prove a theorem with pen and paper before attempting it in Lean. So far it is a useful tool for proof verification, but not for actually coming up with them.

As things stand, computer proofs are only better than humans for things that are highly combinatorial in nature. which due to performance concerns usually aren't written in languages running in VMs.

[0]https://github.com/leanprover-community/mathlib

[1]https://github.com/leanprover-community/mathlib/blob/master/...

Re: Theorem Proving in Lean [pdf]

#22

Earlier quoted context omitted.

So is homotopic type theory just another way to look at the same thing or is it more expressive than type and set theory? In other words, does homotopic type theory really help theorem checkers/provers?

Homotopy Type Theory is based on Martin-Lof Type Theory (which is your standard dependent type theory), but reinterprets equality to mean homotopy equivalence. In vanilla MLTT, a = b is inhabited iff a and b share the same normal form, and its proof is refl (reflexivity). In HoTT, a = b may be inhabited by proofs other than refl. Namely, the univalence axiom states that types are equal when they are isomorphic, and f…

> So, HoTT allows you to prove things that you can't prove under ordinary MLTT.

Well, adding consistent axioms often allows proving more thing, but that in itself does not necessarily mean it's more useful, and certainly not that proofs are easier -- that, I believe, was the question. For example, adding the axiom 1/0 = 0 is consistent with ordinary arithmetics, and also allows you to prove more things (e.g. that 1/0 = 0), but is not necessarily useful and not necessarily helpful.

Post reply on HN