| 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 |
; Section: The Proofs of the Axioms (Part 2) |
| 27 |
; ============================================ |
| 28 |
; builds upon the proofs in proofAxiomsGlobal; |
| 29 |
; contains "Ax2" to "Ax10" ("Ax1" is covered in Part 1) |
| 30 |
|
| 31 |
|
| 32 |
; Subsection: "Ax2" |
| 33 |
; ================= |
| 34 |
|
| 35 |
; Subsubsection: Auxiliaries for "Ax2" |
| 36 |
; :::::::::::::::::::::::::::::::::::: |
| 37 |
|
| 38 |
; Lemma: "ATypJ" |
| 39 |
; -------------- |
| 40 |
(set-goal (pf "all rhos,rho,r,s. |
| 41 |
AInd rhos rho r s -> |
| 42 |
TypJ rhos r rho")) |
| 43 |
|
| 44 |
(assume "rhos" "rho" "r" "s") |
| 45 |
(elim) |
| 46 |
(assume "rhos2" "rho2" "k2") |
| 47 |
(prop) |
| 48 |
|
| 49 |
(assume "rhos2" "rho2" "sig2" |
| 50 |
"r2" "s2" "r1" "s1") |
| 51 |
(assume 1 2 3 4) |
| 52 |
(ng) |
| 53 |
(split) |
| 54 |
(split) |
| 55 |
(split) |
| 56 |
(use-with 4 'left) |
| 57 |
(use-with 2 'left) |
| 58 |
(simp-with 2 'right) |
| 59 |
(simp-with 4 'right) |
| 60 |
(ng) |
| 61 |
(prop) |
| 62 |
(simp-with 4 'right) |
| 63 |
(ng) |
| 64 |
(prop) |
| 65 |
(save "ATypJ") |
| 66 |
|
| 67 |
; Lemma "LemFoldApp" |
| 68 |
; ------------------ |
| 69 |
(set-goal (pf "all rs,r,s. |
| 70 |
(FoldApp r rs)s = FoldApp r (rs:+:s:)")) |
| 71 |
|
| 72 |
(ind) |
| 73 |
(assume "r" "s") |
| 74 |
(ng) |
| 75 |
(prop) |
| 76 |
|
| 77 |
(assume "t" "rs" 1) |
| 78 |
(assume "r" "s") |
| 79 |
(ng) |
| 80 |
(use 1) |
| 81 |
(save "LemFoldApp") |
| 82 |
|
| 83 |
; Definition: "AAtwo" |
| 84 |
; ------------------- |
| 85 |
(add-ids (list (list |
| 86 |
"Atwo" (make-arity (py "list type")(py "type") |
| 87 |
(py "term")(py "term")) )) |
| 88 |
'("all rhos,rho,sigs,n,rs,ss,ts. |
| 89 |
BNs rs ts -> Exps rhos sigs ts ss -> |
| 90 |
TypJ rhos (Var n) (---> sigs rho) -> |
| 91 |
Atwo rhos rho |
| 92 |
(FoldApp (Var n) rs) |
| 93 |
(FoldApp (Var n) ss)" "AtwoIntro")) |
| 94 |
|
| 95 |
; Lemma "AAtwoAux1" |
| 96 |
; ---------------- |
| 97 |
(add-global-assumption "AAtwoAux1" |
| 98 |
(pf "all rs,ss,rs1,ss1. |
| 99 |
BNs rs ss -> BNs rs1 ss1 -> |
| 100 |
BNs (rs:+:rs1) (ss:+:ss1)")) |
| 101 |
|
| 102 |
; Lemma "AAtwoAux2" |
| 103 |
; ---------------- |
| 104 |
(add-global-assumption "AAtwoAux2" |
| 105 |
(pf "all rhos,sigs1,sigs2, |
| 106 |
rs1,rs2,ss1,ss2. |
| 107 |
Exps rhos sigs1 rs1 ss1 -> |
| 108 |
Exps rhos sigs2 rs2 ss2 -> |
| 109 |
Exps rhos (sigs1:+:sigs2) |
| 110 |
(rs1:+:rs2)(ss1:+:ss2)")) |
| 111 |
|
| 112 |
; Lemma "AAtwoAux3" |
| 113 |
; ---------------- |
| 114 |
(add-global-assumption "AAtwoAux3" |
| 115 |
(pf "all sigs,rho,sig. |
| 116 |
--->(sigs:+:rho:)sig = |
| 117 |
--->sigs(rho to sig)")) |
| 118 |
|
| 119 |
; Lemma: "AAtwo" |
| 120 |
; -------------- |
| 121 |
(set-goal (pf "all rhos,rho,r,s. |
| 122 |
AInd rhos rho r s -> Atwo rhos rho r s")) |
| 123 |
|
| 124 |
(assume "rhos" "rho" "r" "s") |
| 125 |
(elim) |
| 126 |
|
| 127 |
; Case 1 |
| 128 |
(assume "rhos1" "rho1" "k" 1) |
| 129 |
(simp (pf "(Var k)= |
| 130 |
FoldApp (Var k) (Nil term)")) |
| 131 |
(intro 0 (pt "(Nil type)") |
| 132 |
(pt "(Nil term)")) |
| 133 |
(intro 0) |
| 134 |
(intro 0) |
| 135 |
(ng) |
| 136 |
(use 1) |
| 137 |
(ng) |
| 138 |
(prop) |
| 139 |
|
| 140 |
; Case 2 |
| 141 |
(assume "rhos1" "rho1" "sig1" |
| 142 |
"r2" "s2" "r1" "s1") |
| 143 |
(assume 1 2 3 4) |
| 144 |
|
| 145 |
; Inversion on Atwo |
| 146 |
(inversion 4) |
| 147 |
|
| 148 |
(assume "rhos2" "rho2" "sigs2" |
| 149 |
"n2" "rs2" "ss2" "ts2") |
| 150 |
(assume 1 2 3 4 5 6 7) |
| 151 |
|
| 152 |
(simp 10) |
| 153 |
(simp 11) |
| 154 |
|
| 155 |
(simp (pf "(FoldApp(Var n2)rs2 r1) = |
| 156 |
(FoldApp(Var n2) (rs2:+:r1:))")) |
| 157 |
(simp (pf "(FoldApp(Var n2)ss2 s1) = |
| 158 |
(FoldApp(Var n2) (ss2:+:s1:))")) |
| 159 |
|
| 160 |
; Inversion on N |
| 161 |
(inversion 3) |
| 162 |
(assume "rhos3" "rho3" "r3" |
| 163 |
"s3" "t3") |
| 164 |
(assume 1 2 3 4 5 6 7) |
| 165 |
|
| 166 |
(intro 0 (pt "(sigs2:+:rho1:)") |
| 167 |
(pt "(ts2:+:t3:)")) |
| 168 |
|
| 169 |
(use "AAtwoAux1") |
| 170 |
(use 5) |
| 171 |
(intro 1) |
| 172 |
(simp 17) |
| 173 |
(use 13) |
| 174 |
(intro 0) |
| 175 |
|
| 176 |
(use "AAtwoAux2") |
| 177 |
(simp 8) |
| 178 |
(use 6) |
| 179 |
(intro 1) |
| 180 |
(simp 15) |
| 181 |
(simp 16) |
| 182 |
(simp 18) |
| 183 |
(use 14) |
| 184 |
(intro 0) |
| 185 |
|
| 186 |
(simp (pf "(--->(sigs2:+:rho1:)sig1) = |
| 187 |
(---> sigs2 (rho1 to sig1))")) |
| 188 |
(simp 9) |
| 189 |
(simp 8) |
| 190 |
(use 7) |
| 191 |
|
| 192 |
(use "AAtwoAux3") |
| 193 |
|
| 194 |
(use "LemFoldApp") |
| 195 |
(use "LemFoldApp") |
| 196 |
(save "AAtwo") |
| 197 |
|
| 198 |
|
| 199 |
; Subsubsection: Proof of "Ax2" |
| 200 |
; ::::::::::::::::::::::::::::: |
| 201 |
|
| 202 |
; Lemma: "Ax2Ind" |
| 203 |
; --------------- |
| 204 |
(set-goal (pf " all rhos,r,s. |
| 205 |
AInd rhos Iota r s -> |
| 206 |
NInd rhos Iota r s")) |
| 207 |
|
| 208 |
(assume "rhos" "r" "s") |
| 209 |
(assume 1) |
| 210 |
(assert (pf "Atwo rhos Iota r s")) |
| 211 |
(use "AAtwo") |
| 212 |
(use 1) |
| 213 |
(assume 1) |
| 214 |
|
| 215 |
; Inversion on Atwo |
| 216 |
(inversion 2) |
| 217 |
(assume "rhos2" "rho2" "sigs2" |
| 218 |
"n2" "rs2" "ss2" "ts2") |
| 219 |
(assume 1 2 3 4 5 6 7) |
| 220 |
(simp 8) |
| 221 |
(simp 9) |
| 222 |
(intro 0 (pt "(FoldApp (Var n2) ts2)")) |
| 223 |
|
| 224 |
; TypJ |
| 225 |
(simp "<-" 8) |
| 226 |
(use "ATypJ" (pt "s")) |
| 227 |
(use 1) |
| 228 |
|
| 229 |
; BN |
| 230 |
(intro 0) |
| 231 |
(use 3) |
| 232 |
|
| 233 |
; Exp |
| 234 |
(simp (pf "rhos= (rhos:+:(Nil type))")) |
| 235 |
(intro 0 (pt "sigs2") (pt "ss2")) |
| 236 |
|
| 237 |
; TypJ |
| 238 |
(simp 7) |
| 239 |
(simp "<-" |
| 240 |
(pf "rhos = rhos:+:(Nil type)")) |
| 241 |
(simp 6) |
| 242 |
(use 5) |
| 243 |
(use "NilAppend") |
| 244 |
|
| 245 |
; Exps |
| 246 |
(simp "<-" |
| 247 |
(pf "rhos = rhos:+:(Nil type)")) |
| 248 |
(simp 6) |
| 249 |
(use 4) |
| 250 |
(use "NilAppend") |
| 251 |
(ng) |
| 252 |
(prop) |
| 253 |
(use "NilAppend") |
| 254 |
(save "Ax2Ind") |
| 255 |
|
| 256 |
|
| 257 |
; Lemma: "Ax2" |
| 258 |
; ------------ |
| 259 |
(set-goal (pf " all rhos,r,s. |
| 260 |
A rhos Iota r s -> |
| 261 |
N rhos Iota r s")) |
| 262 |
|
| 263 |
(assume "rhos" "r" "s" 1) |
| 264 |
(use "NDefRev") |
| 265 |
(assert (pf "AInd rhos Iota r s")) |
| 266 |
(use "ADef") |
| 267 |
(use 1) |
| 268 |
(use "Ax2Ind") |
| 269 |
(save "Ax2") |
| 270 |
|
| 271 |
|
| 272 |
; Subsection: "Ax3" |
| 273 |
; ================= |
| 274 |
|
| 275 |
; Lemma: "Ax3" |
| 276 |
; ------------ |
| 277 |
(set-goal (pf "all rhos,rho,k. |
| 278 |
TypJ rhos(Var k)rho -> A rhos rho(Var k)(Var k)")) |
| 279 |
|
| 280 |
(assume "rhos" "rho" "k" 1) |
| 281 |
(use "ADefRev") |
| 282 |
(intro 0) |
| 283 |
(use 1) |
| 284 |
(save "Ax3") |
| 285 |
|
| 286 |
|
| 287 |
; Subsection: "Ax4" |
| 288 |
; ================= |
| 289 |
|
| 290 |
; Lemma: "Ax4Ind" |
| 291 |
; --------------- |
| 292 |
(set-goal |
| 293 |
(pf "all rhos,rho,sig,r,s,r1,s1. |
| 294 |
AInd rhos(rho to sig)r s -> |
| 295 |
TypJ rhos r1 rho -> |
| 296 |
NInd rhos rho r1 s1 -> |
| 297 |
AInd rhos sig(r r1)(s s1)")) |
| 298 |
|
| 299 |
(assume "rhos" "rho" "sig" "r" "s" |
| 300 |
"r1" "s1") |
| 301 |
(assume 1 2 3) |
| 302 |
(intro 1 (pt "rho")) |
| 303 |
(use 1) |
| 304 |
(use 2) |
| 305 |
(use 3) |
| 306 |
(save "Ax4Ind") |
| 307 |
|
| 308 |
; Lemma: "Ax4" |
| 309 |
; ------------ |
| 310 |
(set-goal |
| 311 |
(pf "all rhos,rho,sig,r,s,r1,s1. |
| 312 |
A rhos(rho to sig)r s -> |
| 313 |
TypJ rhos r1 rho -> |
| 314 |
N rhos rho r1 s1 -> |
| 315 |
A rhos sig(r r1)(s s1)")) |
| 316 |
|
| 317 |
(assume "rhos" "rho" "sig" "r" "s" |
| 318 |
"r1" "s1") |
| 319 |
(assume 1 2 3) |
| 320 |
(use "ADefRev") |
| 321 |
(assert (pf "NInd rhos rho r1 s1")) |
| 322 |
(use "NDef") |
| 323 |
(use 3) |
| 324 |
(assert (pf "TypJ rhos r1 rho")) |
| 325 |
(use 2) |
| 326 |
(assert (pf "AInd rhos(rho to sig)r s")) |
| 327 |
(use "ADef") |
| 328 |
(use 1) |
| 329 |
(use "Ax4Ind") |
| 330 |
(save "Ax4") |
| 331 |
|
| 332 |
|
| 333 |
; Subsection: "Ax5" |
| 334 |
; ================= |
| 335 |
|
| 336 |
(add-program-constant "Id" |
| 337 |
(py "term => term") 1) |
| 338 |
|
| 339 |
(add-computation-rule (pt "Id r") |
| 340 |
(pt "r")) |
| 341 |
; Lemma: "Ax5Ind" |
| 342 |
; --------------- |
| 343 |
(set-goal |
| 344 |
(pf "all rhos,rho,r,s,t^. |
| 345 |
HeadInd r s -> NInd rhos rho s t^ -> |
| 346 |
TypJ rhos r rho -> NInd rhos rho r t^")) |
| 347 |
|
| 348 |
(assume "rhos" "rho" "r" "s" "t^") |
| 349 |
(elim) |
| 350 |
(assume "rho1" "r1" "s1" "rs") |
| 351 |
(assume 1) |
| 352 |
|
| 353 |
(assert (pf " |
| 354 |
Id (FoldApp(Sub r1(Dot s1(Up 0)))rs) = |
| 355 |
(FoldApp(Sub r1(Dot s1(Up 0)))rs)")) |
| 356 |
(ng) |
| 357 |
(prop) |
| 358 |
|
| 359 |
(assume 1) |
| 360 |
(assert (pf " NInd rhos rho |
| 361 |
(Id (FoldApp(Sub r1(Dot s1(Up 0)))rs)) t^")) |
| 362 |
(simp 2) |
| 363 |
(use 1) |
| 364 |
(assume 1) |
| 365 |
|
| 366 |
(assert (pf " |
| 367 |
Id (FoldApp(Sub r1(Dot s1(Up 0)))rs) = |
| 368 |
(FoldApp(Sub r1(Dot s1(Up 0)))rs)")) |
| 369 |
(use 2) |
| 370 |
|
| 371 |
(assert (pf " NInd rhos rho |
| 372 |
(Id (FoldApp(Sub r1(Dot s1(Up 0)))rs)) t^")) |
| 373 |
(use 3) |
| 374 |
|
| 375 |
(elim) |
| 376 |
(assume "rhos2" "rho2" "r2" "s2" "t2") |
| 377 |
(assume 1 2 3 4 5) |
| 378 |
(intro 0 (pt "t2")) |
| 379 |
(use 8) |
| 380 |
|
| 381 |
(simp (pf "(FoldApp(Abs rho1 r1 s1)rs) = |
| 382 |
(FoldApp(Abs rho1 r1) (s1::rs))")) |
| 383 |
(intro 2) |
| 384 |
(ng #t) |
| 385 |
|
| 386 |
(simp "<-" 7) |
| 387 |
(use 5) |
| 388 |
(ng) |
| 389 |
(prop) |
| 390 |
(use 6) |
| 391 |
(save "Ax5Ind") |
| 392 |
|
| 393 |
; Lemma: "Ax5" |
| 394 |
; ------------ |
| 395 |
(set-goal |
| 396 |
(pf "all rhos,rho,r,s,t^. |
| 397 |
Head r s -> N rhos rho s t^ -> |
| 398 |
TypJ rhos r rho -> N rhos rho r t^")) |
| 399 |
|
| 400 |
(assume "rhos" "rho" "r" "s" "t^" 1 2 3) |
| 401 |
(use "NDefRev") |
| 402 |
(assert (pf "TypJ rhos r rho")) |
| 403 |
(use 3) |
| 404 |
(assert (pf "NInd rhos rho s t^")) |
| 405 |
(use "NDef") |
| 406 |
(use 2) |
| 407 |
(assert (pf "HeadInd r s")) |
| 408 |
(use "HeadDef") |
| 409 |
(use 1) |
| 410 |
(use "Ax5Ind") |
| 411 |
(save "Ax5") |
| 412 |
|
| 413 |
|
| 414 |
; Subsection: "Ax6" |
| 415 |
; ================= |
| 416 |
|
| 417 |
; Subsubsection: Auxiliaries for "Ax6" |
| 418 |
; :::::::::::::::::::::::::::::::::::: |
| 419 |
|
| 420 |
; Lemma: "UpIdGeneral" |
| 421 |
; -------------------- |
| 422 |
; a more general lemma to prove "UpId" |
| 423 |
|
| 424 |
(set-goal |
| 425 |
(pf "all r,n.Sub r (Spare n (Up n)) = r")) |
| 426 |
|
| 427 |
(ind) |
| 428 |
(assume "k") |
| 429 |
(cases) |
| 430 |
(ng) |
| 431 |
(prop) |
| 432 |
|
| 433 |
(assume "n") |
| 434 |
(casedist (pt "k< Succ n")) |
| 435 |
(use "SubVarSpareLt") |
| 436 |
(assume 1) |
| 437 |
(assert (pf "k=(k-Succ n)+Succ n")) |
| 438 |
|
| 439 |
(use "Trivial10") |
| 440 |
(use 1) |
| 441 |
(assume 1) |
| 442 |
(simp 2) |
| 443 |
(simp "SubVarSpare") |
| 444 |
(ng) |
| 445 |
(prop) |
| 446 |
|
| 447 |
; Case: App |
| 448 |
(assume "r" "s" "IH r" "IH s") |
| 449 |
(assume "n") |
| 450 |
(ng) |
| 451 |
(split) |
| 452 |
(use 1) |
| 453 |
(use 2) |
| 454 |
|
| 455 |
; Case: Abs |
| 456 |
(assume "rho" "r" "IH") |
| 457 |
(assume "n") |
| 458 |
(ng) |
| 459 |
(inst-with "IH" (pt "Succ n")) |
| 460 |
(simp "DotVarSubliftSpare") |
| 461 |
(ng) |
| 462 |
(use 2) |
| 463 |
(save "UpIdGeneral") |
| 464 |
|
| 465 |
; Lemma: "UpId" |
| 466 |
; ------------- |
| 467 |
(set-goal |
| 468 |
(pf "all r.Sub r (Up 0) = r")) |
| 469 |
|
| 470 |
(assume "r") |
| 471 |
(assert (pf "Up 0 = (Spare 0 (Up 0))")) |
| 472 |
(ng) |
| 473 |
(prop) |
| 474 |
(assume 1) |
| 475 |
(simp 1) |
| 476 |
(use "UpIdGeneral") |
| 477 |
(save "UpId") |
| 478 |
|
| 479 |
; Lemma: "Ax6AuxAux" |
| 480 |
; --------------------- |
| 481 |
(set-goal |
| 482 |
(pf "all r,s. Sub (Lift r 0 1) (Dot s (Up 0)) = r ")) |
| 483 |
|
| 484 |
(assume "r" "s") |
| 485 |
(assert |
| 486 |
(pf "Sub(Lift r 0 (Lh (s:)))(Spare 0 (Pushlist (s:) (Up 0))) = |
| 487 |
Sub r (Spare 0 (Up 0))")) |
| 488 |
(use "SubLiftSpare") |
| 489 |
(assume 1) |
| 490 |
(ng) |
| 491 |
(simp-with 1) |
| 492 |
(use "UpId") |
| 493 |
(save "Ax6AuxAux") |
| 494 |
|
| 495 |
|
| 496 |
; Lemma: "Ax6Aux" |
| 497 |
; --------------- |
| 498 |
(set-goal |
| 499 |
(pf "all theta, s. (Sublift theta 1) circ (Dot s (Up 0)) = |
| 500 |
theta")) |
| 501 |
|
| 502 |
(ind) |
| 503 |
(assume "n" "s") |
| 504 |
(ng) |
| 505 |
(prop) |
| 506 |
|
| 507 |
(assume "r" "theta" "IH") |
| 508 |
(assume "s") |
| 509 |
(ng) |
| 510 |
(split) |
| 511 |
(use "Ax6AuxAux") |
| 512 |
(use 1) |
| 513 |
(save "Ax6Aux") |
| 514 |
|
| 515 |
|
| 516 |
; Subsubsection: Proof of "Ax6" |
| 517 |
; ::::::::::::::::::::::::::::: |
| 518 |
|
| 519 |
; Lemma: "Ax6Ind" |
| 520 |
; --------------- |
| 521 |
(set-goal (pf "all rho,r,s,theta |
| 522 |
HeadInd((Sub(Abs rho r)theta)s)(Sub r(Dot s theta))")) |
| 523 |
|
| 524 |
(assume "rho" "r" "s" "theta") |
| 525 |
(ng) |
| 526 |
|
| 527 |
(assert |
| 528 |
(pf "(Sub (Sub r (Dot(Var 0)(Sublift theta 1))) (Dot s (Up 0))) = |
| 529 |
(Sub r (Dot(Var 0)(Sublift theta 1) circ (Dot s (Up 0)) ))")) |
| 530 |
(use "SubSub") ;Joachimski lemma |
| 531 |
(assume 2) |
| 532 |
|
| 533 |
(assert (pf "HeadInd |
| 534 |
((Abs rho (Sub r(Dot(Var 0)(Sublift theta 1)))) s) |
| 535 |
((Sub (Sub r(Dot(Var 0)(Sublift theta 1))) (Dot s (Up 0))))")) |
| 536 |
|
| 537 |
(simp (pf "((Abs rho (Sub r(Dot(Var 0)(Sublift theta 1)))) s) = |
| 538 |
FoldApp ((Abs rho (Sub r(Dot(Var 0)(Sublift theta 1)))) s) |
| 539 |
(Nil term)")) |
| 540 |
(simp |
| 541 |
(pf "((Sub (Sub r(Dot(Var 0)(Sublift theta 1))) (Dot s (Up 0)))) = |
| 542 |
FoldApp ((Sub (Sub r(Dot(Var 0)(Sublift theta 1))) |
| 543 |
(Dot s (Up 0)))) (Nil term)")) |
| 544 |
|
| 545 |
(intro 0) |
| 546 |
(ng) |
| 547 |
(prop) |
| 548 |
(ng) |
| 549 |
(prop) |
| 550 |
|
| 551 |
(simp-with 1) |
| 552 |
(ng) |
| 553 |
(simp-with "Ax6Aux" (pt "theta") (pt "s")) |
| 554 |
(prop) |
| 555 |
(save "Ax6Ind") |
| 556 |
|
| 557 |
; Lemma: "Ax6" |
| 558 |
; ------------ |
| 559 |
(set-goal |
| 560 |
(pf "all rho,r,s,theta |
| 561 |
Head((Sub(Abs rho r)theta)s)(Sub r(Dot s theta))")) |
| 562 |
|
| 563 |
(assume "rho" "r" "s" "theta") |
| 564 |
(use "HeadDefRev") |
| 565 |
(use "Ax6Ind") |
| 566 |
(save "Ax6") |
| 567 |
|
| 568 |
|
| 569 |
; Subsection: "Ax7" |
| 570 |
; ================= |
| 571 |
|
| 572 |
; Subsubsection: Auxiliaries for "Ax7" |
| 573 |
; :::::::::::::::::::::::::::::::::::: |
| 574 |
|
| 575 |
; Lemma: "Ax7Aux" |
| 576 |
; --------------- |
| 577 |
(set-goal (pf "all t,rs,r. |
| 578 |
(FoldApp r rs) t = (FoldApp r (rs:+:(t:)))")) |
| 579 |
|
| 580 |
(assume "t") |
| 581 |
(ind) |
| 582 |
(assume "r") |
| 583 |
(ng) |
| 584 |
(prop) |
| 585 |
|
| 586 |
(assume "s" "ss" "IH") |
| 587 |
(assume "r") |
| 588 |
(ng) |
| 589 |
(use "IH") |
| 590 |
(save "Ax7Aux") |
| 591 |
|
| 592 |
|
| 593 |
; Subsubsection: Proof of "Ax7" |
| 594 |
; ::::::::::::::::::::::::::::: |
| 595 |
|
| 596 |
; Lemma: "Ax7Ind" |
| 597 |
; --------------- |
| 598 |
(set-goal (pf "all r,s,t. |
| 599 |
HeadInd r s -> HeadInd(r t)(s t)")) |
| 600 |
|
| 601 |
(assume "r" "s" "t") |
| 602 |
(elim) |
| 603 |
(assume "rho" "r1" "s1" "rs") |
| 604 |
(simp "Ax7Aux") |
| 605 |
(simp "Ax7Aux") |
| 606 |
(intro 0) |
| 607 |
(save "Ax7Ind") |
| 608 |
|
| 609 |
; Lemma: "Ax7" |
| 610 |
; ------------ |
| 611 |
(set-goal (pf "all r,s,t. |
| 612 |
Head r s -> Head(r t)(s t)")) |
| 613 |
|
| 614 |
(assume "r" "s" "t" 1) |
| 615 |
(use "HeadDefRev") |
| 616 |
(assert (pf "HeadInd r s")) |
| 617 |
(use "HeadDef") |
| 618 |
(use 1) |
| 619 |
(use "Ax7Ind") |
| 620 |
(save "Ax7") |
| 621 |
|
| 622 |
|
| 623 |
; Subsection: "Ax8" |
| 624 |
; ================= |
| 625 |
|
| 626 |
; Subsubsection: Auxiliaries for "Ax8" |
| 627 |
; :::::::::::::::::::::::::::::::::::: |
| 628 |
|
| 629 |
; Lemma: "HeadTypJAux1Aux1" |
| 630 |
; ------------------------- |
| 631 |
(add-global-assumption "HeadTypJAux1Aux1" |
| 632 |
(pf "all rhos,r,s,ss. |
| 633 |
Cor rhos(FoldApp(r s)ss) -> Cor rhos (r s)")) |
| 634 |
|
| 635 |
; Lemma: "HeadTypJAux1Aux2" |
| 636 |
; ------------------------- |
| 637 |
(add-global-assumption "HeadTypJAux1Aux2" |
| 638 |
(pf "all rhos,r,r1,s,ss. |
| 639 |
Cor rhos(FoldApp(r s)ss) -> |
| 640 |
Typ rhos r=Typ rhos r1 -> |
| 641 |
Cor rhos(FoldApp(r1 s)ss)")) |
| 642 |
|
| 643 |
; Lemma: "HeadTypJAux1" |
| 644 |
; --------------------- |
| 645 |
(set-goal (pf "all rhos, r, r1, rho, sig. |
| 646 |
TypJ rhos r sig -> TypJ rhos r1 sig -> |
| 647 |
TypJ rhos(FoldApp r rs)rho -> |
| 648 |
TypJ rhos(FoldApp r1 rs)rho")) |
| 649 |
|
| 650 |
(ind) |
| 651 |
(assume "rhos" "r" "r1" "rho" "sig" 1 2 3) |
| 652 |
(ng) |
| 653 |
(split) |
| 654 |
(use-with 2 'left) |
| 655 |
(simp (pf "Typ rhos r1 = Typ rhos r")) |
| 656 |
(use-with 3 'right) |
| 657 |
(simp-with 1 'right) |
| 658 |
(use-with 2 'right) |
| 659 |
|
| 660 |
(assume "s" "ss" "IH") |
| 661 |
(assume "rhos" "r" "r1" "rho" "sig" 1 2 3) |
| 662 |
(ng) |
| 663 |
(inst-with "IH" (pt "rhos") (pt "(r s)") |
| 664 |
(pt "(r1 s)") (pt "rho") (pt "Typ rhos (r s)")) |
| 665 |
(use 5) |
| 666 |
(split) |
| 667 |
|
| 668 |
(use "HeadTypJAux1Aux1" (pt "ss")) |
| 669 |
(use-with 4 'left) |
| 670 |
(prop) |
| 671 |
|
| 672 |
(split) |
| 673 |
(use "HeadTypJAux1Aux1" (pt "ss")) |
| 674 |
(use "HeadTypJAux1Aux2" (pt "r")) |
| 675 |
(use-with 4 'left) |
| 676 |
(simp-with 3 'right) |
| 677 |
(use-with 2 'right) |
| 678 |
(ng) |
| 679 |
(simp-with 3 'right) |
| 680 |
(simp-with 2 'right) |
| 681 |
(prop) |
| 682 |
(use 4) |
| 683 |
(save "HeadTypJAux1") |
| 684 |
|
| 685 |
; Lemma: "HeadTypJAux2" |
| 686 |
; -------------------- |
| 687 |
(add-global-assumption "HeadTypJAux2" |
| 688 |
(pf "all rhos,r,rs,rho. TypJ rhos(FoldApp r rs)rho -> |
| 689 |
Cor rhos r")) |
| 690 |
|
| 691 |
; Lemma: "HeadTypJ" |
| 692 |
; ----------------- |
| 693 |
; needs Subject Reduction |
| 694 |
|
| 695 |
(set-goal (pf "all rho,rhos,r,r1. |
| 696 |
HeadInd r r1 -> TypJ rhos r rho -> TypJ rhos r1 rho")) |
| 697 |
|
| 698 |
(assume "rho" "rhos" "r" "r1") |
| 699 |
(elim) |
| 700 |
(assume "rho1" "r2" "s" "rs" 1) |
| 701 |
(use "HeadTypJAux1" |
| 702 |
(pt "(Abs rho1 r2 s)") (pt "Typ rhos (Abs rho1 r2 s)")) |
| 703 |
(use "CorTypJ") |
| 704 |
|
| 705 |
(use "HeadTypJAux2" (pt "rs") (pt "rho")) |
| 706 |
(use 1) |
| 707 |
(simp (pf "(Dot s(Up 0)) = (Wrap 0 (s:))")) |
| 708 |
(use "SR" (pt "rho1") ) |
| 709 |
|
| 710 |
(use "CorTypJ") |
| 711 |
(use "HeadTypJAux2" (pt "rs") (pt "rho")) |
| 712 |
(use 1) |
| 713 |
|
| 714 |
(ng) |
| 715 |
(prop) |
| 716 |
(use 1) |
| 717 |
(save "HeadTypJ") |
| 718 |
|
| 719 |
|
| 720 |
; Subsubsection: Proof of "Ax8" |
| 721 |
; ::::::::::::::::::::::::::::: |
| 722 |
|
| 723 |
; Lemma: "Ax8Ind" |
| 724 |
; ---------------- |
| 725 |
(set-goal (pf "all rhos,rho,r,r1,k. |
| 726 |
HeadInd r r1 -> Fr rhos rho r k -> |
| 727 |
Fr rhos rho r1 k")) |
| 728 |
|
| 729 |
(assume "rhos" "rho" "r" "r1" "k") |
| 730 |
(assume 1 2) |
| 731 |
(use "FrDefRev") |
| 732 |
(assert (pf "TypJ rhos r rho")) |
| 733 |
(use "FrDef" (pt "k")) |
| 734 |
(use 2) |
| 735 |
(assume 1) |
| 736 |
(use "HeadTypJ" (pt "r")) |
| 737 |
(use 1) |
| 738 |
(use 3) |
| 739 |
(use "FrDef" (pt "rho") (pt "r") ) |
| 740 |
(use 2) |
| 741 |
(save "Ax8Ind") |
| 742 |
|
| 743 |
; Lemma: "Ax8" |
| 744 |
; ------------ |
| 745 |
|
| 746 |
(set-goal (pf "all rhos,rho,r,r1,k. |
| 747 |
Head r r1 -> Fr rhos rho r k -> |
| 748 |
Fr rhos rho r1 k")) |
| 749 |
|
| 750 |
(assume "rhos" "rho" "r" "r1" "k") |
| 751 |
(assume 1 2) |
| 752 |
(use "Ax8Ind" (pt "r")) |
| 753 |
(use "HeadDef") |
| 754 |
(use 1) |
| 755 |
(use 2) |
| 756 |
(save "Ax8") |
| 757 |
|
| 758 |
|
| 759 |
; Subsection: "Ax9" |
| 760 |
; ================= |
| 761 |
|
| 762 |
; Subsubsection: Auxiliaries for "Ax9" |
| 763 |
; :::::::::::::::::::::::::::::::::::: |
| 764 |
|
| 765 |
; Lemma: "ExpExtCtx" |
| 766 |
; ------------------ |
| 767 |
(set-goal (pf "Exp rhos rho r s -> |
| 768 |
Exp(rhos:+:sigs)rho r s")) |
| 769 |
|
| 770 |
(assume "rhos" "rho" "r" "s" "sigs") |
| 771 |
(elim (pf "Exps rhos sigs2 rs ss -> |
| 772 |
Exps (rhos:+:sigs) sigs2 rs ss")) |
| 773 |
|
| 774 |
; Case 1 |
| 775 |
(assume "rhos2" "sigs2" |
| 776 |
"rs2" "ss2" "k2" "t2" "rho2") |
| 777 |
(assume 1 2 3 4) |
| 778 |
(intro 0 (pt "sigs2")(pt "ss2")) |
| 779 |
(use "TypJExtCtx") |
| 780 |
(use 1) |
| 781 |
(use 4) |
| 782 |
(use 3) |
| 783 |
|
| 784 |
; Case 2 |
| 785 |
(assume "rhos3" "rhos4" "sigs2" "taus2" "rho2" |
| 786 |
"sig2" "r2" "s2" "k2") |
| 787 |
(assume 1 2 3 4) |
| 788 |
(simp (pf "(rhos3:+:taus2:+:sigs) = |
| 789 |
(rhos3:+:(taus2:+:sigs))")) |
| 790 |
(intro 1 (pt "rhos4") (pt "sigs2")) |
| 791 |
(use 1) |
| 792 |
(use 2) |
| 793 |
(use 3) |
| 794 |
(use "ListAssoc") |
| 795 |
|
| 796 |
; Case 3 |
| 797 |
(assume "rhos3") |
| 798 |
(intro 0) |
| 799 |
|
| 800 |
; Case 4 |
| 801 |
(assume "rhos2" "sigs2" |
| 802 |
"r2" "s2" "rs2" "ss2") |
| 803 |
(assume 1 2 3 4) |
| 804 |
(intro 1) |
| 805 |
(use 3) |
| 806 |
(use 4) |
| 807 |
(save "ExpExtCtx") |
| 808 |
|
| 809 |
|
| 810 |
; Subsubsection: Proof of "Ax9" |
| 811 |
; ::::::::::::::::::::::::::::: |
| 812 |
|
| 813 |
; Lemma: "Ax9Ind" |
| 814 |
; --------------- |
| 815 |
(set-goal |
| 816 |
(pf "all sigs,rhos,rho,r,s^. |
| 817 |
NInd rhos rho r s^ -> |
| 818 |
NInd (rhos:+:sigs) rho r s^")) |
| 819 |
|
| 820 |
(assume "sigs" "rhos" "rho" "r" "s^") |
| 821 |
(elim) |
| 822 |
|
| 823 |
(assume "rhos1" "rho1" "r1" "s1" "t1") |
| 824 |
(assume 1 2 3) |
| 825 |
(intro 0 (pt "t1")) |
| 826 |
(use "TypJExtCtx") |
| 827 |
(use 1) |
| 828 |
|
| 829 |
; BN |
| 830 |
(use 2) |
| 831 |
|
| 832 |
; Exp |
| 833 |
(use "ExpExtCtx") |
| 834 |
(use 3) |
| 835 |
(save "Ax9Ind") |
| 836 |
|
| 837 |
; Lemma: "Ax9" |
| 838 |
; ------------- |
| 839 |
(set-goal |
| 840 |
(pf "all sigs,rhos,rho,r,s^. |
| 841 |
N rhos rho r s^ -> |
| 842 |
N (rhos:+:sigs) rho r s^")) |
| 843 |
|
| 844 |
(assume "sigs" "rhos" "rho" "r" "s^") |
| 845 |
(assume 1) |
| 846 |
(use "NDefRev") |
| 847 |
(assert (pf "NInd rhos rho r s^")) |
| 848 |
(use "NDef") |
| 849 |
(use 1) |
| 850 |
(use "Ax9Ind") |
| 851 |
(save "Ax9") |
| 852 |
|
| 853 |
|
| 854 |
; Subsection: "Ax10" |
| 855 |
; ================= |
| 856 |
|
| 857 |
; Lemma: "Ax10Ind" |
| 858 |
; --------------- |
| 859 |
|
| 860 |
(set-goal |
| 861 |
(pf "all sigs,rhos,rho,r,s. |
| 862 |
AInd rhos rho r s -> AInd(rhos:+:sigs)rho r s")) |
| 863 |
|
| 864 |
(assume "sigs" "rhos" "rho" "r" "s") |
| 865 |
(elim) |
| 866 |
|
| 867 |
; Case 1 |
| 868 |
(assume "rhos1" "rho1" "k1" 1) |
| 869 |
(intro 0) |
| 870 |
(use "TypJExtCtx") |
| 871 |
(use 1) |
| 872 |
|
| 873 |
; Case 2 |
| 874 |
(assume "rhos2" "rho2" "sig2" "r2" "s2" "r1" "s1") |
| 875 |
(assume 1 2 3 4) |
| 876 |
(intro 1 (pt "rho2")) |
| 877 |
(use 4) |
| 878 |
(use "TypJExtCtx") |
| 879 |
(use 2) |
| 880 |
|
| 881 |
(use "Ax9Ind") |
| 882 |
(use 3) |
| 883 |
(save "Ax10Ind") |
| 884 |
|
| 885 |
; Lemma: "Ax10" |
| 886 |
; ------------ |
| 887 |
(set-goal |
| 888 |
(pf "all sigs,rhos,rho,r,s. |
| 889 |
A rhos rho r s -> A(rhos:+:sigs)rho r s")) |
| 890 |
|
| 891 |
(assume "sigs" "rhos" "rho" "r" "s" 1) |
| 892 |
(use "ADefRev") |
| 893 |
(assert (pf "AInd rhos rho r s")) |
| 894 |
(use "ADef") |
| 895 |
(use 1) |
| 896 |
(use "Ax10Ind") |
| 897 |
(save "Ax10") |
| 898 |
|
| 899 |
|
| 900 |
; Subsection: AxNStrict |
| 901 |
; ===================== |
| 902 |
; used in auxSC.scm |
| 903 |
|
| 904 |
; Lemma: "AxNStrict1Ind" |
| 905 |
; ---------------------- |
| 906 |
|
| 907 |
(set-goal |
| 908 |
(pf "all rhos,rho,r^,s^.NInd rhos rho r^s^ -> E r^")) |
| 909 |
|
| 910 |
(assume "rhos" "rho" "r^" "s^") |
| 911 |
(elim) |
| 912 |
(assume "rhos1" "rho1" "r1" "s1" "t1") |
| 913 |
(assume 1 2 3) |
| 914 |
(ng) |
| 915 |
(prop) |
| 916 |
(save "AxNStrict1Ind") |
| 917 |
|
| 918 |
; Lemma: "AxNStrict1" |
| 919 |
; ---------------------- |
| 920 |
(set-goal |
| 921 |
(pf "all rhos,rho,r^,s^.N rhos rho r^s^ -> E r^")) |
| 922 |
|
| 923 |
(assume "rhos" "rho" "r^" "s^") |
| 924 |
(assume 1) |
| 925 |
(assert (pf "NInd rhos rho r^s^")) |
| 926 |
(use "NDef") |
| 927 |
(use 1) |
| 928 |
(use "AxNStrict1Ind") |
| 929 |
(save "AxNStrict1") |
| 930 |
|
| 931 |
|
| 932 |
; Lemma: "AxNStrict2Ind" |
| 933 |
; ---------------------- |
| 934 |
(set-goal |
| 935 |
(pf "all rhos,rho,r^,s^.NInd rhos rho r^s^ -> E s^")) |
| 936 |
|
| 937 |
(assume "rhos" "rho" "r^" "s^") |
| 938 |
(elim) |
| 939 |
(assume "rhos1" "rho1" "r1" "s1" "t1") |
| 940 |
(assume 1 2 3) |
| 941 |
(ng) |
| 942 |
(prop) |
| 943 |
(save "AxNStrict2Ind") |
| 944 |
|
| 945 |
; Lemma: "AxNStrict2" |
| 946 |
; ------------------- |
| 947 |
(set-goal |
| 948 |
(pf "all rhos,rho,r^,s^.N rhos rho r^s^ -> E s^")) |
| 949 |
|
| 950 |
(assume "rhos" "rho" "r^" "s^") |
| 951 |
(assume 1) |
| 952 |
(assert (pf "NInd rhos rho r^s^")) |
| 953 |
(use "NDef") |
| 954 |
(use 1) |
| 955 |
(use "AxNStrict2Ind") |
| 956 |
(save "AxNStrict2") |