; (load "~/minlog/init.scm") (display " Begin of wklfan.scm In this file we prove that Weak Königs Lemma yields FAN. We load first ucomp.scm which contains the construction of the Ucomplement. ") (exload "FAN/ucomp.scm") (begin (display " Weak Königs Lemma: ∀f.WKL(f) ") (define(WKL function) (string-append "( "(TREE function) " ) -> ( " (∞ function) " ) -> ex g. ( " (⊆ "g" function) " ) & ( " (PATH "g") " ) & (" (∞ "g") " )")) (pp (pf (string-append "all f."(WKL "f"))))) (begin (display " FAN ∀f.FAN(f) ") (define(FAN function) (string-append "( "(BAR function) " ) -> ( ex upos.(all g. ( " (PATH "g") " ) -> (" (∞ "g") " ) -> (ex pos.(ℓ pos = upos ∧ g pos ∧ ( " function " pos)))))" )) (pp (pf (string-append "all f."(FAN "f"))))) (display " bigtofan ∀f. ∃n Big(f,n) -> ∀f FAN f ") (sg "all f.(ex upos (BIG f upos)) -> ( " (FAN "f") ")") (begin (assume "f" "exBIG") (by-assume-with "exBIG" "upos" "iBIG") (assume "Bar") (ex-intro(pt"upos")) (assume "g1" "PATHg1" "∞ g1") (use "bigintersect") (auto)) ; Proof finished. (save "bigtofan") (display-theorems "bigtofan") (display " wklinfpathUbinterb: ∀b. WKL(U_b) → BAR(b) → ( ∃g ⊆ U_b ) ( PATH(g) ∧ ∞(g) ∧ ∃k k∈ b∩g ) ") (sg "all b. ( " (WKL "UCOMP b") " ) -> ( " (BAR "b") " ) -> ex g.( " (⊆ "g" "UCOMP b") " ) & ( " (PATH "g") " ) & ( " (∞ "g") " ) & (ex pos. g pos ∧ b pos)") (begin (assume "b") (assume "WKL Ub") (assume "bar") (cut (pf (string-append "ex g. ( " (⊆ "g" "UCOMP b") " ) & ( " (PATH "g") " ) & (" (∞ "g") " )"))) (assume "exinfpath Ub") (by-assume-with "exinfpath Ub" "g" "infpath Ub") (drop "WKL Ub") (ex-intro(pt"g")) (split) (use "infpath Ub") (use "bar") (use "infpath Ub") (use "infpath Ub") (use "WKL Ub") (use "UCOMPtree") (use "bar") (use "UCOMPinfinite")) ; Proof finished. (save "wklinfpathUbinterb") (display-theorems "wklinfpathUbinterb") (display " wklbarbig: ∀b. WKL(U_b) → BAR(b) → ∃k.BIG(b,k) ") (sg "all b. ( " (WKL "UCOMP b") " ) -> ( " (BAR "b") ") -> ex upos BIG b upos ") (begin (assume "b" "WKL Ub" "bar") (cut (pf (string-append "ex g.( " (⊆ "g" "UCOMP b") " ) & ( " (PATH "g") " ) & ( " (∞ "g") " ) & (ex pos. g pos ∧ b pos)"))) (assume "ex infpath Ub") (by-assume-with "ex infpath Ub" "g" "infpath Ub") (inst-with-to "infpath Ub" 'right "∃k") (by-assume-with "∃k" "pos" "∈ g∩b") (drop "ex infpath Ub" "WKL Ub" "∃k") (ex-intro(pt"ℓ pos")) (booleImp "UCOMP b pos ∧ b pos") (ng #t) (simp(pf "(b pos→pos=U b(ℓpos))=(pos=U b(ℓpos))")) (use "Truth-Axiom") (simp-with "∈ g∩b" 'right) (use "Truth-Axiom") (simp-with "∈ g∩b" 'right) (use "BooleImp" (pt"g pos")) (search) (use-with "∈ g∩b" 'left) (use "wklinfpathUbinterb") (use "WKL Ub") (use "bar")) ; Proof finished. (save "wklbarbig") (display-theorems "wklbarbig") (display " wklubfan: ∀b. WKL(U_b) → FAN b ") (sg "all b. ( " (WKL "UCOMP b") " ) -> " (FAN "b")) (begin (assume "b" "WKL Ub" "bar") (use "bigtofan") (use "wklbarbig") (use "WKL Ub") (use "bar") (use "bar")) ; Proof finished. (save "wklubfan") (display-theorems "wklubfan") (display " wklfan: ∀f WKL(f) -> ∀b FAN b ") (sg "( all f. " (WKL "f") ") -> ( all b . " (FAN "b") ")") (begin (assume "WKL" "b" "bar") (use "wklubfan") (use "WKL") (use "bar")) ; Proof finished. (save "wklfan") (display-theorems "wklfan") (begin (set! COMMENT-FLAG #f) (animate "wklfan") (set! COMMENT-FLAG #t) (display "EXTRACTED TERM of ∀f WKL(f) -> ∀b FAN b (pnt \"cwklfan\")") (newline)(newline) (pnt "cwklfan") (newline)(newline) (display " Which folds out to:") (newline)(newline) (set! COMMENT-FLAG #f) (animate "wklubfan") (animate "wklbarbig") (animate "bigtofan") (animate "wklinfpathUbinterb") (animate "UCOMPinfinite") (animate "bigintersect") (set! COMMENT-FLAG #t) (pnt "cwklfan") (set! COMMENT-FLAG #f) (deanimate "wklfan") (deanimate "wklubfan") (deanimate "wklbarbig") (deanimate "bigtofan") (deanimate "wklinfpathUbinterb") (deanimate "UCOMPinfinite") (deanimate "bigintersect")) (display" End of wklfan.scm ")