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