Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

This question is related to (maybe even the same in intent as) Question 1017, but none of the answers seem to address what I'm looking for.

There are a lot of resources available for people who want to use proof assistants like Coq, Isabelle, …, to prove properties about programs—and that's no surprise, since a lot of the development of these programs is done by computer scientists. However, I am interested in resources, and especially in course materials (because I'm trying to put together an independent study for a CS student), involving the use of proof assistants to prove mathematical statements—see the work of Hales and Weedijk for examples. Does anyone know of any such?

share|improve this question
4  
Yeah, it's called graduate student! =p –  Harry Gindi Dec 9 '09 at 5:51
add comment

5 Answers

up vote 3 down vote accepted

I am interested in the same kind of stuff. This article tells about work done to formalize group representation theory in Coq. In particular, they formalize the proof of Maschke's theorem (that $F[G]$ is semisimple when $G$ is a finite group).

Some links to math courses using Coq are listed in Cocorico.

share|improve this answer
add comment

Honestly, part of the reason that proof assistants are focused on proving programs is precisely because of our very limited understanding of how to actually represent mathematics in formal logical systems, as opposed to doing it in principle.

It turns out that program proof is basically applied metamathematics (i.e., verification of imperative programs is model theory, and verification of functional programs is structural proof theory) and this is the one area of mathematics where folks have really fully worked out in full detail how to represent what they're doing in formal logical systems. So the focus on program proof is partly making a virtue of necessity! (It's also because those of us in this area really like both programming and mathematics, and this is a great way to combine them...)

The number of people who know how to do real math in proof assistants and explain it to others can probably be counted on your fingers. A pair of suggestions to add to your list follows:

  • John Harrison wrote a recent book, Handbook of Practical Logic and Automated Reasoning, which people I trust rave about. It's a guide to all the decision procedures (e.g., SAT solving, unification, Presburger arithmetic, Groebner bases, etc.) that you need to raise the level of formal proof to a decent level of abstraction, together with their implementations in the HOL/Light system.

  • George Gonthier (who formally proved the Four Color Theorem in Coq) is currently working on formalzing the Feit-Thompson (aka Odd Order) Theorem of finite group theory. As part of this work, he and his collaborators are developing the more substantial libraries and proof automatation to support a more mathematical (as opposed to logical) style of reasoning in Coq. The guides to this work are "A Modular Formalisation of Finite Group Theory" and their Mathematical Components Library.

share|improve this answer
2  
+1: "how to actually represent mathematics". I'd add a third item: De Bruijn's writings on formalising the mathematical vernacular. –  Charles Stewart Feb 26 '10 at 20:07
    
+1 for mentionning de Bruijn's tremendous work in this area. The Automath papers still contain gems that few have yet to properly understand, and are reinventing all the time. –  Jacques Carette Feb 27 '10 at 2:52
add comment

Are you aware of the Archive of Formal Proof for Isabelle? It's a collection of formalized mathematics (and some program verification). Reading the papers there, and browsing the Isabelle theory file sources is a good way to learn.

The Isar tutorial is also a good place to look, if you want to write proofs that look like informal mathematics (as opposed to tactic style). It's quite hard to get the hang of at first (mostly due to lack of documentation), but once you get it, it's a lot easier to work with than plain lists of tactics.

If you're wanting to formalise anything with name binders (lambda-calculus, FOL, programming languages, pi-calculus, etc.) you should also check out the Nominal package for Isabelle which again helps with abstracting the proofs.

share|improve this answer
    
Thanks --I wasn't, but Cameron Freer (mentioned above by compguy) pointed it out to me when I e-mailed him. –  L Spice Dec 18 '09 at 19:58
1  
Is there a way to use Isabelle without having to learn Emacs and fighting against the usual OSS problems like make scripts that don't compile? –  darij grinberg Feb 13 '10 at 20:26
    
You can use Isabelle from an ML prompt. I wouldn't recommend it though. I think the Emacs frontend is going to be replaced shortly, I know there's been some work on porting ProofGeneral to the Eclipse platform. Also, I've never had a problem compiling Isabelle, even from the nightly SVN repositories. What problem are you encountering? –  user2596 Mar 30 '10 at 13:40
add comment

The best introduction to the usage of proof assistants in mathematics that I'm personally aware of is Cameron Freer's website vdash.org. That website also links to a few resources, including the home pages of Freek Wiedijk and John Harrison, which briefly describe the usage of proof assistants in proving mathematical statements.

Unfortunately, the usability of current proof assistants seems to be extremely primitive, so introducing them in a math graduate course is going to be a challenge. You may wish to take your question to the vdash google group and/or the FOM mailing list, where some might be able to provide you with useful suggestions or unpublished lecture notes.

share|improve this answer
    
Thanks a lot! Cameron was a student in a class I TA'd at Chicago in 1999; this is a good excuse to look him up again. –  L Spice Dec 18 '09 at 19:59
add comment

I would like to mention Mizar, proof verification system based on language which is human readable and very near to natural mathematical language used in mathematical practice. It is one of the longest working proof checkers, and it is one of the most successful one. Here You may find some about it: http://www.cs.ru.nl/~freek/mizar/ There is the whole library congaing presently more that 40Mb zipped proofs ( in pure ascii files!).

share|improve this answer
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.