# HG changeset patch # User Shinji KONO # Date 1718874917 -32400 # Node ID ca5bfb401ada68ce82564033abea8ff041395663 # Parent e8c166541c862c17e42395157f36f1b6953ac3b1 ... diff -r e8c166541c86 -r ca5bfb401ada src/LEMC.agda --- a/src/LEMC.agda Tue Jun 18 18:46:53 2024 +0900 +++ b/src/LEMC.agda Thu Jun 20 18:15:17 2024 +0900 @@ -52,11 +52,6 @@ ... | yes p = p ... | no ¬p = ⊥-elim ( notnot ¬p ) -power→⊆ : ( A t : HOD) → Power A ∋ t → t ⊆ A -power→⊆ A t PA∋t t∋x = subst (λ k → odef A k ) &iso ( t1 (subst (λ k → odef t k ) (sym &iso) t∋x)) where - t1 : {x : HOD } → t ∋ x → A ∋ x - t1 = power→ A t PA∋t - --- With assuption of HOD is ordered, p ∨ ( ¬ p ) <=> axiom of choice --- record choiced ( X : Ordinal ) : Set n where diff -r e8c166541c86 -r ca5bfb401ada src/NSet.agda --- a/src/NSet.agda Tue Jun 18 18:46:53 2024 +0900 +++ b/src/NSet.agda Thu Jun 20 18:15:17 2024 +0900 @@ -1,3 +1,5 @@ +{-# OPTIONS --cubical-compatible --safe #-} + open import Level module NSet (n : Level) where diff -r e8c166541c86 -r ca5bfb401ada src/OD.agda --- a/src/OD.agda Tue Jun 18 18:46:53 2024 +0900 +++ b/src/OD.agda Thu Jun 20 18:15:17 2024 +0900 @@ -119,7 +119,7 @@ eq← = λ {z} d → eq→ *iso ( eq← eq (eq← *iso d) ) } -- =-iso : {x y : HOD } → (od x == od y) ≡ (od (* (& x)) == od y) --- =-iso {_} {y} = cong ( λ k → od k == od y ) ? -- (sym *iso) +-- =-iso {_} {y} = cong ( λ k → od k == od y ) ? -- (==-sym *iso) ord→== : { x y : HOD } → & x ≡ & y → od x == od y ord→== {x} {y} eq = ==-iso (lemma (& x) (& y) (orefl eq)) where @@ -135,6 +135,9 @@ *≡*→≡ : { x y : Ordinal } → * x ≡ * y → x ≡ y *≡*→≡ eq = subst₂ (λ j k → j ≡ k ) &iso &iso ( cong (&) eq ) +&≡&*& : {x : HOD} → & x ≡ & (* (& x)) +&≡&*& = (==→o≡ (==-sym *iso) ) + --- &≡&→≡ : { x y : HOD } → & x ≡ & y → x ≡ y -- &≡&→≡ eq = ? -- subst₂ (λ j k → j ≡ k ) *iso *iso ( cong (*) eq ) @@ -302,9 +305,6 @@ ψiso : {ψ : HOD → Set n} {x y : HOD } → ψ x → x ≡ y → ψ y ψiso {ψ} t refl = t -*iso== : {y : HOD} → od y == od (* (& y)) -*iso== {y} = record { eq→ = λ {x} yx → eq← *iso yx ; eq← = λ {x} yx → eq→ *iso yx } - record RCod (COD : HOD) (ψ : HOD → HOD) : Set (suc n) where field ≤COD : ∀ {x : HOD } → ψ x ⊆ COD @@ -325,7 +325,7 @@ r01 = sym (Replaced.x=ψz lt ) replacement← : {ψ : HOD → HOD} (X x : HOD) → X ∋ x → {C : HOD} → (rc : RCod C ψ) → Replace X ψ rc ∋ ψ x -replacement← {ψ} X x lt {C} rc = record { z = & x ; az = lt ; x=ψz = ==→o≡ (RCod.ψ-eq rc *iso== ) } +replacement← {ψ} X x lt {C} rc = record { z = & x ; az = lt ; x=ψz = ==→o≡ (RCod.ψ-eq rc (==-sym *iso) ) } replacement→ : {ψ : HOD → HOD} (X x : HOD) → {C : HOD} → (rc : RCod C ψ ) → (lt : Replace X ψ rc ∋ x) → ¬ ( (y : HOD) → ¬ (x =h= ψ y)) replacement→ {ψ} X x {C} rc lt eq = eq (* (Replaced.z lt)) (ord→== (Replaced.x=ψz lt)) @@ -488,22 +488,22 @@ lemma4 : owner ≡ & (x , x) lemma4 = trans ao ( ==→o≡ record { eq→ = lemma5 _ ; eq← = lemma6 _ } ) where lemma5 : (x₁ : Ordinal) → (x₁ ≡ & (* (& x))) ∨ (x₁ ≡ & (* (& x))) → (x₁ ≡ & x) ∨ (x₁ ≡ & x) - lemma5 y (case1 eq) = case1 (trans eq (sym (==→o≡ *iso== ) )) - lemma5 y (case2 eq) = case1 (trans eq (sym (==→o≡ *iso== ) )) + lemma5 y (case1 eq) = case1 (trans eq (sym (==→o≡ (==-sym *iso) ) )) + lemma5 y (case2 eq) = case1 (trans eq (sym (==→o≡ (==-sym *iso) ) )) lemma6 : (x₁ : Ordinal) → (x₁ ≡ & x) ∨ (x₁ ≡ & x) → (x₁ ≡ & (* (& x))) ∨ (x₁ ≡ & (* (& x))) - lemma6 y (case1 eq) = case1 (trans eq ((==→o≡ *iso== ) )) - lemma6 y (case2 eq) = case1 (trans eq ((==→o≡ *iso== ) )) + lemma6 y (case1 eq) = case1 (trans eq ((==→o≡ (==-sym *iso) ) )) + lemma6 y (case2 eq) = case1 (trans eq ((==→o≡ (==-sym *iso) ) )) lemma3 : {y : Ordinal} → Own (x , (x , x)) y → Own (* (& x) , (* (& x) , * (& x))) y lemma3 {y} record { owner = owner ; ao = (case1 ao) ; ox = ox } = record { owner = owner - ; ao = case1 (trans ao (==→o≡ *iso== )) ; ox = ox } + ; ao = case1 (trans ao (==→o≡ (==-sym *iso) )) ; ox = ox } lemma3 {y} record { owner = owner ; ao = (case2 ao) ; ox = ox } = record { owner = owner ; ao = case2 (trans ao (==→o≡ record { eq→ = lemma5 _ ; eq← = lemma4 _ })) ; ox = ox } where lemma4 : (x₁ : Ordinal) → (x₁ ≡ & (* (& x))) ∨ (x₁ ≡ & (* (& x))) → (x₁ ≡ & x) ∨ (x₁ ≡ & x) - lemma4 y (case1 eq) = case1 ( trans eq (sym (==→o≡ *iso== ) )) - lemma4 y (case2 eq) = case1 ( trans eq (sym (==→o≡ *iso== ) )) + lemma4 y (case1 eq) = case1 ( trans eq (sym (==→o≡ (==-sym *iso) ) )) + lemma4 y (case2 eq) = case1 ( trans eq (sym (==→o≡ (==-sym *iso) ) )) lemma5 : (x₁ : Ordinal) → (x₁ ≡ & x) ∨ (x₁ ≡ & x) → (x₁ ≡ & (* (& x))) ∨ (x₁ ≡ & (* (& x))) - lemma5 y (case1 eq) = case1 ( trans eq ((==→o≡ *iso== ) )) - lemma5 y (case2 eq) = case1 ( trans eq ((==→o≡ *iso== ) )) + lemma5 y (case1 eq) = case1 ( trans eq ((==→o≡ (==-sym *iso) ) )) + lemma5 y (case2 eq) = case1 ( trans eq ((==→o≡ (==-sym *iso) ) )) infinity : (ho< : ODAxiom-ho<) → (x : HOD) → Omega ho< ∋ x → Omega ho< ∋ Union (x , (x , x )) infinity ho< x lt = subst (λ k → odef (Omega ho<) k ) (==→o≡ Omega-iso) (isuc {& x} lt) @@ -519,11 +519,11 @@ pair-iso : {x y : HOD } → (* (& x) , * (& y)) =h= (x , y) pair-iso {x} {y} = record { eq→ = lem01 ; eq← = lem00 } where lem00 : {z : Ordinal} → (z ≡ & x) ∨ (z ≡ & y) → (z ≡ & (* (& x))) ∨ (z ≡ & (* (& y))) - lem00 {z} (case1 z=x) = case1 (trans z=x ((==→o≡ *iso== ) )) - lem00 {z} (case2 z=y) = case2 (trans z=y ((==→o≡ *iso== ) )) + lem00 {z} (case1 z=x) = case1 (trans z=x ((==→o≡ (==-sym *iso) ) )) + lem00 {z} (case2 z=y) = case2 (trans z=y ((==→o≡ (==-sym *iso) ) )) lem01 : {z : Ordinal} → (z ≡ & (* (& x))) ∨ (z ≡ & (* (& y))) → (z ≡ & x) ∨ (z ≡ & y) - lem01 {z} (case1 z=x) = case1 (trans z=x (sym (==→o≡ *iso== ) )) - lem01 {z} (case2 z=y) = case2 (trans z=y (sym (==→o≡ *iso== ) )) + lem01 {z} (case1 z=x) = case1 (trans z=x (sym (==→o≡ (==-sym *iso) ) )) + lem01 {z} (case2 z=y) = case2 (trans z=y (sym (==→o≡ (==-sym *iso) ) )) o<→c< : {x y : Ordinal } → x o< y → (Ord x) ⊆ (Ord y) o<→c< lt {z} ox = ordtrans ox lt @@ -542,8 +542,8 @@ selection : {ψ : HOD → Set n} → { zψ : ZPred HOD _∋_ _=h=_ ψ } → { X y : HOD} → ((X ∋ y) ∧ ψ y) ⇔ (Select X ψ zψ ∋ y) selection {ψ} {zψ} {X} {y} = ⟪ - ( λ cond → ⟪ proj1 cond , peq (proj2 cond) *iso== ⟫ ) - , ( λ select → ⟪ proj1 select , peq (proj2 select) (==-sym *iso== ) ⟫ ) + ( λ cond → ⟪ proj1 cond , peq (proj2 cond) (==-sym *iso) ⟫ ) + , ( λ select → ⟪ proj1 select , peq (proj2 select) *iso ⟫ ) ⟫ where peq : {x y : HOD } → ψ x → od x == od y → ψ y peq {x} {y} fx eq = proj1 (ZPred.ψ-cong zψ x y eq) fx @@ -580,7 +580,7 @@ r01 = sym (Replaced.x=ψz lt ) zf-replacement← : {ψ : HOD → HOD} → {zfψ : ZFunc HOD _∋_ _=h=_ ψ } → (X x : HOD) → X ∋ x → ZFReplace X ψ zfψ ∋ ψ x -zf-replacement← {ψ} {zfψ} X x lt = record { z = & x ; az = lt ; x=ψz = ==→o≡ (ZFunc.ψ-cong zfψ _ _ *iso== ) } +zf-replacement← {ψ} {zfψ} X x lt = record { z = & x ; az = lt ; x=ψz = ==→o≡ (ZFunc.ψ-cong zfψ _ _ (==-sym *iso) ) } zf-replacement→ : {ψ : HOD → HOD} → {zfψ : ZFunc HOD _∋_ _=h=_ ψ } → (X x : HOD) → (lt : ZFReplace X ψ zfψ ∋ x) → ¬ ( (y : HOD) → ¬ (x =h= ψ y)) zf-replacement→ {ψ} {zfψ} X x lt eq = eq (* (Replaced.z lt)) (ord→== (Replaced.x=ψz lt)) diff -r e8c166541c86 -r ca5bfb401ada src/ODC.agda --- a/src/ODC.agda Tue Jun 18 18:46:53 2024 +0900 +++ b/src/ODC.agda Thu Jun 20 18:15:17 2024 +0900 @@ -63,7 +63,7 @@ lemma eq p0 = ¬x<0 {& ps} (eq→ eq record { proj1 = eqo∅ eq ; proj2 = p0 } ) ¬p : (& ps ≡ o∅) → p → ⊥ ¬p eq = lemma ( begin - pred-od p ≈⟨ *iso== ⟩ + pred-od p ≈⟨ ==-sym *iso ⟩ * ( & ps ) ≡⟨ cong (*) eq ⟩ * ( o∅ ) ≈⟨ o∅==od∅ ⟩ od∅ ∎ ) where open EqR ==-Setoid @@ -101,14 +101,6 @@ ... | case1 a = case1 a ... | case2 ¬a = case2 ( ab ¬a) -power→⊆ : ( A t : HOD) → Power A ∋ t → t ⊆ A -power→⊆ A t PA∋t tx = subst (λ k → odef A k ) &iso ( power→ A t PA∋t (subst (λ k → odef t k) (sym &iso) tx ) ) - -power-∩ : { A x y : HOD } → Power A ∋ x → Power A ∋ y → Power A ∋ ( x ∩ y ) -power-∩ {A} {x} {y} ax ay = power← A (x ∩ y) p01 where - p01 : {z : HOD} → (x ∩ y) ∋ z → A ∋ z - p01 {z} xyz = power→ A x ax (proj1 xyz ) - OrdP : ( x : Ordinal ) ( y : HOD ) → Dec ( Ord x ∋ y ) OrdP x y with trio< x (& y) OrdP x y | tri< a ¬b ¬c = no ¬c diff -r e8c166541c86 -r ca5bfb401ada src/ODUtil.agda --- a/src/ODUtil.agda Tue Jun 18 18:46:53 2024 +0900 +++ b/src/ODUtil.agda Thu Jun 20 18:15:17 2024 +0900 @@ -50,6 +50,17 @@ ⊆∩-incl-2 : {a b c : HOD} → a ⊆ c → ( b ∩ a ) ⊆ c ⊆∩-incl-2 {a} {b} {c} a x ¬a ¬b c = ⊥-elim ( ¬x<0 c ) - --- next< : {x y z : Ordinal} → x o< next z → y o< next x → y o< next z --- next< {x} {y} {z} x ¬a ¬b c = ⊥-elim (¬nx osuc x o< next x o< next (osuc x) -> next x ≡ osuc z -> z o o< next x -> osuc z o< next x -> next x o< next x --- nexto≡ {x} | tri< a ¬b ¬c = ⊥-elim (¬nx osuc x o< next (osuc x) o< next x -> next (osuc x) ≡ osuc z -> z o o< next (osuc x) ... --- nexto≡ {x} | tri> ¬a ¬b c = ⊥-elim (¬nx ¬a ¬b c = -- x < y < next y < next x --- ⊥-elim ( ¬nx ¬a ¬b c with osuc-≡< x≤y --- ≤next {x} {y} x≤y | tri> ¬a ¬b c | case1 refl = o≤-refl -- x = y < next x --- ≤next {x} {y} x≤y | tri> ¬a ¬b c | case2 x ¬a ¬b c = o≤-refl0 (sym ( x ¬a ¬b c = subst (λ k → osuc x o< k ) nexto≡ (osuc ¬a ¬b c = osuc ¬a ¬b c = subst (λ k → x o< k ) nexto≡ xnx - record OrdinalSubset (maxordinal : Ordinal) : Set (suc n) where field os→ : (x : Ordinal) → x o< maxordinal → Ordinal diff -r e8c166541c86 -r ca5bfb401ada src/filter.agda --- a/src/filter.agda Tue Jun 18 18:46:53 2024 +0900 +++ b/src/filter.agda Thu Jun 20 18:15:17 2024 +0900 @@ -1,41 +1,50 @@ -{-# OPTIONS --allow-unsolved-metas #-} +{-# OPTIONS --cubical-compatible --safe #-} +open import Level +open import Ordinals +open import logic +open import Relation.Nullary open import Level open import Ordinals -module filter {n : Level } (O : Ordinals {n}) where +import HODBase +import OD +open import Relation.Nullary +module filter {n : Level } (O : Ordinals {n} ) (HODAxiom : HODBase.ODAxiom O) (ho< : OD.ODAxiom-ho< O HODAxiom ) + (AC : OD.AxiomOfChoice O HODAxiom ) where + + +open import Relation.Binary.PropositionalEquality hiding ( [_] ) +open import Data.Empty + +import OrdUtil + +open Ordinals.Ordinals O +open Ordinals.IsOrdinals isOrdinal +import ODUtil open import logic -import OD - -open import Relation.Nullary -open import Data.Empty -open import Relation.Binary.Core -open import Relation.Binary.PropositionalEquality -import BAlgebra - -open BAlgebra O +open import nat -open inOrdinal O -open OD O -open OD.OD -open ODAxiom odAxiom - -import OrdUtil -import ODUtil -open Ordinals.Ordinals O -open Ordinals.IsOrdinals isOrdinal --- open Ordinals.IsNext isNext open OrdUtil O -open ODUtil O - - -import ODC -open ODC O +open ODUtil O HODAxiom ho< open _∧_ open _∨_ open Bool +open HODBase._==_ + +open HODBase.ODAxiom HODAxiom +open OD O HODAxiom + +open HODBase.HOD + +open AxiomOfChoice AC +open import ODC O HODAxiom AC as ODC + +-- import BAlgebra +-- open BAlgebra O +-- -- L is a boolean algebra, but we don't assume this explicitly -- -- NEG : {p : HOD} → L ∋ p → L ∋ (P \ p) @@ -76,21 +85,20 @@ q∩q⊆q : {p q : HOD } → (q ∩ p) ⊆ q q∩q⊆q lt = proj1 lt -∩→≡1 : {p q : HOD } → p ⊆ q → (q ∩ p) ≡ p -∩→≡1 {p} {q} p⊆q = ==→o≡ record { eq→ = c00 ; eq← = c01 } where +∩→≡1 : {p q : HOD } → p ⊆ q → (q ∩ p) =h= p +∩→≡1 {p} {q} p⊆q = record { eq→ = c00 ; eq← = c01 } where c00 : {x : Ordinal} → odef (q ∩ p) x → odef p x c00 {x} qpx = proj2 qpx c01 : {x : Ordinal} → odef p x → odef (q ∩ p) x c01 {x} px = ⟪ p⊆q px , px ⟫ -∩→≡2 : {p q : HOD } → q ⊆ p → (q ∩ p) ≡ q -∩→≡2 {p} {q} q⊆p = ==→o≡ record { eq→ = c00 ; eq← = c01 } where +∩→≡2 : {p q : HOD } → q ⊆ p → (q ∩ p) =h= q +∩→≡2 {p} {q} q⊆p = record { eq→ = c00 ; eq← = c01 } where c00 : {x : Ordinal} → odef (q ∩ p) x → odef q x c00 {x} qpx = proj1 qpx c01 : {x : Ordinal} → odef q x → odef (q ∩ p) x c01 {x} qx = ⟪ qx , q⊆p qx ⟫ -open HOD ----- -- @@ -118,11 +126,11 @@ lemma4 x lt | case1 px = ⊥-elim ( proj2 (proj2 lt) px ) lemma4 x lt | case2 qx = qx lemma9 : L ∋ ((p ∪ q ) ∩ (P \ p)) - lemma9 = subst (λ k → L ∋ k ) (sym (==→o≡ lemma5)) (CAP Lq (NEG Lp)) + lemma9 = subst (λ k → odef L k ) (sym (==→o≡ lemma5)) (CAP Lq (NEG Lp)) lemma6 : filter F ∋ ((p ∪ q ) ∩ (P \ p)) lemma6 = filter2 F lt ¬p∈P lemma9 lemma7 : filter F ∋ (q ∩ (P \ p)) - lemma7 = subst (λ k → filter F ∋ k ) (==→o≡ lemma5 ) lemma6 + lemma7 = subst (λ k → odef (filter F) k ) (==→o≡ lemma5 ) lemma6 lemma8 : (q ∩ (P \ p)) ⊆ q lemma8 lt = proj1 lt @@ -131,6 +139,13 @@ -- if Filter {L} {P} contains L, prime filter is ultra -- +U-F=∅→F⊆U : {L F U : HOD} → U ⊆ L → ((x : Ordinal) → ¬ ( odef F x ∧ ( ¬ odef U x ))) → F ⊆ U +U-F=∅→F⊆U {L} {F} {U} U⊆L not = gt02 where + gt02 : { x : Ordinal } → odef F x → odef U x + gt02 {x} fx with ODC.∋-p U (* x) + ... | yes y = subst (λ k → odef U k ) &iso y + ... | no n = ⊥-elim ( not x ⟪ fx , subst (λ k → ¬ odef U k ) &iso n ⟫ ) + filter-lemma2 : {P L : HOD} → (LP : L ⊆ Power P) → ({p : HOD} → L ∋ p → L ∋ ( P \ p)) → (F : Filter {L} {P} LP) → filter F ∋ P → prime-filter F → ultra-filter F @@ -138,17 +153,16 @@ proper = prime-filter.proper prime ; ultra = λ {p} L∋p _ → prime-filter.prime prime L∋p (NEG L∋p) (lemma p (p⊆L L∋p )) } where - open _==_ p⊆L : {p : HOD} → L ∋ p → p ⊆ P p⊆L {p} lt = power→⊆ P p ( LP lt ) p+1-p=1 : {p : HOD} → p ⊆ P → P =h= (p ∪ (P \ p)) - eq→ (p+1-p=1 {p} p⊆P) {x} lt with ODC.decp O (odef p x) + eq→ (p+1-p=1 {p} p⊆P) {x} lt with ODC.decp (odef p x) eq→ (p+1-p=1 {p} p⊆P) {x} lt | yes p∋x = case1 p∋x eq→ (p+1-p=1 {p} p⊆P) {x} lt | no ¬p = case2 ⟪ lt , ¬p ⟫ eq← (p+1-p=1 {p} p⊆P) {x} ( case1 p∋x ) = subst (λ k → odef P k ) &iso (p⊆P ( subst (λ k → odef p k) (sym &iso) p∋x )) eq← (p+1-p=1 {p} p⊆P) {x} ( case2 ¬p ) = proj1 ¬p lemma : (p : HOD) → p ⊆ P → filter F ∋ (p ∪ (P \ p)) - lemma p p⊆P = subst (λ k → filter F ∋ k ) (==→o≡ (p+1-p=1 {p} p⊆P)) f∋P + lemma p p⊆P = subst (λ k → odef (filter F ) k ) (==→o≡ (p+1-p=1 {p} p⊆P)) f∋P record Ideal {L P : HOD } (LP : L ⊆ Power P) : Set (suc n) where field @@ -188,18 +202,18 @@ max→ultra {L} {P} LP CAP F0 {y} mfy mx = record { proper = MaximumFilter.proper mx ; ultra = ultra } where mf = MaximumFilter.mf mx ultra : {p : HOD} → L ∋ p → L ∋ (P \ p) → (filter mf ∋ p) ∨ (filter mf ∋ (P \ p)) - ultra {p} Lp Lnp with ODC.∋-p O (filter mf) p + ultra {p} Lp Lnp with ODC.∋-p (filter mf) p ... | yes y = case1 y - ... | no np = case2 (subst (λ k → k ∋ (P \ p)) F=mf F∋P-p) where + ... | no np = case2 (eq→ F=mf F∋P-p ) where F : HOD F = record { od = record { def = λ x → odef L x ∧ Fp {L} {P} LP F0 mx (& p) x } ; odmax = & L ;