Debian Codegraph @

examples/tait/diplomarbeit_schlenker/subst_Joachimski.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 ;
14 ; NOTICE: Uncomment modules only when file is run on its own
15 ; ***********************************************************
16
17
18 ; ==============================
19 ; Section: Substitution Lemmas
20 ; ==============================
21 ; Substitution in Joachimski style
22
23 ; Lemma: "LtSuccCases"
24 ; --------------------
25 ; later used induction scheme
26
27 (set-goal (pf "all m,n.n<Succ m -> (n<m -> Pvar^) ->
28 (n=m -> Pvar^) -> Pvar^"))
29
30 (ind)
31 (cases)
32 (assume "H1" "H2" "H3")
33 (use "H3")
34 (use "Truth-Axiom")
35 (assume "n" "H1" "H2" "H3")
36 (use "Efq")
37 (use "H1")
38 (assume "m" "IHm")
39 (cases)
40 (assume "H1" "H2" "H3")
41 (use "H2")
42 (use "Truth-Axiom")
43 (use "IHm")
44 (save "LtSuccCases")
45
46
47 ; Definition: "Subcompose"
48 ; ------------------------
49 ; Composition on substitutions
50
51 (add-program-constant "Subcompose"
52 (py "Sublist=>Sublist=>Sublist") 1 'const 2)
53
54 ; ________________________ INTERNAL ________________________
55 ; Allows the infix notation with "circ" instead of "Subcompose"
56
57 (add-token
58 "circ"
59 'mul-op
60 (lambda (x y)
61 (let* ((type1 (term-to-type x))
62 (type2 (term-to-type y))
63 (type (types-lub type1 type2)))
64 (mk-term-in-app-form
65 (make-term-in-const-form (pconst-name-to-pconst "Subcompose"))
66 x y))))
67
68 (add-display
69 (py "Sublist")
70 (lambda (x)
71 (let ((op (term-in-app-form-to-final-op x))
72 (args (term-in-app-form-to-args x)))
73 (if (and (term-in-const-form? op)
74 (string=? "Subcompose"
75 (const-to-name
76 (term-in-const-form-to-const op)))
77 (= 2 (length args)))
78 (list 'mul-op "circ"
79 (term-to-token-tree (car args))
80 (term-to-token-tree (cadr args)))
81 #f))))
82 ; _________________________________________________________
83
84
85 (add-computation-rule (pt "Up 0 circ theta") (pt "theta"))
86 (add-computation-rule (pt "Up(Succ n) circ Dot r theta")
87 (pt "Up n circ theta"))
88 (add-computation-rule (pt "Up(Succ n)circ Up m")
89 (pt "Up(Succ n+m)"))
90 (add-computation-rule (pt "Dot r theta circ theta1")
91 (pt "Dot(Sub r theta1)(theta circ theta1)"))
92
93 ; Lemma: "LiftId"
94 ; --------------
95 ; lifting with value 0 is identity
96
97 (set-goal (pf "all r,k.Lift r k 0=r"))
98
99 (ind)
100 (assume "n" "k")
101 (ng)
102 (use "Truth-Axiom")
103
104 ; Case App r s
105 (assume "r" "s" "IHr" "IHs" "k")
106 (ng)
107 (simp "IHr")
108 (simp "IHs")
109 (use "Truth-Axiom")
110
111 ; Case Abs r
112 (assume "rho" "r" "IHr" "k")
113 (ng)
114 (use "IHr")
115 (save "LiftId")
116
117 (add-rewrite-rule (pt "Lift r k 0") (pt "r"))
118
119 ; Lemma: "LiftTwiceMod"
120 ; ---------------------
121 ; lifting with k and then with k1 is the same as lifting
122 ; with (k+k1) at one step
123
124 (set-goal (pf "all r,l,k,k1.Lift(Lift r l k)l k1=Lift r l(k+k1)"))
125
126 (ind)
127 (assume "n" "l" "k" "k1")
128 (cases (pt "n<l"))
129 (assume "n<l")
130 (ng)
131 (simp "n<l")
132 (ng)
133 (simp "n<l")
134 (use "Truth-Axiom")
135
136 (assume "n<l -> F")
137 (ng)
138 (simp "n<l -> F")
139 (ng)
140 (add-global-assumption "LiftTwiceModAux1"
141 (pf "all n,l,k.n+k<l -> n<l"))
142 (cut (pf "n+k<l -> F"))
143 (assume "H1")
144 (simp "H1")
145 (use "Truth-Axiom")
146 (assume "n+k<l")
147 (use "n<l -> F")
148 (use "LiftTwiceModAux1" (pt "k"))
149 (use "n+k<l")
150
151 ; Case App r s
152 (assume "r" "s" "IHr" "IHs" "l" "k" "k1")
153 (ng)
154 (simp "IHr")
155 (simp "IHs")
156 (use "Truth-Axiom")
157
158 ; Case Abs r
159 (assume "rho" "r" "IHr" "l" "k" "k1")
160 (ng)
161 (use "IHr")
162 (save "LiftTwiceMod")
163
164 (add-rewrite-rule (pt "Lift(Lift r l k)l k1") (pt "Lift r l(k+k1)"))
165
166
167 ; Lemma: "LiftTwice"
168 ; ------------------
169 ; Joachimski (1)
170
171 (set-goal (pf "all r,l,k,k1.Lift(Lift r l k)(k+l)k1=
172 Lift r l(k+k1)"))
173
174 (ind)
175 (ng)
176 (assume "n" "l" "k" "k1")
177 (cases (pt "n<l"))
178 (assume "n<l")
179 (ng)
180 (add-global-assumption "LiftTwiceAux1"
181 (pf "all n,l,k.n<l -> n<k+l"))
182 (cut (pf "n<k+l"))
183 (assume "n<k+l")
184 (simp "n<k+l")
185 (use "Truth-Axiom")
186 (use "LiftTwiceAux1")
187 (use "n<l")
188
189 (assume "n<l -> F")
190 (ng)
191 (cut (pf "n+k<k+l -> F"))
192 (assume "n+k<k+l -> F")
193 (simp "n+k<k+l -> F")
194 (use "Truth-Axiom")
195 (assume "n+k<k+l")
196 (use "n<l -> F")
197 (add-global-assumption "LiftTwiceAux2"
198 (pf "all n,l,k.n+k<k+l -> n<l"))
199 (use "LiftTwiceAux2" (pt "k"))
200 (use "n+k<k+l")
201
202 ; Case App r s
203 (assume "r" "s" "IHr" "IHs" "l" "k" "k1")
204 (ng)
205 (simp "IHr")
206 (simp "IHs")
207 (use "Truth-Axiom")
208
209 ; Case Abs r
210 (assume "rho" "r" "IHr" "l" "k" "k1")
211 (ng)
212 (use-with "IHr" (pt "Succ l") (pt "k") (pt "k1"))
213 (save "LiftTwice")
214
215 ; Lemma: "SubliftId"
216 ; ------------------
217 ; lifting of a substitution list with value 0 is identity
218
219 (set-goal (pf "all theta.Sublift theta 0=theta"))
220
221 (ind)
222 (assume "k")
223 (use "Truth-Axiom")
224 (assume "r" "theta" "IHtheta")
225 (ng)
226 (use "IHtheta")
227 (save "SubliftId")
228
229 (add-rewrite-rule (pt "Sublift theta 0") (pt "theta"))
230
231 ; Lemma: "SubliftTwice"
232 ; ---------------------
233 ; lifting with n and then with m is the same as lifting
234 ; with (m+n) at one step
235
236 (set-goal (pf "all theta,n,m.Sublift(Sublift theta n)m=
237 Sublift theta(n+m)"))
238
239 (ind)
240 (assume "k" "n" "m")
241 (ng)
242 (use "Truth-Axiom")
243 (assume "r" "theta" "IHtheta" "n" "m")
244 (ng)
245 (use "IHtheta")
246 (save "SubliftTwice")
247
248
249 ; Definition: "Spare"
250 ; -------------------
251 ; adds 0 1 ... (m-1) to a substitution list
252
253 (add-program-constant "Spare"
254 (py "nat=>Sublist=>Sublist") 1 'const 2)
255
256 (add-computation-rule (pt "Spare 0 theta") (pt "theta"))
257 (add-computation-rule (pt "Spare(Succ m)theta")
258 (pt "Spare m(Dot(Var m)theta)"))
259
260 ; Lemma: "SubVarSpare"
261 ; --------------------
262 (set-goal (pf "all m,k,theta.Sub(Var(k+m))(Spare m theta)=
263 Sub(Var k)theta"))
264
265 (ind)
266 (assume "k" "theta")
267 (use "Truth-Axiom")
268 (assume "m" "IHm" "k" "theta")
269 (ng)
270 (cut (pf "Succ(k+m)=Succ k+m"))
271 (assume "H1")
272 (simp "H1")
273 (use-with "IHm" (pt "Succ k") (pt "Dot(Var m)theta"))
274 (use "Truth-Axiom")
275 (save "SubVarSpare")
276
277 ; Lemma: "SubVarSpareLt"
278 ; ----------------------
279 (set-goal (pf "all m,k,theta.k<m ->
280 Sub(Var k)(Spare m theta)=Var k"))
281
282 (ind)
283 (assume "k" "theta" "Absurd")
284 (use "Efq")
285 (use "Absurd")
286 (assume "m" "IHm" "k" "theta" "k<m+1")
287 (use "LtSuccCases" (pt "m") (pt "k"))
288 (use "k<m+1")
289 (ng)
290 (use "IHm")
291 (assume "k=m")
292 (simp "k=m")
293 (ng)
294 (use-with "SubVarSpare" (pt "m") (pt "0") (pt "Dot(Var m)theta"))
295 (save "SubVarSpareLt")
296
297 ; Lemma: "DotVarSubliftSpare"
298 ; ---------------------------
299 (set-goal
300 (pf "all m,theta.Dot(Var 0)(Sublift(Spare m theta)1)=
301 Spare(Succ m)(Sublift theta 1)"))
302 (ind)
303 (assume "theta")
304 (use "Truth-Axiom")
305 (assume "m" "IHm" "theta")
306 (ng)
307 (use-with "IHm" (pt "Dot(Var m)theta"))
308 (save "DotVarSubliftSpare")
309
310 ; Lemma: "LiftEq"
311 ; ---------------
312 ; Joachimski's (2)
313
314 (set-goal (pf "all r,n,m.Lift r m n=Sub r(Spare m(Up(m+n)))"))
315
316 (ind)
317 (assume "k" "n" "m")
318 (ng)
319
320 ; Case: k<m
321 (cases (pt "k<m"))
322 (assume "k<m")
323 (ng)
324 (inst-with-to "SubVarSpareLt" (pt "m") (pt "k")
325 (pt "Up(m+n)") "k<m" "H1")
326 (simp "H1")
327 (use "Truth-Axiom")
328
329 ; Case k >= m
330 (assume "k<m -> F")
331 (ng)
332 (cut (pf "k=(k-m)+m"))
333 (assume "H2")
334 (simp "H2")
335 (cut (pf "Sub(Var(k-m+m))(Spare m(Up(m+n)))=
336 Sub(Var(k-m))(Up(m+n))"))
337 (assume "H3")
338 (simp "H3")
339 (ng)
340 (use "Truth-Axiom")
341 (use "SubVarSpare")
342 (add-global-assumption "LiftEqAux"
343 (pf "all k,m.(k<m -> F) -> k=k-m+m"))
344 (use "LiftEqAux")
345 (use "k<m -> F")
346
347 ; App
348 (assume "r" "s" "IHr" "IHs" "n" "m")
349 (ng)
350 (inst-with-to "IHr" (pt "n") (pt "m") "IHrEq")
351 (simp "IHrEq")
352 (inst-with-to "IHs" (pt "n") (pt "m") "IHsEq")
353 (simp "IHsEq")
354 (use "Truth-Axiom")
355
356 ; Abs
357 (assume "rho" "r" "IHr" "n" "m")
358 (ng)
359 (simp "DotVarSubliftSpare")
360 (simp "IHr")
361 (use "Truth-Axiom")
362 (save "LiftEq")
363
364 ; Lemma: "CircUpUp"
365 ; -----------------
366 (set-goal (pf "all m,n.Up m circ Up n=Up(m+n)"))
367 (ind)
368 (assume "n")
369 (use "Truth-Axiom")
370 (assume "m" "IHm" "n")
371 (use "Truth-Axiom")
372 (save "CircUpUp")
373
374 (add-rewrite-rule (pt "Up m circ Up n") (pt "Up(m+n)"))
375
376 ; Lemma: "CircUp"
377 ; ---------------
378 ; Joachimski's (3)
379
380 (set-goal (pf "all n,theta.theta circ Up n=Sublift theta n"))
381
382 (assume "n")
383 (ind)
384 (assume "m")
385 (ng)
386 (use "Truth-Axiom")
387 (assume "r" "theta" "IHtheta")
388 (ng)
389 (simp "IHtheta")
390 (simp "LiftEq")
391 (use "Truth-Axiom")
392 (save "CircUp")
393
394 (add-rewrite-rule (pt "theta circ Up n") (pt "Sublift theta n"))
395
396 ; Lemmma: "LiftSubSpare"
397 ; ----------------------
398 ; Joachimski's (4)
399 ; In the original text there is a tiny flaw. Therefore there is a
400 ; corrected version
401
402 (set-goal (pf "all r,m,theta,n.
403 Lift(Sub r(Spare m theta))m n=Sub r(Spare m(Sublift theta n))"))
404
405 ; Counterexample:
406 ; r=Var 1, m=1, theta=Up 0, n=2
407 (pp (nt (pt "Lift(Sub(Var 1)(Spare 1(Up 0)))1 2"))) ;=> Var 0
408 (pp (nt (pt "Sub(Var 1)(Spare 1(Sublift(Up 0)2))"))) ;=> Var 2
409
410 ; Correction (4'). First an auxiliary proposition.
411
412 ; Lemmma: "LiftSubSpareAux1"
413 ; --------------------------
414 (set-goal (pf "all theta,l,m,n.
415 Lift(Sub(Var l)(Sublift theta m))m n=
416 Sub(Var l)(Sublift theta(m+n))"))
417
418 (ind)
419 (assume "k")
420 (ng)
421 (aga "LiftSubSpareAux2" (pf "all l,k,m.l+k+m<m -> F"))
422 (assume "l" "m" "n")
423 (cut (pf "l+k+m<m -> F"))
424 (assume "H1")
425 (simp "H1")
426 (use "Truth-Axiom")
427 (use "LiftSubSpareAux2")
428 (assume "s" "theta" "IHtheta")
429 (ind)
430 (assume "m" "n")
431 (ng)
432 (use-with "LiftTwice" (pt "s") (pt "0") (pt "m") (pt "n"))
433 (assume "l" "IHl" "m" "n")
434 (ng)
435 (use "IHtheta")
436 (save "LiftSubSpareAux1")
437
438 ; Lemmma: "LiftSubSpare"
439 ; ----------------------
440 ; the corrected (4') (see above)
441
442 (set-goal (pf "all r,m,theta,n.
443 Lift(Sub r(Spare m(Sublift theta m)))m n=
444 Sub r(Spare m(Sublift theta(m+n)))"))
445
446 (ind)
447 (assume "k" "m" "theta" "n")
448 (cases (pt "k<m"))
449 (assume "k<m")
450 (simp "SubVarSpareLt")
451 (simp "SubVarSpareLt")
452 (ng)
453 (simp "k<m")
454 (use "Truth-Axiom")
455 (use "k<m")
456 (use "k<m")
457
458 (assume "k<m -> F")
459 (cut (pf "k=(k-m)+m"))
460 (assume "H4")
461 (simp "H4")
462 (simp "SubVarSpare")
463 (simp "SubVarSpare")
464 (use "LiftSubSpareAux1")
465
466 (add-global-assumption "LiftEqAux"
467 (pf "all k,m.(k<m -> F) -> k=k-m+m"))
468 (use "LiftEqAux")
469 (use "k<m -> F")
470
471 ; App
472 (assume "r" "s" "IHr" "IHs" "m" "theta" "n")
473 (ng)
474 (simp "IHr")
475 (simp "IHs")
476 (use "Truth-Axiom")
477
478 ; Abs
479 (assume "rho" "r" "IHr" "m" "theta" "n")
480 (ng)
481 (simp "DotVarSubliftSpare")
482 (simp "SubliftTwice")
483 (simp (pf "m+1=Succ m"))
484 (simp "IHr")
485 (simp "DotVarSubliftSpare")
486 (simp "SubliftTwice")
487 (simp (pf "Succ m+n=m+n+1"))
488 (use "Truth-Axiom")
489 (use "Truth-Axiom")
490 (use "Truth-Axiom")
491 (save "LiftSubSpare")
492
493 ; Lemma: "CircSublift"
494 ; --------------------
495 ; Joachimski's (5)
496
497 (set-goal (pf "all theta,theta1,n.
498 theta circ Sublift theta1 n=Sublift (theta circ theta1) n"))
499
500 (ind)
501 (ind)
502 (assume "theta1" "n")
503 (use "Truth-Axiom")
504 (assume "k" "IHk")
505 (cases)
506 (assume "l" "n")
507 (ng)
508 (use "Truth-Axiom")
509 (assume "r" "theta1" "n")
510 (ng)
511 (use "IHk")
512
513 (assume "r" "theta" "IHtheta" "theta1" "n")
514 (ng)
515 (simp "IHtheta")
516 (ng)
517 (simp-with "<-" "LiftSubSpare" (pt "r") (pt "0")
518 (pt "theta1") (pt "n"))
519 (use "Truth-Axiom")
520 (save "CircSublift")
521
522 ; Definition: "Pushlist"
523 ; ----------------------
524 ; adds the elements of a list to a substitution list
525
526 (add-program-constant "Pushlist"
527 (py "list term=>Sublist=>Sublist") 1 'const 2)
528
529 (add-var-name "rs" "ss" (py "list term"))
530
531 (add-computation-rule (pt "Pushlist(Nil term)theta") (pt "theta"))
532 (add-computation-rule (pt "Pushlist(r::rs)theta")
533 (pt "Dot r(Pushlist rs theta)"))
534
535 ; Lemma: "PushlistEq"
536 ; -------------------
537 (set-goal (pf "all k,theta,rs.Sub(Var(k+Lh rs))(Pushlist rs theta)=
538 Sub(Var k)theta"))
539
540 (assume "k" "theta")
541 (ind)
542 (use "Truth-Axiom")
543 (assume "r" "rs" "IHrs")
544 (ng)
545 (use "IHrs")
546 (save "PushlistEq")
547
548 (add-rewrite-rule (pt "Sub(Var(k+Lh rs))(Pushlist rs theta)")
549 (pt "Sub(Var k)theta"))
550
551 ; Definition: "Liftlist"
552 ; ----------------------
553 ; used in Joachimski (6)
554
555 (add-program-constant "Liftlist"
556 (py "list term=>nat=>nat=>list term") 1)
557
558 (add-computation-rule (pt "Liftlist(Nil term)m n")
559 (pt "(Nil term)"))
560 (add-computation-rule (pt "Liftlist(r::rs)m n")
561 (pt "(Lift r m n)::(Liftlist rs m n)"))
562
563 ; Lemma: "SubliftPushlist"
564 ; ------------------------
565 (set-goal (pf "all theta,n,rs.Sublift(Pushlist rs theta)n=
566 Pushlist(Liftlist rs 0 n)(Sublift theta n)"))
567
568 (assume "theta" "n")
569 (ind)
570 (use "Truth-Axiom")
571 (assume "r" "rs" "IHrs")
572 (ng)
573 (use "IHrs")
574 (save "SubliftPushlist")
575
576 (add-rewrite-rule (pt "Sublift(Pushlist rs theta)n")
577 (pt "Pushlist(Liftlist rs 0 n)(Sublift theta n)"))
578
579 ; Lemma: "LhLiftlist"
580 ; -------------------
581 (set-goal (pf "all m,n,rs.Lh rs=Lh(Liftlist rs m n)"))
582
583 (assume "m" "n")
584 (ind)
585 (use "Truth-Axiom")
586 (assume "r" "rs" "IHrs")
587 (ng)
588 (use "IHrs")
589 (save "LhLiftlist")
590
591 ; Lemma: "SubLiftSpare"
592 ; ---------------------
593 ; Joachimski's (6)
594
595 (set-goal (pf "all r,m,rs,theta.
596 Sub(Lift r m Lh rs)(Spare m(Pushlist rs theta))=
597 Sub r(Spare m theta)"))
598
599 (ind)
600 (assume "k" "m" "rs" "theta")
601 (cases (pt "k<m"))
602 (assume "k<m")
603 (ng)
604 (simp "k<m")
605 (ng)
606 (simp "SubVarSpareLt")
607 (simp "SubVarSpareLt")
608 (use "Truth-Axiom")
609 (use "k<m")
610 (use "k<m")
611
612 (assume "k<m -> F")
613 (ng)
614 (simp "k<m -> F")
615 (ng)
616 (cut (pf "k+Lh rs=k-m+Lh rs+m"))
617 (assume "H3")
618 (simp "H3")
619 (cut (pf "Sub(Var(k-m+Lh rs+m))(Spare m(Pushlist rs theta))=
620 Sub(Var(k-m+Lh rs))(Pushlist rs theta)"))
621 (assume "H4")
622 (ng)
623 (simp "H4")
624 (ng)
625 (cut (pf "Var k=Var(k-m+m)"))
626 (assume "H5")
627 (simp "H5")
628 (cut (pf "Sub(Var(k-m+m))(Spare m theta)=Sub(Var(k-m))theta"))
629 (assume "H6")
630 (simp "H6")
631 (use "Truth-Axiom")
632 (use "SubVarSpare")
633 (add-global-assumption "SubLiftSpareAux1"
634 (pf "all k,m.(k<m -> F) -> k-m+m=k"))
635 (cut (pf "k-m+m=k"))
636 (assume "H7")
637 (simp "H7")
638 (use "Truth-Axiom")
639 (use "SubLiftSpareAux1")
640 (use "k<m -> F")
641 (use "SubVarSpare")
642 (add-global-assumption "SubLiftSpareAux2"
643 (pf "all k,m,n.(k<m -> F) -> k+n=k-m+n+m"))
644 (use "SubLiftSpareAux2")
645 (use "k<m -> F")
646
647 ; App
648 (assume "r" "s" "IHr" "IHs" "m" "rs" "theta")
649 (ng)
650 (simp "IHr")
651 (simp "IHs")
652 (use "Truth-Axiom")
653
654 ; Abs
655 (assume "rho" "r" "IHr" "m" "rs" "theta")
656 (ng)
657 (cut (pf "(Dot(Var 0)(Sublift(Spare m(Pushlist rs theta))1))=
658 Spare(Succ m)(Sublift(Pushlist rs theta)1)"))
659 (assume "H8")
660 (simp "H8")
661 (cut (pf "(Dot(Var 0)(Sublift(Spare m theta)1))=
662 Spare(Succ m)(Sublift theta 1)"))
663 (assume "H9")
664 (simp "H9")
665 (cut (pf "Sublift(Pushlist rs theta)1=
666 Pushlist(Liftlist rs 0 1)(Sublift theta 1)"))
667 (assume "H10")
668 (simp "H10")
669 (cut (pf "Lh rs=Lh(Liftlist rs 0 1)"))
670 (assume "H11")
671 (simp "H11")
672 (use "IHr")
673 (use "LhLiftlist")
674 (use "SubliftPushlist")
675 (use "DotVarSubliftSpare")
676 (use "DotVarSubliftSpare")
677 (save "SubLiftSpare")
678
679 ; Lemma: "SubliftCircAux"
680 ; -----------------------
681 (set-goal
682 (pf "all m,theta,rs.Up(m+Lh rs)circ Pushlist rs theta=
683 Up m circ theta"))
684
685 (assume "m" "theta")
686 (ind)
687 (ng)
688 (use "Truth-Axiom")
689 (assume "r" "rs" "IHr")
690 (ng)
691 (use "IHr")
692 (save "SubliftCircAux")
693
694 ; Lemma: "SubliftCirc"
695 ; --------------------
696 ; Joachimski's (6')
697
698 (set-goal (pf "all theta,theta1,rs.
699 Sublift theta Lh rs circ Pushlist rs theta1=theta circ theta1"))
700
701 (ind)
702 (assume "m" "theta1" "rs")
703 (ng)
704 (use "SubliftCircAux")
705 (assume "r" "theta" "IHtheta" "theta1" "rs")
706 (ng)
707 (cut (pf "(Sub(Lift r 0 Lh rs)(Pushlist rs theta1))=Sub r theta1"))
708 (assume "H1")
709 (simp "H1")
710 (cut (pf "Sublift theta Lh rs circ Pushlist rs theta1=
711 theta circ theta1"))
712 (assume "H2")
713 (simp "H2")
714 (use "Truth-Axiom")
715 (use "IHtheta")
716 (use-with "SubLiftSpare" (pt "r") (pt "0") (pt "rs") (pt "theta1"))
717 (save "SubliftCirc")
718
719 ; Lemma: "SubVarUp"
720 ; -----------------
721 (set-goal (pf "all theta,n,m.Sub(Var(n+m))theta=
722 Sub(Var n)(Up m circ theta)"))
723
724 (ind)
725 (assume "k" "n" "m")
726 (ng)
727 (use "Truth-Axiom")
728 (assume "r" "theta" "IHtheta" "n")
729 (cases)
730 (ng)
731 (use "Truth-Axiom")
732 (assume "m")
733 (use "IHtheta")
734 (save "SubVarUp")
735
736 ; Theorem: "SubSub"
737 ; -----------------
738 ; Joachimski's (7)
739
740 (set-goal (pf "all r,theta,theta1.
741 Sub(Sub r theta)theta1=Sub r(theta circ theta1)"))
742
743 (ind)
744 (ind)
745 (ind)
746 (assume "m" "theta1")
747 (ng)
748 (use-with "SubVarUp" (pt "theta1") (pt "0") (pt "m"))
749 (assume "r" "theta" "IHtheta" "theta1")
750 (ng)
751 (use "Truth-Axiom")
752 (assume "n" "IHn")
753 (ind)
754 (assume "k" "theta1")
755 (ng)
756 (use-with "SubVarUp" (pt "theta1") (pt "Succ n") (pt "k"))
757 (assume "r" "theta" "IHtheta")
758 (ng)
759 (use "IHn")
760
761 ; App
762 (assume "r" "s" "IHr" "IHs" "theta" "theta1")
763 (ng)
764 (simp "IHr")
765 (simp "IHs")
766 (use "Truth-Axiom")
767
768 ; Abs
769 (assume "rho" "r" "IHr" "theta" "theta1")
770 (ng)
771 (cut (pf "Sub(Sub r(Dot(Var 0)(Sublift theta 1)))
772 (Dot(Var 0)(Sublift theta1 1))
773 =Sub r((Dot(Var 0)(Sublift theta 1))circ
774 (Dot(Var 0)(Sublift theta1 1)))"))
775 (assume "H1")
776 (simp "H1")
777 (cut (pf "Dot(Var 0)(Sublift theta 1)circ Dot(Var 0)
778 (Sublift theta1 1)=
779 Dot(Var 0)(Sublift(theta circ theta1)1)"))
780 (assume "H2")
781 (simp "H2")
782 (use "Truth-Axiom")
783 (ng)
784 (cut (pf "Sublift theta 1 circ Dot(Var 0)(Sublift theta1 1)=
785 theta circ(Sublift theta1 1)"))
786 (assume "H3")
787 (simp "H3")
788 (use "CircSublift")
789 (use-with "SubliftCirc" (pt "theta") (pt "Sublift theta1 1")
790 (pt "(Var 0)::(Nil term)"))
791 (use "IHr")
792 (save "SubSub")