Debian Codegraph @

RichterHilbertAxiomGeometry/miz3/Miz3Tips

raw
1 The simplest way to run HilbertAxiom.ml is this.
2 In a terminal window (or Emacs shell), move to your hol_light directory and paste in
3 these 3 commands, followed by a RETURN:
4 ocaml
5 #use "hol.ml";;
6 #use "RichterHilbertAxiomGeometry/make.ml";;
7
8 This will not work if you have already evaluated HilbertAxiom_read.ml,
9 because you will get an error
10 Exception: Failure "new_type: type point has already been declared".
11
12 You will see 190 or so definitions and proved theorems, in perhaps 15
13 minutes.
14
15 How to check the Hilbert axiomatic geometry proofs HilbertAxiom.ml,
16 which are a formalization in the proof assistant HOL Light of
17 http://www.math.northwestern.edu/~richter/hilbert.pdf using Freek
18 Wiedijk's Mizar mode miz3. This has only been checked on Linux. I'll
19 also assume familiarity with the Emacs editor (version 23 or 24).
20
21 First a discussion of miz3. There are a number of good proof
22 assistants to formalize mathematical proofs in, e.g. Coq, with which
23 the 4-color theorem proof was formalized. There are a number of good
24 HOL proof assistants, e.g. HOL4 & Isabelle. Two outstanding
25 advantages of HOL Light are Freek's miz3 and that HOL Light is the
26 preferred proof assistant of Tom Hales, who is ambituously trying to
27 formalize his proof of the Kepler sphere-packing theorem. I suspect
28 that John Harrison's leadership is involved in both advantages.
29
30 Mizar was the first proof assistant allowing readable formal
31 proofs. Miz3 now allows readable formal proofs in HOL Light. Miz3
32 mostly resembles Mizar in its syntax (let, assume, thus, proof, by,
33 end, consider, suppose, cases, ...) and proof structure. The Mizar
34 type system and vocabulary (both quite confusing to beginners) is gone
35 from miz3. As in Mizar, each line in a miz3 proof is of the form
36 statement by list;
37 so the statement is supposed to be justified by the list of results.
38 But the "by justification" in Mizar is quite different from that in
39 miz3. The miz3 by justification is mostly performed by the HOL Light
40 FOL prover MESON, which is quite powerful, so in miz3, one can skip
41 steps that could not be skipped in Mizar, which seems to have
42 intentionally weakened the by justification in order to encourage
43 readable proofs. Miz3 has no such intentional weakness (although
44 timeout must be set to a high value to skip steps), but MESON is not
45 particularly good at equational reasoning, as one sees in this example
46 from the Hilbert code (using fancy fonts for readability):
47
48 let B4 = new_axiom
49 `∀ l A B C. Line l ∧ ¬Collinear A B C ∧
50 A ∉ l ∧ B ∉ l ∧ C ∉ l ∧
51 (∃ X. X ∈ l ∧ Between A X C) ⇒
52 (∃ Y. Y ∈ l ∧ Between A Y B) ∨ (∃ Y. Y ∈ l ∧ Between B Y C)`;;
53
54 let B4' = thm `;
55 ∀ l A B C. Line l ∧ ¬Collinear A B C ∧
56 A ∉ l ∧ B ∉ l ∧ C ∉ l ∧
57 (∃ X. X ∈ l ∧ X ∈ open (A,C)) ⇒
58 (∃ Y. Y ∈ l ∧ Y ∈ open (A,B)) ∨ (∃ Y. Y ∈ l ∧ Y ∈ open (B,C))
59 by IN_Interval, B4;
60 `;;
61
62 B4' does nothing but substitute into B4 the definition
63 IN_Interval |- ∀ A B X. X ∈ open (A,B) ⇔ Between A X B
64 This is equational reasoning, and B4' times out with the default
65 timeout value of 1 (5 suffices), and then, a longer proof is needed:
66
67 let B4prime = thm `;
68 let l be point_set;
69 let A B C be point;
70 assume Line l ∧ ¬Collinear A B C ∧
71 A ∉ l ∧ B ∉ l ∧ C ∉ l ∧
72 (∃ X. X ∈ l ∧ X ∈ open (A,C)) [H1];
73 thus (∃ Y. Y ∈ l ∧ Y ∈ open (A,B)) ∨ (∃ Y. Y ∈ l ∧ Y ∈ open (B,C))
74
75 proof
76 Line l ∧ ¬Collinear A B C ∧
77 A ∉ l ∧ B ∉ l ∧ C ∉ l ∧
78 (∃ X. X ∈ l ∧ Between A X C) by H1, IN_Interval;
79 (∃ Y. Y ∈ l ∧ Between A Y B) ∨ (∃ Y. Y ∈ l ∧ Between B Y C) by -, B4;
80 qed by -, IN_Interval;
81 `;;
82
83 The biggest difference between miz3 and Mizar is that miz3 allows one
84 to mix the procedural and declarative styles of formal proofs (Mizar
85 proofs are entirely declarative). That is, one can use HOL Light
86 tactics in the by list, although this is essentially not done here. A
87 HOL Light tactic that might be helpful here is REWRITE_TAC, which is
88 used in equational reasoning, an interesting area of HOL.
89
90 It pay to write a `skeleton' of your proof before filling in the
91 details, and I always start with this:
92
93 proof
94
95 qed by -;
96
97 My miz3 proof typically end with "qed by ... ;", Freek's macro for
98 "thus thesis by ... ; end;", as in the proof of B4prime above, and
99 rarely with neither qed nor end, as in the short proof of B4', but a
100 proof with cases must end with "end". Suppose in the course of a
101 proof you realize you need cases. Write in the various cases (with
102 suppose) first before giving the proofs, or miz3 will give you a
103 skeleton error. So your proof will then look something like this:
104
105 proof
106 [...]
107 A ∨ B ∨ C;
108 cases by -;
109 suppose A;
110
111 qed by -;
112 suppose B;
113
114 qed by -;
115 suppose C;
116
117 qed by -;
118 end;
119
120 The point is that the final "qed by -;" matching "proof" has been
121 changed to "end;" Here's a partial explanation. In miz3, there is
122 always a thesis, which changes from line to line. "Thus thesis" means
123 the thesis is proven, and then one writes "end" to end the proof. In
124 the cases construction above, each of the 3 forks have their own
125 thesis, A, B and C resp., and each proofs end with qed. So in the
126 final line, there is no thesis! So we merely write "end".
127
128 In the proof B4prime above, "thus" seems to have two separate
129 meanings. The first thus seems to be stating the theorem, and the
130 second thus (contained in the qed) is is ending the proof. In a sense
131 thus has the same meaning. Let's simplify B4prime as
132 let B4prime = thm `;
133 [...]
134 thus α ∨ β
135 proof
136 [...]
137 thus thesis by -, IN_Interval;
138 end;
139 `;;
140 The entire "proof [...] IN_Interval;" is as a justification of the
141 statement α ∨ β, even though there is no "by". So we could in a sense
142 rewrite B4prime as
143 let B4prime = thm `;
144 [...]
145 thus α ∨ β by [...];
146 end;
147 `;;
148
149 As the thesis is α ∨ β on the "thus" line, this is analogous to
150 thus thesis by -, IN_Interval;
151 which ends the proof.
152
153 My code uses a fair amount of set theory, which is explained in John's
154 tutorial briefly in sec 14, and in more detail in his reference
155 manual. I found browsing the file sets.ml to be quite helpful.
156 SET_RULE, explained on p 92 of the tutorial simplified my coding.
157
158
159 At the top I explained how to run HilbertAxiom.ml. For a longer
160 journey, comment the top t two lines of HilbertAxiom.ml and
161 FontHilbertAxiom.ml
162
163 verbose := false;;
164 report_timing := false;;
165
166 Change into the directory containing your HOL source files (named hol_light), as
167 explained in the HOL Light documentation. I'll assume that you can
168 copy and paste with the mouse. Open a terminal window. Paste in
169 these 4 commands and type RET:
170
171 ocaml
172 #use "hol.ml";;
173 #load "unix.cma";;
174 loadt "miz3/miz3.ml";;
175
176 After a short while you will see
177 val it : unit = ()
178 #
179 Now select the entire file HilbertAxiom.ml and paste it in. This will
180 take perhaps 15 minutes and you'll see various numbers and so forth to
181 indicate how hard miz3 is working. Paste the file in again, and in
182 perhaps 15 seconds you will see the miz3 output, with no numbers. The
183 faster speed is due to the fact that miz3 caches information.
184
185 The miz3 cache causes trouble if you change the statement of a
186 theorem. To clear all the theorems from the miz3 cache paste in
187
188 reset_miz3 0;;
189
190 Theorems are created by thm, and definitions are created by
191 new_definition. This command will not clear definitions or axioms, so
192 to change a definition or axioms, end the session and start a new
193 session. Sometimes even when only changing theorems it's good to
194 start a new session.
195
196 To end your ocam/HOL-Light/miz3 session, type
197 C-d
198 If you paste in bad input, sometimes you can fix the problem by typing
199 C-c (or the signal BREAK in an Emacs shell C-c C-c).
200
201 To learn the thesis in a statement in a miz3 proof, insert
202 exec GOAL_TAC;
203 after the statement, and the type
204 p();;
205 at the end of the proof.
206
207 There are two problems with pasting into a terminal window, both
208 solved by using intead an Emacs shell, created with M-x shell. After
209 pasting into the shell, type RET. In a terminal window, miz3 output
210 is mixed with miz3 code pasted in. More seriously, a terminal window
211 can only be scrolled back so far, so with a long program, errors at
212 the top of the file won't be visible. When pasting into an Emacs
213 shell, the output is all at the end, and there is no line limit.
214 Freek has a different system of using miz3 involving code being piped
215 directly from the editor vi, but I have not tried it yet. You should
216 use a separate Emacs process for each shell you use, because in the 30
217 seconds or so when the shell is interpreting the program, no editing
218 can take place in that Emacs process.
219
220 Loading the file hol-light-fonts.el (or for a bit more speed,
221 hol-light-fonts.elc) will put any file with extension `ml' in
222 text-mode with auto-fill-mode turned off (provided it isn't set to be
223 on by default in your .emacs file) and visual-line-mode turned on,
224 which turns on `word-wrap', which aids readability with my long lines.
225
226 The miz3 error messages are rather cryptic, but this seems to be a
227 problem with HOL Light. Some tips on the error messages:
228
229 #1 inference error
230 means that miz3 asserts that your `by' justification is impossible. A
231 simple way to earn a #1 error is to mix up `qed' and `end' in a cases
232 construction.
233
234 #2 inference time-out
235 means that miz3 was unable to calculate your `by' justification before
236 timing out. There are two possibilities:
237 1) your `by' justification doesn't work, so you should fix it;
238 2) you need more time, in which case you can increase the value of
239 timeout, to e.g. 50 as is done here, with
240 timeout := 50;;
241 You never get a #2 time-out error if you set timeout to infinity, by
242 timeout := -1;;
243 As Freek explains, this is useful in checking ones proofs on a slower
244 machine than the one on which the miz3 proofs were debugged on.
245
246 #3 skeleton error
247 require a good understanding of miz3's version of Mizar's (barely documented) notion of the skeleton, which is the outline of the proof. Freek's paper contains a reasonably good explanation of miz3 skeletons.
248
249 The first line with an error message may not be the first line with a
250 mistake on it. Consider this fragment of a miz3 error messages:
251
252 Exception:
253 Mizar_error
254 (`;
255 let A B C be point;
256 assume ~Collinear A B C [H1];
257 assume seg B A === seg C B [H2];
258 :: #3
259 :: 3: skeleton error
260 thus angle BCA === angle CAB
261 :: #8
262 :: 8: syntax or type error hol
263
264 proof
265 [...]
266
267 There is nothing wrong with the line with the #3 error message. The
268 problem is in the next line with the #8 error, where `BCA' & `CAB'
269 should read `B C A' and `C A B'. One this problem is fixed, the earlier #3 error disappears:
270
271 Mizar_error
272 (`;
273 let A B C be point;
274 assume ~Collinear A B C [H1];
275 assume seg B A === seg B C [H2];
276 thus angle B C A === angle C A B
277
278 proof
279 [...]
280
281
282 Here's another example where the first line with a reported error is fine, and the real error occurs later:
283
284 cases;
285 suppose G = A;
286 qed by -;
287 :: #1
288 :: 1: inference error
289 suppose G = C;
290 qed by -;
291 :: #1
292 suppose ~(G = A) /\ ~(G = C) [AGCdistinct];
293 Collinear A G C [AGCcol] by h_line, BGN, Collinear_DEF;
294 G IN open (A,C) \/ C IN open (G,A) \/ A IN open (C,G) by Distinct, AGCdistinct, -, B3';
295 cases by -;
296 suppose G IN open (A,C) [AGC];
297 qed by -;
298 :: #1
299 suppose C IN open (G,A) [GCA];
300 qed by -;
301 :: #1
302 suppose A IN open (C,G) [CAG];
303 qed by -;
304 :: #1#9
305 :: 9: syntax error mizar
306 qed by -;
307 end
308
309 The #1 inference error are all correct, as the proofs is the various cases have not yet been coded up. But the #9 error occurs on a line with no error. The problem is in the line below it, which should be `end' and not `qed'. When we fix this, the #9 error goes away:
310
311 cases;
312 suppose G = A;
313 qed by -;
314 :: #1
315 :: 1: inference error
316 suppose G = C;
317 qed by -;
318 :: #1
319 suppose ~(G = A) /\ ~(G = C) [AGCdistinct];
320 Collinear A G C [AGCcol] by h_line, BGN, Collinear_DEF;
321 G IN open (A,C) \/ C IN open (G,A) \/ A IN open (C,G) by Distinct, AGCdistinct, -, B3';
322 cases by -;
323 suppose G IN open (A,C) [AGC];
324 qed by -;
325 :: #1
326 suppose C IN open (G,A) [GCA];
327 qed by -;
328 :: #1
329 suppose A IN open (C,G) [CAG];
330 qed by -;
331 :: #1
332 end;
333 end
334
335 Here's an example of the error being reported on a line later than the error:
336
337 D,O',F cong A,O,C by H1, H2, -, SAS_THM:
338 seg D F === seg A C by -, TriangleCong_DEF;
339 :: #9
340 :: 9: syntax error mizar
341
342 The problem is the : on the first line, which should be a ;. There is no other error here.
343
344
345
346 #4 unknown label
347 often means that you mis-typed one of the results in the by list. You can also earn a #4 error message by misplacing the "by":
348
349 A,D,M cong B,D,M by [ADMcong] ADMncol, Dexists, -, ADM, AngleSymmetry_THM, SAS_THM;
350 :: #4
351 :: 4: unknown label
352
353 Placing the "by" after the label gets rid of #4 error message:
354
355 A,D,M ≅ B,D,M [ADMcong] by ADMncol, Dexists, -, ADM, AngleSymmetry_THM, SAS_THM;
356
357
358 #8 syntax or type error hol
359
360 often means that e.g. a function has the wong number of arguments, or
361 the `by' is missing, but sometimes HOL Light expertise is needed. You
362 can not e.g. define (by `let') the letter `o' as a variable, because
363 it already means the composition operator. Evaluating
364 type_of `o`;;
365 tells you the hol_type of `o' is
366 `:(?143901->?143903)->(?143902->?143901)->?143902->?143903`
367 meaning that `o' is a function taking two selfmaps and returning the
368 composition. You can see that `o' is infix operator by evaluting
369 infixes();;
370 which gives all the infix operators plus precedence info, including
371 ("o", (26, "right"))
372
373 #9 syntax error mizar
374 might mean that there's a colon (:) instead of a semicolon (;) at the
375 end of the line, or a ;;, or there is no ; at the end of the line,
376 there is a blank between two commas in the `by' list. i.e.
377 statement [label] by X1, X2, , X3, X4;
378 or that there are two occurrences of `by' on the line, as in
379 ray D C = ray D G [rDCrDG] by by DCG, IntervalRay_THM;
380
381 Exception: Failure "lex1".
382 may means you have a bad character, perhaps obtained by pasting from a
383 pdf file, where you can the fancy quote (’) which HOL Light will not
384 parse, and you must replace it by the quote (').
385
386
387 Use `thm' in miz3 for a theorem/proof. The style used here is
388
389 let CarefullyChosenName_THM = thm `;
390 let *;
391 assume *;
392 thus *
393
394 proof
395
396 qed by *;
397 `;;
398
399 Begin with `let' variable bindings, `assume' assumptions, then state
400 the theorem with `thus', then give the proof beginning with `proof',
401 and end the proof with `qed' or `end'. Notice that the `thus' and
402 `proof' statement do not end in a semicolon (;).
403
404 The miz3 comment symbol in a `thm' body is a double colon (::).
405 Outside a `thm' body, use the Hol Light (* ... *) comment convention.
406
407 There are exactly two occurrences of backquote (`) in the `thm' body.
408 You can not have a other backquotes, even a ` commented out with ::.
409
410 If you ever accidentally paste miz3 code with e.g. a misplaced
411 backquote (`), into the miz3 window (or Emacs shell), type C-c to get
412 miz3 to forget about it (C-c C-c in an Emacs shell). You can see
413 there's a bad backquote when miz3 gives you the error message
414 containing "Parse error".
415
416
417 Exception: Failure "term_of_now".
418 This error occurs when ???
419
420
421