Debian Codegraph @

examples/tait/diplomarbeit_schlenker/auxNT.scm

raw
1 ; $Id: auxNT.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 ; (load "./initiate.scm")
12 ; (load "./defsLamCalc.scm")
13 ; (load "./defsSubst.scm")
14 ; (load "./omega.scm")
15 ; (load "./defsNT.scm")
16 ; (load "./defsAxiomsSpecial.scm")
17 ; (load "./defsAxioms.scm")
18 ; (load "./trivial.scm")
19 ; (load "./auxSC.scm")
20 ; (load "./auxGlobal_SHORT.scm")
21 ; (load "./auxLem1_SHORT.scm")
22 ; (load "./Lem1.scm")
23 ;
24 ; NOTICE: Uncomment modules only when file is run on its own
25 ; ***********************************************************
26
27
28 ; ====================================================
29 ; Section: Auxiliaries for the Normalization Theorem
30 ; ====================================================
31 ; contains all auxiliaries for the Normalization Theorem
32
33 ; Subsection: "SCrsSeq"
34 ; =====================
35
36 ; Lemma: "TypJVar"
37 ; ----------------
38 (set-goal (pf "all sigs,rhos,rho
39 TypJ(sigs:+: (rho::rhos))(Var Lh sigs)rho"))
40
41 (ind)
42 ; Base Case: (Nil type)
43 (assume "rhos" "rho")
44 (ng)
45 (use "Truth-Axiom")
46 ; Step Case: (sig :: sigs)
47 (assume "sig" "sigs" "IH")
48 (assume "rhos" "rho")
49 (ng)
50 (use "IH")
51 (save "TypJVar")
52
53 ; Lemma: "SCrsSeq"
54 ; ----------------
55 ; Note: Lemma has computational content
56
57 (set-goal
58 (pf "all rhos,sigs ex as^.
59 SCrs(sigs:+:rhos)rhos as^ (Var map(Seq(Lh sigs)(Lh rhos)))"))
60
61 (ind)
62 ; Base Case: (Nil type)
63 (assume "sigs")
64 (ex-intro (pt "(Nil omega)"))
65 (simp "ListAppendNil")
66 (use "SCrsDefNil")
67
68 ; Step Case: r :: rhos
69 (assume "rho" "rhos" "[IH]" "sigs")
70 (inst-with-to "[IH]" (pt "sigs:+:rho:") "[IH 2]")
71 (by-assume-with "[IH 2]" "as^" "[IHInst]")
72 (assert (pf "ex a^ SCr(sigs:+: (rho::rhos)) rho a^(Var(Lh sigs))"))
73 (use "LemmaOne")
74 (use "TypJVar")
75 (assume "k" 4)
76 (ex-intro (pt "Var Lh sigs"))
77 (use "Ax3")
78 (use "TypJVar")
79 (assume "[SC]")
80 (by-assume-with "[SC]" "a^" "[SC Body]")
81 (ex-intro (pt "a^ ::as^"))
82 (ng #t)
83 (use "SCrsDef")
84 (use "SCrsSTotal" (pt "(sigs:+:rho: :+:rhos)")
85 (pt "rhos")(pt "(Var map Seq Lh(sigs:+:rho:)Lh rhos)"))
86 (prop)
87 (use "[SC Body]")
88 (simp (pf "(sigs:+:(rho::rhos))=(sigs:+:rho: :+:rhos)"))
89 (use "[IHInst]")
90 (simp "ListAppendAssoc")
91 (use "Truth-Axiom")
92 (save "SCrsSeq")
93
94
95 ; Subsection: "SubIds"
96 ; ====================
97
98 ; Lemma: "LhSeq"
99 ; --------------
100 (set-goal (pf "all l,n Lh(Seq n l)=l"))
101
102 (ind)
103 (assume "n")
104 (use "Truth-Axiom")
105 (assume "l" "[IH]")
106 (assume "n")
107 (ng)
108 (use "[IH]")
109 (save "LhSeq")
110
111 ; Lemma: "ListRefMap"
112 ; -------------------
113 (set-goal (pf "all alpha1=>alpha2,(list alpha1),nat.nat<Lh(list alpha1) ->
114 Equal(nat thof(alpha1=>alpha2 map(list alpha1)))
115 (alpha1=>alpha2(nat thof(list alpha1)))"))
116 (assume "alpha1=>alpha2")
117 (ind)
118 (assume "nat" "Absurd")
119 (use "Efq")
120 (use "Absurd")
121 (assume "alpha1" "list alpha1" "IH")
122 (cases)
123 (assume "Trivial")
124 (ng)
125 (use "Eq-Refl")
126 (assume "nat" "nat<Lh List alpha1")
127 (ng)
128 (use "IH")
129 (use "nat<Lh List alpha1")
130 (save "ListRefMap")
131
132 ; Lemma: "ListRefSeq"
133 ; -------------------
134 ; k-th element of Seq
135
136 (set-goal (pf "all l,k,n.k<l -> (k thof Seq n l)=k+n"))
137
138 (ind)
139 (assume "n" "k" "[Absurd]")
140 (use "Efq")
141 (use "[Absurd]")
142 (assume "l" "[IH]")
143 (cases)
144 (assume "k" "[Trivial]")
145 (use "Truth-Axiom")
146 (assume "k" "n" "[k<l]")
147 (ng)
148 (use-with "[IH]" (pt "k") (pt "Succ n") "[k<l]")
149 (save "ListRefSeq")
150
151 ; Lemma: "AuxSubIds"
152 ; ------------------
153 ; an auxiliary for "SubIds" (used as a rewrite-rule).
154
155 (set-goal (pf "all m,n,l.Wrap (Succ n) (Var map Seq (Succ l) m) =
156 Sublift (Wrap n(Var map Seq l m)) 1"))
157
158 (ind)
159 (auto)
160 (save "AuxSubIds")
161
162 (add-rewrite-rule (pt "Wrap (Succ n) (Var map Seq (Succ l) m)")
163 (pt "Sublift (Wrap n(Var map Seq l m)) 1"))
164
165 ; Lemma: "SubIds"
166 ; ---------------
167 (set-goal (pf "all r,rhos, n.Cor rhos r ->
168 Sub r (Wrap n (Var map(Seq 0(Lh rhos))))=r"))
169
170 (ind)
171 (assume "k" "rhos" "n" "[Cor]")
172 (simp "SubVar")
173 (simp "ListRefMap")
174 (simp "ListRefSeq")
175 (auto)
176 (simp "LhSeq")
177 (auto)
178 (simp "LhMap")
179 (simp "LhSeq")
180 (auto)
181
182 ; App
183 (assume "r" "s" "[IHr]" "[IHs]" "rhos" "n" "[Cor]")
184 (ng)
185 (split)
186 (use "[IHr]")
187 (use-with "[Cor]" 'left 'left)
188 (use "[IHs]")
189 (use-with "[Cor]" 'left 'right)
190
191 ; Abs
192 (assume "rho" "r" "[IHr]" "rhos" "n" "[Cor]")
193 (ng)
194 (assert
195 (pf "Sub r (Wrap (Succ n) (Var map Seq 0 Lh(rho::rhos)))=r"))
196 (use "[IHr]")
197 (use "[Cor]")
198 (assume "[EqHyp]")
199 (ng)
200 (auto)
201 (save "SubIds")
202
203
204 ; Subsection: "FrIntro1"
205 ; ======================
206
207 ; Lemma: "FrIntro1"
208 ; -----------------
209 (set-goal (pf "all rhos,r,rho.
210 TypJ rhos r rho -> Fr rhos rho r(Lh rhos)"))
211
212 (assume "rhos" "r" "rho" 1)
213 (use "FrDefRev")
214 (use 1)
215 (use "Trivial1")
216 (save "FrIntro1")