Debian Codegraph @

examples/tait/diplomarbeit_schlenker/proofAxiomsPart1.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 ; ============================================
27 ; Section: The Proofs of the Axioms (Part 1)
28 ; ============================================
29 ; builds upon the proofs in proofAxiomsGlobal;
30 ; contains "Ax1" (the other axioms are covered in Part 2)
31
32 ; Subsection: "Ax1"
33 ; =================
34
35 ; Subsubsection: Auxiliaries for "Ax1"
36 ; ::::::::::::::::::::::::::::::::::::
37 ; contains mainly simple facts
38
39 ; Lemma: "Ax1Aux1"
40 ; ----------------
41 (add-global-assumption "Ax1Aux1"
42 (pf "all n,rs,r,k.
43 FoldApp(Var n)rs=r(Var k) ->
44 ex rs1.
45 rs = (rs1:+:(Var k):) &
46 r = FoldApp (Var n) rs1"))
47
48 ; Lemma: "Ax1Aux2"
49 ; ----------------
50 (add-global-assumption "Ax1Aux2"
51 (pf "all rs,r,ss.
52 BNs (rs:+:r:) ss ->
53 ex ss1,s1. ss = (ss1:+:s1:)"))
54
55 ; Lemma: "Ax1Aux3"
56 ; ----------------
57 (add-global-assumption "Ax1Aux3"
58 (pf "all rs,r,ss,s.
59 BNs (rs:+:r:) (ss:+:s:) ->
60 BNs rs ss & BN r s"))
61
62 ; Lemma: "Ax1Aux4"
63 ; ----------------
64 (add-global-assumption "Ax1Aux4"
65 (pf "all k,s.
66 BN (Var k) s -> (Var k) = s"))
67
68 ; Lemma: "Ax1Aux5"
69 ; ----------------
70 (add-global-assumption "Ax1Aux5"
71 (pf "all n1,n2,rs,ss.
72 FoldApp(Var n1)rs=FoldApp(Var n2)ss ->
73 (Var n1) = (Var n2) &
74 rs = ss"))
75
76 ; Lemma: "Ax1Aux6"
77 ; ----------------
78 (add-global-assumption "Ax1Aux6"
79 (pf "all rhos4,sigs4,ss3,k,ss4.
80 Exps rhos4 sigs4 (ss3:+:(Var k):) ss4 ->
81 ex sigs5,sig5,ss5,s5.
82 sigs4 = (sigs5 :+: sig5:) &
83 ss4 = (ss5 :+: s5:) "))
84
85 ; Lemma: "Ax1Aux7"
86 ; ----------------
87 (add-global-assumption "Ax1Aux7"
88 (pf "all rhos4,sigs5,sig5,ss3,s3,ss4,s4.
89 Exps rhos4 (sigs5:+:sig5:)
90 (ss3:+:s3:) (ss4:+:s4:) ->
91 Exps rhos4 sigs5 ss3 ss4 &
92 Exp rhos4 sig5 s3 s4"))
93
94 ; Lemma: "Ax1Aux8"
95 ; ----------------
96 (add-global-assumption "Ax1Aux8"
97 (pf "all rhos4,sig5,k,s5.
98 Exp rhos4 sig5(Var k)s5 ->
99 TypJ rhos4 (Var k) sig5"))
100 ; proof by inversion
101 ; (or by the more general ExpTypJ)
102
103 ; Lemma: "Ax1Aux9"
104 ; ----------------
105 (add-global-assumption "Ax1Aux9"
106 (pf "all rhos,tau,r,k,rho.
107 Fr rhos tau r k ->
108 TypJ (rhos:+:ExtCtx rhos k rho) (Var k) rho"))
109
110 ; Lemma: "Ax1Aux10"
111 ; -----------------
112 (add-global-assumption "Ax1Aux10"
113 (pf "all sigs,rho,sig.
114 --->sigs (rho to sig)=
115 --->(sigs :+: rho:) sig"))
116
117 ; Lemma: "Ax1Aux11"
118 ; -----------------
119 (add-global-assumption "Ax1Aux11"
120 (pf "all rhos,rho,n,rs,k.
121 Fr rhos rho (FoldApp (Var n) rs) k ->
122 Cor rhos (Var n)"))
123
124 ; Lemma: "Ax1Aux12"
125 ; -----------------
126 (add-global-assumption "Ax1Aux12"
127 (pf "all rhos,n2,rhos4,k,rho,tau.
128 Cor rhos (Var n2) ->
129 rhos4=rhos:+:(ExtCtx rhos k rho) ->
130 TypJ rhos4 (Var n2) tau ->
131 TypJ rhos (Var n2) tau"))
132
133 ; Lemma: "Ax1Aux13"
134 ; -----------------
135 (add-global-assumption "Ax1Aux13"
136 (pf "all rhos,sigs5,tau,n2,rs3,k.
137 Fr rhos tau (FoldApp(Var n2)rs3) k ->
138 TypJ rhos (Var n2)(--->(sigs5) tau) ->
139 TypJs rhos rs3 sigs5"))
140
141 ; Lemma: "BNsTypJ"
142 ; ----------------
143 (add-global-assumption "BNsTypJ"
144 (pf "all rs,ss,rhos,sigs.
145 BNs rs ss -> TypJs rhos rs sigs ->
146 TypJs rhos ss sigs"))
147 ; proof by BNTypJ
148
149 ; Lemma: "ExpsRedCtx"
150 ; -------------------
151 (add-global-assumption "ExpsRedCtx"
152 (pf "all rhos,rhos1,sigs,rs,ss.
153 Exps (rhos:+:rhos1) sigs rs ss ->
154 TypJs rhos rs sigs ->
155 Exps rhos sigs rs ss"))
156 ; clear by definition
157
158 ; Lemma: "Ax1Aux14"
159 ; -----------------
160 (add-global-assumption "Ax1Aux14"
161 (pf "all r,ss5,s5.
162 (FoldApp r ss5) s5 =
163 FoldApp r (ss5:+:s5:)"))
164
165 ; Lemma: "Ax1Aux15"
166 ; -----------------
167 (add-global-assumption "Ax1Aux15"
168 (pf "all rhos4,rho,k,s5.
169 Exp rhos4 rho (Var k) s5 ->
170 s5 = Eta rho (Var k)"))
171 ; proof by inversion
172
173 ; Lemma: "SubThroughEta"
174 ; ----------------------
175 (add-global-assumption "SubThroughEta"
176 (pf "all rho,r,theta.
177 Sub (Eta rho r) theta =
178 Eta rho (Sub r theta)"))
179 ; proof by induction on rho
180
181 ; Lemma: "ABSLift"
182 ; ----------------
183 ; is basically the assertion of
184 ; "Fr rhos r k ->
185 ; ABS k rho r = Abs rho (Lift r 0 1)":
186
187 (add-global-assumption "ABSLift"
188 (pf "all rhos,rho,r,k.
189 Fr rhos rho r k ->
190 Sub r (Wrap(Succ(Succ k))
191 ((Var map Seq 1 k):+:(Var 0):)) =
192 Lift r 0 1"))
193 ; proof by induction on r for the
194 ; more general lemma:
195 ;
196 ; Fr rhos r k ->
197 ; Sub r (Wrap(Succ(Succ (m+k)))
198 ; ((Var map Seq 0 m):+:
199 ; (Var map Seq (m+1) k):+:
200 ; (Var m):)) =
201 ; Lift r m 1"))
202
203 ; Lemma: "ExpsTypJs"
204 ; ------------------
205 (add-global-assumption "ExpsTypJs"
206 (pf "all rhos,sigs,rs,ss.
207 Exps rhos sigs rs ss ->
208 TypJs rhos rs sigs ->
209 TypJs rhos ss sigs"))
210 ; proof by ExpTypJ
211
212 ; Lemma: "Ax1Aux16"
213 ; -----------------
214 (add-global-assumption "Ax1Aux16"
215 (pf "all rhos,n,sigs,tau,ss,k.
216 (k < Lh(rhos) -> F) ->
217 TypJ rhos (Var n) (---> sigs tau) ->
218 TypJs rhos ss sigs ->
219 Fr rhos tau (FoldApp(Var n)ss) k"))
220
221 ; Lemma: "Ax1Aux17"
222 ; -----------------
223 (add-global-assumption "Ax1Aux17"
224 (pf "all k.
225 Sub(Var k)(Wrap(Succ(Succ k))
226 ((Var map Seq 1 k):+:(Var 0):)) =
227 Var 0"))
228
229 ; Lemma: "Ax1Aux18"
230 ; -----------------
231 (add-global-assumption "Ax1Aux18"
232 (pf "all k,rho,r,n,rs.
233 FoldApp(Var n) rs = ABS k rho r -> F"))
234
235 ; Lemma: "Ax1Aux19"
236 ; -----------------
237 (add-global-assumption "Ax1Aux19"
238 (pf "all rho3,r3,s3,rs3,r,k.
239 FoldApp(Abs rho3 r3)(s3::rs3)=r(Var k) ->
240 ex rs4. (s3::rs3) = (rs4:+:(Var k):) &
241 r = FoldApp (Abs rho3 r3) rs4"))
242
243 ; Lemma: "Ax1Aux20"
244 ; -----------------
245 (add-global-assumption "Ax1Aux20"
246 (pf "all rs4,s3,rs3,k.
247 rs4=(Nil term) ->
248 (s3::rs3)= rs4:+:(Var k): ->
249 (Var k) = s3 &
250 rs3 = (Nil term)"))
251
252 ; Lemma: "Ax1Aux21"
253 ; -----------------
254 ; has non-trivial proof
255 (add-global-assumption "Ax1Aux21"
256 (pf "all r3,k,t2.
257 BN(Sub r3(Wrap 0(Var k):))t2 ->
258 ex t3. t2 = (Sub t3(Wrap 0(Var k):)) &
259 BN r3 t3"))
260
261 ; Lemma: "Ax1Aux22"
262 ; -----------------
263 (add-global-assumption "Ax1Aux22"
264 (pf "all rhos,rho,sig,r,k.
265 Fr rhos (rho to sig) (Abs rho r) k ->
266 Fr (rho::rhos) sig r (Succ k)"))
267
268 ; Lemma: "Ax1Aux23"
269 ; -----------------
270 (add-global-assumption "Ax1Aux23"
271 (pf "all rhos,tau,r,k,rho.
272 Fr rhos tau r (Succ k) ->
273 Abs rho r = ABS k rho (Sub r (Wrap 0(Var k):))"))
274 ; proof by induction on k
275 ; Notice: Case k = 0: Trivial
276 ; Case k = n+1: Notice: k is allowed to be in
277 ; r! But it is lowered during substitution
278 ; by 1, hence not conflicting with the new k
279
280 ; Lemma: "Ax1Aux24"
281 ; -----------------
282 (add-global-assumption "Ax1Aux24"
283 (pf "all r,t,k,rhos,rho.
284 BN r t -> Fr rhos rho r k ->
285 Fr rhos rho t k"))
286 ; proof uses BNTypJ
287
288 ; Lemma: "Ax1Aux25"
289 ; -----------------
290 (add-global-assumption "Ax1Aux25"
291 (pf "all k,rhos,rho.
292 (k < Lh rhos -> F) ->
293 TypJ(rhos:+:ExtCtx rhos k rho)(Var k)rho"))
294
295 ; Lemma: "Ax1Aux26"
296 ; -----------------
297 (add-global-assumption "Ax1Aux26"
298 (pf "all rhos,rho,k.
299 (rhos:+:(ExtCtx rhos k rho):+:(Nil type)) =
300 rhos:+:(ExtCtx rhos k rho)"))
301
302 ; Lemma: "Ax1Aux27"
303 ; -----------------
304 (add-global-assumption "Ax1Aux27"
305 (pf "all rhos,rho,sig,r.
306 TypJ (rho::rhos) r sig ->
307 TypJ rhos (Abs rho r) (rho to sig)"))
308
309 ; Lemma: "Ax1Aux28"
310 ; -----------------
311 (add-global-assumption "Ax1Aux28"
312 (pf "all rhos,rho,sig,r.
313 TypJ rhos (Abs rho r) (rho to sig) ->
314 TypJ (rho::rhos) r sig"))
315
316 ; Lemma: "Ax1Aux29"
317 ; -----------------
318 (add-global-assumption "Ax1Aux29"
319 (pf "all s3,rs3,r5,rs5,k.
320 (s3::rs3)=((r5::rs5):+:(Var k):) ->
321 s3 = r5 & rs3 =(rs5:+:(Var k):)"))
322
323 ; Lemma: "Ax1Aux30"
324 ; -----------------
325 (add-global-assumption "Ax1Aux30"
326 (pf "all rho,r,s,ss.
327 (FoldApp((Abs rho r) s) ss) =
328 (FoldApp(Abs rho r)(s::ss))"))
329
330
331 ; Subsubsection: Proof of "Ax1"
332 ; :::::::::::::::::::::::::::::
333
334 ; Lemma: "Ax1Ind"
335 ; ---------------
336 (set-goal
337 (pf "all rhos,rho,sig,r,k,s.
338 Fr rhos(rho to sig)r k ->
339 NInd(rhos :+: ExtCtx rhos k rho)sig(r(Var k))s ->
340 NInd rhos(rho to sig)r (ABS k rho s)"))
341
342 (assume "rhos" "rho" "sig" "r" "k" "s")
343 (assume "[FrTemp]" "[N]")
344
345 ; Inversion on N
346 (inversion "[N]")
347 (drop "[N]")
348 (assume "rhos2" "rho2" "r2" "s2" "t2")
349 (assume 1 2 3 4 5 6 7)
350
351 ; >>> Simplification
352 (assert (pf "BN (r(Var k)) t2"))
353 (simp 8)
354 (use 4)
355 (assume "[BN]")
356 (drop 4)
357
358 (assert (pf "
359 Exp (rhos:+:ExtCtx rhos k rho) sig t2 s"))
360 (simp-with 6)
361 (simp-with 7)
362 (simp-with 9)
363 (use 5)
364 (assume "[ExpTemp]")
365 (drop 5)
366
367 (assert (pf "
368 TypJ (rhos:+:ExtCtx rhos k rho)
369 (r(Var k)) sig"))
370 (simp-with 6)
371 (simp-with 7)
372 (simp-with 8)
373 (use 3)
374 (assume "[TypJ]")
375 (drop 3)
376
377 (drop 6 7 9)
378 ; <<< End Simplification
379
380 ; Generalization
381 (assert (pf "all r.
382 r2 = r (Var k) ->
383 Exp(rhos:+:ExtCtx rhos k rho)sig t2 s ->
384 Fr rhos(rho to sig)r k ->
385 NInd rhos(rho to sig)r(ABS k rho s)"))
386
387
388 ; Induction on BN
389 ; %%%%%%%%%%%%%%%
390 (assert (pf "BN r2 t2"))
391 (simp "<-" 8)
392 (use "[BN]")
393 (elim (pf "BNs rs ss -> T"))
394 (drop "[BN]")
395
396
397 ; Case 1 of BN-Induction
398 ; %%%%%%%%%%%%%%%%%%%%%%
399 (assume "n2" "rs2" "ss2" "[BNs]" 2)
400 (drop 14)
401
402 (assume "r10")
403 (assume "[r k]")
404 (assume "[Exp]")
405 (assume "[Fr]")
406
407 (assert (pf "ex rs1.
408 rs2 = (rs1:+:(Var k):) &
409 r10 = FoldApp (Var n2) rs1"))
410 (use "Ax1Aux1")
411 (use "[r k]")
412 (assume "[Ex]")
413 (by-assume-with "[Ex]" "rs3" "[Inst]")
414
415 (assert (pf "ex ss1,s1. ss2 = (ss1:+:s1:)"))
416 (use "Ax1Aux2" (pt "rs3") (pt "(Var k)"))
417 (simp-with "<-" "[Inst]" 'left)
418 (use "[BNs]")
419 (assume "[Ex2]")
420 (by-assume-with "[Ex2]" "ss3" "[Ex2b]")
421 (by-assume-with "[Ex2b]" "s3" "[Inst2]")
422
423 (assert (pf
424 "BNs (rs3:+:(Var k):) (ss3:+:s3:)"))
425 (simp "<-" "[Inst]" 'left)
426 (simp "<-" "[Inst2]")
427 (use "[BNs]")
428 (assume "[BNs2]")
429 (drop "[BNs]")
430
431 (assert (pf "BN (Var k) s3"))
432 (use "Ax1Aux3" (pt "rs3") (pt "ss3"))
433 (use "[BNs2]")
434 (assume "[BN k]")
435
436 (assert (pf "BNs rs3 ss3"))
437 (use "Ax1Aux3" (pt "(Var k)") (pt "s3"))
438 (use "[BNs2]")
439 (assume "[BNs3]")
440 (drop "[BNs2]")
441
442 (assert (pf "(Var k) = s3"))
443 (use "Ax1Aux4")
444 (use "[BN k]")
445 (assume "[Var k=s3]")
446
447 ; >>> Simplification
448 (assert (pf "
449 Exp(rhos:+:ExtCtx rhos k rho) sig
450 (FoldApp (Var n2) (ss3:+:(Var k):)) s"))
451 (simp-with "[Var k=s3]")
452 (simp-with "<-" "[Inst2]")
453 (use "[Exp]")
454 (assume "[Exp2]")
455 (drop "[Exp]")
456
457 (assert (pf "
458 Fr rhos(rho to sig)
459 (FoldApp(Var n2)rs3) k"))
460 (simp-with "<-" "[Inst]" 'right)
461 (use "[Fr]")
462 (assume "[Fr2]")
463 (drop "[Fr]")
464
465 (simp-with "[Inst]" 'right)
466 (drop 14 15 "[Inst]" "[Inst2]"
467 "[BN k]" "[Var k=s3]")
468 ; <<< Simplification
469
470
471 ; Intro on N
472 ; %%%%%%%%%%
473 (intro 0 (pt "(FoldApp(Var n2)(ss3))"))
474
475 ; Case: TypJ
476 (use "FrDef" (pt "k"))
477 (use "[Fr2]")
478
479 ; Case: BN
480 (intro 0)
481 (use "[BNs3]")
482
483 ; Case: Exp
484
485 ; Inversion on Exp
486 ; %%%%%%%%%%%%%%%%
487 (inversion "[Exp2]"
488 (pf "Exps rhos sigs rs ss -> T"))
489 (drop "[Exp2]")
490
491
492 ; Case 1 of Exp-Inversion
493 ; %%%%%%%%%%%%%%%%%%%%%%%
494 (assume "rhos4" "sigs4" "rs4"
495 "ss4" "n4" "t4" "rho4")
496 (assume 1 2 3 4 5 6 7 8)
497
498 (assert (pf "(Var n4) = (Var n2) &
499 rs4 = (ss3:+:(Var k):)"))
500 (use "Ax1Aux5")
501 (simp 35)
502 (ng #t)
503 (prop)
504 (assume "[Ids]")
505
506 ; >>> Start Clearance
507 (drop 32)
508
509 (assert (pf "
510 s=Eta sig (FoldApp(Var n2)ss4)"))
511 (simp 34)
512 (simp 36)
513 (simp "<-" "[Ids]" 'left)
514 (use 31)
515 (assume "[Eta]")
516 (drop 31 36)
517
518 (assert (pf "
519 TypJ (rhos:+:ExtCtx rhos k rho)
520 (Var n2)(--->sigs4 sig)"))
521 (simp 33)
522 (simp 34)
523 (simp "<-" "[Ids]" 'left)
524 (use 29)
525 (assume "[TypJ1]")
526 (drop 29 35)
527 (drop 34)
528
529 (assert (pf "
530 Exps (rhos:+:ExtCtx rhos k rho)
531 sigs4 (ss3:+:(Var k):) ss4"))
532 (simp "<-" "[Ids]" 'right)
533 (simp 33)
534 (use 30)
535 (assume "[Exps]")
536 (drop 30 33)
537 ; <<< End Clearance
538
539 (assert (pf "ex sigs5,sig5,ss5,s5.
540 sigs4 = (sigs5 :+: sig5:) &
541 ss4 = (ss5 :+: s5:)"))
542 (use "Ax1Aux6" (pt "(rhos:+:ExtCtx rhos k rho)")
543 (pt "ss3") (pt "k"))
544 (use "[Exps]")
545 (assume "[Ex3]")
546 (by-assume-with "[Ex3]" "sigs5" "[Ex3b]")
547 (by-assume-with "[Ex3b]" "sig5" "[Ex3c]")
548 (by-assume-with "[Ex3c]" "ss5" "[Ex3d]")
549 (by-assume-with "[Ex3d]" "s5" "[Inst3]")
550
551 ; >>> Simplification
552 (assert (pf "
553 Exps (rhos:+:ExtCtx rhos k rho) (sigs5:+:sig5:)
554 (ss3:+:(Var k):) (ss5:+:s5:)"))
555 (simp-with "<-" "[Inst3]" 'left)
556 (simp-with "<-" "[Inst3]" 'right)
557 (use "[Exps]")
558 (assume "[Exps2]")
559 (drop "[Exps]")
560 ; <<< End Simplification
561
562 (assert (pf "Exps (rhos:+:ExtCtx rhos k rho) sigs5 ss3 ss5"))
563 (use "Ax1Aux7" (pt "sig5") (pt "(Var k)")(pt "s5"))
564 (use "[Exps2]")
565 (assume "[Exps3]")
566
567 (assert (pf "Exp (rhos:+:ExtCtx rhos k rho) sig5 (Var k) (s5)"))
568 (use "Ax1Aux7" (pt "sigs5") (pt "ss3")(pt "ss5"))
569 (use "[Exps2]")
570 (assume "[Exp3]")
571
572 (drop "[Exps2]")
573
574 ; Part: rho=sig5
575 (assert (pf "rho=sig5"))
576
577 (assert (pf "TypJ (rhos:+:ExtCtx rhos k rho)
578 (Var k) sig5"))
579 (use "Ax1Aux8" (pt "s5"))
580 (use "[Exp3]")
581 (assume "[TypJ k 1]")
582
583 (assert (pf "TypJ (rhos:+:ExtCtx rhos k rho)
584 (Var k) rho"))
585 (use "Ax1Aux9" (pt "(rho to sig)")
586 (pt "(FoldApp(Var n2)rs3)"))
587 (use "[Fr2]")
588 (assume "[TypJ k 2]")
589 (ng)
590 (simp-with "<-" "[TypJ k 2]" 'right)
591 (simp-with "<-" "[TypJ k 1]" 'right)
592 (prop)
593 (assume "[rho=sig5]")
594
595 (assert (pf "TypJ (rhos:+:ExtCtx rhos k rho)
596 (Var n2)
597 (--->(sigs5) (rho to sig))"))
598 (simp (pf "rho = sig5"))
599 (simp (pf "(--->sigs5(sig5 to sig)) =
600 (--->(sigs5:+:sig5:) sig)"))
601 (simp-with "<-" "[Inst3]" 'left)
602 (simp "<-" (pf "rho = sig5"))
603 (use "[TypJ1]")
604 (use "[rho=sig5]")
605 (use "Ax1Aux10")
606 (use "[rho=sig5]")
607 (assume "[TypJ2]")
608 (drop "[TypJ1]")
609
610 ; TypJ rhos
611 (assert (pf "TypJ rhos (Var n2)
612 (--->sigs5(rho to sig))"))
613
614 (use "Ax1Aux12" (pt "(rhos:+:ExtCtx rhos k rho)")
615 (pt "k")
616 (pt "rho"))
617 (use "Ax1Aux11" (pt "(rho to sig)") (pt "rs3")
618 (pt "k"))
619 (use "[Fr2]")
620 (ng #t)
621 (prop)
622 (use "[TypJ2]")
623 (assume "[TypJ3]")
624 (drop "[TypJ2]")
625
626 ; Intermezzo: TypJs ss3
627 ; needed twice
628 (assert (pf "TypJs rhos ss3 sigs5"))
629 (use "BNsTypJ" (pt "rs3"))
630 (use "[BNs3]")
631 (use "Ax1Aux13" (pt "rho to sig")(pt "n2")
632 (pt "k"))
633 (use "[Fr2]")
634 (use "[TypJ3]")
635 (assume "[TypJs ss3]")
636
637 ; Exps rhos
638 (assert (pf "Exps rhos sigs5 ss3 ss5"))
639
640 (use "ExpsRedCtx" (pt "(ExtCtx rhos k rho)"))
641 (use "[Exps3]")
642 (use "[TypJs ss3]")
643 (assume "[Exps4]")
644 (drop "[Exps3]")
645
646 ; Part: Intro Exp
647 (intro 0 (pt "sigs5") (pt "ss5"))
648
649 ; TypJ
650 (use "[TypJ3]")
651
652 ; Exps
653 (use "[Exps4]")
654
655 ; Part: Eta
656 (assert (pf "
657 s = Eta sig ((FoldApp(Var n2)(ss5)) s5)"))
658 (simp "Ax1Aux14")
659 (simp-with "<-" "[Inst3]" 'right)
660 (use "[Eta]")
661 (assume "[Eta2]")
662 (drop "[Eta]")
663
664 ; >>> Simplification
665 (assert (pf "Exp (rhos:+:ExtCtx rhos k rho)
666 rho (Var k) s5"))
667 (simp-with
668 (pf "(rhos:+:(ExtCtx rhos k rho))=
669 (rhos:+:(ExtCtx rhos k sig5))"))
670 (simp-with "[rho=sig5]")
671 (simp-with
672 (pf "(rhos:+:(ExtCtx rhos k sig5))=
673 (rhos:+:(ExtCtx rhos k rho))"))
674 (use "[Exp3]")
675 (simp-with "[rho=sig5]")
676 (ng)
677 (prop)
678 (simp-with "[rho=sig5]")
679 (ng)
680 (prop)
681 (assume "[Exp4]")
682 (drop "[Exp3]")
683 ; <<< End: Simplification
684
685 (assert (pf "s5 = Eta rho (Var k)"))
686 (use "Ax1Aux15" (pt "(rhos:+:ExtCtx rhos k rho)"))
687 (use "[Exp4]")
688 (assume "[s5=Eta rho(Var k)]")
689
690 (assert (pf "
691 s = Eta sig ((FoldApp (Var n2) ss5)
692 (Eta rho(Var k)))"))
693 (simp "<-" "[s5=Eta rho(Var k)]")
694 (use "[Eta2]")
695 (assume "[Eta3]")
696 (drop "[Eta2]")
697
698 (simp "[Eta3]")
699 (ng #t)
700
701 (simp (pf "
702 Sub (Eta sig(FoldApp(Var n2)ss5
703 (Eta rho(Var k))))
704 (Wrap(Succ(Succ k))
705 ((Var map Seq 1 k):+:(Var 0):)) =
706 Eta sig(Sub (FoldApp(Var n2)ss5
707 (Eta rho(Var k)))
708 (Wrap(Succ(Succ k))
709 ((Var map Seq 1 k):+:(Var 0):)))"))
710
711 (ng #t)
712
713 (simp (pf "Sub(FoldApp(Var n2)ss5)
714 (Wrap(Succ(Succ k))((Var map Seq 1 k):+:
715 (Var 0):)) =
716 Lift (FoldApp(Var n2)ss5) 0 1"))
717
718 (simp (pf "(Sub(Eta rho(Var k))
719 (Wrap(Succ(Succ k))
720 ((Var map Seq 1 k):+:(Var 0):))) =
721 Eta rho (Sub (Var k)
722 (Wrap(Succ(Succ k))
723 ((Var map Seq 1 k):+:(Var 0):)))"))
724
725 (simp (pf "(Sub (Var k)
726 (Wrap(Succ(Succ k))
727 ((Var map Seq 1 k):+:(Var 0):))) =
728 (Var 0)"))
729
730 (ng #t)
731 (prop)
732
733 (use "Ax1Aux17")
734 (use "SubThroughEta")
735 (use "ABSLift" (pt "rhos")
736 (pt "(rho to sig)"))
737 (use "Ax1Aux16" (pt "sigs5"))
738 (use "FrDef" (pt "(rho to sig)")
739 (pt "(FoldApp(Var n2)rs3)"))
740 (use "[Fr2]")
741 (use "[TypJ3]")
742 (use "ExpsTypJs" (pt "ss3"))
743 (use "[Exps4]")
744 (use "[TypJs ss3]")
745 (use "SubThroughEta")
746
747
748 ; Case 2 of Exp-Inversion
749 ; %%%%%%%%%%%%%%%%%%%%%%%
750 (assume "rhos584" "rhos4" "sigs12" "taus12"
751 "rho585" "sig586" "r12" "s587" "k588")
752 (assume 1 2 3 4 5 6 7 8)
753
754 (assert (pf "(FoldApp(Var n2)(ss3:+:(Var k):) =
755 ABS k588 rho585 r12) -> F"))
756 (use "Ax1Aux18")
757 (assume "[Contr]")
758 (prop)
759
760 ; Case 3 of Exp-Inversion
761 ; %%%%%%%%%%%%%%%%%%%%%%%
762 (assume "rhos100")
763 (prop)
764
765 ; Case 4 of Exp-Inversion
766 ; %%%%%%%%%%%%%%%%%%%%%%%
767 (assume "rhos5" "sigs5" "r5"
768 "s5" "rs5" "ss5")
769 (prop)
770
771
772 ; Case 2 of BN-Induction
773 ; %%%%%%%%%%%%%%%%%%%%%%
774 ; contradiction of second case:
775
776 (assume "rho3" "r3" "s3" "t3" "rs3")
777 (assume "r4")
778 (ng)
779 (prop)
780
781
782 ; Case 3 of BN-Induction
783 ; %%%%%%%%%%%%%%%%%%%%%%
784 (assume "rho3" "r3" "s3" "t" "rs3")
785 (assume "[BN2]" "[IH BN]")
786 (drop "[BN]" 8)
787 (assume "r10")
788 (assume "[r k]")
789 (assume "[Exp]")
790 (assume "[Fr]")
791
792 (assert (pf "
793 ex rs4. (s3::rs3) = (rs4:+:(Var k):) &
794 r10 = FoldApp (Abs rho3 r3) rs4"))
795
796 (use "Ax1Aux19")
797 (use "[r k]")
798 (assume "[Ex]")
799 (by-assume-with "[Ex]" "rs4" "[Inst]")
800 (drop "[r k]")
801
802 (simp "[Inst]" 'right)
803
804
805 ; Case 3.1: "rs4 = (Nil term)"
806 ; %%%%%%%%%%%%%%%%%%%%%%%%%%%%
807 (cases (pt "rs4"))
808 (assume "[rs4]")
809
810 ; >>> Clearance
811 (assert (pf "(Var k) = s3 &
812 rs3 = (Nil term)"))
813 (use "Ax1Aux20" (pt "rs4")(pt "rs3"))
814 (use "[rs4]")
815 (use-with "[Inst]" 'left)
816 (assume "[Ids]")
817
818 (assert (pf "r10=Abs rho3 r3"))
819 (simp (pf "Abs rho3 r3 =
820 FoldApp (Abs rho3 r3) (Nil term)"))
821 (simp "<-" "[rs4]")
822 (use-with "[Inst]" 'right)
823 (ng)
824 (prop)
825 (assume "[r]")
826 (drop "[Inst]")
827
828 (assert (pf "
829 BN (Sub r3(Wrap 0 (Var k):)) t"))
830 (simp (pf "(Sub r3(Wrap 0 (Var k):)) =
831 (FoldApp(Sub r3 (Wrap 0 (Var k):))
832 (Nil term))"))
833 (simp-with "[Ids]" 'left)
834 (simp (pf "
835 FoldApp(Sub r3(Wrap 0 s3:)) (Nil term) =
836 FoldApp(Sub r3(Wrap 0 s3:))rs3"))
837 (use "[BN2]")
838 (simp-with "<-" "[Ids]" 'right)
839 (ng)
840 (prop)
841 (ng)
842 (prop)
843 (assume "[BN4]")
844 (drop "[BN2]")
845 (drop "[rs4]" "[Ids]")
846
847 (simp (pf "
848 (FoldApp(Abs rho3 r3)(Nil term)) =
849 Abs rho3 r3"))
850 ; >>> End Clearance
851
852 ; rho=rho3
853 (assert (pf "rho=rho3"))
854 (assert (pf "TypJ rhos r10 (rho to sig)"))
855
856 (use "FrDef" (pt "k"))
857 (use "[Fr]")
858 (simp "[r]")
859 (assume "[temp]")
860 (ng "[temp]")
861 (simp-with "<-" "[temp]" 'right 'left)
862 (ng)
863 (prop)
864 (assume "[rho]")
865
866 (assert (pf "r10=Abs rho r3"))
867 (simp "[rho]")
868 (use "[r]")
869 (assume "[r2]")
870 (drop "[r]")
871
872 (simp "<-" "[rho]")
873 (drop "[rho]")
874
875 ; ex t3
876 (assert (pf "
877 ex t3. t = (Sub t3(Wrap 0(Var k):)) &
878 BN r3 t3"))
879 (use "Ax1Aux21")
880 (use "[BN4]")
881 (assume "[Ex2]")
882 (by-assume-with "[Ex2]" "t3" "[Inst3]")
883
884 ; Intro N
885 (intro 0 (pt "Abs rho t3"))
886 (use "FrDef" (pt "k"))
887 (simp "<-" "[r2]")
888 (use "[Fr]")
889
890 ; BN
891 (intro 1)
892 (use-with "[Inst3]" 'right)
893
894 ;Exp
895 (assert (pf "Abs rho t3 =
896 ABS k rho (Sub t3 (Wrap 0(Var k):))"))
897 (use "Ax1Aux23" (pt "(rho::rhos)") (pt "sig"))
898 (use "Ax1Aux24" (pt "r3"))
899 (use "[Inst3]" 'right)
900 (use "Ax1Aux22")
901 (simp "<-" "[r2]")
902 (use "[Fr]")
903 (assume "[ABS]")
904
905 (simp "[ABS]")
906
907 ; Intro Exp:
908 (simp (pf "rhos = (rhos:+:(Nil type))"))
909 (intro 1 (pt "ExtCtx rhos k rho")
910 (pt "(Nil type)"))
911
912 (simp (pf
913 "(rhos:+:(ExtCtx rhos k rho):+:(Nil type)) =
914 rhos:+:(ExtCtx rhos k rho)"))
915
916 (use "Ax1Aux25")
917 (use "FrDef" (pt "(rho to sig)")
918 (pt "r10"))
919 (use "[Fr]")
920
921 (use "Ax1Aux26")
922 (simp "<-" "[Inst3]" 'left)
923 (use "[Exp]")
924
925 (simp "<-" "[ABS]")
926 (use "Ax1Aux27")
927 (use "BNTypJ" (pt "r3"))
928 (use "[Inst3]" 'right)
929 (use "Ax1Aux28")
930 (simp "<-" "[r2]")
931
932 (use "FrDef" (pt "k"))
933 (use "[Fr]")
934 (use "NilAppend")
935 (ng)
936 (prop)
937
938 ; Case 3.1: "rs4 = (r5::rs5)"
939 ; %%%%%%%%%%%%%%%%%%%%%%%%%%%
940 (assume "r5" "rs5")
941 (assume "[r4]")
942
943 ; >>> Start Clearance
944 (assert (pf "s3 = r5 &
945 rs3 =(rs5:+:(Var k):)"))
946 (use "Ax1Aux29")
947 (simp "<-" "[r4]")
948 (use "[Inst]" 'left)
949 (assume "[Inst1]")
950
951 (assert (pf "
952 BN (FoldApp(Sub r3(Wrap 0 r5:))
953 (rs5:+:(Var k):)) t"))
954 (simp "<-" "[Inst1]" 'left)
955 (simp "<-" "[Inst1]" 'right)
956 (use "[BN2]")
957 (assume "[BN3]")
958 (drop "[BN2]")
959
960 (assert (pf "
961 r10=FoldApp(Abs rho3 r3)(r5::rs5)"))
962 (simp "<-" "[r4]" 'right)
963 (use "[Inst]")
964 (assume "[Inst2]")
965 (drop "[Inst]" "[r4]")
966 ; >>> End Clearance
967
968 (assert (pf "
969 NInd rhos(rho to sig)
970 (FoldApp(Sub r3(Wrap 0 r5:))rs5)
971 (ABS k rho s)"))
972
973 (use "[IH BN]")
974
975 ; Fold
976 (simp "[Inst1]" 'left)
977 (simp "[Inst1]" 'right)
978 (simp "Ax1Aux14")
979 (ng)
980 (prop)
981
982 ; Exp
983 (use "[Exp]")
984
985 ; Fr
986 (assert (pf "Fr rhos(rho to sig)
987 (FoldApp ((Abs rho3 r3)r5) rs5) k"))
988 (simp "Ax1Aux30")
989 (simp "<-" "[Inst2]")
990 (use "[Fr]")
991 (assume "[Fr1]")
992
993 (use "FrDefRev")
994 (use "TypJFoldHead"
995 (pt "(Abs rho3 r3 r5)"))
996 (use "FrDef" (pt "k"))
997 (use "[Fr1]")
998 (use "SR" (pt "rho3"))
999 (use "CorTypJ")
1000 (use "TypJFoldHeadCor" (pt "(rho to sig)")
1001 (pt "rs5"))
1002 (use "FrDef" (pt "k"))
1003 (use "[Fr1]")
1004 (use "FrDef" (pt "(rho to sig)")
1005 (pt "(FoldApp(Abs rho3 r3 r5)rs5)"))
1006 (use "[Fr1]")
1007
1008 (assume "[N2]")
1009
1010 (inversion "[N2]")
1011 (assume "rhos4" "rho4" "r4" "s4" "t4")
1012 (assume 1 2 3 4 5 6 7)
1013
1014 ; >>> Start Clearance
1015 (assert (pf "
1016 BN (FoldApp(Sub r3(Wrap 0 r5:))rs5) t4"))
1017 (simp 30)
1018 (use 26)
1019 (assume "[BN4]")
1020 (drop 26 "[BN3]")
1021
1022 (assert (pf "
1023 Exp rhos (rho to sig) t4 (ABS k rho s)"))
1024 (simp 28)
1025 (simp 29)
1026 (simp 31)
1027 (use 27)
1028 (assume "[Exp2]")
1029
1030 (drop 27 28 29 30 31 "[Exp]")
1031 ; <<< End Clearance
1032
1033 (intro 0 (pt "t4"))
1034
1035 ; TypJ
1036 (simp "<-" "[Inst2]")
1037 (use "FrDef" (pt "k"))
1038 (use "[Fr]")
1039
1040 ; BN
1041 (simp (pf "FoldApp(Abs rho3 r3)(r5::rs5) =
1042 FoldApp((Abs rho3 r3)r5) rs5"))
1043
1044 (intro 2)
1045 (use "[BN4]")
1046 (ng)
1047 (prop)
1048 (use "[Exp2]")
1049
1050 ; Final Parts (trivial)
1051 ; =====================
1052 (prop)
1053
1054 (assume "r3" "s3" "rs3" "ss3")
1055 (prop)
1056
1057 (assume "[Gen]")
1058 (use "[Gen]")
1059 (simp 8)
1060 (ng)
1061 (prop)
1062 (use "[ExpTemp]")
1063 (use "[FrTemp]")
1064 (save "Ax1Ind")
1065
1066 ; Lemma: "Ax1"
1067 ; -----------
1068 (set-goal
1069 (pf "all rhos,rho,sig,r,k,s.
1070 Fr rhos(rho to sig)r k ->
1071 N (rhos :+: ExtCtx rhos k rho) sig (r(Var k)) s ->
1072 N rhos (rho to sig) r (ABS k rho s)"))
1073
1074 (assume "rhos" "rho" "sig" "r" "k" "s")
1075 (assume 1 2)
1076 (use "NDefRev")
1077 (assert (pf "NInd (rhos:+:ExtCtx rhos k rho)
1078 sig(r(Var k))s"))
1079 (use "NDef")
1080 (use 2)
1081 (assert (pf "Fr rhos(rho to sig)r k"))
1082 (use 1)
1083
1084 (use "Ax1Ind")
1085 (save "Ax1")