Debian Codegraph @

examples/tait/diplomarbeit_schlenker/proofAxiomsPart2.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 "./subst_Joachimski_SHORT.scm")
14 ; (pload "./omega.scm")
15 ; (pload "./defsNT.scm")
16 ; (pload "./defsAxiomsSpecial.scm")
17 ; (pload "./trivial.scm")
18 ; (pload "./auxGlobal_SHORT.scm")
19 ; (pload "./defsPred.scm")
20 ; (pload "./proofAxiomsGlobal_SHORT.scm")
21 ;
22 ; NOTICE: Uncomment modules only when file is run on its own
23 ; ***********************************************************
24
25 ; ============================================
26 ; Section: The Proofs of the Axioms (Part 2)
27 ; ============================================
28 ; builds upon the proofs in proofAxiomsGlobal;
29 ; contains "Ax2" to "Ax10" ("Ax1" is covered in Part 1)
30
31
32 ; Subsection: "Ax2"
33 ; =================
34
35 ; Subsubsection: Auxiliaries for "Ax2"
36 ; ::::::::::::::::::::::::::::::::::::
37
38 ; Lemma: "ATypJ"
39 ; --------------
40 (set-goal (pf "all rhos,rho,r,s.
41 AInd rhos rho r s ->
42 TypJ rhos r rho"))
43
44 (assume "rhos" "rho" "r" "s")
45 (elim)
46 (assume "rhos2" "rho2" "k2")
47 (prop)
48
49 (assume "rhos2" "rho2" "sig2"
50 "r2" "s2" "r1" "s1")
51 (assume 1 2 3 4)
52 (ng)
53 (split)
54 (split)
55 (split)
56 (use-with 4 'left)
57 (use-with 2 'left)
58 (simp-with 2 'right)
59 (simp-with 4 'right)
60 (ng)
61 (prop)
62 (simp-with 4 'right)
63 (ng)
64 (prop)
65 (save "ATypJ")
66
67 ; Lemma "LemFoldApp"
68 ; ------------------
69 (set-goal (pf "all rs,r,s.
70 (FoldApp r rs)s = FoldApp r (rs:+:s:)"))
71
72 (ind)
73 (assume "r" "s")
74 (ng)
75 (prop)
76
77 (assume "t" "rs" 1)
78 (assume "r" "s")
79 (ng)
80 (use 1)
81 (save "LemFoldApp")
82
83 ; Definition: "AAtwo"
84 ; -------------------
85 (add-ids (list (list
86 "Atwo" (make-arity (py "list type")(py "type")
87 (py "term")(py "term")) ))
88 '("all rhos,rho,sigs,n,rs,ss,ts.
89 BNs rs ts -> Exps rhos sigs ts ss ->
90 TypJ rhos (Var n) (---> sigs rho) ->
91 Atwo rhos rho
92 (FoldApp (Var n) rs)
93 (FoldApp (Var n) ss)" "AtwoIntro"))
94
95 ; Lemma "AAtwoAux1"
96 ; ----------------
97 (add-global-assumption "AAtwoAux1"
98 (pf "all rs,ss,rs1,ss1.
99 BNs rs ss -> BNs rs1 ss1 ->
100 BNs (rs:+:rs1) (ss:+:ss1)"))
101
102 ; Lemma "AAtwoAux2"
103 ; ----------------
104 (add-global-assumption "AAtwoAux2"
105 (pf "all rhos,sigs1,sigs2,
106 rs1,rs2,ss1,ss2.
107 Exps rhos sigs1 rs1 ss1 ->
108 Exps rhos sigs2 rs2 ss2 ->
109 Exps rhos (sigs1:+:sigs2)
110 (rs1:+:rs2)(ss1:+:ss2)"))
111
112 ; Lemma "AAtwoAux3"
113 ; ----------------
114 (add-global-assumption "AAtwoAux3"
115 (pf "all sigs,rho,sig.
116 --->(sigs:+:rho:)sig =
117 --->sigs(rho to sig)"))
118
119 ; Lemma: "AAtwo"
120 ; --------------
121 (set-goal (pf "all rhos,rho,r,s.
122 AInd rhos rho r s -> Atwo rhos rho r s"))
123
124 (assume "rhos" "rho" "r" "s")
125 (elim)
126
127 ; Case 1
128 (assume "rhos1" "rho1" "k" 1)
129 (simp (pf "(Var k)=
130 FoldApp (Var k) (Nil term)"))
131 (intro 0 (pt "(Nil type)")
132 (pt "(Nil term)"))
133 (intro 0)
134 (intro 0)
135 (ng)
136 (use 1)
137 (ng)
138 (prop)
139
140 ; Case 2
141 (assume "rhos1" "rho1" "sig1"
142 "r2" "s2" "r1" "s1")
143 (assume 1 2 3 4)
144
145 ; Inversion on Atwo
146 (inversion 4)
147
148 (assume "rhos2" "rho2" "sigs2"
149 "n2" "rs2" "ss2" "ts2")
150 (assume 1 2 3 4 5 6 7)
151
152 (simp 10)
153 (simp 11)
154
155 (simp (pf "(FoldApp(Var n2)rs2 r1) =
156 (FoldApp(Var n2) (rs2:+:r1:))"))
157 (simp (pf "(FoldApp(Var n2)ss2 s1) =
158 (FoldApp(Var n2) (ss2:+:s1:))"))
159
160 ; Inversion on N
161 (inversion 3)
162 (assume "rhos3" "rho3" "r3"
163 "s3" "t3")
164 (assume 1 2 3 4 5 6 7)
165
166 (intro 0 (pt "(sigs2:+:rho1:)")
167 (pt "(ts2:+:t3:)"))
168
169 (use "AAtwoAux1")
170 (use 5)
171 (intro 1)
172 (simp 17)
173 (use 13)
174 (intro 0)
175
176 (use "AAtwoAux2")
177 (simp 8)
178 (use 6)
179 (intro 1)
180 (simp 15)
181 (simp 16)
182 (simp 18)
183 (use 14)
184 (intro 0)
185
186 (simp (pf "(--->(sigs2:+:rho1:)sig1) =
187 (---> sigs2 (rho1 to sig1))"))
188 (simp 9)
189 (simp 8)
190 (use 7)
191
192 (use "AAtwoAux3")
193
194 (use "LemFoldApp")
195 (use "LemFoldApp")
196 (save "AAtwo")
197
198
199 ; Subsubsection: Proof of "Ax2"
200 ; :::::::::::::::::::::::::::::
201
202 ; Lemma: "Ax2Ind"
203 ; ---------------
204 (set-goal (pf " all rhos,r,s.
205 AInd rhos Iota r s ->
206 NInd rhos Iota r s"))
207
208 (assume "rhos" "r" "s")
209 (assume 1)
210 (assert (pf "Atwo rhos Iota r s"))
211 (use "AAtwo")
212 (use 1)
213 (assume 1)
214
215 ; Inversion on Atwo
216 (inversion 2)
217 (assume "rhos2" "rho2" "sigs2"
218 "n2" "rs2" "ss2" "ts2")
219 (assume 1 2 3 4 5 6 7)
220 (simp 8)
221 (simp 9)
222 (intro 0 (pt "(FoldApp (Var n2) ts2)"))
223
224 ; TypJ
225 (simp "<-" 8)
226 (use "ATypJ" (pt "s"))
227 (use 1)
228
229 ; BN
230 (intro 0)
231 (use 3)
232
233 ; Exp
234 (simp (pf "rhos= (rhos:+:(Nil type))"))
235 (intro 0 (pt "sigs2") (pt "ss2"))
236
237 ; TypJ
238 (simp 7)
239 (simp "<-"
240 (pf "rhos = rhos:+:(Nil type)"))
241 (simp 6)
242 (use 5)
243 (use "NilAppend")
244
245 ; Exps
246 (simp "<-"
247 (pf "rhos = rhos:+:(Nil type)"))
248 (simp 6)
249 (use 4)
250 (use "NilAppend")
251 (ng)
252 (prop)
253 (use "NilAppend")
254 (save "Ax2Ind")
255
256
257 ; Lemma: "Ax2"
258 ; ------------
259 (set-goal (pf " all rhos,r,s.
260 A rhos Iota r s ->
261 N rhos Iota r s"))
262
263 (assume "rhos" "r" "s" 1)
264 (use "NDefRev")
265 (assert (pf "AInd rhos Iota r s"))
266 (use "ADef")
267 (use 1)
268 (use "Ax2Ind")
269 (save "Ax2")
270
271
272 ; Subsection: "Ax3"
273 ; =================
274
275 ; Lemma: "Ax3"
276 ; ------------
277 (set-goal (pf "all rhos,rho,k.
278 TypJ rhos(Var k)rho -> A rhos rho(Var k)(Var k)"))
279
280 (assume "rhos" "rho" "k" 1)
281 (use "ADefRev")
282 (intro 0)
283 (use 1)
284 (save "Ax3")
285
286
287 ; Subsection: "Ax4"
288 ; =================
289
290 ; Lemma: "Ax4Ind"
291 ; ---------------
292 (set-goal
293 (pf "all rhos,rho,sig,r,s,r1,s1.
294 AInd rhos(rho to sig)r s ->
295 TypJ rhos r1 rho ->
296 NInd rhos rho r1 s1 ->
297 AInd rhos sig(r r1)(s s1)"))
298
299 (assume "rhos" "rho" "sig" "r" "s"
300 "r1" "s1")
301 (assume 1 2 3)
302 (intro 1 (pt "rho"))
303 (use 1)
304 (use 2)
305 (use 3)
306 (save "Ax4Ind")
307
308 ; Lemma: "Ax4"
309 ; ------------
310 (set-goal
311 (pf "all rhos,rho,sig,r,s,r1,s1.
312 A rhos(rho to sig)r s ->
313 TypJ rhos r1 rho ->
314 N rhos rho r1 s1 ->
315 A rhos sig(r r1)(s s1)"))
316
317 (assume "rhos" "rho" "sig" "r" "s"
318 "r1" "s1")
319 (assume 1 2 3)
320 (use "ADefRev")
321 (assert (pf "NInd rhos rho r1 s1"))
322 (use "NDef")
323 (use 3)
324 (assert (pf "TypJ rhos r1 rho"))
325 (use 2)
326 (assert (pf "AInd rhos(rho to sig)r s"))
327 (use "ADef")
328 (use 1)
329 (use "Ax4Ind")
330 (save "Ax4")
331
332
333 ; Subsection: "Ax5"
334 ; =================
335
336 (add-program-constant "Id"
337 (py "term => term") 1)
338
339 (add-computation-rule (pt "Id r")
340 (pt "r"))
341 ; Lemma: "Ax5Ind"
342 ; ---------------
343 (set-goal
344 (pf "all rhos,rho,r,s,t^.
345 HeadInd r s -> NInd rhos rho s t^ ->
346 TypJ rhos r rho -> NInd rhos rho r t^"))
347
348 (assume "rhos" "rho" "r" "s" "t^")
349 (elim)
350 (assume "rho1" "r1" "s1" "rs")
351 (assume 1)
352
353 (assert (pf "
354 Id (FoldApp(Sub r1(Dot s1(Up 0)))rs) =
355 (FoldApp(Sub r1(Dot s1(Up 0)))rs)"))
356 (ng)
357 (prop)
358
359 (assume 1)
360 (assert (pf " NInd rhos rho
361 (Id (FoldApp(Sub r1(Dot s1(Up 0)))rs)) t^"))
362 (simp 2)
363 (use 1)
364 (assume 1)
365
366 (assert (pf "
367 Id (FoldApp(Sub r1(Dot s1(Up 0)))rs) =
368 (FoldApp(Sub r1(Dot s1(Up 0)))rs)"))
369 (use 2)
370
371 (assert (pf " NInd rhos rho
372 (Id (FoldApp(Sub r1(Dot s1(Up 0)))rs)) t^"))
373 (use 3)
374
375 (elim)
376 (assume "rhos2" "rho2" "r2" "s2" "t2")
377 (assume 1 2 3 4 5)
378 (intro 0 (pt "t2"))
379 (use 8)
380
381 (simp (pf "(FoldApp(Abs rho1 r1 s1)rs) =
382 (FoldApp(Abs rho1 r1) (s1::rs))"))
383 (intro 2)
384 (ng #t)
385
386 (simp "<-" 7)
387 (use 5)
388 (ng)
389 (prop)
390 (use 6)
391 (save "Ax5Ind")
392
393 ; Lemma: "Ax5"
394 ; ------------
395 (set-goal
396 (pf "all rhos,rho,r,s,t^.
397 Head r s -> N rhos rho s t^ ->
398 TypJ rhos r rho -> N rhos rho r t^"))
399
400 (assume "rhos" "rho" "r" "s" "t^" 1 2 3)
401 (use "NDefRev")
402 (assert (pf "TypJ rhos r rho"))
403 (use 3)
404 (assert (pf "NInd rhos rho s t^"))
405 (use "NDef")
406 (use 2)
407 (assert (pf "HeadInd r s"))
408 (use "HeadDef")
409 (use 1)
410 (use "Ax5Ind")
411 (save "Ax5")
412
413
414 ; Subsection: "Ax6"
415 ; =================
416
417 ; Subsubsection: Auxiliaries for "Ax6"
418 ; ::::::::::::::::::::::::::::::::::::
419
420 ; Lemma: "UpIdGeneral"
421 ; --------------------
422 ; a more general lemma to prove "UpId"
423
424 (set-goal
425 (pf "all r,n.Sub r (Spare n (Up n)) = r"))
426
427 (ind)
428 (assume "k")
429 (cases)
430 (ng)
431 (prop)
432
433 (assume "n")
434 (casedist (pt "k< Succ n"))
435 (use "SubVarSpareLt")
436 (assume 1)
437 (assert (pf "k=(k-Succ n)+Succ n"))
438
439 (use "Trivial10")
440 (use 1)
441 (assume 1)
442 (simp 2)
443 (simp "SubVarSpare")
444 (ng)
445 (prop)
446
447 ; Case: App
448 (assume "r" "s" "IH r" "IH s")
449 (assume "n")
450 (ng)
451 (split)
452 (use 1)
453 (use 2)
454
455 ; Case: Abs
456 (assume "rho" "r" "IH")
457 (assume "n")
458 (ng)
459 (inst-with "IH" (pt "Succ n"))
460 (simp "DotVarSubliftSpare")
461 (ng)
462 (use 2)
463 (save "UpIdGeneral")
464
465 ; Lemma: "UpId"
466 ; -------------
467 (set-goal
468 (pf "all r.Sub r (Up 0) = r"))
469
470 (assume "r")
471 (assert (pf "Up 0 = (Spare 0 (Up 0))"))
472 (ng)
473 (prop)
474 (assume 1)
475 (simp 1)
476 (use "UpIdGeneral")
477 (save "UpId")
478
479 ; Lemma: "Ax6AuxAux"
480 ; ---------------------
481 (set-goal
482 (pf "all r,s. Sub (Lift r 0 1) (Dot s (Up 0)) = r "))
483
484 (assume "r" "s")
485 (assert
486 (pf "Sub(Lift r 0 (Lh (s:)))(Spare 0 (Pushlist (s:) (Up 0))) =
487 Sub r (Spare 0 (Up 0))"))
488 (use "SubLiftSpare")
489 (assume 1)
490 (ng)
491 (simp-with 1)
492 (use "UpId")
493 (save "Ax6AuxAux")
494
495
496 ; Lemma: "Ax6Aux"
497 ; ---------------
498 (set-goal
499 (pf "all theta, s. (Sublift theta 1) circ (Dot s (Up 0)) =
500 theta"))
501
502 (ind)
503 (assume "n" "s")
504 (ng)
505 (prop)
506
507 (assume "r" "theta" "IH")
508 (assume "s")
509 (ng)
510 (split)
511 (use "Ax6AuxAux")
512 (use 1)
513 (save "Ax6Aux")
514
515
516 ; Subsubsection: Proof of "Ax6"
517 ; :::::::::::::::::::::::::::::
518
519 ; Lemma: "Ax6Ind"
520 ; ---------------
521 (set-goal (pf "all rho,r,s,theta
522 HeadInd((Sub(Abs rho r)theta)s)(Sub r(Dot s theta))"))
523
524 (assume "rho" "r" "s" "theta")
525 (ng)
526
527 (assert
528 (pf "(Sub (Sub r (Dot(Var 0)(Sublift theta 1))) (Dot s (Up 0))) =
529 (Sub r (Dot(Var 0)(Sublift theta 1) circ (Dot s (Up 0)) ))"))
530 (use "SubSub") ;Joachimski lemma
531 (assume 2)
532
533 (assert (pf "HeadInd
534 ((Abs rho (Sub r(Dot(Var 0)(Sublift theta 1)))) s)
535 ((Sub (Sub r(Dot(Var 0)(Sublift theta 1))) (Dot s (Up 0))))"))
536
537 (simp (pf "((Abs rho (Sub r(Dot(Var 0)(Sublift theta 1)))) s) =
538 FoldApp ((Abs rho (Sub r(Dot(Var 0)(Sublift theta 1)))) s)
539 (Nil term)"))
540 (simp
541 (pf "((Sub (Sub r(Dot(Var 0)(Sublift theta 1))) (Dot s (Up 0)))) =
542 FoldApp ((Sub (Sub r(Dot(Var 0)(Sublift theta 1)))
543 (Dot s (Up 0)))) (Nil term)"))
544
545 (intro 0)
546 (ng)
547 (prop)
548 (ng)
549 (prop)
550
551 (simp-with 1)
552 (ng)
553 (simp-with "Ax6Aux" (pt "theta") (pt "s"))
554 (prop)
555 (save "Ax6Ind")
556
557 ; Lemma: "Ax6"
558 ; ------------
559 (set-goal
560 (pf "all rho,r,s,theta
561 Head((Sub(Abs rho r)theta)s)(Sub r(Dot s theta))"))
562
563 (assume "rho" "r" "s" "theta")
564 (use "HeadDefRev")
565 (use "Ax6Ind")
566 (save "Ax6")
567
568
569 ; Subsection: "Ax7"
570 ; =================
571
572 ; Subsubsection: Auxiliaries for "Ax7"
573 ; ::::::::::::::::::::::::::::::::::::
574
575 ; Lemma: "Ax7Aux"
576 ; ---------------
577 (set-goal (pf "all t,rs,r.
578 (FoldApp r rs) t = (FoldApp r (rs:+:(t:)))"))
579
580 (assume "t")
581 (ind)
582 (assume "r")
583 (ng)
584 (prop)
585
586 (assume "s" "ss" "IH")
587 (assume "r")
588 (ng)
589 (use "IH")
590 (save "Ax7Aux")
591
592
593 ; Subsubsection: Proof of "Ax7"
594 ; :::::::::::::::::::::::::::::
595
596 ; Lemma: "Ax7Ind"
597 ; ---------------
598 (set-goal (pf "all r,s,t.
599 HeadInd r s -> HeadInd(r t)(s t)"))
600
601 (assume "r" "s" "t")
602 (elim)
603 (assume "rho" "r1" "s1" "rs")
604 (simp "Ax7Aux")
605 (simp "Ax7Aux")
606 (intro 0)
607 (save "Ax7Ind")
608
609 ; Lemma: "Ax7"
610 ; ------------
611 (set-goal (pf "all r,s,t.
612 Head r s -> Head(r t)(s t)"))
613
614 (assume "r" "s" "t" 1)
615 (use "HeadDefRev")
616 (assert (pf "HeadInd r s"))
617 (use "HeadDef")
618 (use 1)
619 (use "Ax7Ind")
620 (save "Ax7")
621
622
623 ; Subsection: "Ax8"
624 ; =================
625
626 ; Subsubsection: Auxiliaries for "Ax8"
627 ; ::::::::::::::::::::::::::::::::::::
628
629 ; Lemma: "HeadTypJAux1Aux1"
630 ; -------------------------
631 (add-global-assumption "HeadTypJAux1Aux1"
632 (pf "all rhos,r,s,ss.
633 Cor rhos(FoldApp(r s)ss) -> Cor rhos (r s)"))
634
635 ; Lemma: "HeadTypJAux1Aux2"
636 ; -------------------------
637 (add-global-assumption "HeadTypJAux1Aux2"
638 (pf "all rhos,r,r1,s,ss.
639 Cor rhos(FoldApp(r s)ss) ->
640 Typ rhos r=Typ rhos r1 ->
641 Cor rhos(FoldApp(r1 s)ss)"))
642
643 ; Lemma: "HeadTypJAux1"
644 ; ---------------------
645 (set-goal (pf "all rhos, r, r1, rho, sig.
646 TypJ rhos r sig -> TypJ rhos r1 sig ->
647 TypJ rhos(FoldApp r rs)rho ->
648 TypJ rhos(FoldApp r1 rs)rho"))
649
650 (ind)
651 (assume "rhos" "r" "r1" "rho" "sig" 1 2 3)
652 (ng)
653 (split)
654 (use-with 2 'left)
655 (simp (pf "Typ rhos r1 = Typ rhos r"))
656 (use-with 3 'right)
657 (simp-with 1 'right)
658 (use-with 2 'right)
659
660 (assume "s" "ss" "IH")
661 (assume "rhos" "r" "r1" "rho" "sig" 1 2 3)
662 (ng)
663 (inst-with "IH" (pt "rhos") (pt "(r s)")
664 (pt "(r1 s)") (pt "rho") (pt "Typ rhos (r s)"))
665 (use 5)
666 (split)
667
668 (use "HeadTypJAux1Aux1" (pt "ss"))
669 (use-with 4 'left)
670 (prop)
671
672 (split)
673 (use "HeadTypJAux1Aux1" (pt "ss"))
674 (use "HeadTypJAux1Aux2" (pt "r"))
675 (use-with 4 'left)
676 (simp-with 3 'right)
677 (use-with 2 'right)
678 (ng)
679 (simp-with 3 'right)
680 (simp-with 2 'right)
681 (prop)
682 (use 4)
683 (save "HeadTypJAux1")
684
685 ; Lemma: "HeadTypJAux2"
686 ; --------------------
687 (add-global-assumption "HeadTypJAux2"
688 (pf "all rhos,r,rs,rho. TypJ rhos(FoldApp r rs)rho ->
689 Cor rhos r"))
690
691 ; Lemma: "HeadTypJ"
692 ; -----------------
693 ; needs Subject Reduction
694
695 (set-goal (pf "all rho,rhos,r,r1.
696 HeadInd r r1 -> TypJ rhos r rho -> TypJ rhos r1 rho"))
697
698 (assume "rho" "rhos" "r" "r1")
699 (elim)
700 (assume "rho1" "r2" "s" "rs" 1)
701 (use "HeadTypJAux1"
702 (pt "(Abs rho1 r2 s)") (pt "Typ rhos (Abs rho1 r2 s)"))
703 (use "CorTypJ")
704
705 (use "HeadTypJAux2" (pt "rs") (pt "rho"))
706 (use 1)
707 (simp (pf "(Dot s(Up 0)) = (Wrap 0 (s:))"))
708 (use "SR" (pt "rho1") )
709
710 (use "CorTypJ")
711 (use "HeadTypJAux2" (pt "rs") (pt "rho"))
712 (use 1)
713
714 (ng)
715 (prop)
716 (use 1)
717 (save "HeadTypJ")
718
719
720 ; Subsubsection: Proof of "Ax8"
721 ; :::::::::::::::::::::::::::::
722
723 ; Lemma: "Ax8Ind"
724 ; ----------------
725 (set-goal (pf "all rhos,rho,r,r1,k.
726 HeadInd r r1 -> Fr rhos rho r k ->
727 Fr rhos rho r1 k"))
728
729 (assume "rhos" "rho" "r" "r1" "k")
730 (assume 1 2)
731 (use "FrDefRev")
732 (assert (pf "TypJ rhos r rho"))
733 (use "FrDef" (pt "k"))
734 (use 2)
735 (assume 1)
736 (use "HeadTypJ" (pt "r"))
737 (use 1)
738 (use 3)
739 (use "FrDef" (pt "rho") (pt "r") )
740 (use 2)
741 (save "Ax8Ind")
742
743 ; Lemma: "Ax8"
744 ; ------------
745
746 (set-goal (pf "all rhos,rho,r,r1,k.
747 Head r r1 -> Fr rhos rho r k ->
748 Fr rhos rho r1 k"))
749
750 (assume "rhos" "rho" "r" "r1" "k")
751 (assume 1 2)
752 (use "Ax8Ind" (pt "r"))
753 (use "HeadDef")
754 (use 1)
755 (use 2)
756 (save "Ax8")
757
758
759 ; Subsection: "Ax9"
760 ; =================
761
762 ; Subsubsection: Auxiliaries for "Ax9"
763 ; ::::::::::::::::::::::::::::::::::::
764
765 ; Lemma: "ExpExtCtx"
766 ; ------------------
767 (set-goal (pf "Exp rhos rho r s ->
768 Exp(rhos:+:sigs)rho r s"))
769
770 (assume "rhos" "rho" "r" "s" "sigs")
771 (elim (pf "Exps rhos sigs2 rs ss ->
772 Exps (rhos:+:sigs) sigs2 rs ss"))
773
774 ; Case 1
775 (assume "rhos2" "sigs2"
776 "rs2" "ss2" "k2" "t2" "rho2")
777 (assume 1 2 3 4)
778 (intro 0 (pt "sigs2")(pt "ss2"))
779 (use "TypJExtCtx")
780 (use 1)
781 (use 4)
782 (use 3)
783
784 ; Case 2
785 (assume "rhos3" "rhos4" "sigs2" "taus2" "rho2"
786 "sig2" "r2" "s2" "k2")
787 (assume 1 2 3 4)
788 (simp (pf "(rhos3:+:taus2:+:sigs) =
789 (rhos3:+:(taus2:+:sigs))"))
790 (intro 1 (pt "rhos4") (pt "sigs2"))
791 (use 1)
792 (use 2)
793 (use 3)
794 (use "ListAssoc")
795
796 ; Case 3
797 (assume "rhos3")
798 (intro 0)
799
800 ; Case 4
801 (assume "rhos2" "sigs2"
802 "r2" "s2" "rs2" "ss2")
803 (assume 1 2 3 4)
804 (intro 1)
805 (use 3)
806 (use 4)
807 (save "ExpExtCtx")
808
809
810 ; Subsubsection: Proof of "Ax9"
811 ; :::::::::::::::::::::::::::::
812
813 ; Lemma: "Ax9Ind"
814 ; ---------------
815 (set-goal
816 (pf "all sigs,rhos,rho,r,s^.
817 NInd rhos rho r s^ ->
818 NInd (rhos:+:sigs) rho r s^"))
819
820 (assume "sigs" "rhos" "rho" "r" "s^")
821 (elim)
822
823 (assume "rhos1" "rho1" "r1" "s1" "t1")
824 (assume 1 2 3)
825 (intro 0 (pt "t1"))
826 (use "TypJExtCtx")
827 (use 1)
828
829 ; BN
830 (use 2)
831
832 ; Exp
833 (use "ExpExtCtx")
834 (use 3)
835 (save "Ax9Ind")
836
837 ; Lemma: "Ax9"
838 ; -------------
839 (set-goal
840 (pf "all sigs,rhos,rho,r,s^.
841 N rhos rho r s^ ->
842 N (rhos:+:sigs) rho r s^"))
843
844 (assume "sigs" "rhos" "rho" "r" "s^")
845 (assume 1)
846 (use "NDefRev")
847 (assert (pf "NInd rhos rho r s^"))
848 (use "NDef")
849 (use 1)
850 (use "Ax9Ind")
851 (save "Ax9")
852
853
854 ; Subsection: "Ax10"
855 ; =================
856
857 ; Lemma: "Ax10Ind"
858 ; ---------------
859
860 (set-goal
861 (pf "all sigs,rhos,rho,r,s.
862 AInd rhos rho r s -> AInd(rhos:+:sigs)rho r s"))
863
864 (assume "sigs" "rhos" "rho" "r" "s")
865 (elim)
866
867 ; Case 1
868 (assume "rhos1" "rho1" "k1" 1)
869 (intro 0)
870 (use "TypJExtCtx")
871 (use 1)
872
873 ; Case 2
874 (assume "rhos2" "rho2" "sig2" "r2" "s2" "r1" "s1")
875 (assume 1 2 3 4)
876 (intro 1 (pt "rho2"))
877 (use 4)
878 (use "TypJExtCtx")
879 (use 2)
880
881 (use "Ax9Ind")
882 (use 3)
883 (save "Ax10Ind")
884
885 ; Lemma: "Ax10"
886 ; ------------
887 (set-goal
888 (pf "all sigs,rhos,rho,r,s.
889 A rhos rho r s -> A(rhos:+:sigs)rho r s"))
890
891 (assume "sigs" "rhos" "rho" "r" "s" 1)
892 (use "ADefRev")
893 (assert (pf "AInd rhos rho r s"))
894 (use "ADef")
895 (use 1)
896 (use "Ax10Ind")
897 (save "Ax10")
898
899
900 ; Subsection: AxNStrict
901 ; =====================
902 ; used in auxSC.scm
903
904 ; Lemma: "AxNStrict1Ind"
905 ; ----------------------
906
907 (set-goal
908 (pf "all rhos,rho,r^,s^.NInd rhos rho r^s^ -> E r^"))
909
910 (assume "rhos" "rho" "r^" "s^")
911 (elim)
912 (assume "rhos1" "rho1" "r1" "s1" "t1")
913 (assume 1 2 3)
914 (ng)
915 (prop)
916 (save "AxNStrict1Ind")
917
918 ; Lemma: "AxNStrict1"
919 ; ----------------------
920 (set-goal
921 (pf "all rhos,rho,r^,s^.N rhos rho r^s^ -> E r^"))
922
923 (assume "rhos" "rho" "r^" "s^")
924 (assume 1)
925 (assert (pf "NInd rhos rho r^s^"))
926 (use "NDef")
927 (use 1)
928 (use "AxNStrict1Ind")
929 (save "AxNStrict1")
930
931
932 ; Lemma: "AxNStrict2Ind"
933 ; ----------------------
934 (set-goal
935 (pf "all rhos,rho,r^,s^.NInd rhos rho r^s^ -> E s^"))
936
937 (assume "rhos" "rho" "r^" "s^")
938 (elim)
939 (assume "rhos1" "rho1" "r1" "s1" "t1")
940 (assume 1 2 3)
941 (ng)
942 (prop)
943 (save "AxNStrict2Ind")
944
945 ; Lemma: "AxNStrict2"
946 ; -------------------
947 (set-goal
948 (pf "all rhos,rho,r^,s^.N rhos rho r^s^ -> E s^"))
949
950 (assume "rhos" "rho" "r^" "s^")
951 (assume 1)
952 (assert (pf "NInd rhos rho r^s^"))
953 (use "NDef")
954 (use 1)
955 (use "AxNStrict2Ind")
956 (save "AxNStrict2")