Mercurial > hg > Members > kono > Proof > ZF-in-agda
annotate Ordinals.agda @ 387:8b0715e28b33
...
| author | Shinji KONO <kono@ie.u-ryukyu.ac.jp> |
|---|---|
| date | Sat, 25 Jul 2020 09:09:00 +0900 |
| parents | 4cbcf71b09c4 |
| children | 19687f3304c9 |
| 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 |
| 320 | 16 record IsOrdinals {n : Level} (ord : Set n) (o∅ : ord ) (osuc : ord → ord ) (_o<_ : ord → ord → Set n) (next : ord → ord ) : 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) | |
|
348
08d94fec239c
Limit ordinal and possible OD bound
Shinji KONO <kono@ie.u-ryukyu.ac.jp>
parents:
347
diff
changeset
|
23 not-limit-p : ( x : ord ) → Dec ( ¬ ((y : ord) → ¬ (x ≡ osuc y) )) |
| 324 | 24 TransFinite : { ψ : ord → Set n } |
|
222
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 |
|
348
08d94fec239c
Limit ordinal and possible OD bound
Shinji KONO <kono@ie.u-ryukyu.ac.jp>
parents:
347
diff
changeset
|
28 record IsNext {n : Level } (ord : Set n) (o∅ : ord ) (osuc : ord → ord ) (_o<_ : ord → ord → Set n) (next : ord → ord ) : Set (suc (suc n)) where |
|
08d94fec239c
Limit ordinal and possible OD bound
Shinji KONO <kono@ie.u-ryukyu.ac.jp>
parents:
347
diff
changeset
|
29 field |
|
08d94fec239c
Limit ordinal and possible OD bound
Shinji KONO <kono@ie.u-ryukyu.ac.jp>
parents:
347
diff
changeset
|
30 x<nx : { y : ord } → (y o< next y ) |
|
08d94fec239c
Limit ordinal and possible OD bound
Shinji KONO <kono@ie.u-ryukyu.ac.jp>
parents:
347
diff
changeset
|
31 osuc<nx : { x y : ord } → x o< next y → osuc x o< next y |
|
08d94fec239c
Limit ordinal and possible OD bound
Shinji KONO <kono@ie.u-ryukyu.ac.jp>
parents:
347
diff
changeset
|
32 ¬nx<nx : {x y : ord} → y o< x → x o< next y → ¬ ((z : ord) → ¬ (x ≡ osuc z)) |
|
222
59771eb07df0
TransFinite induction fixed
Shinji KONO <kono@ie.u-ryukyu.ac.jp>
parents:
221
diff
changeset
|
33 |
|
59771eb07df0
TransFinite induction fixed
Shinji KONO <kono@ie.u-ryukyu.ac.jp>
parents:
221
diff
changeset
|
34 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
|
35 field |
|
95a26d1698f4
try to separate Ordinals
Shinji KONO <kono@ie.u-ryukyu.ac.jp>
parents:
218
diff
changeset
|
36 ord : Set n |
| 221 | 37 o∅ : ord |
| 38 osuc : ord → ord | |
| 39 _o<_ : ord → ord → Set n | |
| 320 | 40 next : ord → ord |
| 41 isOrdinal : IsOrdinals ord o∅ osuc _o<_ next | |
|
348
08d94fec239c
Limit ordinal and possible OD bound
Shinji KONO <kono@ie.u-ryukyu.ac.jp>
parents:
347
diff
changeset
|
42 isNext : IsNext ord o∅ osuc _o<_ next |
| 17 | 43 |
| 221 | 44 module inOrdinal {n : Level} (O : Ordinals {n} ) where |
| 3 | 45 |
| 221 | 46 Ordinal : Set n |
| 47 Ordinal = Ordinals.ord O | |
| 48 | |
| 49 _o<_ : Ordinal → Ordinal → Set n | |
| 50 _o<_ = Ordinals._o<_ O | |
| 218 | 51 |
| 221 | 52 osuc : Ordinal → Ordinal |
| 53 osuc = Ordinals.osuc O | |
| 218 | 54 |
| 221 | 55 o∅ : Ordinal |
| 56 o∅ = Ordinals.o∅ O | |
|
43
0d9b9db14361
equalitu and internal parametorisity
Shinji KONO <kono@ie.u-ryukyu.ac.jp>
parents:
41
diff
changeset
|
57 |
| 320 | 58 next : Ordinal → Ordinal |
| 59 next = Ordinals.next O | |
| 60 | |
| 221 | 61 ¬x<0 = IsOrdinals.¬x<0 (Ordinals.isOrdinal O) |
| 62 osuc-≡< = IsOrdinals.osuc-≡< (Ordinals.isOrdinal O) | |
| 63 <-osuc = IsOrdinals.<-osuc (Ordinals.isOrdinal O) | |
| 235 | 64 TransFinite = IsOrdinals.TransFinite (Ordinals.isOrdinal O) |
|
348
08d94fec239c
Limit ordinal and possible OD bound
Shinji KONO <kono@ie.u-ryukyu.ac.jp>
parents:
347
diff
changeset
|
65 |
|
08d94fec239c
Limit ordinal and possible OD bound
Shinji KONO <kono@ie.u-ryukyu.ac.jp>
parents:
347
diff
changeset
|
66 x<nx = IsNext.x<nx (Ordinals.isNext O) |
|
08d94fec239c
Limit ordinal and possible OD bound
Shinji KONO <kono@ie.u-ryukyu.ac.jp>
parents:
347
diff
changeset
|
67 osuc<nx = IsNext.osuc<nx (Ordinals.isNext O) |
|
08d94fec239c
Limit ordinal and possible OD bound
Shinji KONO <kono@ie.u-ryukyu.ac.jp>
parents:
347
diff
changeset
|
68 ¬nx<nx = IsNext.¬nx<nx (Ordinals.isNext O) |
| 321 | 69 |
| 221 | 70 o<-dom : { x y : Ordinal } → x o< y → Ordinal |
| 71 o<-dom {x} _ = x | |
|
74
819da8c08f05
ordinal atomical successor?
Shinji KONO <kono@ie.u-ryukyu.ac.jp>
parents:
73
diff
changeset
|
72 |
| 221 | 73 o<-cod : { x y : Ordinal } → x o< y → Ordinal |
| 74 o<-cod {_} {y} _ = y | |
| 147 | 75 |
| 221 | 76 o<-subst : {Z X z x : Ordinal } → Z o< X → Z ≡ z → X ≡ x → z o< x |
| 77 o<-subst df refl refl = df | |
| 94 | 78 |
| 221 | 79 ordtrans : {x y z : Ordinal } → x o< y → y o< z → x o< z |
| 80 ordtrans = IsOrdinals.Otrans (Ordinals.isOrdinal O) | |
| 94 | 81 |
| 221 | 82 trio< : Trichotomous _≡_ _o<_ |
| 83 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
|
84 |
| 221 | 85 o<¬≡ : { ox oy : Ordinal } → ox ≡ oy → ox o< oy → ⊥ |
| 86 o<¬≡ {ox} {oy} eq lt with trio< ox oy | |
| 87 o<¬≡ {ox} {oy} eq lt | tri< a ¬b ¬c = ¬b eq | |
| 88 o<¬≡ {ox} {oy} eq lt | tri≈ ¬a b ¬c = ¬a lt | |
| 89 o<¬≡ {ox} {oy} eq lt | tri> ¬a ¬b c = ¬b eq | |
| 23 | 90 |
| 221 | 91 o<> : {x y : Ordinal } → y o< x → x o< y → ⊥ |
| 92 o<> {ox} {oy} lt tl with trio< ox oy | |
| 93 o<> {ox} {oy} lt tl | tri< a ¬b ¬c = ¬c lt | |
| 94 o<> {ox} {oy} lt tl | tri≈ ¬a b ¬c = ¬a tl | |
| 95 o<> {ox} {oy} lt tl | tri> ¬a ¬b c = ¬a tl | |
| 23 | 96 |
| 221 | 97 osuc-< : { x y : Ordinal } → y o< osuc x → x o< y → ⊥ |
| 98 osuc-< {x} {y} y<ox x<y with osuc-≡< y<ox | |
| 99 osuc-< {x} {y} y<ox x<y | case1 refl = o<¬≡ refl x<y | |
| 100 osuc-< {x} {y} y<ox x<y | case2 y<x = o<> x<y y<x | |
| 180 | 101 |
| 221 | 102 osucc : {ox oy : Ordinal } → oy o< ox → osuc oy o< osuc ox |
| 103 ---- y < osuc y < x < osuc x | |
| 104 ---- y < osuc y = x < osuc x | |
| 105 ---- y < osuc y > x < osuc x -> y = x ∨ x < y → ⊥ | |
| 106 osucc {ox} {oy} oy<ox with trio< (osuc oy) ox | |
| 107 osucc {ox} {oy} oy<ox | tri< a ¬b ¬c = ordtrans a <-osuc | |
| 108 osucc {ox} {oy} oy<ox | tri≈ ¬a refl ¬c = <-osuc | |
| 109 osucc {ox} {oy} oy<ox | tri> ¬a ¬b c with osuc-≡< c | |
| 110 osucc {ox} {oy} oy<ox | tri> ¬a ¬b c | case1 eq = ⊥-elim (o<¬≡ (sym eq) oy<ox) | |
| 111 osucc {ox} {oy} oy<ox | tri> ¬a ¬b c | case2 lt = ⊥-elim (o<> lt oy<ox) | |
| 112 | |
| 338 | 113 osucprev : {ox oy : Ordinal } → osuc oy o< osuc ox → oy o< ox |
| 114 osucprev {ox} {oy} oy<ox with trio< oy ox | |
| 115 osucprev {ox} {oy} oy<ox | tri< a ¬b ¬c = a | |
| 116 osucprev {ox} {oy} oy<ox | tri≈ ¬a b ¬c = ⊥-elim (o<¬≡ (cong (λ k → osuc k) b) oy<ox ) | |
| 117 osucprev {ox} {oy} oy<ox | tri> ¬a ¬b c = ⊥-elim (o<> (osucc c) oy<ox ) | |
| 118 | |
| 221 | 119 open _∧_ |
| 84 | 120 |
| 221 | 121 osuc2 : ( x y : Ordinal ) → ( osuc x o< osuc (osuc y )) ⇔ (x o< osuc y) |
| 122 proj2 (osuc2 x y) lt = osucc lt | |
| 123 proj1 (osuc2 x y) ox<ooy with osuc-≡< ox<ooy | |
| 124 proj1 (osuc2 x y) ox<ooy | case1 ox=oy = o<-subst <-osuc refl ox=oy | |
| 125 proj1 (osuc2 x y) ox<ooy | case2 ox<oy = ordtrans <-osuc ox<oy | |
| 129 | 126 |
| 221 | 127 _o≤_ : Ordinal → Ordinal → Set n |
| 326 | 128 a o≤ b = a o< osuc b -- (a ≡ b) ∨ ( a o< b ) |
| 221 | 129 |
| 129 | 130 |
| 221 | 131 xo<ab : {oa ob : Ordinal } → ( {ox : Ordinal } → ox o< oa → ox o< ob ) → oa o< osuc ob |
| 132 xo<ab {oa} {ob} a→b with trio< oa ob | |
| 133 xo<ab {oa} {ob} a→b | tri< a ¬b ¬c = ordtrans a <-osuc | |
| 134 xo<ab {oa} {ob} a→b | tri≈ ¬a refl ¬c = <-osuc | |
| 135 xo<ab {oa} {ob} a→b | tri> ¬a ¬b c = ⊥-elim ( o<¬≡ refl (a→b c ) ) | |
| 88 | 136 |
| 221 | 137 maxα : Ordinal → Ordinal → Ordinal |
| 138 maxα x y with trio< x y | |
| 139 maxα x y | tri< a ¬b ¬c = y | |
| 140 maxα x y | tri> ¬a ¬b c = x | |
| 141 maxα x y | tri≈ ¬a refl ¬c = x | |
| 84 | 142 |
| 308 | 143 omin : Ordinal → Ordinal → Ordinal |
| 144 omin x y with trio< x y | |
| 145 omin x y | tri< a ¬b ¬c = x | |
| 146 omin x y | tri> ¬a ¬b c = y | |
| 147 omin x y | tri≈ ¬a refl ¬c = x | |
| 88 | 148 |
| 308 | 149 min1 : {x y z : Ordinal } → z o< x → z o< y → z o< omin x y |
| 221 | 150 min1 {x} {y} {z} z<x z<y with trio< x y |
| 151 min1 {x} {y} {z} z<x z<y | tri< a ¬b ¬c = z<x | |
| 152 min1 {x} {y} {z} z<x z<y | tri≈ ¬a refl ¬c = z<x | |
| 153 min1 {x} {y} {z} z<x z<y | tri> ¬a ¬b c = z<y | |
| 84 | 154 |
| 221 | 155 -- |
| 156 -- max ( osuc x , osuc y ) | |
| 157 -- | |
| 158 | |
| 159 omax : ( x y : Ordinal ) → Ordinal | |
| 160 omax x y with trio< x y | |
| 161 omax x y | tri< a ¬b ¬c = osuc y | |
| 162 omax x y | tri> ¬a ¬b c = osuc x | |
| 163 omax x y | tri≈ ¬a refl ¬c = osuc x | |
| 86 | 164 |
| 221 | 165 omax< : ( x y : Ordinal ) → x o< y → osuc y ≡ omax x y |
| 166 omax< x y lt with trio< x y | |
| 167 omax< x y lt | tri< a ¬b ¬c = refl | |
| 168 omax< x y lt | tri≈ ¬a b ¬c = ⊥-elim (¬a lt ) | |
| 169 omax< x y lt | tri> ¬a ¬b c = ⊥-elim (¬a lt ) | |
| 86 | 170 |
| 221 | 171 omax≡ : ( x y : Ordinal ) → x ≡ y → osuc y ≡ omax x y |
| 172 omax≡ x y eq with trio< x y | |
| 173 omax≡ x y eq | tri< a ¬b ¬c = ⊥-elim (¬b eq ) | |
| 174 omax≡ x y eq | tri≈ ¬a refl ¬c = refl | |
| 175 omax≡ x y eq | tri> ¬a ¬b c = ⊥-elim (¬b eq ) | |
| 91 | 176 |
| 221 | 177 omax-x : ( x y : Ordinal ) → x o< omax x y |
| 178 omax-x x y with trio< x y | |
| 179 omax-x x y | tri< a ¬b ¬c = ordtrans a <-osuc | |
| 180 omax-x x y | tri> ¬a ¬b c = <-osuc | |
| 181 omax-x x y | tri≈ ¬a refl ¬c = <-osuc | |
| 16 | 182 |
| 221 | 183 omax-y : ( x y : Ordinal ) → y o< omax x y |
| 184 omax-y x y with trio< x y | |
| 185 omax-y x y | tri< a ¬b ¬c = <-osuc | |
| 186 omax-y x y | tri> ¬a ¬b c = ordtrans c <-osuc | |
| 187 omax-y x y | tri≈ ¬a refl ¬c = <-osuc | |
| 188 | |
| 189 omxx : ( x : Ordinal ) → omax x x ≡ osuc x | |
| 190 omxx x with trio< x x | |
| 191 omxx x | tri< a ¬b ¬c = ⊥-elim (¬b refl ) | |
| 192 omxx x | tri> ¬a ¬b c = ⊥-elim (¬b refl ) | |
| 193 omxx x | tri≈ ¬a refl ¬c = refl | |
| 194 | |
| 195 omxxx : ( x : Ordinal ) → omax x (omax x x ) ≡ osuc (osuc x) | |
| 196 omxxx x = trans ( cong ( λ k → omax x k ) (omxx x )) (sym ( omax< x (osuc x) <-osuc )) | |
| 197 | |
| 198 open _∧_ | |
| 16 | 199 |
| 326 | 200 o≤-refl : { i j : Ordinal } → i ≡ j → i o≤ j |
| 201 o≤-refl {i} {j} eq = subst (λ k → i o< osuc k ) eq <-osuc | |
| 221 | 202 OrdTrans : Transitive _o≤_ |
| 326 | 203 OrdTrans a≤b b≤c with osuc-≡< a≤b | osuc-≡< b≤c |
| 204 OrdTrans a≤b b≤c | case1 refl | case1 refl = <-osuc | |
| 205 OrdTrans a≤b b≤c | case1 refl | case2 a≤c = ordtrans a≤c <-osuc | |
| 206 OrdTrans a≤b b≤c | case2 a≤c | case1 refl = ordtrans a≤c <-osuc | |
| 207 OrdTrans a≤b b≤c | case2 a<b | case2 b<c = ordtrans (ordtrans a<b b<c) <-osuc | |
|
97
f2b579106770
power set using sup on Def
Shinji KONO <kono@ie.u-ryukyu.ac.jp>
parents:
94
diff
changeset
|
208 |
| 221 | 209 OrdPreorder : Preorder n n n |
| 210 OrdPreorder = record { Carrier = Ordinal | |
| 211 ; _≈_ = _≡_ | |
| 212 ; _∼_ = _o≤_ | |
| 213 ; isPreorder = record { | |
| 214 isEquivalence = record { refl = refl ; sym = sym ; trans = trans } | |
| 326 | 215 ; reflexive = o≤-refl |
| 221 | 216 ; trans = OrdTrans |
| 217 } | |
| 218 } | |
| 165 | 219 |
| 258 | 220 FExists : {m l : Level} → ( ψ : Ordinal → Set m ) |
| 221 | 221 → {p : Set l} ( P : { y : Ordinal } → ψ y → ¬ p ) |
| 222 → (exists : ¬ (∀ y → ¬ ( ψ y ) )) | |
| 223 → ¬ p | |
| 258 | 224 FExists {m} {l} ψ {p} P = contra-position ( λ p y ψy → P {y} ψy p ) |
| 221 | 225 |
| 339 | 226 next< : {x y z : Ordinal} → x o< next z → y o< next x → y o< next z |
| 227 next< {x} {y} {z} x<nz y<nx with trio< y (next z) | |
| 228 next< {x} {y} {z} x<nz y<nx | tri< a ¬b ¬c = a | |
|
348
08d94fec239c
Limit ordinal and possible OD bound
Shinji KONO <kono@ie.u-ryukyu.ac.jp>
parents:
347
diff
changeset
|
229 next< {x} {y} {z} x<nz y<nx | tri≈ ¬a b ¬c = ⊥-elim (¬nx<nx x<nz (subst (λ k → k o< next x) b y<nx) |
|
08d94fec239c
Limit ordinal and possible OD bound
Shinji KONO <kono@ie.u-ryukyu.ac.jp>
parents:
347
diff
changeset
|
230 (λ w nz=ow → o<¬≡ nz=ow (subst₂ (λ j k → j o< k ) (sym nz=ow) nz=ow (osuc<nx (subst (λ k → w o< k ) (sym nz=ow) <-osuc) )))) |
|
08d94fec239c
Limit ordinal and possible OD bound
Shinji KONO <kono@ie.u-ryukyu.ac.jp>
parents:
347
diff
changeset
|
231 next< {x} {y} {z} x<nz y<nx | tri> ¬a ¬b c = ⊥-elim (¬nx<nx x<nz (ordtrans c y<nx ) |
|
08d94fec239c
Limit ordinal and possible OD bound
Shinji KONO <kono@ie.u-ryukyu.ac.jp>
parents:
347
diff
changeset
|
232 (λ w nz=ow → o<¬≡ (sym nz=ow) (osuc<nx (subst (λ k → w o< k ) (sym nz=ow) <-osuc )))) |
| 339 | 233 |
| 342 | 234 osuc< : {x y : Ordinal} → osuc x ≡ y → x o< y |
| 235 osuc< {x} {y} refl = <-osuc | |
| 236 | |
| 340 | 237 nexto=n : {x y : Ordinal} → x o< next (osuc y) → x o< next y |
|
348
08d94fec239c
Limit ordinal and possible OD bound
Shinji KONO <kono@ie.u-ryukyu.ac.jp>
parents:
347
diff
changeset
|
238 nexto=n {x} {y} x<noy = next< (osuc<nx x<nx) x<noy |
| 340 | 239 |
| 341 | 240 nexto≡ : {x : Ordinal} → next x ≡ next (osuc x) |
| 241 nexto≡ {x} with trio< (next x) (next (osuc x) ) | |
| 342 | 242 -- next x o< next (osuc x ) -> 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 |
|
348
08d94fec239c
Limit ordinal and possible OD bound
Shinji KONO <kono@ie.u-ryukyu.ac.jp>
parents:
347
diff
changeset
|
243 nexto≡ {x} | tri< a ¬b ¬c = ⊥-elim (¬nx<nx (osuc<nx x<nx ) a |
|
08d94fec239c
Limit ordinal and possible OD bound
Shinji KONO <kono@ie.u-ryukyu.ac.jp>
parents:
347
diff
changeset
|
244 (λ z eq → o<¬≡ (sym eq) (osuc<nx (osuc< (sym eq))))) |
| 341 | 245 nexto≡ {x} | tri≈ ¬a b ¬c = b |
| 342 | 246 -- next (osuc x) o< next x -> osuc x o< next (osuc x) o< next x -> next (osuc x) ≡ osuc z -> z o o< next (osuc x) ... |
|
348
08d94fec239c
Limit ordinal and possible OD bound
Shinji KONO <kono@ie.u-ryukyu.ac.jp>
parents:
347
diff
changeset
|
247 nexto≡ {x} | tri> ¬a ¬b c = ⊥-elim (¬nx<nx (ordtrans <-osuc x<nx) c |
|
08d94fec239c
Limit ordinal and possible OD bound
Shinji KONO <kono@ie.u-ryukyu.ac.jp>
parents:
347
diff
changeset
|
248 (λ z eq → o<¬≡ (sym eq) (osuc<nx (osuc< (sym eq))))) |
| 346 | 249 |
| 352 | 250 next-is-limit : {x y : Ordinal} → ¬ (next x ≡ osuc y) |
| 251 next-is-limit {x} {y} eq = o<¬≡ (sym eq) (osuc<nx y<nx) where | |
| 252 y<nx : y o< next x | |
| 253 y<nx = osuc< (sym eq) | |
| 254 | |
| 309 | 255 record OrdinalSubset (maxordinal : Ordinal) : Set (suc n) where |
| 256 field | |
| 257 os→ : (x : Ordinal) → x o< maxordinal → Ordinal | |
| 258 os← : Ordinal → Ordinal | |
| 259 os←limit : (x : Ordinal) → os← x o< maxordinal | |
| 260 os-iso← : {x : Ordinal} → os→ (os← x) (os←limit x) ≡ x | |
| 261 os-iso→ : {x : Ordinal} → (lt : x o< maxordinal ) → os← (os→ x lt) ≡ x | |
| 262 | |
| 361 | 263 module o≤-Reasoning {n : Level} (O : Ordinals {n} ) where |
| 264 | |
| 265 open inOrdinal O | |
| 266 | |
| 267 resp-o< : Ordinals._o<_ O Respects₂ _≡_ | |
| 268 resp-o< = resp₂ _o<_ | |
| 269 | |
| 270 trans1 : {i j k : Ordinal} → i o< j → j o< osuc k → i o< k | |
| 271 trans1 {i} {j} {k} i<j j<ok with osuc-≡< j<ok | |
| 272 trans1 {i} {j} {k} i<j j<ok | case1 refl = i<j | |
| 273 trans1 {i} {j} {k} i<j j<ok | case2 j<k = ordtrans i<j j<k | |
| 274 | |
| 275 trans2 : {i j k : Ordinal} → i o< osuc j → j o< k → i o< k | |
| 276 trans2 {i} {j} {k} i<oj j<k with osuc-≡< i<oj | |
| 277 trans2 {i} {j} {k} i<oj j<k | case1 refl = j<k | |
| 278 trans2 {i} {j} {k} i<oj j<k | case2 i<j = ordtrans i<j j<k | |
| 279 | |
| 280 open import Relation.Binary.Reasoning.Base.Triple {n} {_} {_} {_} {Ordinal } {_≡_} {_o≤_} {_o<_} | |
| 281 (Preorder.isPreorder OrdPreorder) | |
| 282 ordtrans --<-trans | |
| 283 (resp₂ _o<_) --(resp₂ _<_) | |
| 284 (λ x → ordtrans x <-osuc ) --<⇒≤ | |
| 285 trans1 --<-transˡ | |
| 286 trans2 --<-transʳ | |
| 287 public | |
| 288 hiding (_≈⟨_⟩_) | |
| 289 |