# HG changeset patch # User Shinji KONO # Date 1559577933 -32400 # Node ID 96c932d0145d4f25ac3bac10581f5d009d959384 # Parent 461690d60d078ca4fbc829ff60c712185fc778c3 simpler ordinal diff -r 461690d60d07 -r 96c932d0145d ordinal-definable.agda --- a/ordinal-definable.agda Mon Jun 03 12:29:33 2019 +0900 +++ b/ordinal-definable.agda Tue Jun 04 01:05:33 2019 +0900 @@ -73,13 +73,9 @@ ∅1 {n} x (lift ()) ∅3 : {n : Level} → { x : Ordinal {n}} → ( ∀(y : Ordinal {n}) → ¬ (y o< x ) ) → x ≡ o∅ {n} -∅3 {n} {x} = TransFinite {n} c1 c2 c3 x where +∅3 {n} {x} = TransFinite {n} c2 c3 x where c0 : Nat → Ordinal {n} → Set n c0 lx x = (∀(y : Ordinal {n}) → ¬ (y o< x)) → x ≡ o∅ {n} - c1 : ∀ (lx : Nat ) → c0 lx (record { lv = Suc lx ; ord = ℵ lx } ) - c1 lx not with not ( record { lv = lx ; ord = Φ lx } ) - ... | t with t (case1 ≤-refl ) - c1 lx not | t | () c2 : (lx : Nat) → c0 lx (record { lv = lx ; ord = Φ lx } ) c2 Zero not = refl c2 (Suc lx) not with not ( record { lv = lx ; ord = Φ lx } ) @@ -92,9 +88,6 @@ c3 lx (OSuc .lx x₁) d not with not ( record { lv = lx ; ord = OSuc lx x₁ } ) ... | t with t (case2 (s< s : {n : Level } ( ox oy : Ordinal {n}) → ox o< oy → oy o< ox → ⊥ -o<> ox oy (case1 x→¬< x ox oy (case1 x ox oy (case2 x ox oy (case2 x x eq lt o<→¬c> : {n : Level} → { x y : OD {n} } → (od→ord x ) o< ( od→ord y) → ¬ (y c< x ) -o<→¬c> {n} {x} {y} olt clt = o<> (od→ord x) (od→ord y) olt (c<→o< clt ) where +o<→¬c> {n} {x} {y} olt clt = o<> olt (c<→o< clt ) where o≡→¬c< : {n : Level} → { x y : OD {n} } → (od→ord x ) ≡ ( od→ord y) → ¬ x c< y o≡→¬c< {n} {x} {y} oeq lt = o<¬≡ (od→ord x) (od→ord y) (orefl oeq ) (c<→o< lt) @@ -270,7 +246,7 @@ ; Power = Power ; Select = Select ; Replace = Replace - ; infinite = ord→od ( record { lv = Suc Zero ; ord = ℵ Zero } ) + ; infinite = ord→od ( record { lv = Suc Zero ; ord = Φ 1 } ) ; isZF = isZF } where Replace : OD {suc n} → (OD {suc n} → OD {suc n} ) → OD {suc n} @@ -296,7 +272,7 @@ infixr 200 _∈_ infixr 230 _∩_ _∪_ infixr 220 _⊆_ - isZF : IsZF (OD {suc n}) _∋_ _==_ od∅ _,_ Union Power Select Replace (ord→od ( record { lv = Suc Zero ; ord = ℵ Zero } )) + isZF : IsZF (OD {suc n}) _∋_ _==_ od∅ _,_ Union Power Select Replace (ord→od ( record { lv = Suc Zero ; ord = Φ 1} )) isZF = record { isEquivalence = record { refl = eq-refl ; sym = eq-sym; trans = eq-trans } ; pair = pair @@ -368,15 +344,23 @@ eq→ (extensionality {A} {B} eq ) {x} d = def-iso {suc n} {A} {B} (sym diso) (proj1 (eq (ord→od x))) d eq← (extensionality {A} {B} eq ) {x} d = def-iso {suc n} {B} {A} (sym diso) (proj2 (eq (ord→od x))) d next : (x : OD) → Union (x , (x , x)) == ord→od (osuc (od→ord x)) - eq→ (next x ) {y} z = {!!} + eq→ (next x ) {y} z = {!!} eq← (next x ) {y} z = {!!} + next' : (x : OD) → ord→od ( od→ord ( Union (x , (x , x)))) == ord→od (osuc (od→ord x)) + next' x = subst ( λ k → k == ord→od (osuc (od→ord x))) (sym oiso) (next x) infinite : OD {suc n} - infinite = ord→od ( record { lv = Suc Zero ; ord = ℵ Zero } ) - infinity∅ : ord→od ( record { lv = Suc Zero ; ord = ℵ Zero } ) ∋ od∅ {suc n} + infinite = ord→od ( record { lv = Suc Zero ; ord = Φ 1 } ) + infinity∅ : ord→od ( record { lv = Suc Zero ; ord = Φ 1 } ) ∋ od∅ {suc n} infinity∅ = def-subst {suc n} {_} {od→ord (ord→od o∅)} {infinite} {od→ord od∅} (o<→c< ( case1 (s≤s z≤n ))) refl (cong (λ k → od→ord k) o∅≡od∅ ) infinity : (x : OD) → infinite ∋ x → infinite ∋ Union (x , (x , x )) - infinity x ∞∋x = {!!} + infinity x ∞∋x = {!!} where + lemma : (ox : Ordinal {suc n} ) → ox o< record { lv = Suc Zero ; ord = Φ 1 } → osuc ox o< record { lv = Suc Zero ; ord = Φ 1 } + lemma record { lv = Zero ; ord = (Φ .0) } (case1 (s≤s x)) = case1 {!!} + lemma record { lv = Zero ; ord = (OSuc .0 ord₁) } (case1 (s≤s x)) = case1 {!!} + lemma record { lv = (Suc lv₁) ; ord = (Φ .(Suc lv₁)) } (case1 (s≤s ())) + lemma record { lv = (Suc lv₁) ; ord = (OSuc .(Suc lv₁) ord₁) } (case1 (s≤s ())) + lemma record { lv = 1 ; ord = (Φ 1) } (case2 ℵΦ<) = case2 {!!} replacement : {ψ : OD → OD} (X x : OD) → Replace X ψ ∋ ψ x replacement {ψ} X x = {!!} diff -r 461690d60d07 -r 96c932d0145d ordinal.agda --- a/ordinal.agda Mon Jun 03 12:29:33 2019 +0900 +++ b/ordinal.agda Tue Jun 04 01:05:33 2019 +0900 @@ -11,27 +11,18 @@ data OrdinalD {n : Level} : (lv : Nat) → Set n where Φ : (lv : Nat) → OrdinalD lv OSuc : (lv : Nat) → OrdinalD {n} lv → OrdinalD lv - ℵ_ : (lv : Nat) → OrdinalD (Suc lv) record Ordinal {n : Level} : Set n where field lv : Nat ord : OrdinalD {n} lv -data ¬ℵ {n : Level} {lx : Nat } : ( x : OrdinalD {n} lx ) → Set where - ¬ℵΦ : ¬ℵ (Φ lx) - ¬ℵs : {x : OrdinalD {n} lx } → ¬ℵ x → ¬ℵ (OSuc lx x) - -- -- Φ (Suc lv) < ℵ lv < OSuc (Suc lv) (ℵ lv) < OSuc ... < OSuc (Suc lv) (Φ (Suc lv)) < OSuc ... < ℵ (Suc lv) -- data _d<_ {n : Level} : {lx ly : Nat} → OrdinalD {n} lx → OrdinalD {n} ly → Set n where Φ< : {lx : Nat} → {x : OrdinalD {n} lx} → Φ lx d< OSuc lx x s< : {lx : Nat} → {x y : OrdinalD {n} lx} → x d< y → OSuc lx x d< OSuc lx y - ℵΦ< : {lx : Nat} → Φ (Suc lx) d< (ℵ lx) - ℵ< : {lx : Nat} → {x : OrdinalD {n} (Suc lx) } → ¬ℵ x → OSuc (Suc lx) x d< (ℵ lx) - ℵs< : {lx : Nat} → (ℵ lx) d< OSuc (Suc lx) (ℵ lx) - ℵss< : {lx : Nat} → {x : OrdinalD {n} (Suc lx) } → (ℵ lx) d< x → (ℵ lx) d< OSuc (Suc lx) x open Ordinal @@ -41,26 +32,14 @@ s : {n : Level} → {lx : Nat} {x : OrdinalD {n} lx } { y : OrdinalD lx } → y d< x → x d< y → ⊥ trio<> {n} {lx} {.(OSuc lx _)} {.(OSuc lx _)} (s< s) (s< t) = trio<> s t -trio<> {_} {.(Suc _)} {.(OSuc (Suc _) (ℵ _))} {.(ℵ _)} ℵs< (ℵ< {_} {.(ℵ _)} ()) -trio<> {_} {.(Suc _)} {.(ℵ _)} {.(OSuc (Suc _) (ℵ _))} (ℵ< ()) ℵs< trio<> {n} {lx} {.(OSuc lx _)} {.(Φ lx)} Φ< () -trio<> {n} {.(Suc _)} {.(ℵ _)} {.(Φ (Suc _))} ℵΦ< () -trio<> {n} {.(Suc _)} {.(ℵ _)} {.(OSuc (Suc _) (Φ (Suc _)))} (ℵ< ¬ℵΦ) (ℵss< ()) -trio<> {n} {.(Suc _)} {.(ℵ _)} {.(OSuc (Suc _) (OSuc (Suc _) _))} (ℵ< (¬ℵs x)) (ℵss< x (ℵ< x) x {n} {.(Suc _)} {.(OSuc (Suc _) (Φ (Suc _)))} {.(ℵ _)} (ℵss< ()) (ℵ< ¬ℵΦ) -trio<> {n} {.(Suc _)} {.(OSuc (Suc _) (OSuc (Suc _) _))} {.(ℵ _)} (ℵss< y y ly ) triO {n} {lx} {ly} x y = <-cmp lx ly -fin : {n : Level} → {lx : Nat} → {y : OrdinalD {n} (Suc lx) } → y d< (ℵ lx) → ¬ℵ y -fin {_} {_} {Φ (Suc _)} ℵΦ< = ¬ℵΦ -fin {_} {_} {OSuc (Suc _) _} (ℵ< x) = ¬ℵs x - triOrdd : {n : Level} → {lx : Nat} → Trichotomous _≡_ ( _d<_ {n} {lx} {lx} ) triOrdd {_} {lv} (Φ lv) (Φ lv) = tri≈ ≡→¬d< refl ≡→¬d< -triOrdd {_} {Suc lv} (ℵ lv) (ℵ lv) = tri≈ ≡→¬d< refl ≡→¬d< triOrdd {_} {lv} (Φ lv) (OSuc lv y) = tri< Φ< (λ ()) ( λ lt → trio<> lt Φ< ) -triOrdd {_} {.(Suc lv)} (Φ (Suc lv)) (ℵ lv) = tri< ℵΦ< (λ ()) ( λ lt → trio<> lt ℵΦ<) -triOrdd {_} {Suc lv} (ℵ lv) (Φ (Suc lv)) = tri> ( λ lt → trio<> lt ℵΦ< ) (λ ()) ℵΦ< -triOrdd {_} {Suc lv} (ℵ lv) (OSuc (Suc lv) y ) with triOrdd (ℵ lv) y -triOrdd {_} {Suc lv} (ℵ lv) (OSuc .(Suc lv) y) | tri< a ¬b ¬c = tri< (ℵss< a) (λ ()) (trio<> (ℵss< a) ) -triOrdd {_} {Suc lv} (ℵ lv) (OSuc .(Suc lv) y) | tri≈ ¬a refl ¬c = tri< ℵs< (λ ()) ( λ lt → trio<> lt ℵs< ) -triOrdd {_} {Suc lv} (ℵ lv) (OSuc .(Suc lv) y) | tri> ¬a ¬b c = tri> ( λ lt → trio<> lt ( ℵ< (fin c)) ) (λ ()) ( ℵ< (fin c) ) triOrdd {_} {lv} (OSuc lv x) (Φ lv) = tri> (λ lt → trio<> lt Φ<) (λ ()) Φ< -triOrdd {_} {.(Suc lv)} (OSuc (Suc lv) x) (ℵ lv) with triOrdd x (ℵ lv) -triOrdd {_} {.(Suc lv)} (OSuc (Suc lv) x) (ℵ lv) | tri< a ¬b ¬c = tri< (ℵ< (fin a ) ) (λ ()) ( λ lt → trio<> lt (ℵ< (fin a ))) -triOrdd {_} {.(Suc lv)} (OSuc (Suc lv) x) (ℵ lv) | tri≈ ¬a refl ¬c = tri> (λ lt → trio<> lt ℵs< ) (λ ()) ℵs< -triOrdd {_} {.(Suc lv)} (OSuc (Suc lv) x) (ℵ lv) | tri> ¬a ¬b c = tri> (λ lt → trio<> lt (ℵss< c )) (λ ()) ( ℵss< c ) triOrdd {_} {lv} (OSuc lv x) (OSuc lv y) with triOrdd x y triOrdd {_} {lv} (OSuc lv x) (OSuc lv y) | tri< a ¬b ¬c = tri< (s< a) (λ tx=ty → trio<≡ tx=ty (s< a) ) ( λ lt → trio<> lt (s< a) ) triOrdd {_} {lv} (OSuc lv x) (OSuc lv x) | tri≈ ¬a refl ¬c = tri≈ ≡→¬d< refl ≡→¬d< @@ -129,7 +93,6 @@ <-osuc : {n : Level} { x : Ordinal {n} } → x o< osuc x <-osuc {n} {record { lv = lx ; ord = Φ .lx }} = case2 Φ< <-osuc {n} {record { lv = lx ; ord = OSuc .lx ox }} = case2 ( s< s : {n : Level} → {x y : Ordinal {n} } → y o< x → x o< y → ⊥ +o<> {n} {x} {y} (case1 x₁) (case1 x₂) = nat-<> x₁ x₂ +o<> {n} {x} {y} (case1 x₁) (case2 x₂) = nat-≡< (sym (d<→lv x₂)) x₁ +o<> {n} {x} {y} (case2 x₁) (case1 x₂) = nat-≡< (sym (d<→lv x₁)) x₂ +o<> {n} {record { lv = lv₁ ; ord = .(OSuc lv₁ _) }} {record { lv = .lv₁ ; ord = .(Φ lv₁) }} (case2 Φ<) (case2 ()) +o<> {n} {record { lv = lv₁ ; ord = .(OSuc lv₁ _) }} {record { lv = .lv₁ ; ord = .(OSuc lv₁ _) }} (case2 (s< y (case2 y x₁ x₂ -osuc-< {n} {x} {y} y y x₂ x₁ +osuc-< {n} {x} {y} y (case2 x ¬a ¬b c = tri> lemma1 (λ refl → ¬b (cong ( λ x → lv x ) refl ) ) (case1 c) where lemma1 : ¬ (Suc (lv a) ≤ lv b) ∨ (ord a d< ord b) lemma1 (case1 x) = ¬a x - lemma1 (case2 x) with d<→lv x - lemma1 (case2 x) | refl = ¬b refl + lemma1 (case2 x) = ⊥-elim (nat-≡< (sym ( d<→lv x )) c ) trio< a b | tri≈ ¬a refl ¬c with triOrdd ( ord a ) ( ord b ) trio< record { lv = .(lv b) ; ord = x } b | tri≈ ¬a refl ¬c | tri< a ¬b ¬c₁ = tri< (case2 a) (λ refl → ¬b (lemma1 refl )) lemma2 where lemma1 : (record { lv = _ ; ord = x }) ≡ b → x ≡ ord b @@ -273,13 +203,7 @@ OrdTrans (case1 refl) (case1 refl) = case1 refl OrdTrans (case1 refl) (case2 lt2) = case2 lt2 OrdTrans (case2 lt1) (case1 refl) = case2 lt1 -OrdTrans (case2 (case1 x)) (case2 (case1 y)) = case2 (case1 ( <-trans x y ) ) -OrdTrans (case2 (case1 x)) (case2 (case2 y)) with d<→lv y -OrdTrans (case2 (case1 x)) (case2 (case2 y)) | refl = case2 (case1 x ) -OrdTrans (case2 (case2 x)) (case2 (case1 y)) with d<→lv x -OrdTrans (case2 (case2 x)) (case2 (case1 y)) | refl = case2 (case1 y) -OrdTrans (case2 (case2 x)) (case2 (case2 y)) with d<→lv x | d<→lv y -OrdTrans (case2 (case2 x)) (case2 (case2 y)) | refl | refl = case2 (case2 (orddtrans x y )) +OrdTrans (case2 x) (case2 y) = case2 (ordtrans x y) OrdPreorder : {n : Level} → Preorder (suc n) (suc n) (suc n) OrdPreorder {n} = record { Carrier = Ordinal @@ -293,12 +217,9 @@ } TransFinite : {n : Level} → { ψ : Ordinal {n} → Set n } - → ( ∀ (lx : Nat ) → ψ ( record { lv = Suc lx ; ord = ℵ lx } )) → ( ∀ (lx : Nat ) → ψ ( record { lv = lx ; ord = Φ lx } ) ) → ( ∀ (lx : Nat ) → (x : OrdinalD lx ) → ψ ( record { lv = lx ; ord = x } ) → ψ ( record { lv = lx ; ord = OSuc lx x } ) ) → ∀ (x : Ordinal) → ψ x -TransFinite caseℵ caseΦ caseOSuc record { lv = lv ; ord = Φ lv } = caseΦ lv -TransFinite caseℵ caseΦ caseOSuc record { lv = lv ; ord = OSuc lv ord₁ } = caseOSuc lv ord₁ - ( TransFinite caseℵ caseΦ caseOSuc (record { lv = lv ; ord = ord₁ } )) -TransFinite caseℵ caseΦ caseOSuc record { lv = Suc lv₁ ; ord = ℵ lv₁ } = caseℵ lv₁ - +TransFinite caseΦ caseOSuc record { lv = lv ; ord = (Φ (lv)) } = caseΦ lv +TransFinite caseΦ caseOSuc record { lv = lx ; ord = (OSuc lx ox) } = + caseOSuc lx ox (TransFinite caseΦ caseOSuc record { lv = lx ; ord = ox })