Mercurial > hg > Members > kono > Proof > ZF-in-agda
diff ordinal-definable.agda @ 103:c8b79d303867
starting over HOD
author | Shinji KONO <kono@ie.u-ryukyu.ac.jp> |
---|---|
date | Wed, 12 Jun 2019 10:45:00 +0900 |
parents | a402881cc341 |
children | d92411bed18c dab56d357fa3 |
line wrap: on
line diff
--- a/ordinal-definable.agda Mon Jun 10 09:50:52 2019 +0900 +++ b/ordinal-definable.agda Wed Jun 12 10:45:00 2019 +0900 @@ -45,28 +45,27 @@ od∅ : {n : Level} → OD {n} od∅ {n} = record { def = λ _ → Lift n ⊥ } - postulate -- OD can be iso to a subset of Ordinal ( by means of Godel Set ) od→ord : {n : Level} → OD {n} → Ordinal {n} ord→od : {n : Level} → Ordinal {n} → OD {n} - c<→o< : {n : Level} {x y : OD {n} } → def y ( od→ord x ) → od→ord x o< od→ord y - o<→c< : {n : Level} {x y : Ordinal {n} } → x o< y → def (ord→od y) x oiso : {n : Level} {x : OD {n}} → ord→od ( od→ord x ) ≡ x diso : {n : Level} {x : Ordinal {n}} → od→ord ( ord→od x ) ≡ x -- supermum as Replacement Axiom sup-o : {n : Level } → ( Ordinal {n} → Ordinal {n}) → Ordinal {n} sup-o< : {n : Level } → { ψ : Ordinal {n} → Ordinal {n}} → ∀ {x : Ordinal {n}} → ψ x o< sup-o ψ - -- a property of supermum required in Power Set Axiom + -- a contra-position of minimality of supermum sup-x : {n : Level } → ( Ordinal {n} → Ordinal {n}) → Ordinal {n} sup-lb : {n : Level } → { ψ : Ordinal {n} → Ordinal {n}} → {z : Ordinal {n}} → z o< sup-o ψ → z o< osuc (ψ (sup-x ψ)) - -- sup-lb : {n : Level } → ( ψ : Ordinal {n} → Ordinal {n}) → ( ∀ {x : Ordinal {n}} → ψx o< z ) → z o< osuc ( sup-o ψ ) _∋_ : { n : Level } → ( a x : OD {n} ) → Set n _∋_ {n} a x = def a ( od→ord x ) _c<_ : { n : Level } → ( x a : OD {n} ) → Set n -x c< a = a ∋ x +x c< a = od→ord x o< od→ord a + +postulate + o<→c< : {n : Level} {x y : Ordinal {n} } → x o< y → ord→od x c< ord→od y _c≤_ : {n : Level} → OD {n} → OD {n} → Set (suc n) a c≤ b = (a ≡ b) ∨ ( b ∋ a ) @@ -74,15 +73,17 @@ def-subst : {n : Level } {Z : OD {n}} {X : Ordinal {n} }{z : OD {n}} {x : Ordinal {n} }→ def Z X → Z ≡ z → X ≡ x → def z x def-subst df refl refl = df +-- sup-min : {n : Level } → ( ψ : Ordinal {n} → Ordinal {n}) → {z : Ordinal {n}} → ψ z o< z → sup-o ψ o< osuc z + sup-od : {n : Level } → ( OD {n} → OD {n}) → OD {n} sup-od ψ = ord→od ( sup-o ( λ x → od→ord (ψ (ord→od x ))) ) sup-c< : {n : Level } → ( ψ : OD {n} → OD {n}) → ∀ {x : OD {n}} → def ( sup-od ψ ) (od→ord ( ψ x )) sup-c< {n} ψ {x} = def-subst {n} {_} {_} {sup-od ψ} {od→ord ( ψ x )} - ( o<→c< sup-o< ) refl (cong ( λ k → od→ord (ψ k) ) oiso) + {!!} refl (cong ( λ k → od→ord (ψ k) ) oiso) ∅1 : {n : Level} → ( x : OD {n} ) → ¬ ( x c< od∅ {n} ) -∅1 {n} x (lift ()) +∅1 {n} x = {!!} ∅3 : {n : Level} → { x : Ordinal {n}} → ( ∀(y : Ordinal {n}) → ¬ (y o< x ) ) → x ≡ o∅ {n} ∅3 {n} {x} = TransFinite {n} c2 c3 x where @@ -102,18 +103,13 @@ c3 lx (OSuc .lx x₁) d not | t | () transitive : {n : Level } { z y x : OD {suc n} } → z ∋ y → y ∋ x → z ∋ x -transitive {n} {z} {y} {x} z∋y x∋y with ordtrans ( c<→o< {suc n} {x} {y} x∋y ) ( c<→o< {suc n} {y} {z} z∋y ) +transitive {n} {z} {y} {x} z∋y x∋y with ordtrans {!!} {!!} ... | t = lemma0 (lemma t) where lemma : ( od→ord x ) o< ( od→ord z ) → def ( ord→od ( od→ord z )) ( od→ord x) - lemma xo<z = o<→c< xo<z + lemma xo<z = {!!} lemma0 : def ( ord→od ( od→ord z )) ( od→ord x) → def z (od→ord x) lemma0 dz = def-subst {suc n} { ord→od ( od→ord z )} { od→ord x} dz (oiso) refl -record Minimumo {n : Level } (x : Ordinal {n}) : Set (suc n) where - field - mino : Ordinal {n} - min<x : mino o< x - ∅5 : {n : Level} → { x : Ordinal {n} } → ¬ ( x ≡ o∅ {n} ) → o∅ {n} o< x ∅5 {n} {record { lv = Zero ; ord = (Φ .0) }} not = ⊥-elim (not refl) ∅5 {n} {record { lv = Zero ; ord = (OSuc .0 ord) }} not = case2 Φ< @@ -153,12 +149,12 @@ o<→o> : {n : Level} → { x y : OD {n} } → (x == y) → (od→ord x ) o< ( od→ord y) → ⊥ o<→o> {n} {x} {y} record { eq→ = xy ; eq← = yx } (case1 lt) with - yx (def-subst {n} {ord→od (od→ord y)} {od→ord x} (o<→c< (case1 lt )) oiso refl ) -... | oyx with o<¬≡ (od→ord x) (od→ord x) refl (c<→o< oyx ) + yx (def-subst {n} {ord→od (od→ord y)} {od→ord x} {!!} oiso refl ) +... | oyx with o<¬≡ (od→ord x) (od→ord x) refl {!!} ... | () o<→o> {n} {x} {y} record { eq→ = xy ; eq← = yx } (case2 lt) with - yx (def-subst {n} {ord→od (od→ord y)} {od→ord x} (o<→c< (case2 lt )) oiso refl ) -... | oyx with o<¬≡ (od→ord x) (od→ord x) refl (c<→o< oyx ) + yx (def-subst {n} {ord→od (od→ord y)} {od→ord x} {!!} oiso refl ) +... | oyx with o<¬≡ (od→ord x) (od→ord x) refl {!!} ... | () ==→o≡ : {n : Level} → { x y : Ordinal {suc n} } → ord→od x == ord→od y → x ≡ y @@ -172,8 +168,8 @@ lemma : ord→od x == record { def = λ z → z o< x } eq→ lemma {w} z = subst₂ (λ k j → k o< j ) diso refl (subst (λ k → (od→ord ( ord→od w)) o< k ) diso t ) where t : (od→ord ( ord→od w)) o< (od→ord (ord→od x)) - t = c<→o< {suc n} {ord→od w} {ord→od x} (def-subst {suc n} {_} {_} {ord→od x} {_} z refl (sym diso)) - eq← lemma {w} z = def-subst {suc n} {_} {_} {ord→od x} {w} ( o<→c< {suc n} {_} {_} z ) refl refl + t = {!!} + eq← lemma {w} z = def-subst {suc n} {_} {_} {ord→od x} {w} {!!} refl refl od≡-def : {n : Level} → { x : Ordinal {suc n} } → ord→od x ≡ record { def = λ z → z o< x } od≡-def {n} {x} = subst (λ k → ord→od x ≡ k ) oiso (cong ( λ k → ord→od k ) (≡-def {n} {x} )) @@ -190,19 +186,19 @@ ∋→o< : {n : Level} → { a x : OD {suc n} } → a ∋ x → od→ord x o< od→ord a ∋→o< {n} {a} {x} lt = t where t : (od→ord x) o< (od→ord a) - t = c<→o< {suc n} {x} {a} lt + t = {!!} o<∋→ : {n : Level} → { a x : OD {suc n} } → od→ord x o< od→ord a → a ∋ x o<∋→ {n} {a} {x} lt = subst₂ (λ k j → def k j ) oiso refl t where t : def (ord→od (od→ord a)) (od→ord x) - t = o<→c< {suc n} {od→ord x} {od→ord a} lt + t = {!!} o∅≡od∅ : {n : Level} → ord→od (o∅ {suc n}) ≡ od∅ {suc n} o∅≡od∅ {n} with trio< {n} (o∅ {suc n}) (od→ord (od∅ {suc n} )) o∅≡od∅ {n} | tri< a ¬b ¬c = ⊥-elim (lemma a) where lemma : o∅ {suc n } o< (od→ord (od∅ {suc n} )) → ⊥ - lemma lt with def-subst (o<→c< lt) oiso refl - lemma lt | lift () + lemma lt with def-subst {!!} oiso refl + lemma lt | t = {!!} o∅≡od∅ {n} | tri≈ ¬a b ¬c = trans (cong (λ k → ord→od k ) b ) oiso o∅≡od∅ {n} | tri> ¬a ¬b c = ⊥-elim (¬x<0 c) @@ -210,21 +206,21 @@ o<→¬== {n} {x} {y} lt eq = o<→o> 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<> olt (c<→o< clt ) where +o<→¬c> {n} {x} {y} olt clt = o<> olt {!!} 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) +o≡→¬c< {n} {x} {y} oeq lt = o<¬≡ (od→ord x) (od→ord y) (orefl oeq ) lt tri-c< : {n : Level} → Trichotomous _==_ (_c<_ {suc n}) tri-c< {n} x y with trio< {n} (od→ord x) (od→ord y) -tri-c< {n} x y | tri< a ¬b ¬c = tri< (def-subst (o<→c< a) oiso refl) (o<→¬== a) ( o<→¬c> a ) +tri-c< {n} x y | tri< a ¬b ¬c = tri< (def-subst {!!} oiso refl) (o<→¬== a) ( o<→¬c> a ) tri-c< {n} x y | tri≈ ¬a b ¬c = tri≈ (o≡→¬c< b) (ord→== b) (o≡→¬c< (sym b)) -tri-c< {n} x y | tri> ¬a ¬b c = tri> ( o<→¬c> c) (λ eq → o<→¬== c (eq-sym eq ) ) (def-subst (o<→c< c) oiso refl) +tri-c< {n} x y | tri> ¬a ¬b c = tri> ( o<→¬c> c) (λ eq → o<→¬== c (eq-sym eq ) ) (def-subst {!!} oiso refl) c<> : {n : Level } { x y : OD {suc n}} → x c< y → y c< x → ⊥ c<> {n} {x} {y} x<y y<x with tri-c< x y c<> {n} {x} {y} x<y y<x | tri< a ¬b ¬c = ¬c y<x -c<> {n} {x} {y} x<y y<x | tri≈ ¬a b ¬c = o<→o> b ( c<→o< x<y ) +c<> {n} {x} {y} x<y y<x | tri≈ ¬a b ¬c = o<→o> b x<y c<> {n} {x} {y} x<y y<x | tri> ¬a ¬b c = ¬a x<y ∅< : {n : Level} → { x y : OD {n} } → def x (od→ord y ) → ¬ ( x == od∅ {n} ) @@ -232,16 +228,16 @@ ∅< {n} {x} {y} d eq | lift () ∅6 : {n : Level} → { x : OD {suc n} } → ¬ ( x ∋ x ) -- no Russel paradox -∅6 {n} {x} x∋x = c<> {n} {x} {x} x∋x x∋x +∅6 {n} {x} x∋x = c<> {n} {x} {x} {!!} {!!} def-iso : {n : Level} {A B : OD {n}} {x y : Ordinal {n}} → x ≡ y → (def A y → def B y) → def A x → def B x def-iso refl t = t is-∋ : {n : Level} → ( x y : OD {suc n} ) → Dec ( x ∋ y ) is-∋ {n} x y with tri-c< x y -is-∋ {n} x y | tri< a ¬b ¬c = no ¬c -is-∋ {n} x y | tri≈ ¬a b ¬c = no ¬c -is-∋ {n} x y | tri> ¬a ¬b c = yes c +is-∋ {n} x y | tri< a ¬b ¬c = no {!!} +is-∋ {n} x y | tri≈ ¬a b ¬c = no {!!} +is-∋ {n} x y | tri> ¬a ¬b c = yes {!!} is-o∅ : {n : Level} → ( x : Ordinal {suc n} ) → Dec ( x ≡ o∅ {suc n} ) is-o∅ {n} record { lv = Zero ; ord = (Φ .0) } = yes refl @@ -258,7 +254,7 @@ lemma1 : od→ord (ord→od o∅) ≡ od→ord od∅ lemma1 = cong ( λ k → od→ord k ) o∅≡od∅ lemma o∅ ne | yes refl | () - lemma ox ne | no ¬p = subst ( λ k → def (ord→od ox) (od→ord k) ) o∅≡od∅ (o<→c< (subst (λ k → k o< ox ) (sym diso) (∅5 ¬p)) ) + lemma ox ne | no ¬p = subst ( λ k → def (ord→od ox) (od→ord k) ) o∅≡od∅ {!!} -- open import Relation.Binary.HeterogeneousEquality as HE using (_≅_ ) -- postulate f-extensionality : { n : Level} → Relation.Binary.PropositionalEquality.Extensionality (suc n) (suc (suc n)) @@ -311,10 +307,12 @@ A ∈ B = B ∋ A _⊆_ : ( A B : ZFSet ) → ∀{ x : ZFSet } → Set (suc n) _⊆_ A B {x} = A ∋ x → B ∋ x - -- _∩_ : ( A B : ZFSet ) → ZFSet - -- A ∩ B = Select (A , B) ( λ x → ( A ∋ x ) ∧ (B ∋ x) ) + _∩_ : ( A B : ZFSet ) → ZFSet + A ∩ B = Select (A , B) ( λ x → ( A ∋ x ) ∧ (B ∋ x) ) -- _∪_ : ( A B : ZFSet ) → ZFSet -- A ∪ B = Select (A , B) ( λ x → (A ∋ x) ∨ ( B ∋ x ) ) + {_} : ZFSet → ZFSet + { x } = ( x , x ) infixr 200 _∈_ -- infixr 230 _∩_ _∪_ infixr 220 _⊆_ @@ -337,7 +335,6 @@ ; replacement = replacement } where open _∧_ - open Minimumo pair : (A B : OD {suc n} ) → ((A , B) ∋ A) ∧ ((A , B) ∋ B) proj1 (pair A B ) = omax-x {n} (od→ord A) (od→ord B) proj2 (pair A B ) = omax-y {n} (od→ord A) (od→ord B) @@ -347,7 +344,7 @@ --- ZFSubset A x = record { def = λ y → def A y ∧ def x y } subset of A --- Power X = ord→od ( sup-o ( λ x → od→ord ( ZFSubset A (ord→od x )) ) ) Power X is a sup of all subset of A -- - -- if Power A ∋ t, from a propertiy of minimum sup there is osuc ZFSubset A ∋ t + -- if Power A ∋ t, from a minimulity of sup, there is osuc ZFSubset A ∋ t -- then ZFSubset A ≡ t or ZFSubset A ∋ t. In the former case ZFSubset A ∋ x implies A ∋ x -- In case of later, ZFSubset A ∋ t and t ∋ x implies ZFSubset A ∋ x by transitivity -- @@ -356,19 +353,16 @@ minsup : OD minsup = ZFSubset A ( ord→od ( sup-x (λ x → od→ord ( ZFSubset A (ord→od x))))) lemma-t : csuc minsup ∋ t - lemma-t = o<→c< (o<-subst (sup-lb (o<-subst (c<→o< P∋t) refl diso )) refl refl ) + lemma-t = {!!} lemma-s : ZFSubset A ( ord→od ( sup-x (λ x → od→ord ( ZFSubset A (ord→od x))))) ∋ x - lemma-s with osuc-≡< ( o<-subst (c<→o< lemma-t ) refl diso ) - lemma-s | case1 eq = def-subst ( ==-def-r (o≡→== eq) (subst (λ k → def k (od→ord x)) (sym oiso) t∋x ) ) oiso refl - lemma-s | case2 lt = transitive {n} {minsup} {t} {x} (def-subst (o<→c< lt) oiso refl ) t∋x + lemma-s = {!!} -- -- we have t ∋ x → A ∋ x means t is a subset of A, that is ZFSubset A t == t -- Power A is a sup of ZFSubset A t, so Power A ∋ t -- power← : (A t : OD) → ({x : OD} → (t ∋ x → A ∋ x)) → Power A ∋ t power← A t t→A = def-subst {suc n} {_} {_} {Power A} {od→ord t} - ( o<→c< {suc n} {od→ord (ZFSubset A (ord→od (od→ord t)) )} {sup-o (λ x → od→ord (ZFSubset A (ord→od x)))} - lemma ) refl lemma1 where + {!!} refl lemma1 where lemma-eq : ZFSubset A t == t eq→ lemma-eq {z} w = proj2 w eq← lemma-eq {z} w = record { proj2 = w ; @@ -380,17 +374,17 @@ union-lemma-u : {X z : OD {suc n}} → (U>z : Union X ∋ z ) → csuc z ∋ z union-lemma-u {X} {z} U>z = lemma <-osuc where lemma : {oz ooz : Ordinal {suc n}} → oz o< ooz → def (ord→od ooz) oz - lemma {oz} {ooz} lt = def-subst {suc n} {ord→od ooz} (o<→c< lt) refl refl + lemma {oz} {ooz} lt = def-subst {suc n} {ord→od ooz} {!!} refl refl union→ : (X z u : OD) → (X ∋ u) ∧ (u ∋ z) → Union X ∋ z union→ X y u xx with trio< ( od→ord u ) ( osuc ( od→ord y )) - union→ X y u xx | tri< a ¬b ¬c with osuc-< a (c<→o< (proj2 xx)) + union→ X y u xx | tri< a ¬b ¬c with osuc-< a {!!} union→ X y u xx | tri< a ¬b ¬c | () - union→ X y u xx | tri≈ ¬a b ¬c = lemma b (c<→o< (proj1 xx )) where + union→ X y u xx | tri≈ ¬a b ¬c = lemma b {!!} where lemma : {oX ou ooy : Ordinal {suc n}} → ou ≡ ooy → ou o< oX → ooy o< oX lemma refl lt = lt - union→ X y u xx | tri> ¬a ¬b c = ordtrans {suc n} {osuc ( od→ord y )} {od→ord u} {od→ord X} c ( c<→o< (proj1 xx )) + union→ X y u xx | tri> ¬a ¬b c = ordtrans {suc n} {osuc ( od→ord y )} {od→ord u} {od→ord X} c {!!} union← : (X z : OD) (X∋z : Union X ∋ z) → (X ∋ csuc z) ∧ (csuc z ∋ z ) - union← X z X∋z = record { proj1 = def-subst {suc n} {_} {_} {X} {od→ord (csuc z )} (o<→c< X∋z) oiso (sym diso) ; proj2 = union-lemma-u X∋z } + union← X z X∋z = record { proj1 = def-subst {suc n} {_} {_} {X} {od→ord (csuc z )} {!!} oiso (sym diso) ; proj2 = union-lemma-u X∋z } ψiso : {ψ : OD {suc n} → Set (suc n)} {x y : OD {suc n}} → ψ x → x ≡ y → ψ y ψiso {ψ} t refl = t selection : {ψ : OD → Set (suc n)} {X y : OD} → ((X ∋ y) ∧ ψ y) ⇔ (Select X ψ ∋ y) @@ -419,7 +413,7 @@ xxx-union : {x : OD {suc n}} → (x , (x , x)) ≡ record { def = λ z → z o< osuc (osuc (od→ord x))} xxx-union {x} = cong ( λ k → record { def = λ z → z o< k } ) lemma where lemma1 : {x : OD {suc n}} → od→ord x o< od→ord (x , x) - lemma1 {x} = c<→o< ( proj1 (pair x x ) ) + lemma1 {x} = {!!} lemma2 : {x : OD {suc n}} → od→ord (x , x) ≡ osuc (od→ord x) lemma2 = trans ( cong ( λ k → od→ord k ) xx-union ) (sym ≡-def) lemma : {x : OD {suc n}} → omax (od→ord x) (od→ord (x , x)) ≡ osuc (osuc (od→ord x)) @@ -438,7 +432,7 @@ infinite = ord→od ( omega ) infinity∅ : ord→od ( omega ) ∋ od∅ {suc n} infinity∅ = def-subst {suc n} {_} {o∅} {infinite} {od→ord od∅} - (o<→c< ( case1 (s≤s z≤n ))) refl (subst ( λ k → ( k ≡ od→ord od∅ )) diso (cong (λ k → od→ord k) o∅≡od∅ )) + {!!} refl (subst ( λ k → ( k ≡ od→ord od∅ )) diso (cong (λ k → od→ord k) o∅≡od∅ )) infinite∋x : (x : OD) → infinite ∋ x → od→ord x o< omega infinite∋x x lt = subst (λ k → od→ord x o< k ) diso t where t : od→ord x o< od→ord (ord→od (omega)) @@ -456,4 +450,15 @@ lemma record { lv = (Suc lv₁) ; ord = (OSuc .(Suc lv₁) ord₁) } (case1 (s≤s ())) lemma record { lv = 1 ; ord = (Φ 1) } (case2 c2) with d<→lv c2 lemma record { lv = (Suc Zero) ; ord = (Φ .1) } (case2 ()) | refl + -- ∀ X [ ∅ ∉ X → (∃ f : X → ⋃ X ) → ∀ A ∈ X ( f ( A ) ∈ A ) ] -- this form is no good since X is a transitive set + -- ∀ z [ ∀ x ( x ∈ z → ¬ ( x ≈ ∅ ) ) ∧ ∀ x ∀ y ( x , y ∈ z ∧ ¬ ( x ≈ y ) → x ∩ y ≈ ∅ ) → ∃ u ∀ x ( x ∈ z → ∃ t ( u ∩ x) ≈ { t }) ] + record Choice (z : OD {suc n}) : Set (suc (suc n)) where + field + u : {x : OD {suc n}} ( x∈z : x ∈ z ) → OD {suc n} + t : {x : OD {suc n}} ( x∈z : x ∈ z ) → (x : OD {suc n} ) → OD {suc n} + choice : { x : OD {suc n} } → ( x∈z : x ∈ z ) → ( u x∈z ∩ x) == { t x∈z x } + -- choice : {x : OD {suc n}} ( x ∈ z → ¬ ( x ≈ ∅ ) ) → + -- axiom-of-choice : { X : OD } → ( ¬x∅ : ¬ ( X == od∅ ) ) → { A : OD } → (A∈X : A ∈ X ) → choice ¬x∅ A∈X ∈ A + -- axiom-of-choice {X} nx {A} lt = ¬∅=→∅∈ {!!} +