| 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") |