User:Boris Tsirelson/Sandbox1: Difference between revisions

From Citizendium
Jump to navigation Jump to search
imported>Boris Tsirelson
No edit summary
 
(313 intermediate revisions by one other user not shown)
Line 1: Line 1:
For a [[theory (mathematics)|mathematical theory]], correctness means formalizability.
{{AccountNotLive}}
''"In practice, the mathematician ... is content to bring the exposition to a point where his experience and mathematical flair tell him that translation into formal language would be no more than an exercise of patience (though doubtless a very tedious one)."''<ref>{{harvnb|Bourbaki|1968|loc=page 8}}.</ref> Reliability of these experience and flair appears to be high but not perfect. Formalization is especially desirable in complicated cases, but feasible only in very simple cases, unless computers help. (Similarly, without computers a programmer is able to debug only very simple programs.)
The [[Heisenberg Uncertainty Principle|Heisenberg uncertainty principle]] for a particle does not allow a state in which the particle is simultaneously at a definite location and has also a definite momentum. Instead the particle has a range of momentum and spread in location attributable to quantum fluctuations.


A '''proof assistant''' is a computer program used interactively for developing human-readable reliable mathematical documents in a formal language. (It is not the same as a non-interactive, fully automated theorem prover.)
An uncertainty principle applies to most of quantum mechanical operators that do not commute (specifically, to every pair of operators whose commutator is a non-zero scalar operator).
 
==Isabelle/Isar==
 
Nowadays (about 2010) the most successful project of this class combines
* ''Isabelle,'' a generic system for implementing logical formalisms;
* ''Isar'' (Intelligible SemiAutomated Reasoning), a versatile language environment for structured formal proofs;
* ''Proof General,'' a configurable user interface (front-end) for proof assistants;
* ''HOL'' (Higher-Order Logic).
 
[http://www.cse.unsw.edu.au/~kleing/top100/#1 Top 100 theorems in Isabelle] +
[http://www.cs.ru.nl/~freek/100/ Formalizing 100 Theorems] +
[http://isabelle.in.tum.de/ Isabelle] +
[http://isabelle.in.tum.de/download.html Download and installation] +
[http://isabelle.in.tum.de/projects.html Projects] +
[http://isabelle.in.tum.de/library/ The Isabelle2009-2 Library] +
[http://isarmathlib.org/ IsarMathLib: A library of formalized mathematics for Isabelle/ZF]
 
[http://en.wikipedia.org/wiki/Fold_(higher-order_function) WP:fold]
 
===Example session===
 
====First impressions====
 
An existing file, verified before, is used as the source text in this example. Thus, the session is not really interactive. However, this fact is not known to ''Isabelle.'' The proof assistant treats the session as interactive, and the text as new.
 
We start ''Proof General'' (Fig. 1) and enter the source text (Fig. 2).
 
{| align=center
|-
|
{{Image|Isabelle1.png|left|350px|Fig. 1: ''Proof General'' welcome}}
{{Image|Isabelle2.png|right|350px|Fig. 2: Source text entered}}
|}
 
On this stage ''Proof General'' does not send the text to ''Isabelle''; we still can edit the text. ''Proof General'' helps us by automatic colorization according to the syntax of the ''Isar'' language.
 
We start a new theory "CauchysMeanTheorem". (The well-know [[Algebraic-geometric mean inequality|Cauchy's Mean Theorem]] says that the geometric mean is less than, or equal to, the arithmetic mean, for every finite collection of positive numbers. However, this theorem will appear much later, near the end of the source text.) The existing theory "Complex_Main" is a prerequisite. (It contains main facts about real and complex numbers; only real numbers are relevant, but some useful formulas about <math>(a+b)^2</math> appear in "Complex_Main".)
 
Clicking the red button "<math>\triangleright</math>" we send the first portion of the text to ''Isabelle.'' After two more such clicks ''Isabelle'' reads the line "imports Complex_Main" and finds in the library the "Complex_Main" theory (since it is a prerequisite to the new "CauchysMeanTheorem"), but also "Real", since it appears to be a prerequisite to "Complex_Main", and so on, recursively, until all prerequisites are found and processed (in a logical order). Then, after 9 more clicks we come to the screen shown on Fig. 3. The definitions (and everything before them) are already processed by ''Isabelle''; accordingly, they turn into blue, and become read-only. The formulation of the first lemma is being processed by ''Isabelle''; accordingly, it turns into orange. A fraction of a second later we get Fig. 4. The formulation of the lemma is read by ''Isabelle''; a dialog about its proof starts on the bottom window.
 
{| align=center
|-
|
{{Image|Isabelle3.png|left|350px|Fig. 3: Definitions are done; now reading the lemma.}}
{{Image|Isabelle4.png|right|350px|Fig. 4: The proof mode started.}}
|}
 
====A robot as a student====
 
The first lemma "listsum_empty" (of the new "CauchysMeanTheorem" theory) is ridiculously trivial; it claims that the sum of the empty collection of numbers is equal to zero! Here is an explanation of this disturbing situation.
 
A human student would not start to learn Cauchy's mean theorem
:<math> \sqrt[n]{a_1\dots a_n} \le \frac{a_1+\dots+a_n}n </math>
being unfamiliar with such notions as the sum <math>(a_1+\dots+a_n)</math> and the product <math>(a_1\dots a_n)</math> of ''n'' numbers. However, a robot (like ''Isabelle'') is not a human. A robot never was in a kindergarten or elementary school. We cannot say to ''Isabelle:'' "Look, here is a sum of three numbers: 15+5+10=30; note that also 5+10+15=30 etc. Likewise, any finite collection of numbers has its sum." Children proceed from the particular to the general, but proof assistants proceed from the general to the particular.
 
For now, ''Isabelle'' is not well-educated. Its mathematical knowledge is rather fragmentary. Some volunteers contribute some theories to the library of ''Isabelle;'' this is not a well-organized process rich of resources. Each contributor has to find out, which of the relevant facts are already known to ''Isabelle'' and which are not.
 
Definitions of the sum and the product of a list of numbers are given to ''Isabelle'' just before the first lemma (see "listsum" and "listprod" on Fig. 3 or 4) in terms of
* addition and multiplication for two numbers (already known), and
* "foldr", the right fold operation defined in the "List" theory (one of the prerequisites).
Informally, the right fold applies to a binary operation (say, "+"), a list (say, "[''x'',''y'',''z'']") and an initial value (say, "''a''"), giving "''x''+(''y''+(''z''+''a''))"; more formally,
foldr op+ [''x'',''y'',''z''] a  =  ''x''+(''y''+(''z''+''a'')).
(For the summation case one may write just "''x''+''y''+''z''+''a''", but in general an operation need not be associative.) The "listsum" definition stipulates the addition operation and the initial value 0; the "listprod" definition stipulates the multiplication operation and the initial value 1. The sum of a list is denoted by ''Isabelle'' as follows:
:<math> \Sigma: [x,y,z] = x+(y+(z+0)) \, . </math>
A human student, given by such a formal definition of sum (only sketched here) would not be too astonished by the trivial exercise "prove that the sum of the empty list is equal to 0"; this is our "listsum_empty" lemma. After the formulation, the source text contains a hint to the proof,
unfolding listsum_def by simp
which means informally: "''Isabelle,'' use the definition of the sum of a list, do evident simplifications, and hopefully you'll find a proof of the lemma." And indeed, ''Isabelle'' is cute enough in order take the hint. After a fraction of a second it reports that the lemma is successfully proved.
 
Now we continue the example session.
 
====Hard work====
 
After more than 30 rather boring, mostly trivial lemmas, whose proofs vary in length from one line to about 50 lines, we arrive to a more interesting lemma (Fig. 5) and start proving it (Fig. 6).
 
{| align=center
|-
|
{{Image|Isabelle5.png|left|350px|Fig. 5: The main lemma.}}
{{Image|Isabelle6.png|right|350px|Fig. 6: The proof mode started.}}
|}
 
We make a claim of the form "from A have B..."; ''Isabelle'' responds by "using this: A, goal: B" (Fig. 7) and waits. We add a hint "...by C"; ''Isabelle'' takes the hint, finds a proof and responds by "have B" (Fig. 8).
 
{| align=center
|-
|
{{Image|Isabelle7.png|left|350px|Fig. 7: A claim.}}
{{Image|Isabelle8.png|right|350px|Fig. 8: A hint is taken.}}
|}
 
We continue; the work becomes hard (Fig. 9).
After a lot of effort we get close to the happy end (Fig. 10), and finally the theorem is proved (Fig. 11).
 
{| align=center
|-
|
{{Image|Isabelle9.png|left|350px|Fig. 9: Working hard.}}
{{Image|Isabelle10.png|right|350px|Fig. 10: Happy end is close.}}
|}
 
{| align=center
|-
|
{{Image|Isabelle11.png|left|350px|Fig. 11: The theorem is proved!}}
|}
 
====Options====
 
Many options are available for ''Proof General'' (Fig. 12) and ''Isabelle''. In particular, many kinds of additional information may be requested from ''Isabelle'' at any moment of the session (Fig. 13).
 
{| align=center
|-
|
{{Image|Isabelle12.png|left|350px|Fig. 12: Some options of ''Proof General.''}}
{{Image|Isabelle13.png|right|350px|Fig. 13: ''Isabelle,'' show us your methods!}}
|}
 
===Higher-order logic versus theory of sets===
 
===Reliability===
 
===Availability===
 
==Other systems==
 
* [[Mizar (software)|Mizar]]
* Hol88, Hol98, Hol4, Hol Light
* Lego, Coq
* Lambda-CLAM
* Matita
* Otter
* Prover9
* Mace2
* Jape, Ssreflect, PhoX, pvs
* ACL2, Twelf
 
==Notes==
{{reflist|2}}
 
==References==
 
{{Citation
| last = Bourbaki
| first = Nicolas
| title = Elements of mathematics: Theory of sets
| year = 1968
| publisher = Hermann (original), Addison-Wesley (translation)
}}.

Latest revision as of 03:25, 22 November 2023


The account of this former contributor was not re-activated after the server upgrade of March 2022.


The Heisenberg uncertainty principle for a particle does not allow a state in which the particle is simultaneously at a definite location and has also a definite momentum. Instead the particle has a range of momentum and spread in location attributable to quantum fluctuations.

An uncertainty principle applies to most of quantum mechanical operators that do not commute (specifically, to every pair of operators whose commutator is a non-zero scalar operator).

Retrieved from "https://citizendium.org/wiki/index.php?title=User:Boris_Tsirelson/Sandbox1&oldid=904361"