Debian Codegraph @

examples/tait/diplomarbeit_schlenker/auxGlobal.scm

raw
1 ; ***********************************************************
2 ; ; Adapt path if necessary:
3 ; (define path "~/minlog/examples/tait/diplomarbeit_schlenker/")
4
5 ; ; Defines the function "pload" to load files
6 ; ; from the path defined above
7 ; (define pload (lambda (x) (load (string-append path x))))
8
9 ; ; Used Modules:
10 ; (pload "./initiate.scm")
11 ; (pload "./defsLamCalc.scm")
12 ; (pload "./defsSubst.scm")
13 ; (pload "./omega.scm")
14 ; (pload "./defsNT.scm")
15 ; (pload "./defsAxiomsSpecial.scm")
16 ; (pload "./defsAxioms.scm")
17 ; (pload "./trivial.scm")
18 ; (pload "./auxSC.scm")
19
20 ; NOTICE: Uncomment modules only when file is run on its own
21 ; ***********************************************************
22
23
24 ; =============================
25 ; Section: Global Auxiliaries
26 ; =============================
27 ; contains global auxiliaries used in more than one module
28
29 ; Subsection: Miscellaneous
30 ; =========================
31
32 ; Lemma: "SubVar"
33 ; ---------------
34 (set-goal (pf "all k,ss,m.
35 k<Lh ss -> Sub(Var k) (Wrap m ss) =
36 (k thof ss)"))
37
38 (ind)
39 (ind)
40 (assume "m")
41 (auto)
42 (prop)
43 (auto)
44 (assume "n" "IHn")
45 (cases)
46 (assume "m")
47 (prop)
48 (auto)
49 (save "SubVar")
50
51 ; Lemma: "TypJArrow"
52 ; ------------------
53 (set-goal
54 (pf "all rhos,rho,sig,r,s.
55 TypJ rhos r (rho to sig) -> TypJ rhos s rho ->
56 TypJ rhos (r s) sig"))
57 (assume "rhos" "rho" "sig" "r" "s")
58 (assume 1 2)
59 (ng)
60 (split)(split)(split)
61 (use-with 1 'left)
62 (use-with 2 'left)
63 (simp-with 1 'right)
64 (simp-with 2 'right)
65 (ng)
66 (prop)
67 (simp-with 1 'right)
68 (ng)
69 (prop)
70 (save "TypJArrow")
71
72 ; Lemma: "TypJTyp"
73 ; ----------------
74 (set-goal
75 (pf "all rhos,rho,r.
76 TypJ rhos r rho -> rho = Typ rhos r"))
77 (assume "rhos" "rho" "r" 1)
78 (ng)
79 (simp-with "<-" 1 'right)
80 (prop)
81 (save "TypJTyp")
82
83
84 ; Subsection: SCrs
85 ; ================
86
87 ; Lemma: "SCrsSTotal"
88 ; -------------------
89 (set-goal (pf "all sigs,rhos,as^,ss.
90 SCrs sigs rhos as^ ss -> STotal as^"))
91
92 (assume "sigs" "rhos" "as^" "ss")
93 (elim)
94 (assume "sigs1")
95 (use "STotalNilOmega")
96 (assume "sigs1" "rho" "rhos1" "a^" "as^1"
97 "s" "ss1" "H1" "H2" "H3" "H4")
98 (use "STotalConsOmega")
99 (use "H4")
100 (save "SCrsSTotal")
101
102 ; Lemma: "SCrsLh"
103 ; ---------------
104 (set-goal (pf "all sigs,rhos,as^,ss.SCrs sigs rhos as^ ss ->
105 (Lh as^ =Lh rhos & Lh rhos=Lh ss)"))
106 (assume "sigs" "rhos" "as^" "ss")
107 (elim)
108 (strip)
109 (split)
110 (use "Truth-Axiom")
111 (use "Truth-Axiom")
112 (strip)
113 (use 4)
114 (save "SCrsLh")
115
116 ; Lemma: "SCrsDefRev"
117 ; -------------------
118 (add-global-assumption
119 "SCrsDefRev"
120 (pf "all sigs,rho,rhos,a^,as^,s,ss.
121 SCrs sigs(rho::rhos)(a^ ::as^)(s::ss) ->
122 (SCr sigs rho a^s & SCrs sigs rhos as^ss)"))
123 ; proof by inversion
124
125 ; Subsection: TypJExtCtx
126 ; ======================
127
128 ; Lemma: "TypJExtCtxAux1"
129 ; -----------------------
130 (set-goal
131 (pf "all rhos,r,s,sig.
132 TypJ rhos (r s) sig -> TypJ rhos r ((Typ rhos s) to sig)"))
133
134 (assume "rhos" "r" "s" "sig" 1)
135 (ng)
136 (split)
137 (use-with 1 'left 'left 'left)
138 (assert (pf "Valtyp(Typ rhos r)=sig"))
139 (use-with 1 'right)
140 (assume 2)
141 (simp-with "<-" 2)
142 (use-with 1 'left 'right)
143 (save "TypJExtCtxAux1")
144
145 ; Lemma: "TypJExtCtxAux2"
146 ; -----------------------
147 (set-goal
148 (pf "all rhos,r,s,sig.
149 TypJ rhos (r s) sig -> TypJ rhos s (Typ rhos s)"))
150
151 (assume "rhos" "r" "s" "sig" 1)
152 (ng)
153 (use-with 1 'left 'left 'right)
154 (save "TypJExtCtxAux2")
155
156 ; Lemma: "TypJExtCtx"
157 ; -------------------
158 ; auxiliary for "TypJAppIntro"
159
160 (set-goal
161 (pf "all r,rhos,rho,sigs.
162 TypJ rhos r rho -> TypJ (rhos :+: sigs) r rho"))
163
164 (ind)
165 ; Base Case: r= Var n
166 (ind)
167 ; Base Case: n=0
168 (assume "rhos" "rho" "sigs" 1)
169 (ng)
170 (split)
171 (assert (pf "0<Lh rhos"))
172 (use-with 1 'left)
173 (use "Trivial5")
174
175 (cases (pt "rhos"))
176 (assume 2)
177 (assert (pf "Lh rhos = 0"))
178 (simp-with 2)
179 (ng)
180 (prop)
181 (assume 3)
182
183 (assert (pf "0<Lh rhos -> F"))
184 (simp-with 3)
185 (use "Trivial6")
186 (assume 4)
187 (assert (pf "F"))
188 (use 4)
189 (use-with 1 'left)
190 (prop)
191
192 (assume "tau" "taus" 1)
193 (ng)
194 (assert (pf "Typ rhos(Var 0)=rho"))
195 (use-with 1 'right)
196 (simp-with 2)
197 (ng)
198 (prop)
199
200 (assume "n" "IH")
201 (cases)
202 (assume "rho" "sigs" 1)
203 (ng)
204 (prop)
205
206 (assume "rho" "rhos" "sig" "sigs" 1)
207 (ng)
208 (inst-with "IH" (pt "rhos") (pt "sig") (pt "sigs") 2)
209 (use 3)
210
211 ;Step Case n+1
212 ; Case rs
213 (assume "r" "s" "[IHr]" "[IHs]")
214 (assume "rhos" "sig" "sigs" "[TypJ]")
215 (inst-with-to "[IHr]"
216 (pt "rhos") (pt "((Typ rhos s) to sig)") (pt "sigs")
217 "[IHr Inst]" )
218 (inst-with-to "[IHs]"
219 (pt "rhos") (pt "(Typ rhos s)") (pt "sigs")
220 "[IHs Inst]")
221
222 (assert (pf "TypJ rhos r(Typ rhos s to sig)"))
223 (use "TypJExtCtxAux1")
224 (use "[TypJ]")
225 (assume 6)
226 (inst-with "[IHr Inst]" 6)
227
228 (assert (pf "TypJ rhos s(Typ rhos s)"))
229 (use "TypJExtCtxAux2" (pt "r") (pt "sig"))
230 (use "[TypJ]")
231 (assume 8)
232
233 (inst-with "[IHs Inst]" 8)
234 (use "TypJArrow" (pt "(Typ rhos s)"))
235 (use 7)
236 (use 9)
237
238 ; Case: Abs
239 (assume "rho" "r" "IH")
240 (assume "rhos" "sig" "sigs" 1)
241 (ng)
242 (inst-with "IH" (pt "rho::rhos")
243 (pt "(Typ(rho::rhos)r)") (pt "sigs"))
244 (ng)
245 (split)
246 (assert (pf "Cor(rho::rhos)r"))
247 (use-with 2 'left)
248 (assume 4)
249 (inst-with 3 4)
250 (use-with 5 'left)
251
252 (assert (pf "Cor(rho::rhos)r"))
253 (use-with 2 'left)
254 (assume 4)
255 (inst-with 3 4)
256 (simp-with 5 'right)
257 (use-with 2 'right)
258 (save "TypJExtCtx")
259
260
261 ; Subsection: "TypJAppIntro"
262 ; ==========================
263
264 ; Lemma: "TypJAppIntro"
265 ; ---------------------
266 (set-goal
267 (pf "all rhos,sigs,rho,sig,r,s.
268 TypJ rhos r(rho to sig) -> TypJ(rhos:+:sigs)s rho ->
269 TypJ(rhos:+:sigs)(r s)sig"))
270
271 (assume "rhos" "sigs" "rho" "sig" "r" "s")
272 (assume 1 2)
273 (assert (pf "TypJ (rhos:+:sigs) r(rho to sig)"))
274 (use "TypJExtCtx")
275 (use 1)
276 (assume 3)
277 (use "TypJArrow" (pt "rho"))
278 (use 3)
279 (use 2)
280 (save "TypJAppIntro")
281
282
283 ; Subsection: "TypJSub"
284 ; =====================
285 ; used for "Subject Reduction" and for an auxiliary for Lemma 3
286
287 ; Definition: "TypJsSublist"
288 ; --------------------------
289 ; TypJ for a Sublist
290 ; (leads to easier proofs than with list of terms)
291
292 (add-program-constant "TypJsSublist"
293 (py "list type=> Sublist => list type=> boole") 1)
294
295 (add-computation-rule (pt "TypJsSublist sigs (Up n) (Nil type)")
296 (pt "T"))
297 (add-computation-rule (pt "TypJsSublist sigs (Up n) (rho::rhos)")
298 (pt "F"))
299 (add-computation-rule
300 (pt "TypJsSublist sigs (Dot r theta) (Nil type)")
301 (pt "F"))
302 (add-computation-rule
303 (pt "TypJsSublist sigs (Dot r theta) (rho::rhos)")
304 (pt "(TypJ sigs r rho) and (TypJsSublist sigs theta rhos)"))
305
306 ; Definition: "TypJs"
307 ; -------------------
308 ; TypJ for a list of terms
309
310 (add-program-constant "TypJs"
311 (py "list type=> list term => list type=> boole") 1)
312
313 (add-computation-rule (pt "TypJs sigs ss rhos")
314 (pt "TypJsSublist sigs (Wrap 0 ss) rhos"))
315
316 ; Lemma: "TypLiftAux1"
317 ; --------------------
318 ; auxiliary for "TypJLift"
319 (set-goal
320 (pf "all sig, sigs, rhos,k.
321 k<Lh rhos ->
322 (Typ(rhos:+:(sig::sigs))(Var k)) =
323 (Typ(rhos:+:sigs)(Var k))"))
324
325 (assume "sig" "sigs")
326 (ind)
327 (assume "k" 1)
328 (ng)
329 (prop)
330
331 (assume "rho" "rhos" "IH")
332 (cases)
333 (assume 1)
334 (ng)
335 (prop)
336
337 (assume "n" 1)
338 (ng)
339 (use "IH")
340 (use 2)
341 (save "TypLiftAux1")
342
343 ; Lemma: "TypLiftAux2"
344 ; --------------------
345 ; auxiliary for "TypJLift"
346
347 (set-goal
348 (pf "all sig, sigs, rhos,k.
349 (k<Lh rhos -> F) ->
350 (Typ(rhos:+:(sig::sigs))(Var(Succ k))) =
351 (Typ(rhos:+:sigs)(Var k))"))
352
353 (assume "sig" "sigs")
354 (ind)
355 (assume "k" 1)
356 (ng)
357 (prop)
358
359 (assume "rho" "rhos" "IH")
360 (cases)
361 (assume 1)
362 (ng)
363 (prop)
364
365 (assume "n" 1)
366 (ng)
367 (use "IH")
368 (use 2)
369 (save "TypLiftAux2")
370
371 ; Lemma: "TypLift"
372 ; ----------------
373 ; auxiliary for "TypJLift"
374
375 (set-goal
376 (pf "all sig,sigs,r,rhos,n.
377 (Lh rhos = n) ->
378 (Typ (rhos:+:(sig::sigs)) (Lift r n 1)) =
379 (Typ (rhos:+:sigs) r)"))
380
381 (assume "sig" "sigs")
382 (ind)
383
384 ; Case: Var k
385 (assume "k" "rhos" "n" "[Lh]")
386 (ng)
387 (casedist (pt "k<n"))
388 (assume 1)
389 (ng)
390 (simp "[Lh]")
391
392 (assert (pf "k<Succ(n+Lh sigs)"))
393 (use "Trivial8")
394 (use 2)
395 (assume 1)
396
397 (assert (pf "k<n+Lh sigs"))
398 (use "Trivial9")
399 (use 2)
400 (assume 1)
401 (use "TypLiftAux1" )
402 (simp "[Lh]")
403 (use 2)
404 (assume 1)
405 (ng)
406
407 (assert (pf "
408 (Typ(rhos:+:(sig::sigs))(Var(Succ k))) =
409 (Typ(rhos:+:sigs)(Var k))"))
410 (use "TypLiftAux2")
411 (simp "[Lh]")
412 (use 2)
413 (assume 1)
414 (simp 3)
415 (prop)
416
417 ; Case: App
418 (assume "r" "s" "[IH r]" "[IH s]")
419 (assume "rhos" "n" "[Lh]")
420 (ng)
421 (assert
422 (pf "Typ(rhos:+:(sig::sigs))(Lift r n 1)=Typ(rhos:+:sigs)r"))
423 (use "[IH r]")
424 (use "[Lh]")
425 (assume 1)
426 (simp 4)
427 (prop)
428
429 ; Case: Abs
430 (assume "rho" "r" "[IH]")
431 (assume "rhos" "n" "[Lh]")
432 (ng)
433 (inst-with "[IH]" (pt "rho::rhos") (pt "Succ n"))
434 (use 3)
435 (ng)
436 (use "[Lh]")
437 (save "TypLift")
438
439 ; Lemma: "CorLift"
440 ; -------------------
441 ; auxiliary for "TypJLift"
442
443 (set-goal
444 (pf "all sig,sigs,r,rhos,n.
445 (Lh rhos = n) ->
446 (Cor (rhos:+:(sig::sigs)) (Lift r n 1)) =
447 (Cor (rhos:+:sigs) r)"))
448
449 (assume "sig" "sigs")
450 (ind)
451 (assume "k" "rhos" "n" "[Lh]")
452 (ng)
453 (casedist (pt "k<n"))
454 (assume 1)
455 (ng)
456 (simp "[Lh]")
457
458 (assert (pf "k<Succ(n+Lh sigs)"))
459 (use "Trivial8")
460 (use 2)
461 (assume 1)
462
463 (assert (pf "k<n+Lh sigs"))
464 (use "Trivial9")
465 (use 2)
466 (assume 1)
467 (simp 3)
468 (simp 4)
469 (ng)
470 (prop)
471 (assume 1)
472 (ng)
473 (prop)
474
475 ;Case App
476 (assume "r" "s" "[IH r]" "[IH s]" )
477 (assume "rhos" "n" "[Lh]")
478 (ng)
479
480 (inst-with "[IH r]" (pt "rhos") (pt "n") "[Lh]")
481 (simp 4)
482 (inst-with "[IH s]" (pt "rhos") (pt "n") "[Lh]")
483 (simp 5)
484
485 (assert (pf "Typ(rhos:+:(sig::sigs))(Lift r n 1) =
486 Typ(rhos:+:sigs)r"))
487 (use "TypLift")
488 (use "[Lh]")
489 (assume 1)
490 (simp-with 6)
491
492 (assert (pf "Typ(rhos:+:(sig::sigs))(Lift s n 1) =
493 Typ(rhos:+:sigs)s"))
494 (use "TypLift")
495 (use "[Lh]")
496 (assume 1)
497 (simp-with 7)
498
499 (assert (pf "Valtyp(Typ(rhos:+:(sig::sigs))(Lift r n 1)) =
500 Valtyp(Typ(rhos:+:sigs)r)"))
501 (simp-with 6)
502 (prop)
503 (assume 1)
504
505 (assert (pf "
506 (Typ(rhos:+:(sig::sigs))(Lift s n 1)
507 to Valtyp(Typ(rhos:+:(sig::sigs))(Lift r n 1))) =
508 (Typ(rhos:+:sigs)s to Valtyp(Typ(rhos:+:sigs)r))"))
509 (simp-with 7)
510 (ng)
511 (simp 8)
512 (prop)
513
514 (assume 1)
515 (simp 9)
516 (ng)
517 (prop)
518
519 ; Case: Abs
520 (assume "rho" "r" "[IH]")
521 (assume "rhos" "n" "[Lh]")
522 (ng)
523 (inst-with "[IH]" (pt "rho::rhos") (pt "Succ n"))
524 (use 3)
525 (ng)
526 (use "[Lh]")
527 (save "CorLift")
528
529 ; Lemma: "TypJLift"
530 ; -----------------
531 ; auxiliary for "TypJsSubliftAux"
532
533 (set-goal
534 (pf "all rhos,sig,sigs,rho,n,r.
535 (Lh rhos = n) ->
536 (TypJ (rhos:+:(sig::sigs)) (Lift r n 1) rho) =
537 (TypJ (rhos:+:sigs) r rho)"))
538
539 (assume "rhos" "sig" "sigs" "rho" "n" "r" "[Lh]")
540 (ng)
541 (simp "CorLift")
542 (simp "TypLift")
543 (auto)
544 (save "TypJLift")
545
546 ; Lemma: "TypJsSubliftAux"
547 ; ------------------------
548 ;
549 (set-goal
550 (pf "all sig,sigs,rho,r.
551 TypJ (sig::sigs) (Lift r 0 1) rho =
552 TypJ sigs r rho"))
553
554 (assume "sig" "sigs" "rho" "r")
555 (assert (pf "(TypJ ((Nil type):+:(sig::sigs)) (Lift r 0 1) rho) =
556 (TypJ ((Nil type):+:sigs) r rho)"))
557 (use "TypJLift")
558 (ng)
559 (prop)
560 (assume 1)
561 (assert (pf "(sig::sigs) = (Nil type):+:(sig::sigs)"))
562 (ng)
563 (prop)
564 (assume 2)
565 (simp 2)
566 (use 1)
567 (save "TypJsSubliftAux")
568
569 ; Lemma: "TypJsSublift"
570 ; ---------------------
571 (set-goal
572 (pf "all sig, sigs, theta, rhos.
573 TypJsSublist(sig::sigs)(Sublift theta 1)rhos =
574 TypJsSublist sigs theta rhos"))
575
576 (assume "sig" "sigs")
577 (ind)
578
579 ; Case: theta = Up n
580 (cases)
581 (cases)
582 (ng)
583 (prop)
584
585 (assume "rho" "rhos")
586 (ng)
587 (prop)
588
589 (assume "n")
590 (cases)
591 (ng)
592 (prop)
593
594 (assume "rho" "rhos")
595 (ng)
596 (prop)
597
598 ; Case: theta = Dot r theta
599 (assume "r" "theta" "[IH]")
600 (cases)
601 (ng)
602 (prop)
603
604 (assume "rho" "rhos")
605 (assert
606 (pf "TypJ (sig::sigs) (Lift r 0 1) rho =
607 TypJ sigs r rho"))
608 (use "TypJsSubliftAux")
609 (assume 2)
610 (ng)
611 (simp 2)
612 (inst-with "[IH]" (pt "rhos"))
613 (simp 3)
614 (ng)
615 (prop)
616 (save "TypJsSublift")
617
618 ; Lemma: "TypJSub"
619 ; ----------------
620 (set-goal
621 (pf "all r,rhos, theta, sigs,rho.TypJ rhos r rho ->
622 TypJsSublist sigs theta rhos ->
623 TypJ sigs (Sub r theta) rho"))
624
625 (ind)
626 (ind)
627 (cases)
628 (cases)
629 (assume "n" "sigs" "rho" "[TypJ]" "[TypJsSublist]")
630
631 (ng)
632 (prop)
633
634 (assume "r" "theta" "sigs" "rho" "[TypJ]" "[TypJsSublist]")
635 (ng)
636 (prop)
637
638 (assume "rho" "rhos")
639 (cases)
640 (assume "n" "sigs" "tau" "[TypJ]" "[TypJsSublist]")
641 (ng)
642 (prop)
643
644 (assume "r" "theta" "sigs" "tau" "[TypJ]" "[TypJsSublist]")
645 (ng)
646 (simp "<-" "[TypJ]")
647 (use-with "[TypJsSublist]" 'left)
648
649 ; Case r = Succ k
650 (assume "n" "[IH]")
651 (cases)
652 (cases)
653 (assume "k" "sigs" "tau" "[TypJ]" "[TypJsSublist]")
654 (ng)
655 (prop)
656
657 (assume "r" "theta" "sigs" "rho" "[TypJ]" "[TypJsSublist]")
658 (ng)
659 (prop)
660
661 (assume "rho" "rhos")
662 (cases)
663 (assume "k" "sigs" "tau" "[TypJ]" "[TypJsSublist]")
664 (ng)
665 (prop)
666
667 (assume "r" "theta" "sigs" "tau" "[TypJ]" "[TypJsSublist]")
668 (ng)
669 (use "[IH]" (pt "rhos"))
670 (use "[TypJ]")
671 (use-with "[TypJsSublist]" 'right)
672
673 ; Case: App
674 (assume "r" "s" "[IH r]" "[IH s]")
675 (assume "rhos" "theta" "sigs" "tau" "[TypJ]" "[TypJsSublist]")
676 (ng)
677
678 (assert (pf "Cor sigs(Sub s theta) and
679 Typ sigs(Sub s theta)=Typ rhos s"))
680 (use "[IH s]" (pt "rhos"))
681 (split)
682 (use-with "[TypJ]" 'left 'left 'right)
683 (prop)
684 (use "[TypJsSublist]")
685 (assume "[Part s]")
686
687 (assert (pf "Cor sigs(Sub r theta) and
688 Typ sigs(Sub r theta)=(Typ sigs(Sub s theta)to tau)"))
689 (use "[IH r]" (pt "rhos"))
690 (split)
691 (use-with "[TypJ]" 'left 'left 'left)
692 (assert (pf "Valtyp(Typ rhos r)=tau"))
693 (use-with "[TypJ]" 'right)
694 (assume "[Simp 1]")
695
696 (assert (pf "Typ rhos r=(Typ rhos s to Valtyp(Typ rhos r))"))
697 (use-with "[TypJ]" 'left 'right)
698 (assume "[Simp 2]")
699 (simp "[Simp 2]")
700 (simp "[Simp 1]")
701 (ng)
702 (use "Symmetry")
703 (use-with "[Part s]" 'right)
704 (use "[TypJsSublist]")
705 (assume "[Part r]")
706 (split)
707 (split)
708 (split)
709 (use-with "[Part r]" 'left)
710 (use-with "[Part s]" 'left)
711
712 (simp (pf "Valtyp(Typ sigs(Sub r theta))=tau"))
713
714 (use-with "[Part r]" 'right)
715 (simp-with
716 (pf "Typ sigs(Sub r theta)=(Typ sigs(Sub s theta)to tau)"))
717 (ng)
718 (prop)
719 (use-with "[Part r]" 'right)
720
721 (simp-with
722 (pf "Typ sigs(Sub r theta)=(Typ sigs(Sub s theta)to tau)"))
723 (ng)
724 (prop)
725 (use-with "[Part r]" 'right)
726
727 ; Case: Abs
728 (get 4)
729 (assume "rho" "r" "[IH]")
730 (assume "rhos" "theta" "sigs" "tau" "[TypJ]" "[TypJsSublist]")
731 (ng)
732 (simp-with "<-" (pf "(rho to Typ(rho::rhos)r)=tau"))
733 (ng)
734 (use "[IH]" (pt "rho::rhos"))
735 (split)
736 (use-with "[TypJ]" 'left)
737 (prop)
738 (ng)
739 (simp "TypJsSublift")
740 (use "[TypJsSublist]")
741 (use-with "[TypJ]" 'right)
742 (save "TypJSub")