Mercurial > hg > Members > kono > Proof > ZF-in-agda
diff Ordinals.agda @ 348:08d94fec239c
Limit ordinal and possible OD bound
author | Shinji KONO <kono@ie.u-ryukyu.ac.jp> |
---|---|
date | Tue, 14 Jul 2020 07:59:17 +0900 |
parents | cfecd05a4061 |
children | adc3c3a37308 e27769992399 |
line wrap: on
line diff
--- a/Ordinals.agda Mon Jul 13 22:40:37 2020 +0900 +++ b/Ordinals.agda Tue Jul 14 07:59:17 2020 +0900 @@ -20,9 +20,7 @@ ¬x<0 : { x : ord } → ¬ ( x o< o∅ ) <-osuc : { x : ord } → x o< osuc x osuc-≡< : { a x : ord } → x o< osuc a → (x ≡ a ) ∨ (x o< a) - not-limit : ( x : ord ) → Dec ( ¬ ((y : ord) → ¬ (x ≡ osuc y) )) - next-limit : { y : ord } → (y o< next y ) ∧ ((x : ord) → x o< next y → osuc x o< next y ) ∧ - ( (x : ord) → y o< x → x o< next y → ¬ ((z : ord) → ¬ (x ≡ osuc z) )) + not-limit-p : ( x : ord ) → Dec ( ¬ ((y : ord) → ¬ (x ≡ osuc y) )) TransFinite : { ψ : ord → Set n } → ( (x : ord) → ( (y : ord ) → y o< x → ψ y ) → ψ x ) → ∀ (x : ord) → ψ x @@ -30,6 +28,11 @@ → ( (x : ord) → ( (y : ord ) → y o< x → ψ y ) → ψ x ) → ∀ (x : ord) → ψ x +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 + field + x<nx : { y : ord } → (y o< next y ) + osuc<nx : { x y : ord } → x o< next y → osuc x o< next y + ¬nx<nx : {x y : ord} → y o< x → x o< next y → ¬ ((z : ord) → ¬ (x ≡ osuc z)) record Ordinals {n : Level} : Set (suc (suc n)) where field @@ -39,6 +42,7 @@ _o<_ : ord → ord → Set n next : ord → ord isOrdinal : IsOrdinals ord o∅ osuc _o<_ next + isNext : IsNext ord o∅ osuc _o<_ next module inOrdinal {n : Level} (O : Ordinals {n} ) where @@ -62,7 +66,10 @@ <-osuc = IsOrdinals.<-osuc (Ordinals.isOrdinal O) TransFinite = IsOrdinals.TransFinite (Ordinals.isOrdinal O) TransFinite1 = IsOrdinals.TransFinite1 (Ordinals.isOrdinal O) - next-limit = IsOrdinals.next-limit (Ordinals.isOrdinal O) + + x<nx = IsNext.x<nx (Ordinals.isNext O) + osuc<nx = IsNext.osuc<nx (Ordinals.isNext O) + ¬nx<nx = IsNext.¬nx<nx (Ordinals.isNext O) o<-dom : { x y : Ordinal } → x o< y → Ordinal o<-dom {x} _ = x @@ -223,43 +230,26 @@ next< : {x y z : Ordinal} → x o< next z → y o< next x → y o< next z next< {x} {y} {z} x<nz y<nx with trio< y (next z) next< {x} {y} {z} x<nz y<nx | tri< a ¬b ¬c = a - next< {x} {y} {z} x<nz y<nx | tri≈ ¬a b ¬c = ⊥-elim ((proj2 (proj2 next-limit)) (next z) x<nz (subst (λ k → k o< next x) b y<nx) - (λ w nz=ow → o<¬≡ nz=ow (subst₂ (λ j k → j o< k ) (sym nz=ow) nz=ow (proj1 (proj2 next-limit) w (subst (λ k → w o< k ) (sym nz=ow) <-osuc) )))) - next< {x} {y} {z} x<nz y<nx | tri> ¬a ¬b c = ⊥-elim (proj2 (proj2 next-limit) (next z) x<nz (ordtrans c y<nx ) - (λ w nz=ow → o<¬≡ (sym nz=ow) (proj1 (proj2 next-limit) _ (subst (λ k → w o< k ) (sym nz=ow) <-osuc )))) + 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) + (λ 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) )))) + next< {x} {y} {z} x<nz y<nx | tri> ¬a ¬b c = ⊥-elim (¬nx<nx x<nz (ordtrans c y<nx ) + (λ w nz=ow → o<¬≡ (sym nz=ow) (osuc<nx (subst (λ k → w o< k ) (sym nz=ow) <-osuc )))) osuc< : {x y : Ordinal} → osuc x ≡ y → x o< y osuc< {x} {y} refl = <-osuc nexto=n : {x y : Ordinal} → x o< next (osuc y) → x o< next y - nexto=n {x} {y} x<noy = next< (proj1 (proj2 next-limit) _ (proj1 next-limit)) x<noy + nexto=n {x} {y} x<noy = next< (osuc<nx x<nx) x<noy nexto≡ : {x : Ordinal} → next x ≡ next (osuc x) nexto≡ {x} with trio< (next x) (next (osuc x) ) -- 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 - nexto≡ {x} | tri< a ¬b ¬c = ⊥-elim ((proj2 (proj2 next-limit)) _ (proj1 (proj2 next-limit) _ (proj1 next-limit) ) a - (λ z eq → o<¬≡ (sym eq) ((proj1 (proj2 next-limit)) _ (osuc< (sym eq))))) + nexto≡ {x} | tri< a ¬b ¬c = ⊥-elim (¬nx<nx (osuc<nx x<nx ) a + (λ z eq → o<¬≡ (sym eq) (osuc<nx (osuc< (sym eq))))) nexto≡ {x} | tri≈ ¬a b ¬c = b -- 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) ... - nexto≡ {x} | tri> ¬a ¬b c = ⊥-elim ((proj2 (proj2 next-limit)) _ (ordtrans <-osuc (proj1 next-limit)) c - (λ z eq → o<¬≡ (sym eq) ((proj1 (proj2 next-limit)) _ (osuc< (sym eq))))) - - record prev-choiced ( x : Ordinal ) : Set (suc n) where - field - prev : Ordinal - is-prev : osuc prev ≡ x - not-limit-p : ( x : Ordinal ) → Dec ( ¬ ((y : Ordinal) → ¬ (x ≡ osuc y) )) - not-limit-p x = {!!} where - ψ : ( ox : Ordinal ) → Set (suc n) - ψ ox = (( y : Ordinal ) → y o< ox → ( ¬ (osuc y ≡ x) )) ∨ prev-choiced x - ind : (ox : Ordinal) → ((y : Ordinal) → y o< ox → ψ y) → ψ ox - ind ox prev with trio< (osuc ox) x - ind ox prev | tri≈ ¬a b ¬c = case2 (record { prev = ox ; is-prev = b }) - ind ox prev | tri< a ¬b ¬c = case1 (λ y y<ox oy=x → o<> (subst (λ k → k o< osuc ox) oy=x (osucc y<ox )) a ) - -- osuc y = x < osuc ox, y < ox - ind ox prev | tri> ¬a ¬b c = {!!} - find : (y : Ordinal) → ψ y - find ox = TransFinite1 {ψ} ind ox + nexto≡ {x} | tri> ¬a ¬b c = ⊥-elim (¬nx<nx (ordtrans <-osuc x<nx) c + (λ z eq → o<¬≡ (sym eq) (osuc<nx (osuc< (sym eq))))) record OrdinalSubset (maxordinal : Ordinal) : Set (suc n) where field