# How do proof verifiers work?

I'm currently trying to understand the concepts and theory behind some of the common proof verifiers out there, but am not quite sure on the exact nature and construction of the sort of systems/proof calculi they use. Are they essentially based on higher-order logics that use Henkin semantics, or is there something more to it? As I understand, extending Henkin semantics to higher-order logic does not render the formal system any less sound, though I am not too clear on that.

Though I'm mainly looking for a general answer with useful examples, here are a few specific questions:

• What exactly is the role of type theory in creating higher-order logics? Same goes with category theory/model theory, which I believe is an alternative.
• Is extending a) natural deduction, b) sequent calculus, or c) some other formal system the best way to go for creating higher order logics?
• Where does typed lambda calculus come into proof verification?
• Are there any other approaches than higher order logic to proof verification?
• What are the limitations/shortcomings of existing proof verification systems (see below)?

The Wikipedia pages on proof verification programs such as HOL Light Coq, and Metamath give some idea, but these pages contain limited/unclear information, and there are rather few specific high-level resources elsewhere. There are so many variations on formal logics/systems used in proof theory that I'm not sure quite what the base ideas of these systems are - what is required or optimal and what is open to experimentation.

Perhaps a good way of answering this, certainly one I would appreciate, would be a brief guide (albeit with some technical detail/specifics) on how one might go about generating a complete proof calculus (proof verification system) from scratch? Any other information in the form of explanations and examples would be great too, however.

• Not quite a full answer, but do recall that the Curry-Howard correspondence links type theory to formal logic. Types and functions are isomorphic to propositions and implications. Of course it's more thorough, but that's the gist. Jul 22 '10 at 9:30
• @Quadrescence: Thanks, I'll have to have a look at that. It's also struck me that proof systems seem to be based off constructive (intuitionistic) logic rather than classical logic. Is this the case? Jul 22 '10 at 9:39
• For an overview of the different provers, you might like Freek Wiedijk's "Comparing mathematical provers", cs.ru.nl/~freek/comparison/diffs.pdf John Harrison's book, "Handbook of Practical Logic and Automated Reasoning", contains the description of an interactive theorem prover in the LCF style. The code is available online: cl.cam.ac.uk/~jrh13/atp/index.html Jul 22 '10 at 15:14
• @Noldorin: Concerning constructive/classical logic: both are used, with for example Coq being popular for constructive reasoning (though also supporting classical logic), while the various HOL systems are popular for classical reasoning. Jul 22 '10 at 15:24
• @Noldorin: I don't know of short summary, but with a constructive system you can in principle extract witnesses to existential statements and computable functions for $\forall\exists$-statements and so on. However, constructive and classical logic can be interpreted in each other, so in that sense they're equivalent. And for instance both Coq and Isabelle/HOL allow program extraction from constructive proofs. Jul 22 '10 at 17:52

• What exactly is the role of type theory in creating higher-order logics? Same goes with category theory/model theory, which I believe is an alternative.

Don't think of type theory, categorical logic, and model theory as alternatives to one another. Each step on the progression forgets progressively more structure, and whether that structure is essence or clutter depends on the problem you are trying to solve. Roughly speaking, the two poles are type theory and model theory, which focus on proofs and provability, respectively.

To a model theorist, two propositions are the same if they have the same provability/truth value. To a type theorist, equisatisfiability means that we have a proof of the biimplication, which is obviously not the same thing as the propositions being the same. (In fact, even the right notion of equivalence for proofs is still not settled to type theorists' satisfaction.)

Categorical logicians tend to move between these two poles; on the one hand, gadgets like Lawvere doctrines and topoi are essentially model-theoretic, since they are provability models. On the other hand, gadgets like cartesian closed categories give models of proofs, up to $\beta\eta$-equivalence.

• Is extending a) natural deduction, b) sequent calculus, or c) some other formal system the best way to go for creating higher order logics?

It depends on what you are doing. If you are building a computerized tool, then typically either natural deduction or sequent calculus is the way to go, because these calculi both line up with human practice and help constrain proof search in ways helpful to computers. It makes sense to cook up a sequent calculus or natural deduction system even if the theory you want to use (e.g., set theory) is not normally cast in these terms.

On the other hand, model theory has been spectacularly successful in applications to mathematics, and this is in part because it does not have a built-in notion of proof system -- so there is simply less machinery you need to reinterpret before you can apply it to a mathematical problem. (The corresponding use of type theory is much less developed; homotopy theorists are in the very earliest stages of turning dependent type theory into ordinary mathematics.)

• Where does typed lambda calculus come into proof verification?

Every well-behaved intuitionistic logic has a corresponding typed lambda calculus. See Sorensen and Urcyczyn's Lectures on the Curry-Howard Correspondence for (many) more details.

• Are there any other approaches than higher order logic to proof verification?

Yes and no. If you're interested in actual, serious mathematics, then there is no alternative to HOL or the moral equivalent (such as dependent type theory or set theory) because mathematics deals intrinsically with higher-order concepts.

However, large portions of any development involve no logically or conceptually complex arguments: they are just symbol management, often involving decidable theories. This is often amenable to automation, if the problems in question are not stated in unnaturally higher-order language. (Sometimes, as in the case of the Kepler conjecture, there is an artificial way of stating the problem in a simple theory. This is essentially the reason why Hales' proof relies so heavily on computers: he very carefully reduced the Kepler conjecture to a collection of machine-checkable statements about real closed fields.)

• What are the limitations/shortcomings of existing proof verification systems (see below)?

The main difficulty with these tools is finding the right balance between automation and abstraction. Basically, the more expressive the logic, the harder automated proof search becomes, and the more easily and naturally you can define abstract theories that can be used in many different contexts.

• Thanks Neel, your answers definitely help clarify many points. Following up on things, if I were to go about writing a proof verifier as an exercise, are there any recommendations you would make? Should I use classical/constructive logic (natural/sequent/Hilbert-style calculus or another)? Henkin semantics for HOL is a given I presume? Also, I would guess model theory is largely irrelevant, and I would want to be basing the HOL on type theory? Cheers. Jul 23 '10 at 7:35
• As a related point, do Henkin semantics actually provide a proof theoretical advantage, or are they used primarily from model theory? I'm wondering if using the more intuitive 'standard semantics' would be sufficient/just as good for HOL. Jul 23 '10 at 16:24
• @Noldorin: When developing a proof system, you might have an intended model in mind, but you don't necessarily have to say anything about semantics. You might even want to allow for several intended models (e.g., a full set theoretical one and a computable one). For systems with a minimum of strength there will always be non-standard models (incompleteness). Henkin semantics is just a way to get completeness by allowing all possible models. Therefore, it is circular to have Henkin semantics in mind during the design of a system ("I want just those models I'll end up with!"). Jul 23 '10 at 19:22
• @Ulrik: Cheers. I think I understand that now. Jul 26 '10 at 7:19

Hope I'm not too late to help, but....

As far as I know, the proof verifiers most extensively used in serious mathematics formalisation are the HOL systems (HOL4, ProofPower HOL, HOL Light), Isabelle, Coq and Mizar. Unlike the others, Isabelle can be configured with the logic it supports, but the only two logics with significant support are HOL and ZF. The HOL logic is classical, higher-order and polymorphically (but not dependently) typed. Isabelle ZF is classical, first-order and not typed. Coq's logic is intuitionistic, higher-order and polymorphically and dependently typed. Mizar's logic is classical, second-order and not typed (I think). All these systems except Mizar are implemented in the "LCF-style", which means that their logical soundness depends on only a relatively small kernel of source code.

Except for Mizar, these systems are all open source and implemented in functional programming languages (e.g. ML, Lisp, Haskell). Assuming you know a little about functional programming, the best way to get a good concrete understanding is to examine their source code, but this will take a huge amount of time because their implementations are large, complicated and poorly documented. However HOL Light (the principal system used in Hale's Flyspeck project to formalise the proof of his Kepler Conjecture proof) is much simpler than the rest, although the source code comments are rather sparse.

I released a new, open source HOL theorem prover last year, called HOL Zero. It fully implements the HOL logic, but is much simpler than the other systems (it only supports basic interaction, and is primarily aimed at checking proofs imported from other systems). I have gone to great lengths to make the source code and user interface as simple and easy to understand as possible, and the source code comments are very clear and extensive. Importantly, I have written a glossary that explains all the technical terminology used. So I recommend you take a look at HOL Zero if you want to get your hands dirty by looking at source code. If you want to actually run it, it requires OCaml (a dialect of ML) and a Unix-like operating system:

http://www.proof-technologies.com/holzero

In my opinion, the main limitations of current systems are (in decreasing order of importance):

1. They take a long time to learn to use proficiently. It typically takes something like three to six months, and even then there is always more to learn.

2. Even when fairly proficient, you will inevitably occasionally (maybe once a day) come across infuriating situations where what appears to be the simplest of steps on paper takes an inordinate amount of interaction with the system (sometimes taking 10 minutes, sometimes hours).

3. They each have large gaps in their library of mathematical theory that has been established, so using them for serious work will inevitably involve developing a lot of supporting theory.

4. There is generally poor support for porting proofs between different systems.

5. When displaying results, each (except HOL Zero) suffers from problems that can occasionally mislead the user as to what has actually been proved.
• @Mark: You're certainly not too late; I'm always willing to learn more. :) Thanks for pointing out HOL Zero, it looks like a very useful way to learn things. It's also interesting to hear how there is no standard/accepted way of designing a proof theory (and thus verification system). I suppose none of them are truly capable of representing all mathematics, but they vary in their "strength"? I wonder if there exists an "ideal" proof theory under which all mathematics can be proven, minus of course the limitations of Godel's Incompleteness Theorems. Jan 31 '11 at 17:23
• @Noldorin: That's good then. :) Yes, there is logic that has become standard, and they vary in strength. The logic chosen usually relates to the system's intended purporse. Coq uses an intuitionistic, dependently-typed logic so that (due to Curry-Howard isomorphism) computer programs can be extracted from proofs performed in the logic. The HOL logic is relatively powerful but less powerful than Coq's. HOL Omega is a recent, more powerful variant of HOL with a more powerful type system, but I think also has limitations. 1st-order logics are used in other systems, making proof automation easier. Feb 1 '11 at 11:45
• @Noldorin: Meant to say "there is no logic that has become standard"... Feb 1 '11 at 14:16

You ask how proof verifiers work, but it seems you are asking a somewhat more precise question: how do proof verifiers based on various higher-order logics work? If you are interested only in classical first-order logic (or less, e.g., propositional logic), then you don't need to worry about higher-order issues. (There are important caveats. For example, the expressiveness of plain first-order logic has limits that you might consider unwelcome for various purposes, such as its inability to capture, e.g., reachability in a graph.) The Mizar system, for example, is based on classical first-order logic plus (a rather strong) set theory.

• Indeed, I did mean that. Thanks for the info about Mizar in particular; that's intriguing. Alas, I wrote this post when my knowledge was comparatively quite immature. Proof verifiers which are concerned with the entirety of proofs known to modern mathematics (and thus higher than simple FOL) are of particular interest here. Feb 5 '13 at 3:04

I do not have any general answer, but I do have an example of a proof checker that is small enough. The accompanying paper should make it easier to understand and it should give some idea of how the proof system was designed. I should mention that it does not handle HO proofs. One interesting feature is that it dumps HO proof obligations that essentially say "the calculus rules I use are sound." (And most of those proof obligations are handled by some tactics in Coq automatically.)

You said:

The Wikipedia pages on blah blah blah give some idea, but these pages contain limited/unclear information, and there are rather few specific high-level resources elsewhere.

Wikipedia is great for subjects you know nothing about, but if you actually know something, all you see is incoherence, misdirection, and sometimes, when lucky, actual errors.

As to actual proof verifiers, it's just the case that each verifier has a different philosophy and different mechanism behind it (there is no one foundation that they all use). So it is difficult to answer your questions (the answer itself will be too broad).

A comment though: category theory itself is not really a foundation for proof verification. It is definitely a conceptual foundation for mathematics in that it creates analogies (and analogies of analogies) -formally- between different domains of mathematics. However there is the subdiscipline of category theory called topos theory which -does- purport to be an alternative foundation (when 'foundation' is intended to be about provability). To bounce back and forth...I don't think there is a verifier based on topos theory.