My favorite minimalistic example of the Metamath base language (which higher level languages can compile down to), which, saved as, say, prop.mm can be verified with the verifier:
$c wff $. $( we use this $constant as a type of formula (well formed formula) $)
$c ( ) ! -> $. $( brackets, negation, implication $)
$v A B C $. $( $variables to be used in formulas $)
wa $f wff A $. $( $floating hypothesis "wa" which says, that A is a well-formed formula $)
wb $f wff B $.
wc $f wff C $.
$( The following assertions define the rules to create formulas $)
$( In Metamath (unlike Metamath Zero), definitions also use the $axiom statement type $)
wng $a wff ! A $. $( "not A is a well-formed-formula" - mandatory hypotheses are (wa) $)
wim $a wff ( A -> B ) $. $( "A implies B is a well-formed-formula" - mandatory hypotheses are (wa, wb) $)
$c |- $. $( this $constant will be used as a type of provable formula $)
$( Schemes of $axioms of propositional logic $)
a1 $a |- ( A -> ( B -> A ) ) $.
a2 $a |- ( ( A -> ( B -> C ) ) -> ( ( A -> B ) -> ( A -> C ) ) ) $.
a3 $a |- ( ( ! A -> ! B ) -> ( B -> A ) ) $.
$( Definition of the Modus Ponens rule of inference in new scope; otherwise $essential hypotheses (inputs) mp1, mp2 will become mandatory for all upcoming assertions $)
${
mp1 $e |- A $.
mp2 $e |- ( A -> B ) $.
mp $a |- B $. $( mandatory hypotheses of "mp" are (wa, wb, mp1, mp2) $)
$}
$( A $proof states the string of symbols to be proven, followed by a list of labels used by the stack machine $)
$( $floating and $essential hypotheses are pushed onto the top of the stack, $axioms and $proofs transform it by using the top of the stack as inputs $)
$( When the stack is empty at the end, the proof is successful, and the proved statement can be reused in further proofs using its label $)
$( " A implies ( B implies C) is a well-formed-formula" $)
formula1 $p wff ( A -> ( B -> C ) ) $= wa wb wc wim wim $.
$( "( A -> A ) -> ( A -> A ) is true (follows from the axioms)" $)
formula2 $p |- ( ( A -> A ) -> ( A -> A ) ) $= wa wa wa wim wim
wa wa wim wa wa wim wim
wa wa a1
wa wa wa a2
mp $.
> Metamath is based on set theory, and would therefore address some concerns one might have with the propositions-as-types philosophy used by Lean
Isn't the entire point mathematicians adopted Lean where they spurned Haskell is because of the batteries-included ZFC object language in the former? Metamath implements a set theory object language just the same, it's not based on it at all in this sense. You just changed one metalanguage for another.
I don't think Haskell would have been useful anyway? You'd want a dependently typed language for this, not Haskell. Haskell's types can't really express anything non-trivial.
In Metamath the proofs hide absolutely nothing. There's no hand-waving "it's obvious that". Every step in a proof must be rigorously and directly proven by some axiom or a previously-proven theorem with absolutely no exceptions. This also means that while finding proofs can be hard, verifying proofs is fast. I just ran a proof verification run of over 47,000 theorems in 6.35 seconds. In the Metamath Proof Explorer / set.mm database (the one with classical logic and ZFC), we routinely run multiple provers by different people on every proposed change. So not only is the kernel small, it's implemented by multiple different programs, making it extremely unlikely we'll accept an invalid proof.
What semantics do you use for your HOL library? I scanned around but documentation on that page is a bit sparse. The github repo goes to a random user's page, and all I could find there was this unrelated repo: https://github.com/digama0/HOL
There are other forms of logic? is intuitionistic logic as rigorous? fascinating
edit: the link says it is a weakening. if it is weakened, how can you prove the same stuff? i am a bit confused but i can see how it is useful for smarter people than me!
Metamath is interesting for education in the principles of formal proofs, because:
1. The Metamath Book is self-contained well written, simple introduction.
2. Everything is explicit, nothing is hidden.
3. Because of extremely simple syntax and semantics it's easy write own proof verifier.
The drawbacks are:
1. Non-standard approach to free and bound variables.
2. Very weak logic in comparison to Lean. The logical syntax rules and logical semantics rules used for proving mathematical statements in Metamath, have to be explicitly specified in the Metamath database. In Lean they are part of the Lean kernel. An bug in this Metamath specification is equivalent to a bug in Lean kernel.
3. Almost no proof automation. No tactics. Long, hard to read proofs.
I would characterize Metamath as the assembly language of proof assistants, very low level and detailed way to write proofs.
I find it really strange that people who don't use lean don't just get on and use the alternatives rather that trying to get everyone who is using lean to use something else. It feels exactly like if all the emacs users in the world tried to force all vim users to use emacs.
It's important to meet reality head on: Every mathematician is not going to collaborate on the same tooling (as wonderful as that might seem on the surface to be as an outcome) human beings are different and want different things, and people are productive in different environments. In particular, people who want to formalize results within the standard framework (including zfc) are never really as a group going to care that much that lean4 doesn't let them formalize results outside of zfc.
Reminds me of the idea of Radical Monopolies from Ivan Illich in a way. If a technology or service becomes so wide spread within society, even though many different versions of the technology or service may exist, a Radical Monopoly means that non users will suffer for their non use. Cars and non drivers in cities are the typical example. And I wonder, whether mathematicians who don't user theorem provers will soon suffer under the tyranny of the theorem provers, whether it be Lean or one of the others.
Recent posts on formal proofs usually talk about Lean, Rocq, Isabelle and (due to this post) Metamath.
What do people think of F* [1]? At least, for non-mathematics projects, doesn't it seem to be a more appropriate option [2]? It seems even the CS community is gravitating towards Lean.
Was genuinely expecting an article about manufacturing methodologies! Very interesting teachable moment for me, I've always wanted to learn more about Set Theory.
I spent far too long comparing dozens of languages, only some of which are part of the above project, before switching from Haskell to Lean for a new phase of my math research. Lean wins for me without considering or using dependent types (for now). It is simply a better programming language than any I have seen.
This is a critical advantage for those interested in proof. One codes tactics using the same language as for proof.
I do have a future interest in proof, giving Lean an edge for me. I prefer my symbolic reasoning in visual form. I anticipate a future where we draw and view AI drawings, and see any printing press derived notation as antiquated as cuneiform. The above image is a possible language for representing the first Lean proof in "The Natural Number Game". About one in ten mathematicians that I show this to can grasp it much faster than the Lean notation. The other nine imagine a visual programming language to be something like a PowerPoint slide or a children's graphics language, and don't see the point.
Isn't it today/wouldn't it be in the close future relatively trivial to port most of the already formalized results between languages with help of LLMs?
Haven't seen much about SPARK and why3 recently, combined with frontier LLMs. It would seem easier to progressively prove properties from an actual implementation (going from absence of runtime errors to partial functional proof to full functional proof if you can beau the cost) and only focus the Lean effort on places where why3 (and its menagerie) of SMT provers give up ?
It would also seem highly agent-able since verification is very modular in SPARK.
I don't see what the issue is. Isn't the entire point of LLMs that we can easily translate between languages? What better way to cross check the correctness of a proof than to run it on several different systems simultaneously.
No programming language will ever be perfect. But it's still better for everyone to focus on improving one language than to recreate the same ideas across dozens of different languages, like a Tower of Babel of duplicated effort.
25 comments
[ 2.0 ms ] story [ 6.1 ms ] threadMetamath Zero's Haskell implementation 700, and the C implementation 1000 lines (or 1800 overall) https://github.com/digama0/mm0
How do other proof systems compare?
Some bug counts: https://tristan.st/blog/in_search_of_falsehood
[0] https://dl.acm.org/doi/pdf/10.1145/3747511
Isn't the entire point mathematicians adopted Lean where they spurned Haskell is because of the batteries-included ZFC object language in the former? Metamath implements a set theory object language just the same, it's not based on it at all in this sense. You just changed one metalanguage for another.
One thing that's cool about Metamath is that the axioms are not built-in. It's true that the most-used system is based on classical logic and ZFC set theory https://us.metamath.org/mpeuni/mmset.html ... but you don't have to use that system. There's a well-maintained database using intuitionistic logic: https://us.metamath.org/ileuni/mmil.html ; on the so-called "New Foundations" (a many-sorted system): https://us.metamath.org/nfeuni/mmnf.html ; on HOL https://us.metamath.org/holuni/mmhol.html ; and you can make your own if you want to.
In Metamath the proofs hide absolutely nothing. There's no hand-waving "it's obvious that". Every step in a proof must be rigorously and directly proven by some axiom or a previously-proven theorem with absolutely no exceptions. This also means that while finding proofs can be hard, verifying proofs is fast. I just ran a proof verification run of over 47,000 theorems in 6.35 seconds. In the Metamath Proof Explorer / set.mm database (the one with classical logic and ZFC), we routinely run multiple provers by different people on every proposed change. So not only is the kernel small, it's implemented by multiple different programs, making it extremely unlikely we'll accept an invalid proof.
This video I made years ago summarizes Metamath: https://www.youtube.com/watch?v=8WH4Rd4UKGE
edit: the link says it is a weakening. if it is weakened, how can you prove the same stuff? i am a bit confused but i can see how it is useful for smarter people than me!
1. The Metamath Book is self-contained well written, simple introduction.
2. Everything is explicit, nothing is hidden.
3. Because of extremely simple syntax and semantics it's easy write own proof verifier.
The drawbacks are:
1. Non-standard approach to free and bound variables.
2. Very weak logic in comparison to Lean. The logical syntax rules and logical semantics rules used for proving mathematical statements in Metamath, have to be explicitly specified in the Metamath database. In Lean they are part of the Lean kernel. An bug in this Metamath specification is equivalent to a bug in Lean kernel.
3. Almost no proof automation. No tactics. Long, hard to read proofs.
I would characterize Metamath as the assembly language of proof assistants, very low level and detailed way to write proofs.
It's important to meet reality head on: Every mathematician is not going to collaborate on the same tooling (as wonderful as that might seem on the surface to be as an outcome) human beings are different and want different things, and people are productive in different environments. In particular, people who want to formalize results within the standard framework (including zfc) are never really as a group going to care that much that lean4 doesn't let them formalize results outside of zfc.
What do people think of F* [1]? At least, for non-mathematics projects, doesn't it seem to be a more appropriate option [2]? It seems even the CS community is gravitating towards Lean.
[1] https://fstar-lang.org/
[2] https://fstarlang.github.io/lowstar/html/Introduction.html
I spent far too long comparing dozens of languages, only some of which are part of the above project, before switching from Haskell to Lean for a new phase of my math research. Lean wins for me without considering or using dependent types (for now). It is simply a better programming language than any I have seen.
This is a critical advantage for those interested in proof. One codes tactics using the same language as for proof.
https://github.com/Syzygies/Compare/blob/main/source/lean/Na...
I do have a future interest in proof, giving Lean an edge for me. I prefer my symbolic reasoning in visual form. I anticipate a future where we draw and view AI drawings, and see any printing press derived notation as antiquated as cuneiform. The above image is a possible language for representing the first Lean proof in "The Natural Number Game". About one in ten mathematicians that I show this to can grasp it much faster than the Lean notation. The other nine imagine a visual programming language to be something like a PowerPoint slide or a children's graphics language, and don't see the point.
For software projects it seemed very approachable, even for a complete newbie like me. Probably not for Math though.
For those who found it interesting, perhaps you will also find this term enjoyable https://en.wikipedia.org/wiki/Kairos for its similarity.
It would also seem highly agent-able since verification is very modular in SPARK.