Debian Codegraph @

examples/tait/diplomarbeit_schlenker/proofAxiomsGlobal.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 ;
21 ; NOTICE: Uncomment modules only when file is run on its own
22 ; ***********************************************************
23
24 ; =======================================
25 ; Section: Global Proofs for the Axioms
26 ; =======================================
27 ; contains global lemmas and definitions for
28 ; the proofs of the axioms
29
30 ; Subsection: "Miscellaneous"
31 ; ===========================
32
33 ; Definition: "Typs"
34 ; ------------------
35 (add-program-constant "Typs"
36 (py "list type => list term => list type") 1)
37
38 (add-computation-rule (pt "Typs rhos (Nil term)")
39 (pt "(Nil type)"))
40 (add-computation-rule (pt "Typs rhos (r::rs)")
41 (pt "(Typ rhos r)::(Typs rhos rs)"))
42
43 ; Lemma: "CorTypJ"
44 ; ---------------
45 (set-goal
46 (pf "all rhos, r.Cor rhos r -> TypJ rhos r (Typ rhos r)"))
47
48 (assume "rhos" "r" 1)
49 (ng)
50 (use 1)
51 (save "CorTypJ")
52
53 ; Lemma: "TypJFoldHead"
54 ; ---------------------
55 (add-global-assumption "TypJFoldHead"
56 (pf "all rhos,rho,r,s,rs.
57 TypJ rhos (FoldApp r rs) rho ->
58 TypJ rhos s (Typ rhos r) ->
59 TypJ rhos (FoldApp s rs) rho"))
60
61 ; Lemma: "TypJFoldHeadCor"
62 ; ------------------------
63 (add-global-assumption "TypJFoldHeadCor"
64 (pf "all rhos,rho,sig,r,s,rs.
65 TypJ rhos (FoldApp (Abs rho r s) rs) sig ->
66 Cor rhos (Abs rho r s)"))
67
68
69 ; Subsection: "SR"
70 ; ================
71 ; "SR" stands for "Subject Reduction";
72 ; needed for Ax8, BNTypJ and Ax1
73
74 ; Subsubsection: Auxiliaries for "SR"
75 ; :::::::::::::::::::::::::::::::::::
76
77 ; Lemma: "SRAux1"
78 ; ---------------
79 (set-goal (pf "all rhos,rho,sig,r,s.
80 TypJ rhos ((Abs sig r) s) rho ->
81 TypJ (sig::rhos) r rho & TypJ rhos s sig"))
82
83 (assume "rhos" "rho" "sig" "r" "s" 1)
84 (split)
85 (ng)
86 (split)
87 (use-with 1 'left 'left 'left)
88 (use-with 1 'right)
89
90 (ng)
91 (split)
92 (use-with 1 'left 'left 'right)
93 (simp-with 1 'left 'right)
94 (prop)
95 (save "SRAux1")
96
97 ; Lemma: "SRAux2aAux"
98 ; -------------------
99 (add-global-assumption "SRAux2aAux"
100 (pf "all n, sigs,rhos,rho1.Lh sigs=n ->
101 n<Succ(Lh sigs+Lh rhos)and
102 Typ(sigs:+:(rho1::rhos))(Var n)=rho1"))
103
104 ; Lemma: "SRAux2a"
105 ; ----------------
106 (set-goal (pf "all rhos,sigs,n,k.
107 Lh sigs = n ->
108 TypJsSublist (sigs:+:rhos)
109 (Wrap k(Var map Seq n Lh rhos)) rhos"))
110
111 (ind)
112 (assume "sigs" "n" "k")
113 (assume 1)
114 (ng)
115 (prop)
116
117 (assume "rho1" "rhos" "IH")
118 (assume "sigs" "n" "k")
119 (assume 1)
120 (ng)
121 (split)
122
123 (use "SRAux2aAux")
124 (use 2)
125
126 (simp (pf "(sigs:+:(rho1::rhos) =
127 (sigs:+:rho1:):+:rhos) "))
128 (use "IH")
129 (ng)
130 (use 2)
131
132 (use "SRAux2aTrivial")
133 (save "SRAux2a")
134
135 ; Lemma: "SRAux2b"
136 ; ----------------
137 (set-goal (pf "all rhos,k.
138 TypJsSublist rhos
139 (Wrap k (Var map Seq 0 Lh rhos)) rhos"))
140
141 (assume "rhos" "k")
142
143 (simp (pf "TypJsSublist rhos
144 (Wrap k(Var map Seq 0 Lh rhos))rhos =
145 TypJsSublist ((Nil type) :+: rhos)
146 (Wrap k(Var map Seq 0 Lh rhos))rhos "))
147
148 (use "SRAux2a")
149 (ng)
150 (prop)
151 (simp (pf "(Nil type) :+: rhos = rhos"))
152 (ng)
153 (prop)
154 (use "NilAppend2")
155 (save "SRAux2b")
156
157 ; Lemma: "SRAux2"
158 ; ---------------
159 (set-goal (pf "all rhos,rho,sig,r,s,k.
160 TypJ (sig::rhos) r rho -> TypJ rhos s sig ->
161 TypJsSublist rhos
162 (Wrap k (s::(Var map (Seq 0 (Lh(rhos)))))) (sig::rhos)"))
163
164 (ng)
165 (assume "rhos" "rho" "sig" "r" "s" "k" 1 2)
166 (split)
167 (use 2)
168 (use "SRAux2b")
169 (save "SRAux2")
170
171 ; Lemma: "SRAux3"
172 ; ---------------
173 (set-goal (pf "all rhos,r,rho,s,sig,k.
174 TypJ (sig::rhos) r rho ->
175 TypJsSublist rhos (Wrap k (s::(Var map (Seq 0 (Lh(rhos))))))
176 (sig::rhos) ->
177 TypJ rhos (Sub r
178 (Wrap k (s::(Var map (Seq 0 (Lh(rhos)))))))
179 rho"))
180
181 (assume "rhos" "r" "rho" "s" "sig" "k")
182 (use "TypJSub")
183 (save "SRAux3")
184
185 ; Lemma: "SRAux4"
186 ; ---------------
187 (set-goal (pf "all rhos,r,rho,s,sig,k.
188 TypJ rhos ((Abs sig r) s) rho ->
189 TypJ rhos (Sub r
190 (Wrap k (s::(Var map (Seq 0 (Lh(rhos)))))))
191 rho"))
192
193 (assume "rhos" "r" "rho" "s" "sig" "k" 1)
194 (assert (pf "
195 TypJ (sig::rhos) r rho ->
196 TypJsSublist rhos (Wrap k (s::(Var map (Seq 0 (Lh(rhos))))))
197 (sig::rhos) ->
198 TypJ rhos (Sub r
199 (Wrap k (s::(Var map (Seq 0 (Lh(rhos)))))))
200 rho"))
201 (use "SRAux3")
202 (assume 1)
203 (use 2)
204 (assert (pf "TypJ rhos ((Abs sig r) s) rho ->
205 TypJ (sig::rhos) r rho & TypJ rhos s sig"))
206 (use "SRAux1")
207 (assume 1)
208 (use 3)
209 (use 1)
210 (assert (pf "TypJ (sig::rhos) r rho -> TypJ rhos s sig ->
211 TypJsSublist rhos (Wrap k (s::(Var map (Seq 0 (Lh(rhos))))))
212 (sig::rhos)"))
213 (use "SRAux2")
214 (assume 1)
215 (use 3)
216 (assert (pf "TypJ rhos ((Abs sig r) s) rho ->
217 TypJ (sig::rhos) r rho & TypJ rhos s sig"))
218 (use "SRAux1")
219 (assume 1)
220 (use 4)
221 (use 1)
222 (assert (pf "TypJ rhos ((Abs sig r) s) rho ->
223 TypJ (sig::rhos) r rho & TypJ rhos s sig"))
224 (use "SRAux1")
225 (assume 1)
226 (use 4)
227 (use 1)
228 (save "SRAux4")
229
230 ; Lemma: "SRAux5"
231 ; ---------------
232 (add-global-assumption "SRAux5"
233 (pf "all sigs,r,ss,k,l.
234 Cor sigs r -> (l + Lh ss < Lh sigs -> F) ->
235 Sub r (Wrap k (ss)) =
236 Sub r (Wrap 0 ((ss)
237 :+:(Var map (Seq k l))))"))
238
239 ; Lemma: "SRAux6"
240 ; ---------------
241 (set-goal (pf "all sig,rhos,r,k,s. Cor (sig::rhos) r ->
242 Sub r (Wrap k ((Var map (Seq 0 k)):+:(Lift s 0 k):)) =
243 Sub r (Wrap 0 (((Var map (Seq 0 k)):+:(Lift s 0 k):)
244 :+:(Var map (Seq k (Lh rhos)))))"))
245
246 (assume "sig" "rhos" "r" "k" "s" 1)
247 (use "SRAux5" (pt "(sig::rhos)") (pt "r")
248 (pt "((Var map (Seq 0 k)):+:(Lift s 0 k):)")
249 (pt "Lh rhos") )
250 (use 1)
251 (ng)
252
253 (use "SRAux6Trivial")
254 (save "SRAux6")
255
256 ; Lemma: "SRAux7"
257 ; ---------------
258 (set-goal (pf "all sig,rhos,r,s.
259 Cor (sig::rhos) r ->
260 Sub r (Wrap 0 (s:)) =
261 Sub r (Wrap 0 (s::(Var map (Seq 0 (Lh (rhos))))))"))
262
263 (assume "sig" "rhos" "r" "s" 1)
264 (simp (pf "(s::Var map Seq 0 Lh rhos) =
265 ((s:):+:(Var map Seq 0 Lh rhos))"))
266 (simp (pf "(s:) = (Var map (Seq 0 0)):+:(Lift s 0 0):"))
267 (use "SRAux6" (pt "sig"))
268 (use 1)
269 (ng)
270 (prop)
271 (use "SRAux7Trivial2")
272 (save "SRAux7")
273
274
275 ; Subsubsection: Proof of "SR"
276 ; ::::::::::::::::::::::::::::
277
278 ; Lemma: "SR"
279 ; -----------
280 (set-goal (pf "all rhos,rho,sig,r,s.
281 TypJ rhos ((Abs sig r) s) rho ->
282 TypJ rhos (Sub r (Wrap 0 (s:))) rho"))
283
284 (assume "rhos" "rho" "sig" "r" "s" 1)
285 (simp "SRAux7" (pt "sig") (pt "rhos"))
286 (use "SRAux4" (pt "sig"))
287 (use 1)
288 (ng)
289 (use-with 1 'left 'left 'left)
290 (save "SR")
291
292
293 ; Subsection: "ExpTypJ"
294 ; =====================
295
296 ; Subsubsection: Auxiliaries for "ExpTypJ"
297 ; ::::::::::::::::::::::::::::::::::::::::
298
299 ; Lemma: "FoldTypJ"
300 ; -----------------
301 ; auxiliary for "ExpTypJLeft"
302
303 (add-global-assumption "FoldTypJ"
304 (pf "all rhos,k,sigs,rho,rs.
305 TypJ rhos (Var k) (---> sigs rho) ->
306 TypJs rhos rs sigs ->
307 TypJ rhos (FoldApp (Var k) rs) rho"))
308
309 ; Definition: "OR"
310 ; ----------------
311 (add-program-constant "OR"
312 (py "boole => boole => boole") 1)
313
314 (add-computation-rule (pt "OR F F ")
315 (pt "F"))
316 (add-computation-rule (pt "OR T F ")
317 (pt "T"))
318 (add-computation-rule (pt "OR F T ")
319 (pt "T"))
320 (add-computation-rule (pt "OR T T ")
321 (pt "T"))
322
323 ; Definition: "Occurs"
324 ; --------------------
325 (add-program-constant "Occurs"
326 (py "nat => term => boole") 1)
327
328 (add-computation-rule (pt "Occurs 0 (Var 0) ")
329 (pt "T"))
330 (add-computation-rule (pt "Occurs 0 (Var (Succ n)) ")
331 (pt "F"))
332 (add-computation-rule (pt "Occurs (Succ n) (Var 0) ")
333 (pt "F"))
334 (add-computation-rule (pt "Occurs n (r s) ")
335 (pt "OR (Occurs n r) (Occurs n s)"))
336 (add-computation-rule (pt "Occurs n (Abs rho s) ")
337 (pt "Occurs (Succ n) s"))
338
339 ; Definition: "Occurss"
340 ; ---------------------
341 (add-program-constant "Occurss"
342 (py "nat => list term => boole") 1)
343
344 (add-computation-rule (pt "Occurss n (Nil term)")
345 (pt "F"))
346 (add-computation-rule (pt "Occurss n (r::rs)")
347 (pt "OR (Occurs n r) (Occurss n rs)"))
348
349 ; Lemma: "OccursFold"
350 ; -------------------
351 ; auxiliary for "ExpOccurs"
352
353 (add-global-assumption "OccursFold"
354 (pf "all n,rs,ss,k.
355 Occurss n rs = Occurss n ss ->
356 Occurs n (FoldApp(Var k)rs) =
357 Occurs n (FoldApp(Var k)ss)"))
358
359 ; Lemma: "EtaOccurs"
360 ; ------------------
361 ; auxiliary for "ExpOccurs"
362
363 (add-global-assumption "EtaOccurs"
364 (pf "all n,r,rho.
365 Occurs n (Eta rho r) = Occurs n r"))
366
367 ; Lemma: "OccursABS"
368 ; ------------------
369 ; auxiliary for "ExpOccurs"
370
371 (add-global-assumption "OccursABS"
372 (pf "all r,s.
373 all k (Occurs k r = Occurs k s) ->
374 all n,m,rho.
375 Occurs n (ABS m rho r) =
376 Occurs n (ABS m rho s)"))
377
378 ; Lemma: "OccurssAux"
379 ; -------------------
380 ; auxiliary for "ExpOccurs"
381
382 (add-global-assumption "OccurssAux"
383 (pf "all k,r,s,rs,ss.
384 Occurs k r = Occurs k s ->
385 Occurss k rs = Occurss k ss ->
386 Occurss k (r::rs) =
387 Occurss k (s::ss)"))
388
389 ; Lemma: "ExpOccurs"
390 ; ------------------
391 ; auxiliary for "ExpTypJRight"
392
393 (set-goal (pf "all rhos,rho,r,s.
394 Exp rhos rho r s ->
395 all k. Occurs k r = Occurs k s"))
396
397 (assume "rhos" "rho" "r" "s")
398 (elim (pf "Exps rhos sigs rs ss ->
399 all k. Occurss k rs = Occurss k ss"))
400
401 (assume "rhos2" "sigs" "rs" "ss"
402 "k" "t" "rho2")
403 (assume 1 2 3 4)
404
405 (assume "n")
406 (simp 3)
407
408 (simp (pf "
409 Occurs n(Eta rho2(FoldApp(Var k)ss)) =
410 Occurs n (FoldApp(Var k)ss)"))
411 (use "OccursFold")
412 (use 4)
413 (use "EtaOccurs")
414
415 ; Case 2
416 (assume "rhos1" "rhos2" "sigs" "taus"
417 "rho2" "sig" "r2" "s2" "k")
418
419 (assume 1 2 3 4)
420 (assume "n")
421 (use "OccursABS")
422 (use 4)
423
424 ; Case 3
425 (assume "rhos2" "k")
426 (ng)
427 (prop)
428
429 ; Case 4
430 (assume "rhos2" "sigs" "r2" "s2"
431 "rs" "ss")
432 (assume 1 2 3 4)
433 (assume "k")
434 (use "OccurssAux")
435 (use 3)
436 (use 4)
437 (save "ExpOccurs")
438
439 ; Lemma: "EtaTypJ2"
440 ; -----------------
441 ; auxiliary for "ExpTypJRight"
442
443 (add-global-assumption "EtaTypJ2"
444 (pf "all rhos,rho,r.
445 TypJ rhos r rho ->
446 TypJ rhos (Eta rho r) rho"))
447
448 ; Lemma: "OccursAux"
449 ; ------------------
450 ; auxiliary for "ExpTypJRight"
451
452 (add-global-assumption "OccursAux"
453 (pf "all rhos1,rhos2,sigs,rho,sig,r,s,k.
454 TypJ (rhos1:+:rhos2) r sig ->
455 TypJ (rhos1:+:rhos2) s sig ->
456 TypJ ((rhos1:+:rhos2):+:sigs) (Var k) rho ->
457 Occurs k r = Occurs k s ->
458 TypJ (rhos1) (ABS k rho r) (rho to sig) ->
459 TypJ (rhos1) (ABS k rho s) (rho to sig)"))
460
461
462 ; Subsubsection: Proof of "ExpTypJ"
463 ; :::::::::::::::::::::::::::::::::
464 ; contains "ExpTypJLeft" "ExpTypJRight" and
465 ; "ExpTypJ"
466
467 ; Lemma: "ExpTypJLeft"
468 ; --------------------
469 (set-goal (pf "all rhos,rho,r,s.
470 Exp rhos rho r s ->
471 TypJ rhos r rho"))
472
473 (assume "rhos" "rho" "r" "s")
474 (elim (pf "Exps rhos sigs rs ss ->
475 TypJs rhos rs sigs"))
476
477 ; Case 1
478 (assume "rhos2" "sigs" "rs" "ss"
479 "k" "t" "rho2")
480 (assume 1 2 3 4)
481
482 (use "FoldTypJ" (pt "sigs"))
483 (use 1)
484 (use 4)
485
486 ; Case 2
487 (assume "rhos1" "rhos2" "sigs" "taus"
488 "rho2" "sig" "r2" "s2" "k")
489
490 (assume 1 2 3 4)
491 (use "TypJExtCtx")
492 (use 3)
493
494 ; Case 3
495 (assume "rhos2")
496 (ng)
497 (prop)
498
499 ; Case 4
500 (assume "rhos2" "sigs2" "r2" "s2"
501 "rs2" "ss2")
502 (assume 1 2 3 4)
503 (ng)
504 (split)
505 (use 3)
506 (use 4)
507 (save "ExpTypJLeft")
508
509 ; Lemma: "ExpTypJRight"
510 ; --------------------
511 (set-goal (pf "all rhos,rho,r,s.
512 Exp rhos rho r s ->
513 TypJ rhos s rho"))
514
515 (assume "rhos" "rho" "r" "s")
516 (elim (pf "Exps rhos sigs rs ss ->
517 TypJs rhos ss sigs"))
518
519 ; Case 1
520 (assume "rhos2" "sigs" "rs" "ss"
521 "k" "t" "rho2")
522 (assume 1 2 3 4)
523
524 (simp 3)
525 (use "EtaTypJ2")
526 (use "FoldTypJ" (pt "sigs"))
527 (use 1)
528 (use 4)
529
530 ; Case 2
531 (assume "rhos1" "rhos2" "sigs" "taus"
532 "rho2" "sig" "r2" "s2" "k")
533
534 (assume 1 2 3 4)
535 (use "TypJExtCtx")
536 (use "OccursAux" (pt "rhos2") (pt "sigs")
537 (pt "r2"))
538 (use "ExpTypJLeft" (pt "s2"))
539 (use 2)
540 (use 4)
541 (use 1)
542
543 (use "ExpOccurs" (pt "(rhos1:+:rhos2)")
544 (pt "sig"))
545 (use 2)
546 (use 3)
547
548 ; Case 3
549 (assume "rhos2")
550 (ng)
551 (prop)
552
553 ; Case 4
554 (assume "rhos2" "sigs2" "r2" "s2"
555 "rs2" "ss2")
556 (assume 1 2 3 4)
557 (ng)
558 (split)
559 (use 3)
560 (use 4)
561 (save "ExpTypJRight")
562
563 ; Lemma: "ExpTypJ"
564 ; ----------------
565 (set-goal (pf "all rhos,rho,r,s.
566 Exp rhos rho r s ->
567 TypJ rhos r rho & TypJ rhos s rho"))
568
569 (assume "rhos" "rho" "r" "s")
570 (assume 1)
571 (split)
572 (use "ExpTypJLeft" (pt "s"))
573 (use 1)
574 (use "ExpTypJRight" (pt "r"))
575 (use 1)
576 (save "ExpTypJ")
577
578
579 ; Subsection: "BNTypJ"
580 ; ====================
581
582 ; Subsubsection: Auxiliaries for "BNTypJ"
583 ; :::::::::::::::::::::::::::::::::::::::
584
585 ; Lemma: "BNTypJAux1"
586 ; -------------------
587 (add-global-assumption "BNTypJAux1"
588 (pf "all rhos,sigs,rho,rs,n.
589 TypJ rhos (Var n) (---> sigs rho) ->
590 TypJs rhos rs sigs ->
591 TypJ rhos (FoldApp(Var n)rs) rho"))
592
593 ; Lemma: "BNTypJAux2"
594 ; -------------------
595 (add-global-assumption "BNTypJAux2"
596 (pf "all rhos,rho,rs,n.
597 TypJ rhos (FoldApp(Var n)rs) rho ->
598 TypJ rhos (Var n)
599 (---> (Typs rhos rs) rho) &
600 TypJs rhos rs (Typs rhos rs)"))
601
602 ; Lemma: "BNTypJAux3"
603 ; -------------------
604 (add-global-assumption "BNTypJAux3"
605 (pf "all rhos,rho,sig,r.
606 TypJ rhos (Abs rho r) (rho to sig) ->
607 TypJ (rho::rhos) r sig"))
608
609 ; Lemma: "BNTypJAux4"
610 ; -------------------
611 (add-global-assumption "BNTypJAux4"
612 (pf "all rhos,rho,sig,r.
613 TypJ (rho::rhos) r sig ->
614 TypJ rhos (Abs rho r) (rho to sig)"))
615
616 ; Lemma: "BNTypJAux5"
617 ; -------------------
618 (add-global-assumption "BNTypJAux5"
619 (pf "all rhos3,rho2,r2,sig1,sig2.
620 TypJ rhos3(Abs rho2 r2)(sig1 to sig2) ->
621 rho2 = sig1"))
622
623
624 ; Subsubsection: Proof of "BNTypJ"
625 ; ::::::::::::::::::::::::::::::::
626
627 ; Lemma: "BNTypJ"
628 ; ---------------
629 (set-goal (pf "all r,s.
630 BN r s ->
631 all rhos,rho.TypJ rhos r rho ->
632 TypJ rhos s rho"))
633
634 (assume "r" "s")
635 (elim (pf "BNs rs ss ->
636 all rhos.
637 TypJs rhos rs (Typs rhos rs) ->
638 TypJs rhos ss (Typs rhos rs)"))
639
640 ; Case 0
641 (assume "n" "rs" "ss")
642 (assume 1 2)
643 (assume "rhos" "rho")
644 (assume 1)
645
646 (assert (pf "
647 TypJs rhos rs (Typs rhos rs)"))
648
649 (use "BNTypJAux2" (pt "rho") (pt "n"))
650 (use 3)
651
652 (assume 1)
653
654 (assert (pf "
655 TypJ rhos (Var n)
656 (---> (Typs rhos rs) rho) &
657 TypJs rhos rs (Typs rhos rs)"))
658
659 (use "BNTypJAux2")
660 (use 3)
661 (assume 1)
662 (assert (pf "
663 TypJs rhos ss(Typs rhos rs)"))
664 (use 2)
665 (use 4 'right)
666 (assume 1)
667
668 (use "BNTypJAux1" (pt "(Typs rhos rs)"))
669 (use 5 'left)
670 (use 6)
671
672 ; Case 1
673 (assume "rho2" "r2" "s2")
674 (assume 1 2)
675 (assume "rhos3" "rho3")
676 (assume 1)
677
678 (cut (pf "TypJ rhos3(Abs rho2 r2)rho3"))
679 (cases (pt "rho3"))
680 (assume 1 2)
681 (ng 5)
682 (prop)
683
684 ; Case 2
685 (assume "sig1" "sig2")
686 (assume 1 2)
687
688 (assert (pf "rho2 = sig1"))
689 (use "BNTypJAux5" (pt "rhos3") (pt "r2")
690 (pt "sig2"))
691 (use 5)
692 (assume 1)
693 (simp "<-" 6)
694
695 (use "BNTypJAux4")
696 (use 2)
697 (use "BNTypJAux3")
698 (simp (pf "(rho2 to sig2) = (sig1 to sig2)"))
699 (use 5)
700
701 (simp 6)
702 (ng)
703 (prop)
704 (use 3)
705
706 ; Case 3
707 (assume "rho2" "r2" "s2" "t2" "rs2")
708 (assume 1 2)
709 (assume "rhos3" "rho3")
710 (assume 1)
711 (use 2)
712
713 (assert (pf "TypJ rhos3
714 (FoldApp((Abs rho2 r2) s2) rs2) rho3"))
715 (ng)
716 (use 3)
717 (assume 1)
718
719 (use "TypJFoldHead" (pt "(Abs rho2 r2) s2"))
720 (use 4)
721
722 (use "SR" (pt "rho2"))
723 (use "CorTypJ")
724 (use "TypJFoldHeadCor" (pt"rho3")(pt "rs2"))
725 (use 4)
726
727 ; Residual Cases
728 (assume "rhos")
729 (prop)
730
731 (assume "r2" "s2" "rs" "ss")
732 (assume 1 2 3 4)
733 (assume "rhos")
734 (assume 1)
735 (ng)
736
737 (split)
738 ;(split)
739 (inst-with 3 (pt "rhos")
740 (pt "Typ rhos r2"))
741 (use 6)
742 (split)
743 (use-with 5 'left)
744 (ng)
745 (prop)
746
747 (use 4)
748 (use-with 5 'right)
749 (save "BNTypJ")
750
751
752 ; Subsection: "NTypJ"
753 ; ===================
754 ; not used explicitly, but for "N" to be
755 ; a proper definition the formula
756 ; "TypJ rhos r rho -> N rhos rho r s -> TypJ rhos s rho"
757 ; is implicitly required.
758 ;
759 ; Our Definition of "N" has the property
760 ; that the type judgements follow directly from "N".
761 ; Hence N rhos rho r s means exactly that
762 ; "s" is the long Normalform of "r"
763 ; in the given context with the given type
764
765 ; Lemma: "NIndTypJLeft"
766 ; ---------------------
767 (set-goal
768 (pf "all rhos,rho,r,s.
769 NInd rhos rho r s -> TypJ rhos r rho"))
770
771 (assume "rhos" "rho" "r" "s")
772 (elim)
773
774 (assume "rhos2" "rho2" "r2" "s2" "t2")
775 (assume 1 2 3)
776 (use 1)
777 (save "NIndTypJLeft")
778
779 ; Lemma: "NIndTypJRight"
780 ; ----------------------
781 (set-goal
782 (pf "all rhos,rho,r,s.
783 NInd rhos rho r s -> TypJ rhos s rho"))
784
785 (assume "rhos" "rho" "r" "s")
786 (elim)
787
788 (assume "rhos2" "rho2" "r2" "s2" "t2")
789 (assume 1 2 3)
790 (use "ExpTypJRight" (pt "t2"))
791 (use 3)
792 (save "NIndTypJRight")
793
794 ; Lemma: "NIndTyp"
795 ; ----------------
796 (set-goal
797 (pf "all rhos,rho,r,s.
798 NInd rhos rho r s ->
799 TypJ rhos r rho & TypJ rhos s rho"))
800
801 (assume "rhos" "rho" "r" "s")
802 (assume 1)
803 (split)
804 (use "NIndTypJLeft" (pt "s"))
805 (use 1)
806 (use "NIndTypJRight" (pt "r"))
807 (use 1)
808 (save "NIndTypJ")
809
810 ; Lemma: "NTypJ"
811 ; --------------
812 (set-goal
813 (pf "all rhos,rho,r,s.
814 N rhos rho r s ->
815 TypJ rhos r rho & TypJ rhos s rho"))
816
817 (assume "rhos" "rho" "r" "s")
818 (assume 1)
819
820 (assert (pf "NInd rhos rho r s"))
821 (use "NDef")
822 (use 1)
823 (use "NIndTypJ")
824 (save "NTypJ")