Mercurial > hg > Members > kono > Proof > ZF-in-agda
annotate Ordinals.agda @ 302:304c271b3d47
HOD and reduction mapping of Ordinals
| author | Shinji KONO <kono@ie.u-ryukyu.ac.jp> |
|---|---|
| date | Sun, 28 Jun 2020 18:09:04 +0900 |
| parents | 63df67b6281c |
| children | b172ab9f12bc |
| rev | line source |
|---|---|
| 16 | 1 open import Level |
|
220
95a26d1698f4
try to separate Ordinals
Shinji KONO <kono@ie.u-ryukyu.ac.jp>
parents:
218
diff
changeset
|
2 module Ordinals where |
| 3 | 3 |
|
14
e11e95d5ddee
separete constructible set
Shinji KONO <kono@ie.u-ryukyu.ac.jp>
parents:
11
diff
changeset
|
4 open import zf |
| 3 | 5 |
| 23 | 6 open import Data.Nat renaming ( zero to Zero ; suc to Suc ; ℕ to Nat ; _⊔_ to _n⊔_ ) |
| 75 | 7 open import Data.Empty |
|
14
e11e95d5ddee
separete constructible set
Shinji KONO <kono@ie.u-ryukyu.ac.jp>
parents:
11
diff
changeset
|
8 open import Relation.Binary.PropositionalEquality |
|
213
22d435172d1a
separate logic and nat
Shinji KONO <kono@ie.u-ryukyu.ac.jp>
parents:
204
diff
changeset
|
9 open import logic |
|
22d435172d1a
separate logic and nat
Shinji KONO <kono@ie.u-ryukyu.ac.jp>
parents:
204
diff
changeset
|
10 open import nat |
|
220
95a26d1698f4
try to separate Ordinals
Shinji KONO <kono@ie.u-ryukyu.ac.jp>
parents:
218
diff
changeset
|
11 open import Data.Unit using ( ⊤ ) |
|
95a26d1698f4
try to separate Ordinals
Shinji KONO <kono@ie.u-ryukyu.ac.jp>
parents:
218
diff
changeset
|
12 open import Relation.Nullary |
|
95a26d1698f4
try to separate Ordinals
Shinji KONO <kono@ie.u-ryukyu.ac.jp>
parents:
218
diff
changeset
|
13 open import Relation.Binary |
|
95a26d1698f4
try to separate Ordinals
Shinji KONO <kono@ie.u-ryukyu.ac.jp>
parents:
218
diff
changeset
|
14 open import Relation.Binary.Core |
| 3 | 15 |
|
222
59771eb07df0
TransFinite induction fixed
Shinji KONO <kono@ie.u-ryukyu.ac.jp>
parents:
221
diff
changeset
|
16 record IsOrdinals {n : Level} (ord : Set n) (o∅ : ord ) (osuc : ord → ord ) (_o<_ : ord → ord → Set n) : Set (suc (suc n)) where |
| 16 | 17 field |
| 221 | 18 Otrans : {x y z : ord } → x o< y → y o< z → x o< z |
| 19 OTri : Trichotomous {n} _≡_ _o<_ | |
| 20 ¬x<0 : { x : ord } → ¬ ( x o< o∅ ) | |
| 21 <-osuc : { x : ord } → x o< osuc x | |
| 22 osuc-≡< : { a x : ord } → x o< osuc a → (x ≡ a ) ∨ (x o< a) | |
|
302
304c271b3d47
HOD and reduction mapping of Ordinals
Shinji KONO <kono@ie.u-ryukyu.ac.jp>
parents:
258
diff
changeset
|
23 is-limit : { x : ord } → Dec ( ¬ ((y : ord) → x ≡ osuc y) ) |
|
222
59771eb07df0
TransFinite induction fixed
Shinji KONO <kono@ie.u-ryukyu.ac.jp>
parents:
221
diff
changeset
|
24 TransFinite : { ψ : ord → Set (suc n) } |
|
59771eb07df0
TransFinite induction fixed
Shinji KONO <kono@ie.u-ryukyu.ac.jp>
parents:
221
diff
changeset
|
25 → ( (x : ord) → ( (y : ord ) → y o< x → ψ y ) → ψ x ) |
|
59771eb07df0
TransFinite induction fixed
Shinji KONO <kono@ie.u-ryukyu.ac.jp>
parents:
221
diff
changeset
|
26 → ∀ (x : ord) → ψ x |
| 16 | 27 |
|
222
59771eb07df0
TransFinite induction fixed
Shinji KONO <kono@ie.u-ryukyu.ac.jp>
parents:
221
diff
changeset
|
28 |
|
59771eb07df0
TransFinite induction fixed
Shinji KONO <kono@ie.u-ryukyu.ac.jp>
parents:
221
diff
changeset
|
29 record Ordinals {n : Level} : Set (suc (suc n)) where |
|
220
95a26d1698f4
try to separate Ordinals
Shinji KONO <kono@ie.u-ryukyu.ac.jp>
parents:
218
diff
changeset
|
30 field |
|
95a26d1698f4
try to separate Ordinals
Shinji KONO <kono@ie.u-ryukyu.ac.jp>
parents:
218
diff
changeset
|
31 ord : Set n |
| 221 | 32 o∅ : ord |
| 33 osuc : ord → ord | |
| 34 _o<_ : ord → ord → Set n | |
| 35 isOrdinal : IsOrdinals ord o∅ osuc _o<_ | |
| 17 | 36 |
| 221 | 37 module inOrdinal {n : Level} (O : Ordinals {n} ) where |
| 3 | 38 |
| 221 | 39 Ordinal : Set n |
| 40 Ordinal = Ordinals.ord O | |
| 41 | |
| 42 _o<_ : Ordinal → Ordinal → Set n | |
| 43 _o<_ = Ordinals._o<_ O | |
| 218 | 44 |
| 221 | 45 osuc : Ordinal → Ordinal |
| 46 osuc = Ordinals.osuc O | |
| 218 | 47 |
| 221 | 48 o∅ : Ordinal |
| 49 o∅ = Ordinals.o∅ O | |
|
43
0d9b9db14361
equalitu and internal parametorisity
Shinji KONO <kono@ie.u-ryukyu.ac.jp>
parents:
41
diff
changeset
|
50 |
| 221 | 51 ¬x<0 = IsOrdinals.¬x<0 (Ordinals.isOrdinal O) |
| 52 osuc-≡< = IsOrdinals.osuc-≡< (Ordinals.isOrdinal O) | |
| 53 <-osuc = IsOrdinals.<-osuc (Ordinals.isOrdinal O) | |
| 235 | 54 TransFinite = IsOrdinals.TransFinite (Ordinals.isOrdinal O) |
| 221 | 55 |
| 56 o<-dom : { x y : Ordinal } → x o< y → Ordinal | |
| 57 o<-dom {x} _ = x | |
|
74
819da8c08f05
ordinal atomical successor?
Shinji KONO <kono@ie.u-ryukyu.ac.jp>
parents:
73
diff
changeset
|
58 |
| 221 | 59 o<-cod : { x y : Ordinal } → x o< y → Ordinal |
| 60 o<-cod {_} {y} _ = y | |
| 147 | 61 |
| 221 | 62 o<-subst : {Z X z x : Ordinal } → Z o< X → Z ≡ z → X ≡ x → z o< x |
| 63 o<-subst df refl refl = df | |
| 94 | 64 |
| 221 | 65 ordtrans : {x y z : Ordinal } → x o< y → y o< z → x o< z |
| 66 ordtrans = IsOrdinals.Otrans (Ordinals.isOrdinal O) | |
| 94 | 67 |
| 221 | 68 trio< : Trichotomous _≡_ _o<_ |
| 69 trio< = IsOrdinals.OTri (Ordinals.isOrdinal O) | |
|
9
5ed16e2d8eb7
try to fix axiom of replacement
Shinji KONO <kono@ie.u-ryukyu.ac.jp>
parents:
8
diff
changeset
|
70 |
| 221 | 71 o<¬≡ : { ox oy : Ordinal } → ox ≡ oy → ox o< oy → ⊥ |
| 72 o<¬≡ {ox} {oy} eq lt with trio< ox oy | |
| 73 o<¬≡ {ox} {oy} eq lt | tri< a ¬b ¬c = ¬b eq | |
| 74 o<¬≡ {ox} {oy} eq lt | tri≈ ¬a b ¬c = ¬a lt | |
| 75 o<¬≡ {ox} {oy} eq lt | tri> ¬a ¬b c = ¬b eq | |
| 23 | 76 |
| 221 | 77 o<> : {x y : Ordinal } → y o< x → x o< y → ⊥ |
| 78 o<> {ox} {oy} lt tl with trio< ox oy | |
| 79 o<> {ox} {oy} lt tl | tri< a ¬b ¬c = ¬c lt | |
| 80 o<> {ox} {oy} lt tl | tri≈ ¬a b ¬c = ¬a tl | |
| 81 o<> {ox} {oy} lt tl | tri> ¬a ¬b c = ¬a tl | |
| 23 | 82 |
| 221 | 83 osuc-< : { x y : Ordinal } → y o< osuc x → x o< y → ⊥ |
| 84 osuc-< {x} {y} y<ox x<y with osuc-≡< y<ox | |
| 85 osuc-< {x} {y} y<ox x<y | case1 refl = o<¬≡ refl x<y | |
| 86 osuc-< {x} {y} y<ox x<y | case2 y<x = o<> x<y y<x | |
| 180 | 87 |
| 221 | 88 osucc : {ox oy : Ordinal } → oy o< ox → osuc oy o< osuc ox |
| 89 ---- y < osuc y < x < osuc x | |
| 90 ---- y < osuc y = x < osuc x | |
| 91 ---- y < osuc y > x < osuc x -> y = x ∨ x < y → ⊥ | |
| 92 osucc {ox} {oy} oy<ox with trio< (osuc oy) ox | |
| 93 osucc {ox} {oy} oy<ox | tri< a ¬b ¬c = ordtrans a <-osuc | |
| 94 osucc {ox} {oy} oy<ox | tri≈ ¬a refl ¬c = <-osuc | |
| 95 osucc {ox} {oy} oy<ox | tri> ¬a ¬b c with osuc-≡< c | |
| 96 osucc {ox} {oy} oy<ox | tri> ¬a ¬b c | case1 eq = ⊥-elim (o<¬≡ (sym eq) oy<ox) | |
| 97 osucc {ox} {oy} oy<ox | tri> ¬a ¬b c | case2 lt = ⊥-elim (o<> lt oy<ox) | |
| 98 | |
| 99 open _∧_ | |
| 84 | 100 |
| 221 | 101 osuc2 : ( x y : Ordinal ) → ( osuc x o< osuc (osuc y )) ⇔ (x o< osuc y) |
| 102 proj2 (osuc2 x y) lt = osucc lt | |
| 103 proj1 (osuc2 x y) ox<ooy with osuc-≡< ox<ooy | |
| 104 proj1 (osuc2 x y) ox<ooy | case1 ox=oy = o<-subst <-osuc refl ox=oy | |
| 105 proj1 (osuc2 x y) ox<ooy | case2 ox<oy = ordtrans <-osuc ox<oy | |
| 129 | 106 |
| 221 | 107 _o≤_ : Ordinal → Ordinal → Set n |
| 108 a o≤ b = (a ≡ b) ∨ ( a o< b ) | |
| 109 | |
| 129 | 110 |
| 221 | 111 xo<ab : {oa ob : Ordinal } → ( {ox : Ordinal } → ox o< oa → ox o< ob ) → oa o< osuc ob |
| 112 xo<ab {oa} {ob} a→b with trio< oa ob | |
| 113 xo<ab {oa} {ob} a→b | tri< a ¬b ¬c = ordtrans a <-osuc | |
| 114 xo<ab {oa} {ob} a→b | tri≈ ¬a refl ¬c = <-osuc | |
| 115 xo<ab {oa} {ob} a→b | tri> ¬a ¬b c = ⊥-elim ( o<¬≡ refl (a→b c ) ) | |
| 88 | 116 |
| 221 | 117 maxα : Ordinal → Ordinal → Ordinal |
| 118 maxα x y with trio< x y | |
| 119 maxα x y | tri< a ¬b ¬c = y | |
| 120 maxα x y | tri> ¬a ¬b c = x | |
| 121 maxα x y | tri≈ ¬a refl ¬c = x | |
| 84 | 122 |
| 221 | 123 minα : Ordinal → Ordinal → Ordinal |
| 124 minα x y with trio< x y | |
| 125 minα x y | tri< a ¬b ¬c = x | |
| 126 minα x y | tri> ¬a ¬b c = y | |
| 127 minα x y | tri≈ ¬a refl ¬c = x | |
| 88 | 128 |
| 221 | 129 min1 : {x y z : Ordinal } → z o< x → z o< y → z o< minα x y |
| 130 min1 {x} {y} {z} z<x z<y with trio< x y | |
| 131 min1 {x} {y} {z} z<x z<y | tri< a ¬b ¬c = z<x | |
| 132 min1 {x} {y} {z} z<x z<y | tri≈ ¬a refl ¬c = z<x | |
| 133 min1 {x} {y} {z} z<x z<y | tri> ¬a ¬b c = z<y | |
| 84 | 134 |
| 221 | 135 -- |
| 136 -- max ( osuc x , osuc y ) | |
| 137 -- | |
| 138 | |
| 139 omax : ( x y : Ordinal ) → Ordinal | |
| 140 omax x y with trio< x y | |
| 141 omax x y | tri< a ¬b ¬c = osuc y | |
| 142 omax x y | tri> ¬a ¬b c = osuc x | |
| 143 omax x y | tri≈ ¬a refl ¬c = osuc x | |
| 86 | 144 |
| 221 | 145 omax< : ( x y : Ordinal ) → x o< y → osuc y ≡ omax x y |
| 146 omax< x y lt with trio< x y | |
| 147 omax< x y lt | tri< a ¬b ¬c = refl | |
| 148 omax< x y lt | tri≈ ¬a b ¬c = ⊥-elim (¬a lt ) | |
| 149 omax< x y lt | tri> ¬a ¬b c = ⊥-elim (¬a lt ) | |
| 86 | 150 |
| 221 | 151 omax≡ : ( x y : Ordinal ) → x ≡ y → osuc y ≡ omax x y |
| 152 omax≡ x y eq with trio< x y | |
| 153 omax≡ x y eq | tri< a ¬b ¬c = ⊥-elim (¬b eq ) | |
| 154 omax≡ x y eq | tri≈ ¬a refl ¬c = refl | |
| 155 omax≡ x y eq | tri> ¬a ¬b c = ⊥-elim (¬b eq ) | |
| 91 | 156 |
| 221 | 157 omax-x : ( x y : Ordinal ) → x o< omax x y |
| 158 omax-x x y with trio< x y | |
| 159 omax-x x y | tri< a ¬b ¬c = ordtrans a <-osuc | |
| 160 omax-x x y | tri> ¬a ¬b c = <-osuc | |
| 161 omax-x x y | tri≈ ¬a refl ¬c = <-osuc | |
| 16 | 162 |
| 221 | 163 omax-y : ( x y : Ordinal ) → y o< omax x y |
| 164 omax-y x y with trio< x y | |
| 165 omax-y x y | tri< a ¬b ¬c = <-osuc | |
| 166 omax-y x y | tri> ¬a ¬b c = ordtrans c <-osuc | |
| 167 omax-y x y | tri≈ ¬a refl ¬c = <-osuc | |
| 168 | |
| 169 omxx : ( x : Ordinal ) → omax x x ≡ osuc x | |
| 170 omxx x with trio< x x | |
| 171 omxx x | tri< a ¬b ¬c = ⊥-elim (¬b refl ) | |
| 172 omxx x | tri> ¬a ¬b c = ⊥-elim (¬b refl ) | |
| 173 omxx x | tri≈ ¬a refl ¬c = refl | |
| 174 | |
| 175 omxxx : ( x : Ordinal ) → omax x (omax x x ) ≡ osuc (osuc x) | |
| 176 omxxx x = trans ( cong ( λ k → omax x k ) (omxx x )) (sym ( omax< x (osuc x) <-osuc )) | |
| 177 | |
| 178 open _∧_ | |
| 16 | 179 |
| 221 | 180 OrdTrans : Transitive _o≤_ |
| 181 OrdTrans (case1 refl) (case1 refl) = case1 refl | |
| 182 OrdTrans (case1 refl) (case2 lt2) = case2 lt2 | |
| 183 OrdTrans (case2 lt1) (case1 refl) = case2 lt1 | |
| 184 OrdTrans (case2 x) (case2 y) = case2 (ordtrans x y) | |
|
97
f2b579106770
power set using sup on Def
Shinji KONO <kono@ie.u-ryukyu.ac.jp>
parents:
94
diff
changeset
|
185 |
| 221 | 186 OrdPreorder : Preorder n n n |
| 187 OrdPreorder = record { Carrier = Ordinal | |
| 188 ; _≈_ = _≡_ | |
| 189 ; _∼_ = _o≤_ | |
| 190 ; isPreorder = record { | |
| 191 isEquivalence = record { refl = refl ; sym = sym ; trans = trans } | |
| 192 ; reflexive = case1 | |
| 193 ; trans = OrdTrans | |
| 194 } | |
| 195 } | |
| 165 | 196 |
| 258 | 197 FExists : {m l : Level} → ( ψ : Ordinal → Set m ) |
| 221 | 198 → {p : Set l} ( P : { y : Ordinal } → ψ y → ¬ p ) |
| 199 → (exists : ¬ (∀ y → ¬ ( ψ y ) )) | |
| 200 → ¬ p | |
| 258 | 201 FExists {m} {l} ψ {p} P = contra-position ( λ p y ψy → P {y} ψy p ) |
| 221 | 202 |