Metamath


Metamath is a formal language and an associated computer program for archiving, verifying, and studying mathematical proofs. Several databases of proved theorems have been developed using Metamath covering standard results in logic, set theory, number theory, algebra, topology and analysis, among others.
As of July 2020, the set of proved theorems using Metamath is one of the largest bodies of formalized mathematics, containing in particular proofs of 74 of the 100 theorems of the challenge, making it third after HOL Light and Isabelle, but before Coq, Mizar, , , Nqthm, ACL2, and Nuprl. There are at least 17 proof verifiers for databases that use the Metamath format.

The Metamath language

The Metamath language is a metalanguage, suitable for developing a wide variety of formal systems. The Metamath language has no specific logic embedded in it. Instead, it can simply be regarded as a way to prove that inference rules can be applied.
The largest database of proved theorems follows conventional ZFC set theory and classic logic, but other databases exist and others can be created.
The Metamath language design is focused on simplicity; the language, employed to state the definitions, axioms, inference rules and theorems is only composed of a handful of keywords, and all the proofs are checked using one simple algorithm based on the substitution of variables.

Language Basics

The set of symbols that can be used for constructing formulas is declared using $c
and $v statements; for example:

$
 $c 0 + = -> term wff |- $.
$
 $v t r s P Q $.

The grammar for formulas is specified using a combination of $f and $a statements; for example:

$
 tt $f term t $.
 tr $f term r $.
 ts $f term s $.
 wp $f wff P $.
 wq $f wff Q $.
$
 weq $a wff t = r $.
$
 wim $a wff $.

Axioms and rules of inference are specified with $a statements
along with $ for block scoping and
optional $e statements; for example:

$
 a1 $a |- $.
$
 a2 $a |- = t $.
 $

Using one construct, $a statements, to capture syntactic rules, axiom schemas, and rules of inference is intended to provide a level of flexibility similar to higher order logical frameworks without a dependency on a complex type system.

Proofs

Theorems are written with $p statements;
for example:

$
 th1 $p |- t = t $=
 $
 tt tze tpl tt weq tt tt weq tt a2 tt tze tpl
 tt weq tt tze tpl tt weq tt tt weq wim tt a2
 tt tze tpl tt tt a1 mp mp
 $.

Note the inclusion of the proof in the $p statement. It abbreviates
the following detailed proof:

tt $f term t
tze $a term 0
1,2 tpl $a term
3,1 weq $a wff = t
1,1 weq $a wff t = t
1 a2 $a |- = t
1,2 tpl $a term
7,1 weq $a wff = t
1,2 tpl $a term
9,1 weq $a wff = t
1,1 weq $a wff t = t
10,11 wim $a wff
1 a2 $a |- = t
1,2 tpl $a term
14,1,1 a1 $a |-
8,12,13,15 mp $a |-
4,5,6,16 mp $a |- t = t

The "essential" form of the proof elides syntactic details, leaving a more conventional presentation:

a2 $a |- = t
a2 $a |- = t
a1 $a |-
2,3 mp $a |-
1,4 mp $a |- t = t

Substitution

All Metamath proof steps use a single substitution rule, which is just the simple replacement of a variable with an expression and not the proper substitution described in works on predicate calculus. Proper substitution, in Metamath databases that support it, is a derived construct instead of one built into the Metamath language itself.
The substitution rule makes no assumption about the logic system in use and only requires that the substitutions of variables are correctly done.
Here is a detailed example of how this algorithm works. Steps 1 and 2 of the theorem 2p2e4 in the Metamath Proof Explorer are depicted left. Let's explain how Metamath uses its substitution algorithm to check that step 2 is the logical consequence of step 1 when you use the theorem opreq2i. Step 2 states that. It is the conclusion of the theorem opreq2i. The theorem opreq2i states that if, then. This theorem would never appear under this cryptic form in a textbook but its literate formulation is banal: when two quantities are equal, one can replace one by the other in an operation. To check the proof Metamath attempts to unify with. There is only one way to do so: unifying with, with, with and with. So now Metamath uses the premise of opreq2i. This premise states that. As a consequence of its previous computation, Metamath knows that should be substituted by and by. The premise becomes and thus step 1 is therefore generated. In its turn step 1 is unified with df-2. df-2 is the definition of the number 2 and states that 2 = . Here the unification is simply a matter of constants and is straightforward. So the verification is finished and these two steps of the proof of 2p2e4 are correct.
When Metamath unifies with it has to check that the syntactical rules are respected. In fact has the type class thus Metamath has to check that is also typed class.

The Metamath proof checker

The Metamath program is the original program created to manipulate databases written using the Metamath language. It has a text interface and is written in C. It can read a Metamath database into memory, verify the proofs of a database, modify the database, and write them back out to storage.
It has a prove command that enables users to enter a proof, along with mechanisms to search for existing proofs.
The Metamath program can convert statements to HTML or TeX notation;
for example, it can output the modus ponens axiom from set.mm as:
Many other programs can process Metamath databases, in particular, there are at least 17 proof verifiers for databases that use the Metamath format.

Metamath databases

The Metamath website hosts several databases that store theorems derived from various axiomatic systems. Most databases have an associated interface, called an "Explorer", which allows one to navigate the statements and proofs interactively on the website, in a user-friendly way. Most databases use a Hilbert system of formal deduction though this is not a requirement.

Metamath Proof Explorer

The Metamath Proof Explorer is the main and by far the largest database, with over 23,000 proofs in its main part as of July 2019. It is based on classical first-order logic and ZFC set theory. The database has been maintained for over twenty years. The database contains developments, among other fields, of set theory, the construction of the real and complex number systems, order theory, graph theory, abstract algebra, linear algebra, general topology, real and complex analysis, Hilbert spaces, number theory, and elementary geometry. This database was first created by Norman Megill, but as of 2019-10-04 there have been 48 contributors.
The Metamath Proof Explorer references many text books that can be used in conjunction with Metamath. Thus, people interested in studying mathematics can use Metamath in connection with these books and verify that the proved assertions match the literature.

Intuitionistic Logic Explorer

This database develops mathematics from a constructive point of view, starting with the axioms of intuitionistic logic and continuing with axiom systems of constructive set theory.

New Foundations Explorer

This database develops mathematics from Quine's New Foundations set theory.

Higher-Order Logic Explorer

This database starts with higher-order logic and derives equivalents to axioms of first-order logic and of ZFC set theory.

Databases without explorers

The Metamath website hosts a few other databases which are not associated with explorers but are nonetheless noteworthy. The database peano.mm written by Robert Solovay formalizes Peano arithmetic. The database nat.mm formalizes natural deduction. The database miu.mm formalizes the MU puzzle based on the formal system MIU presented in Gödel, Escher, Bach.

Older explorers

The Metamath website also hosts a few older databases which are not maintained anymore, such as the "Hilbert Space Explorer", which presents theorems pertaining to Hilbert space theory which have now been merged into the Metamath Proof Explorer, and the "Quantum Logic Explorer", which develops quantum logic starting with the theory of orthomodular lattices.

Natural Deduction

Because Metamath has a very generic concept of what a proof is and no specific logic is embedded in the software, Metamath can be used with species of logic as different as Hilbert-style logics or sequents-based logics or even with lambda calculus.
However, Metamath provides no direct support for natural deduction systems. As noted earlier, the database nat.mm formalizes natural deduction. The Metamath Proof Explorer instead use a set of conventions that allow the use of natural deduction approaches within a Hilbert-style logic.

Other works connected to Metamath

Proof checkers

Using the design ideas implemented in Metamath, Raph Levien has implemented very small proof checker, mmverify.py, at only 500 lines of Python code.
Ghilbert is a similar though more elaborate language based on mmverify.py. Levien would like to implement a system where several people could collaborate and his work is emphasizing modularity and connection between small theories.
Using Levien seminal works, many other implementations of the Metamath design principles have been implemented for a broad variety of languages. Juha Arpiainen has implemented his own proof checker in Common Lisp called Bourbaki and Marnix Klooster has coded a proof checker in Haskell called Hmm.
Although they all use the overall Metamath approach to formal system checker coding, they also implement new concepts of their own.

Editors

Mel O'Cat designed a system called Mmj2, which provides a graphic user interface for proof entry. The initial aim of Mel O'Cat was to allow the user to enter the proofs by simply typing the formulas and letting Mmj2 find the appropriate inference rules to connect them. In Metamath on the contrary you may only enter the theorems names. You may not enter the formulas directly. Mmj2 has also the possibility to enter the proof forward or backward. Moreover Mmj2 has a real grammar parser. This technical difference brings more comfort to the user. In particular Metamath sometimes hesitates between several formulas analyzes and asks the user to choose. In Mmj2 this limitation no longer exists.
There is also a project by William Hale to add a graphical user interface to Metamath called Mmide. Paul Chapman in its turn is working on a new proof browser, which has highlighting that allows you to see the referenced theorem before and after the substitution was made.
Milpgame is a proof assistant and a checker with a graphic user interface for the Metamath language,written by Filip Cernatescu, it is an open source Java application. User can enter the demonstration in two modes : forward and backward relative to the statement to prove. Milpgame checks if a statement is well formed. It can save unfinished proofs without the use of dummylink theorem. The demonstration is shown as tree, the statements are shown using html definitions. Milpgame is distributed as Java.jar.