; (load "~/minlog/init.scm") (display " Begin of ucomp.scm In this file we define Ucompliment of a bar and show some theorems. We load first bar.scm which contains some basic definitions. ") (exload "FAN/bar.scm") (begin (display " BIG (f,n) iff {0,1}^n ⊆ f ") (add-program-constant "BIG" (mk-arrow (mk-arrow (py "pos") (py "boole")) (py "upos") (py "boole")) 1 'const 2) ; COMPUTATION RULES (add-computation-rule (pt "BIG f Unum")(pt "f 1")) (add-computation-rule (pt "BIG f (SUCC upos)") (pt "TOT (f ∪ ([pos] (ℓ pos)◁(SUCC upos)) ) (Postoupos (₂ (SUCC upos)))")) (display-program-constants "BIG")) (av "e" (mk-arrow (py "upos") (py "pos"))) (display " ∀ f,k,n (BIG f k ∧ ℓn=k) → fn ") (sg "all f,upos,pos.(BIG f upos ∧ ℓ pos=upos) → f pos") (begin (assume "f") (cases) (cases) (auto) (assume "upos") (cases) (use "Truth-Axiom") (assume "pos") (simp "lengthequal") (cd "SZero(SZero pos)< ₂(SUCC(SUCC upos))" "n<2^k") (cd "BIG f(SUCC upos)" "BIGfk+1") (ng #t) (simp(pf"(SZero pos< ₂upos∨f(SZero pos)) = ([pos0]f pos0 ∨ (pos0< ₂upos)) (SZero pos)")) (use (pf "all f,upos,pos. (TOT f upos ∧ pos f pos") (pt"uposPLUS(Postoupos(₂upos))(Postoupos(₂upos))")) (assume "g" "upos0" "pos0") (use "BooleImp") (auto) (ng) (simp "BIGfk+1") (auto) (ng #t) (cases(pt"f(SZero pos)")) (auto) (assume "pos") (simp "lengthequal") (cd "SZero(SOne pos)< ₂(SUCC(SUCC upos))" "2n+1<2^(k+1)") (cd "BIG f(SUCC upos)" "BIGfk+1") (ng #t) (simp(pf"(SZero pos< ₂upos∨f(SOne pos)) = ([pos0]f pos0 ∨ (pos0< ₂upos)) (SOne pos)")) (use (pf "all f,upos,pos. (TOT f upos ∧ pos f pos") (pt"uposPLUS(Postoupos(₂upos))(Postoupos(₂upos))")) (assume "g" "upos0" "pos0") (use "BooleImp") (auto) (ng) (simp "BIGfk+1") (auto) (ng #t) (cases(pt"f(SOne pos)")) (auto)) ; Proof finished. (nrw "(BIG f upos ∧ ℓ pos=upos) → f pos") (nrw "(ℓ pos=upos ∧ BIG f upos) → f pos") (display " bigintersect ∀g,f,i . infpath(g) -> BIG(f,i) -> ∃n. (ℓn=i ∧ i∈g∩f) PROOF: ") (sg "all g,f,upos.( " (∞ "g") " ) -> (BIG f upos) -> ex pos.(ℓ pos=upos ∧ g pos ∧ f pos)") (begin (assume "g" "f") (cases) (ng #t) (assume "∞" "f1") (inst-with-to "∞" (pt"Unum") "l=1") (by-assume-with "l=1" "pos" "ln=1") (ex-intro(pt"pos")) (simp (pf"f pos")) (use "ln=1") (simp(pf"pos=1")) (use "f1") (use "BooleImp" (pt"ℓ pos=Unum ")) (auto) (use-with "ln=1" 'left) (assume "upos" "∞" "BIG (f n+1)") (inst-with-to "∞" (pt"SUCC upos") "l=n+1") (by-assume-with "l=n+1" "pos" "lk=n+1") (ex-intro(pt"pos")) (simp (pf"f pos")) (use "lk=n+1") (use (pf "all upos.(BIG f upos ∧ ℓ pos=upos) -> f pos") (pt"SUCC upos")) (assume "upos0") (use "BooleImp") (auto) (simp "BIG (f n+1)") (simp-with "lk=n+1" 'left) (use "Truth-Axiom")) ; Proof finished. (save "bigintersect") (display-theorems "bigintersect") (display " notTOTchoice: (∀f∀k) ∃n . (TOT f k) | (n<(Upostopos k) and ¬f n ") (sg "all f,upos.ex pos. (TOT f upos) ∨ (pos<(Upostopos upos) ∧ ¬(f pos))") (begin (assume "f") (ind) (ex-intro(pt"1")) (use "Truth-Axiom") (assume "upos" "IH") (cd "TOT f(SUCC upos)" "total") (ex-intro(pt"1")) (use "Truth-Axiom") (assume "nottot") (cd "f (Upostopos upos)" "fn") (by-assume-with "IH" "pos" "IH1") (ex-intro(pt "pos")) (ng #t) (cut(pf"TOT f upos∨(pospos)1 ; ([upos1,pos2] ; [if (TOT([pos3]f pos3∨pos3< ₂upos0)upos1∧ ; (f(Upostopos upos1)∨Upostopos upos1< ₂upos0)) ; 1 ; [if (f(Upostopos upos1)∨Upostopos upos1< ₂upos0) ; pos2 ; (Upostopos upos1)]]) ; (uposPLUS(Postoupos₂upos0)(Postoupos₂upos0)))]= ; upos∧ ; ¬ ; (f ; [if upos ; 1 ; ([upos0] ; (Rec upos=>pos)1 ; ([upos1,pos2] ; [if (TOT([pos3]f pos3∨pos3< ₂upos0)upos1∧ ; (f(Upostopos upos1)∨Upostopos upos1< ₂upos0)) ; 1 ; [if (f(Upostopos upos1)∨Upostopos upos1< ₂upos0) ; pos2 ; (Upostopos upos1)]]) ; (uposPLUS(Postoupos₂upos0)(Postoupos₂upos0)))]))") (deanimate "nonBIGchoice") (sg "¬(¬(BIG f upos)∧f(cnonBIGchoice f upos))") (begin (assume "f" "upos") (use "BooleImp" (pt"(BIG f upos) ∨ ((([pos] (ℓ pos)= upos) ∖ f ) (cnonBIGchoice f upos))")) (cases(pt"BIG f upos")) (auto)) ; Proof finished. (nrw "¬(¬(BIG f upos)∧f(cnonBIGchoice f upos))") (sg "(BIG f upos) ∨ (ℓ(cnonBIGchoice f upos)=upos)") (assume "f" "upos") (use (pf"all boole1,boole2,boole3.boole1∨(boole2∧boole3)->boole1∨boole2") (pt "¬(f(cnonBIGchoice f upos))")) (assume "boole1" "boole2" "boole3") (use "BooleImp") (auto) ; Proof finished. (nrw "(BIG f upos) ∨ (ℓ(cnonBIGchoice f upos)=upos)") (begin (deanimate "nonBIGchoice") (deanimate "notTOTchoice") (animate "notTOTchoice") (animate "nonBIGchoice") (display-theorems "nonBIGchoice") (display " TEST cnonBIGchoice f upos ") (pnt "cnonBIGchoice f upos") (display "cnonBIGchoice ([pos] (ℓ pos)◁(Postoupos 3)) (Postoupos 2) ") (pnt "cnonBIGchoice ([pos] (ℓ pos)◁(Postoupos 3)) (Postoupos 2)") (display "cnonBIGchoice ([pos] (ℓ pos)◁(Postoupos 3)) (Postoupos 3) ") (pnt "cnonBIGchoice ([pos] (ℓ pos)◁(Postoupos 3)) (Postoupos 3)") (display "cnonBIGchoice (([pos] (ℓ pos)◁(Postoupos 3)) ∪ ([pos] (ℓ pos)=(Postoupos 5))) (Postoupos 4) ") (pnt "cnonBIGchoice (([pos] (ℓ pos)◁(Postoupos 3)) ∪ ([pos] (ℓ pos)=(Postoupos 5))) (Postoupos 4)") (display " ") (deanimate "nonBIGchoice") (deanimate "notTOTchoice") ) (begin (deanimate "nonBIGchoice") (deanimate "notTOTchoice") (animate "notTOTchoice") (animate "nonBIGchoice") (display " U : upos -> pos ") (add-program-constant "U" (mk-arrow (mk-arrow (py "pos") (py "boole")) (py "upos") (py "pos")) 1 'const 2) ; COMPUTATION RULES (add-computation-rule (pt "U f Unum")(pt "1")) (add-computation-rule (pt "U f (SUCC upos)") (pt "[if (BIG f (SUCC upos)) (SZero (U f upos)) (cnonBIGchoice f (SUCC upos))]")) (display-program-constants "U") (display" Test of U: ") (display "U ([pos](11 boole) -> (pos -> boole) ") (add-program-constant "UCOMP" (mk-arrow (mk-arrow (py "pos") (py "boole")) (mk-arrow (py "pos") (py "boole"))) 1 'const 2) ; COMPUTATION RULES (add-computation-rule (pt "UCOMP f pos")(pt "f pos → (pos = (U f (ℓ pos)))")) (display-program-constants "UCOMP") (display" Test of UCOMP: ") (display "UCOMP ([pos](11 BIG(f,ℓn) ") (sg "all pos.(pos=U f(ℓpos)∧f pos) → (BIG f (ℓ pos))") (begin (assume "f") (cases) (auto) (assume "pos") (cd "BIG f(ℓ(SZero pos))" "bigl+1") (use "Truth-Axiom") (assume "small(l+1)") (ng) (simp "small(l+1)") (ng) (cds "SZero pos=cnonBIGchoice f(SUCC(ℓ pos))" "2n=bigchoice(l+1)") (ng #t) (use "BooleImp" (pt"¬(BIG f (SUCC(ℓpos)))")) (use (pf"all upos.BIG f upos∨ ¬(f(cnonBIGchoice f upos))")) (auto) (ng) (simp "small(l+1)") (use "Truth-Axiom") (search) (assume "pos") (cd "BIG f(ℓ(SOne pos))" "bigl+1") (use "Truth-Axiom") (assume "small(l+1)") (ng) (simp "small(l+1)") (ng) (cds "SOne pos=cnonBIGchoice f(SUCC(ℓ pos))" "2n+1=bigchoice(l+1)") (ng #t) (use "BooleImp" (pt"¬(BIG f (SUCC(ℓpos)))")) (use (pf"all upos.BIG f upos∨ ¬(f(cnonBIGchoice f upos))")) (auto) (ng) (simp "small(l+1)") (use "Truth-Axiom") (search)) ; Proof finished. (nrw "(pos=U f(ℓpos)∧f pos) → (BIG f (ℓ pos))") (nrw "(f pos∧pos=U f(ℓpos)) → (BIG f (ℓ pos))") (display " ℓ(U f k)=k ") (sg "ℓ(U f upos)=upos") (begin (assume "f") (ind) (auto) (assume "upos" "IH") (ng) (cd "TOT ([pos](f pos ∨ (pos< ₂upos))) (uposPLUS (Postoupos(₂ upos))(Postoupos(₂ upos)))" "big") (auto) (assume "small") (ng) (use "BooleImp" (pt"¬(BIG f (SUCC(upos)))")) (use (pf"all upos.(BIG f upos) ∨ (ℓ(cnonBIGchoice f upos)=upos)")) (auto) (ng) (simp "small") (auto)) ; Proof finished. (add-rewrite-rule(pt "ℓ(U f upos)")(pt"upos")) (display " UCOMP f is an infinite tree: ") (sg "all f." (∞ "(UCOMP f)")) (assume "f" "upos") (ex-intro(pt"U f upos")) (use "Truth-Axiom") ; Proof finished. (save "UCOMPinfinite") (display-theorems "UCOMPinfinite") (display " BAR f → TREE (UCOMP f) ") (sg"all f." (BAR "f") " -> "(TREE "(UCOMP f)")) (begin (assume "f" "bar" "pos") (ng) (cd "(TOT([pos0]f pos0∨pos0< ₂(ℓpos))(uposPLUS(Postoupos₂(ℓpos))(Postoupos₂(ℓpos))))" "big") (ng) (cases (pt"pos=U f(ℓpos)")) (search) (assume "n≠U f(ℓk)") (ng) (cut(pf"f pos → (f(SZero pos)∧ f(SOne pos))")) (cd "f pos" "fn") (auto) (assume "small") (ng) (cases (pt"pos=U f(ℓpos)")) (search) (assume "n≠U f(ℓk)") (ng) (cd "SZero pos=cnonBIGchoice f(SUCC(ℓpos))" "2n=nbc fln+1") (ng) (simp (pf"¬(SOne pos=cnonBIGchoice f(SUCC(ℓpos)))")) (ng) (cut(pf"f pos → (f(SZero pos)∧ f(SOne pos))")) (cd "f pos" "fn") (simp"2n=nbc fln+1") (ng #t) (simp(pf"(f(cnonBIGchoice f (SUCC(ℓpos))))=False")) (auto) (use "BooleImp" (pt"¬(f(cnonBIGchoice f (SUCC(ℓpos))))")) (auto) (use "BooleImp" (pt"¬(¬(BIG f (SUCC(ℓpos)))∧f(cnonBIGchoice f (SUCC(ℓpos))))")) (ng #t) (simp "small") (auto) (use (pf"all upos.¬(¬(BIG f upos)∧f(cnonBIGchoice f upos))")) (auto) (simp "<-" "2n=nbc fln+1") (auto) (assume "2n≠nbc fln+1") (ng) (cd "SOne pos=cnonBIGchoice f(SUCC(ℓpos))" "2n+1=nbc fln+1") (ng) (cut(pf"f pos → (f(SZero pos)∧ f(SOne pos))")) (cd "f pos" "fn") (ng) (simp"2n+1=nbc fln+1") (use "BooleImp") (use "BooleImp" (pt"¬(f(cnonBIGchoice f (SUCC(ℓpos))))")) (auto) (use "BooleImp" (pt"¬(¬(BIG f (SUCC(ℓpos)))∧f(cnonBIGchoice f (SUCC(ℓpos))))")) (ng #t) (simp "small") (auto) (simp(pf"(f(cnonBIGchoice f (SUCC(ℓpos))))=False")) (auto) (use "BooleImp" (pt"¬(f(cnonBIGchoice f (SUCC(ℓpos))))")) (auto) (use "BooleImp" (pt"¬(¬(BIG f (SUCC(ℓpos)))∧f(cnonBIGchoice f (SUCC(ℓpos))))")) (ng #t) (simp "small") (auto) (use (pf"all upos.¬(¬(BIG f upos)∧f(cnonBIGchoice f upos))")) (auto) (assume "2n+1≠nbc fln+1") (ng) (cut(pf"f pos → (f(SZero pos)∧ f(SOne pos))")) (cd "f pos" "fn") (auto)) ; Proof finished. (save "UCOMPtree") (display-theorems "UCOMPtree") (display" End of ucomp.scm ")