# HG changeset patch # User Shinji KONO # Date 1671502852 -32400 # Node ID 63c1167b234376e0d042a79ac80e5e70d3985497 # Parent 2cf182f0f583b575d247ccd9545f88039b727cc9 fix comments diff -r 2cf182f0f583 -r 63c1167b2343 src/OD.agda --- a/src/OD.agda Mon Dec 19 09:50:51 2022 +0900 +++ b/src/OD.agda Tue Dec 20 11:20:52 2022 +0900 @@ -1,12 +1,12 @@ -{-# OPTIONS --allow-unsolved-metas #-} +{-# OPTIONS --allow-unsolved-metas #-} open import Level open import Ordinals module OD {n : Level } (O : Ordinals {n} ) where open import zf -open import Data.Nat renaming ( zero to Zero ; suc to Suc ; ℕ to Nat ; _⊔_ to _n⊔_ ) +open import Data.Nat renaming ( zero to Zero ; suc to Suc ; ℕ to Nat ; _⊔_ to _n⊔_ ) open import Relation.Binary.PropositionalEquality hiding ( [_] ) -open import Data.Nat.Properties +open import Data.Nat.Properties open import Data.Empty open import Relation.Nullary open import Relation.Binary hiding (_⇔_) @@ -17,8 +17,8 @@ open import nat open Ordinals.Ordinals O -open Ordinals.IsOrdinals isOrdinal -open Ordinals.IsNext isNext +open Ordinals.IsOrdinals isOrdinal +open Ordinals.IsNext isNext open OrdUtil O -- Ordinal Definable Set @@ -35,24 +35,24 @@ record _==_ ( a b : OD ) : Set n where field - eq→ : ∀ { x : Ordinal } → def a x → def b x - eq← : ∀ { x : Ordinal } → def b x → def a x + eq→ : ∀ { x : Ordinal } → def a x → def b x + eq← : ∀ { x : Ordinal } → def b x → def a x ==-refl : { x : OD } → x == x ==-refl {x} = record { eq→ = λ x → x ; eq← = λ x → x } -open _==_ +open _==_ ==-trans : { x y z : OD } → x == y → y == z → x == z ==-trans x=y y=z = record { eq→ = λ {m} t → eq→ y=z (eq→ x=y t) ; eq← = λ {m} t → eq← x=y (eq← y=z t) } -==-sym : { x y : OD } → x == y → y == x +==-sym : { x y : OD } → x == y → y == x ==-sym x=y = record { eq→ = λ {m} t → eq← x=y t ; eq← = λ {m} t → eq→ x=y t } -⇔→== : { x y : OD } → ( {z : Ordinal } → (def x z ⇔ def y z)) → x == y -eq→ ( ⇔→== {x} {y} eq ) {z} m = proj1 eq m -eq← ( ⇔→== {x} {y} eq ) {z} m = proj2 eq m +⇔→== : { x y : OD } → ( {z : Ordinal } → (def x z ⇔ def y z)) → x == y +eq→ ( ⇔→== {x} {y} eq ) {z} m = proj1 eq m +eq← ( ⇔→== {x} {y} eq ) {z} m = proj2 eq m -- next assumptions are our axiom -- @@ -62,7 +62,7 @@ -- If all ZF Set have supreme upper bound, the solutions of OD have to be bounded, i.e. -- bbounded ODs are ZF Set. Unbounded ODs are classes. -- --- In classical Set Theory, HOD is used, as a subset of OD, +-- In classical Set Theory, HOD is used, as a subset of OD, -- HOD = { x | TC x ⊆ OD } -- where TC x is a transitive clusure of x, i.e. Union of all elemnts of all subset of x. -- This is not possible because we don't have V yet. So we assumes HODs are bounded OD. @@ -89,18 +89,18 @@ open HOD -record ODAxiom : Set (suc n) where +record ODAxiom : Set (suc n) where field -- HOD is isomorphic to Ordinal (by means of Goedel number) - & : HOD → Ordinal - * : Ordinal → HOD + & : HOD → Ordinal + * : Ordinal → HOD c<→o< : {x y : HOD } → def (od y) ( & x ) → & x o< & y ⊆→o≤ : {y z : HOD } → ({x : Ordinal} → def (od y) x → def (od z) x ) → & y o< osuc (& z) *iso : {x : HOD } → * ( & x ) ≡ x &iso : {x : Ordinal } → & ( * x ) ≡ x ==→o≡ : {x y : HOD } → (od x == od y) → x ≡ y - sup-o : (A : HOD) → ( ( x : Ordinal ) → def (od A) x → Ordinal ) → Ordinal - sup-o≤ : (A : HOD) → { ψ : ( x : Ordinal ) → def (od A) x → Ordinal } → ∀ {x : Ordinal } → (lt : def (od A) x ) → ψ x lt o≤ sup-o A ψ + sup-o : (A : HOD) → ( ( x : Ordinal ) → def (od A) x → Ordinal ) → Ordinal + sup-o≤ : (A : HOD) → { ψ : ( x : Ordinal ) → def (od A) x → Ordinal } → ∀ {x : Ordinal } → (lt : def (od A) x ) → ψ x lt o≤ sup-o A ψ -- possible order restriction ho< : {x : HOD} → & x o< next (odmax x) @@ -112,7 +112,7 @@ -- -- since we have ==→o≡ , so odmax have to be unique. We should have odmaxmin in HOD. -- We can calculate the minimum using sup but it is tedius. --- Only Select has non minimum odmax. +-- Only Select has non minimum odmax. -- We have the same problem on 'def' itself, but we leave it. odmaxmin : Set (suc n) @@ -122,20 +122,14 @@ ¬OD-order : ( & : OD → Ordinal ) → ( * : Ordinal → OD ) → ( { x y : OD } → def y ( & x ) → & x o< & y) → ⊥ ¬OD-order & * c<→o< = o≤> <-osuc (c<→o< {Ords} OneObj ) --- Open supreme upper bound leads a contradition, so we use domain restriction on sup -¬open-sup : ( sup-o : (Ordinal → Ordinal ) → Ordinal) → ((ψ : Ordinal → Ordinal ) → (x : Ordinal) → ψ x o< sup-o ψ ) → ⊥ -¬open-sup sup-o sup-o< = o<> <-osuc (sup-o< next-ord (sup-o next-ord)) where - next-ord : Ordinal → Ordinal - next-ord x = osuc x - -- Ordinal in OD ( and ZFSet ) Transitive Set -Ord : ( a : Ordinal ) → HOD +Ord : ( a : Ordinal ) → HOD Ord a = record { od = record { def = λ y → y o< a } ; odmax = a ; ¬a ¬b c = no ¬b +odef< : {b : Ordinal } { A : HOD } → odef A b → b o< & A +odef< {b} {A} ab = subst (λ k → k o< & A) &iso ( c<→o< (subst (λ k → odef A k ) (sym &iso ) ab)) + +odef∧< : {A : HOD } {y : Ordinal} {n : Level } → {P : Set n} → odef A y ∧ P → y o< & A +odef∧< {A } {y} p = subst (λ k → k o< & A) &iso ( c<→o< (subst (λ k → odef A k ) (sym &iso ) (proj1 p ))) + -- the pair -_,_ : HOD → HOD → HOD +_,_ : HOD → HOD → HOD x , y = record { od = record { def = λ t → (t ≡ & x ) ∨ ( t ≡ & y ) } ; odmax = omax (& x) (& y) ; 0 = ? + +-- Open supreme upper bound leads a contradition, so we use domain restriction on sup +¬open-sup : ( sup-o : (Ordinal → Ordinal ) → Ordinal) → ((ψ : Ordinal → Ordinal ) → (x : Ordinal) → ψ x o< sup-o ψ ) → ⊥ +¬open-sup sup-o sup-o< = o<> <-osuc (sup-o< next-ord (sup-o next-ord)) where + next-ord : Ordinal → Ordinal + next-ord x = osuc x + +Select : (X : HOD ) → ((x : HOD ) → Set n ) → HOD Select X ψ = record { od = record { def = λ x → ( odef X x ∧ ψ ( * x )) } ; odmax = odmax X ; u ¬a ¬b c with (incl lt) (o<-subst c (sym &iso) refl ) @@ -430,14 +458,14 @@ , ( λ select → ⟪ proj1 select , ψiso {ψ} (proj2 select) *iso ⟫ ) ⟫ -selection-in-domain : {ψ : HOD → Set n} {X y : HOD} → Select X ψ ∋ y → X ∋ y +selection-in-domain : {ψ : HOD → Set n} {X y : HOD} → Select X ψ ∋ y → X ∋ y selection-in-domain {ψ} {X} {y} lt = proj1 ((proj2 (selection {ψ} {X} )) lt) sup-c≤ : (ψ : HOD → HOD) → {X x : HOD} → X ∋ x → & (ψ x) o≤ (sup-o X (λ y X∋y → & (ψ (* y)))) sup-c≤ ψ {X} {x} lt = subst (λ k → & (ψ k) o< _ ) *iso (sup-o≤ X lt ) replacement← : {ψ : HOD → HOD} (X x : HOD) → X ∋ x → Replace X ψ ∋ ψ x -replacement← {ψ} X x lt = ⟪ sup-c≤ ψ {X} {x} lt , lemma ⟫ where +replacement← {ψ} X x lt = ⟪ sup-c≤ ψ {X} {x} lt , lemma ⟫ where lemma : def (in-codomain X ψ) (& (ψ x)) lemma not = ⊥-elim ( not ( & x ) ⟪ lt , cong (λ k → & (ψ k)) (sym *iso)⟫ ) replacement→ : {ψ : HOD → HOD} (X x : HOD) → (lt : Replace X ψ ∋ x) → ¬ ( (y : HOD) → ¬ (x =h= ψ y)) @@ -445,7 +473,7 @@ lemma2 : ¬ ((y : Ordinal) → ¬ odef X y ∧ ((& x) ≡ & (ψ (* y)))) → ¬ ((y : Ordinal) → ¬ odef X y ∧ (* (& x) =h= ψ (* y))) lemma2 not not2 = not ( λ y d → not2 y ⟪ proj1 d , lemma3 (proj2 d)⟫) where - lemma3 : {y : Ordinal } → (& x ≡ & (ψ (* y))) → (* (& x) =h= ψ (* y)) + lemma3 : {y : Ordinal } → (& x ≡ & (ψ (* y))) → (* (& x) =h= ψ (* y)) lemma3 {y} eq = subst (λ k → * (& x) =h= k ) *iso (o≡→== eq ) lemma : ( (y : HOD) → ¬ (x =h= ψ y)) → ( (y : Ordinal) → ¬ odef X y ∧ (* (& x) =h= ψ (* y)) ) lemma not y not2 = not (* y) (subst (λ k → k =h= ψ (* y)) *iso ( proj2 not2 )) @@ -462,29 +490,29 @@ ∩-≡ {a} {b} inc = record { eq→ = λ {x} x ( - IsMinSUP.minsup (is-minsup b≤z) asupf (λ {z} uzb → IsMinSUP.x≤sup (is-minsup a≤z) (subst (λ k → odef k z) (sym ua=ub) uzb)) ) sa ¬a ¬b sb ( - IsMinSUP.minsup (is-minsup a≤z) asupf (λ {z} uza → IsMinSUP.x≤sup (is-minsup b≤z) (subst (λ k → odef k z) ua=ub uza)) ) sb ¬a ¬b b z48 b ( + IsMinSUP.minsup (is-minsup b≤z) asupf (λ {z} uzb → IsMinSUP.x≤sup (is-minsup a≤z) (subst (λ k → odef k z) (sym ua=ub) uzb)) ) sa ¬a ¬b sb ( + IsMinSUP.minsup (is-minsup a≤z) asupf (λ {z} uza → IsMinSUP.x≤sup (is-minsup b≤z) (subst (λ k → odef k z) ua=ub uza)) ) sb ¬a ¬b c = ⊥-elim ( o≤> ( begin - ZChain.supf (pzc (pic ¬a ¬b c = zc01 where -- supf1 z o≤ sps zc01 : supf1 z o≤ sps zc01 with trio< z x ... | tri< z ¬a ¬b c = o≤-refl -- (sf1=sps c) @@ -1422,7 +1392,6 @@ ⟪ az , ch-is-sup u u