Questions on proof assistants

Timothy Y. Chow tchow at math.princeton.edu
Fri May 15 13:19:03 EDT 2020


Hendrik Boom wrote:

> On Wed, May 13, 2020 at 08:34:58PM -0400, Timothy Y. Chow wrote:
> ...
>>
>> I would say that the main reason I haven't dived into Lean is that it seems
>> not to have stabilized yet.  Lean version 3 is not compatible with Lean
>> version 2, and Lean version 4 (which isn't ready yet) will not be compatible
>> with Lean version 3.  Lean version 4 may address some of Hales's criticisms
>> but at the cost of breaking many of the existing libraries (which, as I
>> said, are one of the best features of Lean).
>
> We could hope that it wuold be easy to mechanically convert proofs from old
> versions of Lean to new ones.
>
> Are they really *that* incompatible?

Someone who actually knows Lean should answer this question, but for 
example I believe that Lean 2 libraries were *not* in fact converted to 
Lean 3 libraries, so that doesn't bode well.  Also, Kevin Buzzard tells me 
that the entire typeclass system is being rewritten in Lean 4.  This 
sounds to me like a rather fundamental change.  Maybe a mechanical 
conversion of the old libraries would fail to take advantage of the new 
typeclass system and therefore partially defeat the purpose of the 
upgrade?

Kevin Buzzard's response to the question of the interoperability of 
different proof assistants is an interesting one.  When it comes to 
ordinary software, it is routine practice to completely discard old code 
and start afresh.  I remember in the early days of Java, one mantra was 
"write once, run anywhere."  Nowadays, a more accurate mantra for Java is 
"write once, run nowhere" because Java has had so many security holes that 
many browsers disable it by default.  But who cares?  Java is old news. 
There are new programming languages coming out all the time.  If you want 
something, just rewrite it.

Now I think when it comes to formal proofs, most mathematicians 
instinctively balk at this kind of philosophy.  The Flyspeck project 
finished successfully with a formal proof of the Kepler conjecture. 
Suppose I want to use the Kepler conjecture as a step in my own proof. 
Instinctively, it feels wrong to take the attitude, "Well, if you need it, 
just rewrite the proof yourself."  Who is really going to do that?  If one 
day the classification of finite simple groups (CFSG) is formalized, do we 
expect to have to re-implement it every couple of years when there's a 
software upgrade or a hot new proof assistant du jour?  I don't think 
these are "wrong questions" as Buzzard seems to suggest.  We no longer 
have much need for software that reads 5.25" floppy disks, so it's no big 
loss if that software dies.  But we *do* expect to use CFSG for many 
decades if not centuries to come.

It's possible that we have to let go of the "prove once, use forever" 
mentality as a naive youthful dream of formalized mathematics that is just 
not realistic.  Still, if we let go of too many dreams, then we should ask 
ourselves what is left.  For example, driving down error rates is another 
dream that may be unrealistic, as I've discussed on FOM before:

https://cs.nyu.edu/pipermail/fom/2014-August/018067.html

Another dream is that once a proof is formalized, the running time 
requires for a computer to check the proof will be negligible.  This dream 
we already know is likely to be shattered.  Flyspeck is a case in point. 
There are increasingly many theorems whose proofs require thousands of 
hours of computer time even without formalization.  It seems inevitable 
that people are going to want to be able to use such theorems without 
having to check the proof each time, and once that starts to happen, the 
chances of errors creeping in is going to rise.

None of this is to denigrate formal proofs or proof assistants, which I do 
believe are the way of the future.  But it's probably worth getting our 
story straight about what we can realistically expect from them.

Tim


More information about the FOM mailing list