Mercurial > hg > Members > kono > Proof > ZF-in-agda
annotate src/OrdUtil.agda @ 1100:c90eec304cfa
PFOD
| author | Shinji KONO <kono@ie.u-ryukyu.ac.jp> |
|---|---|
| date | Mon, 26 Dec 2022 14:00:57 +0900 |
| parents | a8d6ac036d88 |
| children | 619e68271cf8 ad9ed7c4a0b3 |
| rev | line source |
|---|---|
| 431 | 1 open import Level |
| 2 open import Ordinals | |
| 3 module OrdUtil {n : Level} (O : Ordinals {n} ) where | |
| 4 | |
| 5 open import logic | |
| 6 open import nat | |
| 815 | 7 open import Data.Nat renaming ( zero to Zero ; suc to Suc ; ℕ to Nat ; _⊔_ to _n⊔_ ) |
| 431 | 8 open import Data.Empty |
| 9 open import Relation.Binary.PropositionalEquality | |
| 10 open import Relation.Nullary | |
| 11 open import Relation.Binary hiding (_⇔_) | |
| 12 | |
| 13 open Ordinals.Ordinals O | |
| 815 | 14 open Ordinals.IsOrdinals isOrdinal |
| 15 open Ordinals.IsNext isNext | |
| 431 | 16 |
| 815 | 17 o<-dom : { x y : Ordinal } → x o< y → Ordinal |
| 431 | 18 o<-dom {x} _ = x |
| 19 | |
| 815 | 20 o<-cod : { x y : Ordinal } → x o< y → Ordinal |
| 431 | 21 o<-cod {_} {y} _ = y |
| 22 | |
| 23 o<-subst : {Z X z x : Ordinal } → Z o< X → Z ≡ z → X ≡ x → z o< x | |
| 24 o<-subst df refl refl = df | |
| 25 | |
| 26 o<¬≡ : { ox oy : Ordinal } → ox ≡ oy → ox o< oy → ⊥ | |
| 27 o<¬≡ {ox} {oy} eq lt with trio< ox oy | |
| 28 o<¬≡ {ox} {oy} eq lt | tri< a ¬b ¬c = ¬b eq | |
| 29 o<¬≡ {ox} {oy} eq lt | tri≈ ¬a b ¬c = ¬a lt | |
| 30 o<¬≡ {ox} {oy} eq lt | tri> ¬a ¬b c = ¬b eq | |
| 31 | |
| 32 o<> : {x y : Ordinal } → y o< x → x o< y → ⊥ | |
| 33 o<> {ox} {oy} lt tl with trio< ox oy | |
| 34 o<> {ox} {oy} lt tl | tri< a ¬b ¬c = ¬c lt | |
| 35 o<> {ox} {oy} lt tl | tri≈ ¬a b ¬c = ¬a tl | |
| 36 o<> {ox} {oy} lt tl | tri> ¬a ¬b c = ¬a tl | |
| 37 | |
| 830 | 38 o≤> : { x y : Ordinal } → y o< osuc x → x o< y → ⊥ |
| 39 o≤> {x} {y} y<ox x<y with osuc-≡< y<ox | |
| 40 o≤> {x} {y} y<ox x<y | case1 refl = o<¬≡ refl x<y | |
| 41 o≤> {x} {y} y<ox x<y | case2 y<x = o<> x<y y<x | |
| 431 | 42 |
| 712 | 43 open _∧_ |
| 44 | |
| 45 ¬p<x<op : { p b : Ordinal } → ¬ ( (p o< b ) ∧ (b o< osuc p ) ) | |
| 46 ¬p<x<op {p} {b} P with osuc-≡< (proj2 P) | |
| 815 | 47 ... | case1 eq = o<¬≡ (sym eq) (proj1 P) |
| 48 ... | case2 lt = o<> lt (proj1 P) | |
| 712 | 49 |
| 715 | 50 b<x→0<x : { p b : Ordinal } → p o< b → o∅ o< b |
| 51 b<x→0<x {p} {b} p<b with trio< o∅ b | |
| 52 ... | tri< a ¬b ¬c = a | |
| 53 ... | tri≈ ¬a 0=b ¬c = ⊥-elim ( ¬x<0 ( subst (λ k → p o< k) (sym 0=b) p<b ) ) | |
| 54 ... | tri> ¬a ¬b c = ⊥-elim ( ¬x<0 c ) | |
| 55 | |
| 815 | 56 ob<x : {b x : Ordinal} (lim : ¬ (Oprev Ordinal osuc x ) ) (b<x : b o< x ) → osuc b o< x |
| 57 ob<x {b} {x} lim b<x with trio< (osuc b) x | |
| 58 ... | tri< a ¬b ¬c = a | |
| 59 ... | tri≈ ¬a ob=x ¬c = ⊥-elim ( lim record { oprev = b ; oprev=x = ob=x } ) | |
| 60 ... | tri> ¬a ¬b c = ⊥-elim ( ¬p<x<op ⟪ b<x , c ⟫ ) | |
| 61 | |
| 744 | 62 |
| 815 | 63 pxo<x : {x : Ordinal} (op : Oprev Ordinal osuc x) → Oprev.oprev op o< x |
| 64 pxo<x {x} op with trio< (Oprev.oprev op) x | |
| 65 ... | tri< a ¬b ¬c = a | |
| 66 ... | tri≈ ¬a b ¬c = ⊥-elim ( o<¬≡ (trans b (sym (Oprev.oprev=x op))) <-osuc ) | |
| 67 ... | tri> ¬a ¬b c = ⊥-elim ( o<> c (subst₂ (λ j k → j o< k ) refl (Oprev.oprev=x op) <-osuc ) ) | |
| 68 | |
| 69 pxo≤x : {x : Ordinal} (op : Oprev Ordinal osuc x) → Oprev.oprev op o< osuc x | |
| 70 pxo≤x {x} op = ordtrans (pxo<x {x} op ) <-osuc | |
| 71 | |
| 850 | 72 |
| 815 | 73 osucc : {ox oy : Ordinal } → oy o< ox → osuc oy o< osuc ox |
| 431 | 74 osucc {ox} {oy} oy<ox with trio< (osuc oy) ox |
| 75 osucc {ox} {oy} oy<ox | tri< a ¬b ¬c = ordtrans a <-osuc | |
| 76 osucc {ox} {oy} oy<ox | tri≈ ¬a refl ¬c = <-osuc | |
| 77 osucc {ox} {oy} oy<ox | tri> ¬a ¬b c with osuc-≡< c | |
| 78 osucc {ox} {oy} oy<ox | tri> ¬a ¬b c | case1 eq = ⊥-elim (o<¬≡ (sym eq) oy<ox) | |
| 79 osucc {ox} {oy} oy<ox | tri> ¬a ¬b c | case2 lt = ⊥-elim (o<> lt oy<ox) | |
| 80 | |
| 815 | 81 osucprev : {ox oy : Ordinal } → osuc oy o< osuc ox → oy o< ox |
| 431 | 82 osucprev {ox} {oy} oy<ox with trio< oy ox |
| 83 osucprev {ox} {oy} oy<ox | tri< a ¬b ¬c = a | |
| 84 osucprev {ox} {oy} oy<ox | tri≈ ¬a b ¬c = ⊥-elim (o<¬≡ (cong (λ k → osuc k) b) oy<ox ) | |
| 85 osucprev {ox} {oy} oy<ox | tri> ¬a ¬b c = ⊥-elim (o<> (osucc c) oy<ox ) | |
| 86 | |
| 653 | 87 ordtrans≤-< : {ox oy oz : Ordinal } → ox o< osuc oy → oy o< oz → ox o< oz |
| 88 ordtrans≤-< {ox} {oy} {oz} x≤y y<z with osuc-≡< x≤y | |
| 89 ... | case1 x=y = subst ( λ k → k o< oz ) (sym x=y) y<z | |
| 90 ... | case2 x<y = ordtrans x<y y<z | |
| 91 | |
|
732
ddeb107b6f71
bchain can be reached from upwords by f. so it is worng.
Shinji KONO <kono@ie.u-ryukyu.ac.jp>
parents:
715
diff
changeset
|
92 ordtrans<-≤ : {ox oy oz : Ordinal } → ox o< oy → oy o< osuc oz → ox o< oz |
|
ddeb107b6f71
bchain can be reached from upwords by f. so it is worng.
Shinji KONO <kono@ie.u-ryukyu.ac.jp>
parents:
715
diff
changeset
|
93 ordtrans<-≤ {ox} {oy} {oz} x<y y≤z with osuc-≡< y≤z |
|
ddeb107b6f71
bchain can be reached from upwords by f. so it is worng.
Shinji KONO <kono@ie.u-ryukyu.ac.jp>
parents:
715
diff
changeset
|
94 ... | case1 x=y = subst ( λ k → ox o< k ) (x=y) x<y |
|
ddeb107b6f71
bchain can be reached from upwords by f. so it is worng.
Shinji KONO <kono@ie.u-ryukyu.ac.jp>
parents:
715
diff
changeset
|
95 ... | case2 y<z = ordtrans x<y y<z |
|
ddeb107b6f71
bchain can be reached from upwords by f. so it is worng.
Shinji KONO <kono@ie.u-ryukyu.ac.jp>
parents:
715
diff
changeset
|
96 |
| 789 | 97 o∅≤z : {z : Ordinal } → o∅ o< (osuc z) |
| 98 o∅≤z {z} = b<x→0<x ( <-osuc ) | |
| 431 | 99 |
| 100 osuc2 : ( x y : Ordinal ) → ( osuc x o< osuc (osuc y )) ⇔ (x o< osuc y) | |
| 101 proj2 (osuc2 x y) lt = osucc lt | |
| 102 proj1 (osuc2 x y) ox<ooy with osuc-≡< ox<ooy | |
| 103 proj1 (osuc2 x y) ox<ooy | case1 ox=oy = o<-subst <-osuc refl ox=oy | |
| 815 | 104 proj1 (osuc2 x y) ox<ooy | case2 ox<oy = ordtrans <-osuc ox<oy |
| 431 | 105 |
| 538 | 106 o≡? : (x y : Ordinal) → Dec ( x ≡ y ) |
| 107 o≡? x y with trio< x y | |
| 108 ... | tri< a ¬b ¬c = no ¬b | |
| 109 ... | tri≈ ¬a b ¬c = yes b | |
| 110 ... | tri> ¬a ¬b c = no ¬b | |
| 111 | |
| 431 | 112 _o≤_ : Ordinal → Ordinal → Set n |
| 113 a o≤ b = a o< osuc b -- (a ≡ b) ∨ ( a o< b ) | |
| 114 | |
| 653 | 115 o<→≤ : {a b : Ordinal} → a o< b → a o≤ b |
| 116 o<→≤ {a} {b} lt with trio< a (osuc b) | |
| 117 ... | tri< a₁ ¬b ¬c = a₁ | |
| 118 ... | tri≈ ¬a b₁ ¬c = ⊥-elim (¬a (ordtrans lt <-osuc ) ) | |
| 119 ... | tri> ¬a ¬b c = ⊥-elim (¬a (ordtrans lt <-osuc ) ) | |
| 120 | |
| 611 | 121 -- o<-irr : { x y : Ordinal } → { lt lt1 : x o< y } → lt ≡ lt1 |
| 431 | 122 |
| 123 xo<ab : {oa ob : Ordinal } → ( {ox : Ordinal } → ox o< oa → ox o< ob ) → oa o< osuc ob | |
| 124 xo<ab {oa} {ob} a→b with trio< oa ob | |
| 125 xo<ab {oa} {ob} a→b | tri< a ¬b ¬c = ordtrans a <-osuc | |
| 126 xo<ab {oa} {ob} a→b | tri≈ ¬a refl ¬c = <-osuc | |
| 127 xo<ab {oa} {ob} a→b | tri> ¬a ¬b c = ⊥-elim ( o<¬≡ refl (a→b c ) ) | |
| 128 | |
| 129 maxα : Ordinal → Ordinal → Ordinal | |
| 130 maxα x y with trio< x y | |
| 131 maxα x y | tri< a ¬b ¬c = y | |
| 132 maxα x y | tri> ¬a ¬b c = x | |
| 133 maxα x y | tri≈ ¬a refl ¬c = x | |
| 134 | |
| 135 omin : Ordinal → Ordinal → Ordinal | |
| 136 omin x y with trio< x y | |
| 137 omin x y | tri< a ¬b ¬c = x | |
| 138 omin x y | tri> ¬a ¬b c = y | |
| 139 omin x y | tri≈ ¬a refl ¬c = x | |
| 140 | |
| 141 min1 : {x y z : Ordinal } → z o< x → z o< y → z o< omin x y | |
| 142 min1 {x} {y} {z} z<x z<y with trio< x y | |
| 143 min1 {x} {y} {z} z<x z<y | tri< a ¬b ¬c = z<x | |
| 144 min1 {x} {y} {z} z<x z<y | tri≈ ¬a refl ¬c = z<x | |
| 145 min1 {x} {y} {z} z<x z<y | tri> ¬a ¬b c = z<y | |
| 146 | |
| 147 -- | |
| 148 -- max ( osuc x , osuc y ) | |
| 149 -- | |
| 150 | |
| 815 | 151 omax : ( x y : Ordinal ) → Ordinal |
| 431 | 152 omax x y with trio< x y |
| 153 omax x y | tri< a ¬b ¬c = osuc y | |
| 154 omax x y | tri> ¬a ¬b c = osuc x | |
| 155 omax x y | tri≈ ¬a refl ¬c = osuc x | |
| 156 | |
| 157 omax< : ( x y : Ordinal ) → x o< y → osuc y ≡ omax x y | |
| 158 omax< x y lt with trio< x y | |
| 159 omax< x y lt | tri< a ¬b ¬c = refl | |
| 160 omax< x y lt | tri≈ ¬a b ¬c = ⊥-elim (¬a lt ) | |
| 161 omax< x y lt | tri> ¬a ¬b c = ⊥-elim (¬a lt ) | |
| 162 | |
| 163 omax≤ : ( x y : Ordinal ) → x o≤ y → osuc y ≡ omax x y | |
| 164 omax≤ x y le with trio< x y | |
| 165 omax≤ x y le | tri< a ¬b ¬c = refl | |
| 166 omax≤ x y le | tri≈ ¬a refl ¬c = refl | |
| 167 omax≤ x y le | tri> ¬a ¬b c with osuc-≡< le | |
| 168 omax≤ x y le | tri> ¬a ¬b c | case1 eq = ⊥-elim (¬b eq) | |
| 169 omax≤ x y le | tri> ¬a ¬b c | case2 x<y = ⊥-elim (¬a x<y) | |
| 170 | |
| 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 ) | |
| 176 | |
| 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 | |
| 182 | |
| 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 _∧_ | |
| 199 | |
| 625 | 200 o≤-refl0 : { i j : Ordinal } → i ≡ j → i o≤ j |
| 201 o≤-refl0 {i} {j} eq = subst (λ k → i o< osuc k ) eq <-osuc | |
| 202 | |
| 203 o≤-refl : { i : Ordinal } → i o≤ i | |
| 204 o≤-refl {i} = subst (λ k → i o< osuc k ) refl <-osuc | |
| 205 | |
| 674 | 206 o≤? : (x y : Ordinal) → Dec ( x o≤ y ) |
| 207 o≤? x y with trio< x y | |
| 208 ... | tri< a ¬b ¬c = yes (ordtrans a <-osuc) | |
| 209 ... | tri≈ ¬a b ¬c = yes (o≤-refl0 b) | |
| 830 | 210 ... | tri> ¬a ¬b c = no (λ n → o≤> n c ) |
| 674 | 211 |
| 683 | 212 o¬≤→< : {x z : Ordinal} → ¬ (x o< osuc z) → z o< x |
| 213 o¬≤→< {x} {z} not with trio< z x | |
| 214 ... | tri< a ¬b ¬c = a | |
| 215 ... | tri≈ ¬a b ¬c = ⊥-elim (not (o≤-refl0 (sym b))) | |
| 216 ... | tri> ¬a ¬b c = ⊥-elim (not (o<→≤ c )) | |
| 217 | |
| 850 | 218 b≤px∨b=x : {b x : Ordinal } → (op : Oprev Ordinal osuc x ) → b o≤ x → (b o≤ (Oprev.oprev op) ) ∨ (b ≡ x ) |
| 219 b≤px∨b=x {b} {x} op b≤x with trio< b (Oprev.oprev op) | |
| 220 ... | tri< a ¬b ¬c = case1 (o<→≤ a) | |
| 221 ... | tri≈ ¬a b ¬c = case1 (o≤-refl0 b) | |
| 222 ... | tri> ¬a ¬b px<b with osuc-≡< b≤x | |
| 223 ... | case1 eq = case2 eq | |
| 224 ... | case2 b<x = ⊥-elim ( ¬p<x<op ⟪ px<b , subst (λ k → b o< k ) (sym (Oprev.oprev=x op)) b<x ⟫ ) | |
| 225 | |
| 1048 | 226 x<y∨y≤x : (x sp1 : Ordinal ) → ( x o< sp1 ) ∨ ( sp1 o≤ x ) |
| 227 x<y∨y≤x x sp1 with trio< x sp1 | |
| 228 ... | tri< a ¬b ¬c = case1 a | |
| 229 ... | tri≈ ¬a b ¬c = case2 (o≤-refl0 (sym b)) | |
| 230 ... | tri> ¬a ¬b c = case2 (o<→≤ c) | |
| 231 | |
| 431 | 232 OrdTrans : Transitive _o≤_ |
| 233 OrdTrans a≤b b≤c with osuc-≡< a≤b | osuc-≡< b≤c | |
| 234 OrdTrans a≤b b≤c | case1 refl | case1 refl = <-osuc | |
| 235 OrdTrans a≤b b≤c | case1 refl | case2 a≤c = ordtrans a≤c <-osuc | |
| 236 OrdTrans a≤b b≤c | case2 a≤c | case1 refl = ordtrans a≤c <-osuc | |
| 237 OrdTrans a≤b b≤c | case2 a<b | case2 b<c = ordtrans (ordtrans a<b b<c) <-osuc | |
| 238 | |
| 239 OrdPreorder : Preorder n n n | |
| 240 OrdPreorder = record { Carrier = Ordinal | |
| 815 | 241 ; _≈_ = _≡_ |
| 431 | 242 ; _∼_ = _o≤_ |
| 243 ; isPreorder = record { | |
| 244 isEquivalence = record { refl = refl ; sym = sym ; trans = trans } | |
| 625 | 245 ; reflexive = o≤-refl0 |
| 815 | 246 ; trans = OrdTrans |
| 431 | 247 } |
| 248 } | |
| 249 | |
| 815 | 250 FExists : {m l : Level} → ( ψ : Ordinal → Set m ) |
| 431 | 251 → {p : Set l} ( P : { y : Ordinal } → ψ y → ¬ p ) |
| 252 → (exists : ¬ (∀ y → ¬ ( ψ y ) )) | |
| 253 → ¬ p | |
| 815 | 254 FExists {m} {l} ψ {p} P = contra-position ( λ p y ψy → P {y} ψy p ) |
| 431 | 255 |
| 256 nexto∅ : {x : Ordinal} → o∅ o< next x | |
| 257 nexto∅ {x} with trio< o∅ x | |
| 258 nexto∅ {x} | tri< a ¬b ¬c = ordtrans a x<nx | |
| 259 nexto∅ {x} | tri≈ ¬a b ¬c = subst (λ k → k o< next x) (sym b) x<nx | |
| 260 nexto∅ {x} | tri> ¬a ¬b c = ⊥-elim ( ¬x<0 c ) | |
| 261 | |
| 262 next< : {x y z : Ordinal} → x o< next z → y o< next x → y o< next z | |
| 263 next< {x} {y} {z} x<nz y<nx with trio< y (next z) | |
| 264 next< {x} {y} {z} x<nz y<nx | tri< a ¬b ¬c = a | |
| 265 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) | |
| 266 (λ 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) )))) | |
| 267 next< {x} {y} {z} x<nz y<nx | tri> ¬a ¬b c = ⊥-elim (¬nx<nx x<nz (ordtrans c y<nx ) | |
| 268 (λ w nz=ow → o<¬≡ (sym nz=ow) (osuc<nx (subst (λ k → w o< k ) (sym nz=ow) <-osuc )))) | |
| 269 | |
| 270 osuc< : {x y : Ordinal} → osuc x ≡ y → x o< y | |
| 815 | 271 osuc< {x} {y} refl = <-osuc |
| 431 | 272 |
| 815 | 273 nexto=n : {x y : Ordinal} → x o< next (osuc y) → x o< next y |
| 431 | 274 nexto=n {x} {y} x<noy = next< (osuc<nx x<nx) x<noy |
| 275 | |
| 815 | 276 nexto≡ : {x : Ordinal} → next x ≡ next (osuc x) |
| 277 nexto≡ {x} with trio< (next x) (next (osuc x) ) | |
| 431 | 278 -- 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 |
| 279 nexto≡ {x} | tri< a ¬b ¬c = ⊥-elim (¬nx<nx (osuc<nx x<nx ) a | |
| 280 (λ z eq → o<¬≡ (sym eq) (osuc<nx (osuc< (sym eq))))) | |
| 281 nexto≡ {x} | tri≈ ¬a b ¬c = b | |
| 282 -- 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) ... | |
| 283 nexto≡ {x} | tri> ¬a ¬b c = ⊥-elim (¬nx<nx (ordtrans <-osuc x<nx) c | |
| 284 (λ z eq → o<¬≡ (sym eq) (osuc<nx (osuc< (sym eq))))) | |
| 285 | |
| 286 next-is-limit : {x y : Ordinal} → ¬ (next x ≡ osuc y) | |
| 287 next-is-limit {x} {y} eq = o<¬≡ (sym eq) (osuc<nx y<nx) where | |
| 288 y<nx : y o< next x | |
| 289 y<nx = osuc< (sym eq) | |
| 290 | |
| 291 omax<next : {x y : Ordinal} → x o< y → omax x y o< next y | |
| 292 omax<next {x} {y} x<y = subst (λ k → k o< next y ) (omax< _ _ x<y ) (osuc<nx x<nx) | |
| 293 | |
| 294 x<ny→≡next : {x y : Ordinal} → x o< y → y o< next x → next x ≡ next y | |
| 815 | 295 x<ny→≡next {x} {y} x<y y<nx with trio< (next x) (next y) |
| 431 | 296 x<ny→≡next {x} {y} x<y y<nx | tri< a ¬b ¬c = -- x < y < next x < next y ∧ next x = osuc z |
| 815 | 297 ⊥-elim ( ¬nx<nx y<nx a (λ z eq → o<¬≡ (sym eq) (osuc<nx (subst (λ k → z o< k ) (sym eq) <-osuc )))) |
| 431 | 298 x<ny→≡next {x} {y} x<y y<nx | tri≈ ¬a b ¬c = b |
| 299 x<ny→≡next {x} {y} x<y y<nx | tri> ¬a ¬b c = -- x < y < next y < next x | |
| 815 | 300 ⊥-elim ( ¬nx<nx (ordtrans x<y x<nx) c (λ z eq → o<¬≡ (sym eq) (osuc<nx (subst (λ k → z o< k ) (sym eq) <-osuc )))) |
| 431 | 301 |
| 302 ≤next : {x y : Ordinal} → x o≤ y → next x o≤ next y | |
| 303 ≤next {x} {y} x≤y with trio< (next x) y | |
| 304 ≤next {x} {y} x≤y | tri< a ¬b ¬c = ordtrans a (ordtrans x<nx <-osuc ) | |
| 305 ≤next {x} {y} x≤y | tri≈ ¬a refl ¬c = (ordtrans x<nx <-osuc ) | |
| 306 ≤next {x} {y} x≤y | tri> ¬a ¬b c with osuc-≡< x≤y | |
| 625 | 307 ≤next {x} {y} x≤y | tri> ¬a ¬b c | case1 refl = o≤-refl -- x = y < next x |
| 815 | 308 ≤next {x} {y} x≤y | tri> ¬a ¬b c | case2 x<y = o≤-refl0 (x<ny→≡next x<y c) -- x ≤ y < next x |
| 431 | 309 |
| 310 x<ny→≤next : {x y : Ordinal} → x o< next y → next x o≤ next y | |
| 311 x<ny→≤next {x} {y} x<ny with trio< x y | |
| 312 x<ny→≤next {x} {y} x<ny | tri< a ¬b ¬c = ≤next (ordtrans a <-osuc ) | |
| 815 | 313 x<ny→≤next {x} {y} x<ny | tri≈ ¬a refl ¬c = o≤-refl |
| 625 | 314 x<ny→≤next {x} {y} x<ny | tri> ¬a ¬b c = o≤-refl0 (sym ( x<ny→≡next c x<ny )) |
| 431 | 315 |
| 316 omax<nomax : {x y : Ordinal} → omax x y o< next (omax x y ) | |
| 317 omax<nomax {x} {y} with trio< x y | |
| 318 omax<nomax {x} {y} | tri< a ¬b ¬c = subst (λ k → osuc y o< k ) nexto≡ (osuc<nx x<nx ) | |
| 319 omax<nomax {x} {y} | tri≈ ¬a refl ¬c = subst (λ k → osuc x o< k ) nexto≡ (osuc<nx x<nx ) | |
| 320 omax<nomax {x} {y} | tri> ¬a ¬b c = subst (λ k → osuc x o< k ) nexto≡ (osuc<nx x<nx ) | |
| 321 | |
| 322 omax<nx : {x y z : Ordinal} → x o< next z → y o< next z → omax x y o< next z | |
| 323 omax<nx {x} {y} {z} x<nz y<nz with trio< x y | |
| 324 omax<nx {x} {y} {z} x<nz y<nz | tri< a ¬b ¬c = osuc<nx y<nz | |
| 325 omax<nx {x} {y} {z} x<nz y<nz | tri≈ ¬a refl ¬c = osuc<nx y<nz | |
| 326 omax<nx {x} {y} {z} x<nz y<nz | tri> ¬a ¬b c = osuc<nx x<nz | |
| 327 | |
| 328 nn<omax : {x nx ny : Ordinal} → x o< next nx → x o< next ny → x o< next (omax nx ny) | |
| 329 nn<omax {x} {nx} {ny} xnx xny with trio< nx ny | |
| 330 nn<omax {x} {nx} {ny} xnx xny | tri< a ¬b ¬c = subst (λ k → x o< k ) nexto≡ xny | |
| 331 nn<omax {x} {nx} {ny} xnx xny | tri≈ ¬a refl ¬c = subst (λ k → x o< k ) nexto≡ xny | |
| 332 nn<omax {x} {nx} {ny} xnx xny | tri> ¬a ¬b c = subst (λ k → x o< k ) nexto≡ xnx | |
| 333 | |
| 334 record OrdinalSubset (maxordinal : Ordinal) : Set (suc n) where | |
| 335 field | |
| 336 os→ : (x : Ordinal) → x o< maxordinal → Ordinal | |
| 337 os← : Ordinal → Ordinal | |
| 338 os←limit : (x : Ordinal) → os← x o< maxordinal | |
| 339 os-iso← : {x : Ordinal} → os→ (os← x) (os←limit x) ≡ x | |
| 340 os-iso→ : {x : Ordinal} → (lt : x o< maxordinal ) → os← (os→ x lt) ≡ x | |
| 341 | |
| 342 module o≤-Reasoning {n : Level} (O : Ordinals {n} ) where | |
| 343 | |
| 344 -- open inOrdinal O | |
| 345 | |
| 346 resp-o< : _o<_ Respects₂ _≡_ | |
| 347 resp-o< = resp₂ _o<_ | |
| 348 | |
| 349 trans1 : {i j k : Ordinal} → i o< j → j o< osuc k → i o< k | |
| 350 trans1 {i} {j} {k} i<j j<ok with osuc-≡< j<ok | |
| 351 trans1 {i} {j} {k} i<j j<ok | case1 refl = i<j | |
| 352 trans1 {i} {j} {k} i<j j<ok | case2 j<k = ordtrans i<j j<k | |
| 353 | |
| 354 trans2 : {i j k : Ordinal} → i o< osuc j → j o< k → i o< k | |
| 355 trans2 {i} {j} {k} i<oj j<k with osuc-≡< i<oj | |
| 356 trans2 {i} {j} {k} i<oj j<k | case1 refl = j<k | |
| 357 trans2 {i} {j} {k} i<oj j<k | case2 i<j = ordtrans i<j j<k | |
| 358 | |
| 815 | 359 open import Relation.Binary.Reasoning.Base.Triple |
| 360 (Preorder.isPreorder OrdPreorder) | |
| 431 | 361 ordtrans --<-trans |
| 362 (resp₂ _o<_) --(resp₂ _<_) | |
| 363 (λ x → ordtrans x <-osuc ) --<⇒≤ | |
| 364 trans1 --<-transˡ | |
| 365 trans2 --<-transʳ | |
| 366 public | |
| 367 -- hiding (_≈⟨_⟩_) | |
| 368 |