Debian Codegraph @

examples/tait/diplomarbeit_schlenker/auxLem3.scm

raw
1 ; $Id: auxLem3.scm 2156 2008-01-25 13:25:12Z schimans $
2 ; ***********************************************************
3 ; ; Adapt path if necessary:
4 ; (define path "~/minlog/examples/tait/diplomarbeit_schlenker/")
5
6 ; ; Defines the function "pload" to load files
7 ; ; from the path defined above
8 ; (define pload (lambda (x) (load (string-append path x))))
9
10 ; ; Used Modules:
11 ; (pload "./initiate.scm")
12 ; (pload "./defsLamCalc.scm")
13 ; (pload "./defsSubst.scm")
14 ; (pload "./omega.scm")
15 ; (pload "./defsNT.scm")
16 ; (pload "./defsAxiomsSpecial.scm")
17 ; (pload "./defsAxioms.scm")
18 ; (pload "./trivial.scm")
19 ; (pload "./auxGlobal_SHORT.scm")
20 ;
21 ; NOTICE: Uncomment modules only when file is run on its own
22 ; ***********************************************************
23
24
25 ; ==================================
26 ; Section: Auxiliaries for Lemma 3
27 ; ==================================
28 ; contains all auxiliaries for Lemma 3
29
30 ; Lemma: "FrExtCtxRev"
31 ; --------------------
32 (set-goal
33 (pf "all rhos, sigs, rho, r, k.
34 TypJ rhos r rho ->
35 Fr(rhos:+:sigs) rho r k -> Fr rhos rho r k"))
36
37 (assume "rhos" "sigs" "rho" "r" "k" 1 2)
38 (use "FrDefRev")
39 (use 1)
40 (assert (pf "k<Lh (rhos:+:sigs) -> F"))
41 (use "FrDef" (pt "rho") (pt "r"))
42 (use 2)
43 (assert (pf "Lh (rhos :+: sigs) = Lh rhos + Lh sigs"))
44 (use "LhRhosSigs")
45 (assume 1)
46 (simp-with 3)
47 (use "Trivial7")
48 (save "FrExtCtxRev")
49
50 ; Lemma: "SCrExtCtx"
51 ; ------------------
52 (set-goal
53 (pf "all rho,rhos,sigs,a^,s.
54 SCr rhos rho a^ s -> SCr (rhos:+:sigs) rho a^ s"))
55
56 (ind)
57
58 ;Case: Iota
59 (assume "rhos" "sigs" "a^" "s" 1)
60 (use "SCrIotaFold")
61 (assert (pf "TypJ rhos s Iota"))
62 (use "SCrUnfoldTwo" (pt "a^"))
63 (use 1)
64 (assume 2)
65 (use "TypJExtCtx")
66 (use 2)
67
68 (use "SCrUnfoldTwo" (pt "rhos") (pt "s"))
69 (use 1)
70
71 (assert (pf "all k.Fr rhos Iota s k
72 -> N rhos Iota s (ModIota a^ k)"))
73 (use "SCrIotaUnfold")
74 (use 1)
75
76 (assume "[neu]")
77 (assume "k" 2)
78
79 (use "Ax9")
80 (use "SCrIotaUnfold")
81 (use 1)
82
83 (use "FrExtCtxRev" (pt "sigs"))
84 (use "SCrUnfoldTwo" (pt "a^"))
85 (use 1)
86 (use 3)
87
88 ; Case (rho to sig)
89 (assume "rho" "sig" "[IH rho]" "[IH sig]")
90
91 ; Case: sigs = (Nil type)
92 (assume "rhos" "sigs" "a^" "s" 1)
93
94 (assert (pf "all sigs,b^,r.SCr (rhos:+:sigs) rho b^ r ->
95 SCr(rhos:+:sigs) sig (Mod a^ b^) (s r)"))
96
97 (use "SCrUnfold")
98 (use 3)
99
100 (assume "[SCr]")
101
102 (use "SCrFold")
103 (assert (pf "TypJ rhos s (rho to sig)"))
104 (use "SCrUnfoldTwo" (pt "a^"))
105 (use 3)
106 (assume 2)
107 (use "TypJExtCtx")
108 (use 5)
109
110 (use "SCrUnfoldTwo" (pt "rhos") (pt "s"))
111 (use 3)
112
113 (assume "taus" "b^" "r" 1)
114
115 (assert (pf "(rhos:+:sigs:+:taus) =
116 (rhos:+:(sigs:+:taus))"))
117 (use "ListAssoc")
118 (assume 1)
119 (simp-with 6)
120
121 (use "[SCr]")
122 (simp-with "<-" 6)
123 (use 5)
124 (save "SCrExtCtx")
125
126 ; Lemma: "SCrsExtCtxSTotal"
127 ; -------------------------
128 (set-goal
129 (pf "all sigs,taus,rhos,as^.STotal as^ -> all ss.
130 SCrs sigs rhos as^ss -> SCrs(sigs:+:taus)rhos as^ss"))
131
132
133 (assume "sigs" "taus")
134 (ind)
135
136 (cases)
137 (cases)
138 (assume 1)
139 (use "SCrsDefNil")
140
141 (assume "r" "rs" 1)
142 ; contradiction:
143 (assert (pf " Lh (Nil type) = Lh (r::rs)"))
144 (use "SCrsLh" (pt "sigs") (pt "(Nil omega)"))
145
146 (use 1)
147 (assume 2)
148 (ng)
149 (prop)
150
151 (assume "a^" "as^" "[STotal]" "ss" 1)
152 ; contradiction:
153 (assert (pf " Lh (a^ ::as^) = Lh (Nil type)"))
154 (use "SCrsLh" (pt "sigs") (pt "ss"))
155
156 (prop)
157 (assume 1)
158 (prop)
159
160 (assume "rho" "rhos" "[IH]")
161 (cases)
162 (assume "ss" 1)
163 ; contradiction:
164 (assert (pf " Lh (Nil omega) = Lh (rho::rhos)"))
165 (use "SCrsLh" (pt "sigs") (pt "ss"))
166 (use 2)
167 (assume 3)
168 (ng)
169 (prop)
170
171 (assume "a^" "as^")
172 (assume "[STotal]")
173 (cases)
174 (assume 1)
175 ; contradiction:
176 (assert (pf " Lh (rho::rhos) = Lh (Nil term)"))
177 (use "SCrsLh" (pt "sigs") (pt "(a^ ::as^)"))
178
179 (use 3)
180 (assume 4)
181 (ng)
182 (prop)
183
184 (assume "r" "rs" "[SCrs]")
185 (use "SCrsDef")
186 (use "[STotal]")
187
188 (assert (pf "SCr sigs rho a^ r"))
189 (use "SCrsDefRev" (pt "rhos") (pt "as^") (pt "rs"))
190 (use "[SCrs]")
191 (assume "[SCr]")
192 (use "SCrExtCtx")
193 (use "[SCr]")
194
195 (use "[IH]")
196 (use "[STotal]")
197
198 (use "SCrsDefRev" (pt "rho") (pt "a^") (pt "r"))
199 (use "[SCrs]")
200 (save "SCrsExtCtxSTotal")
201
202 ; Lemma: "SCrsExtCtx"
203 ; -------------------
204 (set-goal
205 (pf "all sigs,taus,rhos,as^,ss.
206 SCrs sigs rhos as^ss -> SCrs(sigs:+:taus)rhos as^ss"))
207
208 (strip)
209 (use "SCrsExtCtxSTotal")
210 (use "SCrsSTotal" (pt "sigs") (pt "rhos")
211 (pt "ss"))
212 (prop)
213 (prop)
214 (save "SCrsExtCtx")
215
216 ; Lemma: "TypJAbsElim"
217 ; --------------------
218 (set-goal (pf "all rhos,rho,tau,r.
219 TypJ rhos(Abs rho r)tau -> TypJ(rho::rhos)r(Typ(rho::rhos)r)"))
220
221 (assume "rhos" "rho" "tau" "r" 1)
222 (ng)
223 (use-with 1 'left)
224 (save "TypJAbsElim")
225
226 ; Lemma: "TypJVarRef"
227 ; -------------------
228 (set-goal
229 (pf "all k,rhos,rho.
230 TypJ rhos(Var k)rho -> rho=(k thof rhos)"))
231
232 (ind)
233 (ind)
234 (assume "rho" 1)
235 (ng)
236 (prop)
237
238 (assume "rho" "rhos" "IH")
239 (assume "sig" 2)
240 (ng)
241 (simp-with "<-" 2)
242 (prop)
243
244 (assume "n" "IH")
245 (ind)
246 (assume "rho" 2)
247 (ng)
248 (prop)
249
250 (assume "rho" "rhos" "IH 2")
251 (assume "sig" 1)
252 (ng)
253 (inst-with "IH" (pt "rhos") (pt "sig") 3)
254 (prop)
255 (save "TypJVarRef")
256
257 ; Lemma: "TypJAbsArrow"
258 ; ---------------------
259 (set-goal
260 (pf "all rhos,rho,tau,r.
261 TypJ rhos(Abs rho r)tau ->
262 tau=(rho to Typ(rho::rhos)r)"))
263
264 (assume "rhos" "rho" "tau" "r" 1)
265 (assert (pf "tau= Typ rhos (Abs rho r)"))
266 (use "TypJTyp")
267 (use 1)
268 (assume 2)
269 (simp-with 2)
270 (prop)
271 (save "TypJAbsArrow")
272
273 ; Lemma: "LemmaThreeVarSTotal"
274 ; ----------------------------
275 (set-goal
276 (pf "all sigs,rhos,k,as^.STotal as^ -> all ss.
277 SCrs sigs rhos as^ ss -> k<Lh rhos ->
278 SCr sigs(k thof rhos)(k thof as^)(k thof ss)"))
279
280 (assume "sigs")
281 (ind)
282 (assume "k" "as^" 1 "ss" 2 3)
283 (ng)
284 (prop)
285
286 (assume "rho" "rhos" "IH" "k")
287
288 (cases)
289 (cases)
290
291 (assume 1 2)
292 ; contradiction:
293 (assert (pf "Lh (rho::rhos) = Lh (Nil term)"))
294 (use "SCrsLh" (pt "sigs") (pt "(Nil omega)"))
295 (use 2)
296 (assume 4)
297 (ng)
298 (prop)
299
300 (assume "r" "rs" "IH 2" 3)
301 ; contradiction:
302 (assert (pf "Lh (Nil omega) = Lh (rho::rhos)"))
303 (use "SCrsLh" (pt "sigs") (pt "(r::rs)"))
304 (use 2)
305 (assume 4)
306 (ng)
307 (prop)
308
309 (assume "a^" "as^" "[STotal]")
310 (cases)
311 (assume 3 4)
312 ; contradiction:
313 (assert (pf "Lh (rho::rhos) = Lh (Nil term)"))
314 (use "SCrsLh" (pt "sigs") (pt "a^ ::as^"))
315 (use 3)
316 (assume 5)
317 (ng)
318 (prop)
319
320 (assume "r" "rs" 1 2)
321 (inst-with "SCrsDefRev" (pt "sigs")
322 (pt "rho") (pt "rhos") (pt "a^") (pt "as^")
323 (pt "r") (pt "rs") 3)
324 (cases (pt "k"))
325 (assume 6)
326 (ng)
327 (use-with 5 'left)
328
329 (assume "n" 6)
330 (ng)
331 (use "IH")
332 (use "[STotal]")
333 (use-with 5 'right)
334 (assert (pf "Succ n < Succ Lh rhos"))
335 (simp-with "<-" 6)
336 (use 4)
337 (ng)
338 (prop)
339 (save "LemmaThreeVarSTotal")
340
341 ; Lemma: "LemmaThreeVar"
342 ; ----------------------
343 (set-goal
344 (pf "all sigs,rhos,k,as^,ss.
345 SCrs sigs rhos as^ ss -> k<Lh rhos ->
346 SCr sigs(k thof rhos)(k thof as^)(k thof ss)"))
347
348 (strip)
349 (use "LemmaThreeVarSTotal")
350 (use "SCrsSTotal" (pt "sigs") (pt "rhos")
351 (pt "ss"))
352 (prop)
353 (prop)
354 (prop)
355 (save "LemmaThreeVar")
356
357 ; Lemma: "TypJApp"
358 ; ----------------
359 ; auxiliary for LemmaThree
360
361 (set-goal
362 (pf "all sig,rhos,r,s.
363 TypJ rhos(r s)sig ->
364 Typ rhos r = (Typ rhos s to sig)"))
365
366 (ng)
367 (assume "sig" "rhos" "r" "s" "[Ass1]")
368 (simp "<-" (pf "Valtyp(Typ rhos r)=sig"))
369 (use-with "[Ass1]" 'left 'right)
370 (use-with "[Ass1]" 'right)
371 (save "TypJApp")
372
373
374 ; Subsection: LemmaThreeAux1
375 ; ==========================
376 ; makes particularly use of "TypJSub" from the global auxiliaries
377
378 ; Lemma: "SCrsTypJsAllSTotal"
379 ; ---------------------------
380 (set-goal
381 (pf "all sigs,rhos,ss,as^.STotal as^ ->
382 SCrs sigs rhos as^ ss ->
383 TypJs sigs ss rhos"))
384
385 (assume "sigs")
386 (ind)
387 (ind)
388 (assume "as^" "[STotal]" "[SCrs]")
389 (ng)
390 (prop)
391
392 (assume "r" "rs" "[IH rhos]")
393 (assume "as^" "[STotal]" "[SCrs]")
394 ;contradiction
395 (assert (pf " Lh (Nil type) = Lh (r::rs)"))
396 (use "SCrsLh" (pt "sigs") (pt "as^"))
397 (use "[SCrs]")
398 (assume 2)
399 (ng)
400 (prop)
401
402 (assume "rho" "rhos" "[IH rhos]")
403 (ind)
404 (assume "as^" "[STotal]" "[SCrs]")
405 ;contradiction
406 (assert (pf " Lh (rho::rhos) = Lh (Nil term)"))
407 (use "SCrsLh" (pt "sigs") (pt "as^"))
408 (use "[SCrs]")
409 (assume 2)
410 (ng)
411 (prop)
412
413 (assume "r" "rs" "[IH ss]")
414 (cases)
415 (assume "[SCrs]")
416 ;contradiction
417 (assert (pf " Lh (Nil omega) = Lh (rho::rhos)"))
418 (use "SCrsLh" (pt "sigs") (pt "(r::rs)"))
419 (use "[SCrs]")
420 (assume 2)
421 (ng)
422 (prop)
423
424 (assume "a^" "as^" "[STotal]" "[SCrs]")
425 (assert (pf "TypJ sigs r rho"))
426 (use "SCrUnfoldTwo" (pt "a^"))
427 (use "SCrsDefRev" (pt "rhos") (pt "as^") (pt "rs"))
428 (use "[SCrs]")
429
430 (assume "[TypJ]")
431 (ng)
432 (split)
433 (use "[TypJ]")
434
435 (use "[IH rhos]" (pt "as^"))
436 (use "[STotal]")
437 (use "SCrsDefRev" (pt "rho") (pt "a^") (pt "r"))
438 (use "[SCrs]")
439 (save "SCrsTypJsAllSTotal")
440
441 ; Lemma: "SCrsTypJsAll"
442 ; ---------------------
443 (set-goal
444 (pf "all sigs,rhos,ss,as^.
445 SCrs sigs rhos as^ ss ->
446 TypJs sigs ss rhos"))
447
448 (strip)
449 (use "SCrsTypJsAllSTotal" (pt "as^"))
450 (use "SCrsSTotal" (pt "sigs") (pt "rhos")
451 (pt "ss"))
452 (prop)
453 (prop)
454 (save "SCrsTypJsAll")
455
456 ; Lemma: "SCrsTypJs"
457 ; -------------------
458 (set-goal
459 (pf "all sigs,rhos,ss.
460 (ex as^.SCrs sigs rhos as^ ss) ->
461 TypJs sigs ss rhos"))
462
463 (assume "sigs" "rhos" "ss" 1)
464 (by-assume-with 1 "as^" 2)
465 (use "SCrsTypJsAll" (pt "as^"))
466 (prop)
467 (save "SCrsTypJs")
468
469 ; Lemma: "TypJSubSCrs"
470 ; --------------------
471 (set-goal
472 (pf "all rhos,sigs,rho,r,ss.TypJ rhos r rho ->
473 (ex as^.SCrs sigs rhos as^ ss) ->
474 TypJ sigs (Sub r (Wrap 0 ss)) rho"))
475
476 (assume "rhos" "sigs" "rho" "r" "ss" 1 2)
477 (use "TypJSub" (pt "rhos"))
478 (use 1)
479
480 (use "SCrsTypJs")
481 (use 2)
482 (save "TypJSubSCrs")
483
484 ; Lemma: "LemmaThreeAux1"
485 ; ------------------------
486 (set-goal
487 (pf "all rhos,sigs,rho,tau,r,ss.TypJ rhos(Abs rho r)tau ->
488 (ex as^.SCrs sigs rhos as^ ss) ->
489 TypJ sigs(Sub(Abs rho r)
490 (Wrap 0 ss))(rho to Typ(rho::rhos)r)"))
491
492 (assume "rhos" "sigs" "rho" "tau" "r" "ss" 1 2)
493 (assert (pf "tau=(rho to Typ(rho::rhos)r)"))
494 (use "TypJAbsArrow")
495 (prop)
496 (assume "[tau]")
497 (simp "<-" "[tau]")
498 (use "TypJSubSCrs" (pt "rhos"))
499 (use 1)
500 (use 2)
501 (save "LemmaThreeAux1")