Mizar system

From Wikipedia, the free encyclopedia
Jump to: navigation, search
Mizar
Mizar system logo.gif
Paradigm(s) Declarative
Designed by Andrzej Trybulec
Appeared in 1973
Typing discipline Weak, static
Influenced by Automath
Influenced OMDoc, HOL Light and Coq mizar modes
Filename extension(s) .miz .voc
Website www.mizar.org

The Mizar system consists of a formal language for writing mathematical definitions and proofs, a proof assistant which is able to mechanically check proofs written in this language, and a library of formalized mathematics which can be used in the proof of new theorems.[1] The system is maintained and developed by the Mizar Project, formerly under the direction of its founder Andrzej Trybulec.

The Mizar Mathematical Library is the largest coherent body of strictly formalized mathematics in existence.[2]

History[edit]

The Mizar Project was started around 1973 by Andrzej Trybulec as an attempt to reconstruct mathematical vernacular so it can be checked by a computer.[3] Its current goal, apart from the continual development of the Mizar System, is the collaborative creation of a large library of formally verified proofs, covering most of the core of modern mathematics. This is in-line with the influential QED manifesto.[4]

Currently the project is developed and maintained by research groups at Białystok University, Poland, the University of Alberta, Canada, and Shinshu University, Japan. While the Mizar proof checker remains proprietary,[5] the Mizar Mathematical Library – the sizable body of formalized mathematics that it verified – is licensed open-source.[6]

Papers related to the Mizar system regularly appear in the peer-reviewed journals of the mathematic formalization academic community. These include Studies in Logic, Grammar and Rhetoric, Intelligent Computer Mathematics, Interactive Theorem Proving, Journal of Automated Reasoning and the Journal of Formalized Reasoning.

Mizar language[edit]

The distinctive feature of the Mizar language is its readability. As is common in mathematical text, it relies on classical logic and a declarative style.[7] Mizar articles are written in ordinary ASCII, but the language was designed to be close enough to the mathematical vernacular that most mathematicians could read and understand Mizar articles without special training.[1] Yet, the language enables the increased level of formality necessary for automated proof checking.

For a proof to be admitted, all steps have to be justified either by elementary logical arguments or by citing previously verified proofs.[8] This results in a higher level of rigor and detail than customary in mathematical text-books and publications. Thus, a typical Mizar article is about four times as long as an equivalent paper written in ordinary style.[9]

Formalization is relatively labor-intensive, but not impossibly difficult. Once one is versed in the system, it takes about one week of full-time work to have a text-book page formally verified. This suggests that its benefits are now in the reach of applied fields such as probability theory and economics.[2]

Mizar Mathematical Library[edit]

The Mizar Mathematical Library (MML) includes all theorems which can be referred in newly written articles. Once approved by the proof checker they are further evaluated in a process of peer-review for appropriate contribution and style. If accepted they are published in the associated Journal of Formalized Mathematics[10] and added to the MML.

Breadth[edit]

As of July 2012, the MML included 1150 articles written by 241 authors.[11] In aggregate, these contain more than 10,000 formal definitions of mathematical objects and about 52,000 theorems proved on these objects. More than 180 named mathematical facts have so benefited from formal codification.[12] Some examples are the Hahn–Banach theorem, König's lemma, Brouwer fixed point theorem, Gödel's completeness theorem and Jordan curve theorem.

This breadth of coverage has led some[13] to suggest Mizar as one of the leading approximations to the QED utopia of encoding all core mathematics in computer verifiable form.

Availability[edit]

All MML articles are available in PDF form as the papers of the Journal of Formalized Mathematics.[10] The full text of the MML is distributed with the Mizar checker and can be freely downloaded from the Mizar website. In an on-going recent project[14] the library was also made available in an experimental wiki form[15] that only admits edits when they are approved by the Mizar checker.[16]

The MML Query website[11] implements a powerful search engine for the contents of the MML. Among other abilities, it can retrieve all MML theorems proved about any particular type or operator.[17][18]

Logical structure[edit]

The MML is built on the axioms of the Tarski–Grothendieck set theory. Even though semantically all objects are sets, the language allows one to define and use syntactical weak types. For example, a set may be declared to be of type Nat only when its internal structure conforms with a particular list of requirements. In turn, this list serves as the definition of the natural numbers and the set of all the sets that conform to this list is denoted as NAT.[19] This implementation of types seeks to reflect the way most mathematicians formally think of symbols[20] and so streamline codification.

Mizar Proof Checker[edit]

Distributions of the Mizar Proof Checker for all major operating systems are freely available for download at the Mizar Project website. Use of the proof checker is free for all non-commercial purposes. It is written in Free Pascal and the source code is available to all members of the Association of Mizar Users.[21]

See also[edit]

References[edit]

  1. ^ a b Naumowicz, Adam; Artur Korniłowicz (2009). "A Brief Overview of Mizar". Theorem Proving in Higher Order Logics. Lecture Notes in Computer Science 5674: 67–72. 
  2. ^ a b Wiedijk, Freek (2009). "Formalizing Arrow's theorem". Sadhana 34 (1): 193–220. 
  3. ^ Matuszewski, Roman; Piotr Rudnicki (2005). "Mizar: the first 30 years". Mechanized Mathematics and Its Applications 4. 
  4. ^ Wiedijk, Freek. "Mizar". Retrieved July 2012. 
  5. ^ Mailing list discussion referring to the close-sourcing of Mizar.
  6. ^ Mailing list announcement referring to the open-sourcing of MML.
  7. ^ Geuvers, H. (2009). "Proof assistants: History, ideas and future". Sadhana 34 (1). 
  8. ^ Wiedijk, Freek (2008). "Formal Proof--Getting Started". AMS Special Issue on Formal Proof. 
  9. ^ Wiedijk, Freek. "The "de Bruijn factor"". Retrieved July 2012. 
  10. ^ a b Journal of Formalized Mathematics
  11. ^ a b The MML Query search engine
  12. ^ "A list of named theorems in the MML". Retrieved July 2012. 
  13. ^ Wiedijk, Freek (2007). "The QED Manifesto Revisited". From Insight to Proof: Festschrift in Honour of Andrzej Trybulec. Studies in Logic Grammar and Rhetoric 10 (23). 
  14. ^ The MathWiki project homepage
  15. ^ The MML in wiki form
  16. ^ Alama, Jesse; Kasper Brink, Lionel Mamane and Josef Urban (2011). "Large Formal Wikis: Issues and Solutions". Intelligent Computer Mathematics. Lecture Notes in Computer Science 6824: 133–148. 
  17. ^ An example of an MML query, yielding all theorems proved on the exponent operator, by the number of times they are cited in subsequent theorems.
  18. ^ Another example of an MML query, yielding all theorems proved on sigma fields.
  19. ^ Grabowski, Adam; Artur Kornilowicz, Adam Naumowicz (2010). "Mizar in a Nutshell". Journal of Formalized Reasoning 3 (2): 152–245. 
  20. ^ Taylor, Paul (1999). Practical Foundations of Mathematics. Cambridge University Press. ISBN 9780521631075. 
  21. ^ The Association of Mizar Users website

External links[edit]