2 added 453 characters in body

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 simply 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)?

Proof

The Wikipedia pages on proof verification programs such as HOL Light and 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 idea sof 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.

1

# How do proof verifiers work?

I'm 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 simply based on higher-order logics that use Henkin semantics, or is there something more to it? 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)?

Proof verification programs such as HOL Light and Coq give some idea, but these pages contain limited/unclear information. There are so many variations on formal logics/systems used in proof theory that I'm not sure quite what the base idea sof these systems are.

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?