Mercurial > hg > Members > kono > Proof > ZF-in-agda
annotate src/generic-filter.agda @ 1096:55ab5de1ae02
recovery
| author | Shinji KONO <kono@ie.u-ryukyu.ac.jp> |
|---|---|
| date | Fri, 23 Dec 2022 12:54:05 +0900 |
| parents | 5acf6483a9e3 |
| children | 7ce2cc622c92 |
| rev | line source |
|---|---|
| 431 | 1 open import Level |
| 2 open import Ordinals | |
| 3 module generic-filter {n : Level } (O : Ordinals {n}) where | |
| 4 | |
| 5 import filter | |
| 6 open import zf | |
| 7 open import logic | |
| 8 -- open import partfunc {n} O | |
| 9 import OD | |
| 10 | |
| 11 open import Relation.Nullary | |
| 12 open import Relation.Binary | |
| 13 open import Data.Empty | |
| 14 open import Relation.Binary | |
| 15 open import Relation.Binary.Core | |
| 16 open import Relation.Binary.PropositionalEquality | |
| 17 open import Data.Nat renaming ( zero to Zero ; suc to Suc ; ℕ to Nat ; _⊔_ to _n⊔_ ) | |
| 18 import BAlgbra | |
| 19 | |
| 20 open BAlgbra O | |
| 21 | |
| 22 open inOrdinal O | |
| 23 open OD O | |
| 24 open OD.OD | |
| 25 open ODAxiom odAxiom | |
| 26 import OrdUtil | |
| 27 import ODUtil | |
| 28 open Ordinals.Ordinals O | |
| 29 open Ordinals.IsOrdinals isOrdinal | |
| 30 open Ordinals.IsNext isNext | |
| 31 open OrdUtil O | |
| 32 open ODUtil O | |
| 33 | |
| 34 | |
| 35 import ODC | |
| 36 | |
| 37 open filter O | |
| 38 | |
| 39 open _∧_ | |
| 40 open _∨_ | |
| 41 open Bool | |
| 42 | |
| 43 | |
| 44 open HOD | |
| 45 | |
| 46 ------- | |
| 47 -- the set of finite partial functions from ω to 2 | |
| 48 -- | |
| 49 -- | |
| 50 | |
| 51 open import Data.List hiding (filter) | |
| 52 open import Data.Maybe | |
| 53 | |
| 54 import OPair | |
| 55 open OPair O | |
| 56 | |
|
453
e5f0ac638c01
P should be an order structure not Power Ser
Shinji KONO <kono@ie.u-ryukyu.ac.jp>
parents:
452
diff
changeset
|
57 record CountableModel : Set (suc (suc n)) where |
| 431 | 58 field |
| 461 | 59 ctl-M : HOD |
| 434 | 60 ctl→ : Nat → Ordinal |
| 461 | 61 ctl<M : (x : Nat) → odef (ctl-M) (ctl→ x) |
| 62 ctl← : (x : Ordinal )→ odef (ctl-M ) x → Nat | |
| 63 ctl-iso→ : { x : Ordinal } → (lt : odef (ctl-M) x ) → ctl→ (ctl← x lt ) ≡ x | |
| 446 | 64 ctl-iso← : { x : Nat } → ctl← (ctl→ x ) (ctl<M x) ≡ x |
| 65 -- | |
| 66 -- almmost universe | |
| 67 -- find-p contains ∃ x : Ordinal → x o< & M → ∀ r ∈ M → ∈ Ord x | |
| 68 -- | |
| 436 | 69 |
| 457 | 70 -- we expect P ∈ * ctl-M ∧ G ⊆ L ⊆ Power P , ¬ G ∈ * ctl-M, |
| 434 | 71 |
| 72 open CountableModel | |
| 431 | 73 |
| 74 ---- | |
| 75 -- a(n) ∈ M | |
| 457 | 76 -- ∃ q ∈ L ⊆ Power P → q ∈ a(n) ∧ q ⊆ p(n) |
| 431 | 77 -- |
| 457 | 78 PGHOD : (i : Nat) (L : HOD) (C : CountableModel ) → (p : Ordinal) → HOD |
| 79 PGHOD i L C p = record { od = record { def = λ x → | |
| 80 odef L x ∧ odef (* (ctl→ C i)) x ∧ ( (y : Ordinal ) → odef (* x) y → odef (* p) y ) } | |
| 81 ; odmax = odmax L ; <odmax = λ {y} lt → <odmax L (proj1 lt) } | |
| 431 | 82 |
| 83 --- | |
| 464 | 84 -- p(n+1) = if ({q | q ∈ a(n) ∧ q ⊆ p(n))} != ∅ then q otherwise p(n) |
| 446 | 85 -- |
| 457 | 86 find-p : (L : HOD ) (C : CountableModel ) (i : Nat) → (x : Ordinal) → Ordinal |
| 87 find-p L C Zero x = x | |
| 88 find-p L C (Suc i) x with is-o∅ ( & ( PGHOD i L C (find-p L C i x)) ) | |
| 89 ... | yes y = find-p L C i x | |
| 90 ... | no not = & (ODC.minimal O ( PGHOD i L C (find-p L C i x)) (λ eq → not (=od∅→≡o∅ eq))) -- axiom of choice | |
| 431 | 91 |
| 92 --- | |
| 457 | 93 -- G = { r ∈ L ⊆ Power P | ∃ n → p(n) ⊆ r } |
| 431 | 94 -- |
| 457 | 95 record PDN (L p : HOD ) (C : CountableModel ) (x : Ordinal) : Set n where |
| 431 | 96 field |
| 97 gr : Nat | |
| 457 | 98 pn<gr : (y : Ordinal) → odef (* (find-p L C gr (& p))) y → odef (* x) y |
| 99 x∈PP : odef L x | |
| 431 | 100 |
| 101 open PDN | |
| 102 | |
| 103 --- | |
| 104 -- G as a HOD | |
| 105 -- | |
| 457 | 106 PDHOD : (L p : HOD ) (C : CountableModel ) → HOD |
| 107 PDHOD L p C = record { od = record { def = λ x → PDN L p C x } | |
| 108 ; odmax = odmax L ; <odmax = λ {y} lt → <odmax L {y} (PDN.x∈PP lt) } | |
| 431 | 109 |
| 110 open PDN | |
| 111 | |
| 112 ---- | |
| 113 -- Generic Filter on Power P for HOD's Countable Ordinal (G ⊆ Power P ≡ G i.e. Nat → P → Set ) | |
| 114 -- | |
| 115 -- p 0 ≡ ∅ | |
| 434 | 116 -- p (suc n) = if ∃ q ∈ M ∧ p n ⊆ q → q (by axiom of choice) ( q = * ( ctl→ n ) ) |
| 431 | 117 --- else p n |
| 118 | |
| 119 P∅ : {P : HOD} → odef (Power P) o∅ | |
| 120 P∅ {P} = subst (λ k → odef (Power P) k ) ord-od∅ (lemma o∅ o∅≡od∅) where | |
| 121 lemma : (x : Ordinal ) → * x ≡ od∅ → odef (Power P) (& od∅) | |
| 122 lemma x eq = power← P od∅ (λ {x} lt → ⊥-elim (¬x<0 lt )) | |
| 123 x<y→∋ : {x y : Ordinal} → odef (* x) y → * x ∋ * y | |
| 124 x<y→∋ {x} {y} lt = subst (λ k → odef (* x) k ) (sym &iso) lt | |
| 125 | |
| 446 | 126 open import Data.Nat.Properties |
| 127 open import nat | |
| 433 | 128 |
| 457 | 129 p-monotonic1 : (L p : HOD ) (C : CountableModel ) → {n : Nat} → (* (find-p L C (Suc n) (& p))) ⊆ (* (find-p L C n (& p))) |
| 1096 | 130 p-monotonic1 L p C {n} {x} with is-o∅ (& (PGHOD n L C (find-p L C n (& p)))) |
| 131 ... | yes y = refl-⊆ {* (find-p L C n (& p))} | |
| 132 ... | no not = λ lt → proj2 (proj2 fmin∈PGHOD) _ lt where | |
| 447 | 133 fmin : HOD |
| 457 | 134 fmin = ODC.minimal O (PGHOD n L C (find-p L C n (& p))) (λ eq → not (=od∅→≡o∅ eq)) |
| 135 fmin∈PGHOD : PGHOD n L C (find-p L C n (& p)) ∋ fmin | |
| 136 fmin∈PGHOD = ODC.x∋minimal O (PGHOD n L C (find-p L C n (& p))) (λ eq → not (=od∅→≡o∅ eq)) | |
| 438 | 137 |
| 457 | 138 p-monotonic : (L p : HOD ) (C : CountableModel ) → {n m : Nat} → n ≤ m → (* (find-p L C m (& p))) ⊆ (* (find-p L C n (& p))) |
| 1096 | 139 p-monotonic L p C {Zero} {Zero} n≤m = refl-⊆ {* (find-p L C Zero (& p))} |
| 140 p-monotonic L p C {Zero} {Suc m} z≤n lt = (p-monotonic L p C {Zero} {m} z≤n ) (p-monotonic1 L p C {m} lt ) | |
| 457 | 141 p-monotonic L p C {Suc n} {Suc m} (s≤s n≤m) with <-cmp n m |
| 1096 | 142 ... | tri< a ¬b ¬c = λ lt → (p-monotonic L p C {Suc n} {m} a) (p-monotonic1 L p C {m} lt ) |
| 143 ... | tri≈ ¬a refl ¬c = λ x → x | |
| 446 | 144 ... | tri> ¬a ¬b c = ⊥-elim ( nat-≤> n≤m c ) |
| 438 | 145 |
| 1096 | 146 P-GenericFilter : (P L p0 : HOD ) → (LP : L ⊆ Power P) → L ∋ p0 → (C : CountableModel ) → GenericFilter {L} {P} LP ( ctl-M C ) |
| 457 | 147 P-GenericFilter P L p0 L⊆PP Lp0 C = record { |
| 460 | 148 genf = record { filter = PDHOD L p0 C ; f⊆L = f⊆PL ; filter1 = λ L∋q PD∋p p⊆q → f1 L∋q PD∋p p⊆q ; filter2 = f2 } |
| 149 ; generic = fdense | |
| 431 | 150 } where |
| 461 | 151 f⊆PL : PDHOD L p0 C ⊆ L |
| 1096 | 152 f⊆PL lt = x∈PP lt |
| 460 | 153 f1 : {p q : HOD} → L ∋ q → PDHOD L p0 C ∋ p → p ⊆ q → PDHOD L p0 C ∋ q |
| 154 f1 {p} {q} L∋q PD∋p p⊆q = record { gr = gr PD∋p ; pn<gr = f04 ; x∈PP = L∋q } where | |
| 155 f04 : (y : Ordinal) → odef (* (find-p L C (gr PD∋p) (& p0))) y → odef (* (& q)) y | |
| 1096 | 156 f04 y lt1 = subst₂ (λ j k → odef j k ) (sym *iso) &iso (p⊆q (subst₂ (λ j k → odef k j ) (sym &iso) *iso ( pn<gr PD∋p y lt1 ))) |
| 446 | 157 -- odef (* (find-p P C (gr PD∋p) (& p0))) y → odef (* (& q)) y |
| 461 | 158 f2 : {p q : HOD} → PDHOD L p0 C ∋ p → PDHOD L p0 C ∋ q → L ∋ (p ∩ q) → PDHOD L p0 C ∋ (p ∩ q) |
| 159 f2 {p} {q} PD∋p PD∋q L∋pq with <-cmp (gr PD∋q) (gr PD∋p) | |
| 160 ... | tri< a ¬b ¬c = record { gr = gr PD∋p ; pn<gr = λ y lt → subst (λ k → odef k y ) (sym *iso) (f3 y lt ) ; x∈PP = L∋pq } where | |
| 460 | 161 f3 : (y : Ordinal) → odef (* (find-p L C (gr PD∋p) (& p0))) y → odef (p ∩ q) y |
| 448 | 162 f3 y lt = ⟪ subst (λ k → odef k y) *iso (pn<gr PD∋p y lt) , subst (λ k → odef k y) *iso (pn<gr PD∋q y (f5 lt)) ⟫ where |
| 460 | 163 f5 : odef (* (find-p L C (gr PD∋p) (& p0))) y → odef (* (find-p L C (gr PD∋q) (& p0))) y |
| 1096 | 164 f5 lt = subst (λ k → odef (* (find-p L C (gr PD∋q) (& p0))) k ) &iso ( (p-monotonic L p0 C {gr PD∋q} {gr PD∋p} (<to≤ a)) |
| 460 | 165 (subst (λ k → odef (* (find-p L C (gr PD∋p) (& p0))) k ) (sym &iso) lt) ) |
| 461 | 166 ... | tri≈ ¬a refl ¬c = record { gr = gr PD∋p ; pn<gr = λ y lt → subst (λ k → odef k y ) (sym *iso) (f4 y lt) ; x∈PP = L∋pq } where |
| 460 | 167 f4 : (y : Ordinal) → odef (* (find-p L C (gr PD∋p) (& p0))) y → odef (p ∩ q) y |
| 447 | 168 f4 y lt = ⟪ subst (λ k → odef k y) *iso (pn<gr PD∋p y lt) , subst (λ k → odef k y) *iso (pn<gr PD∋q y lt) ⟫ |
| 461 | 169 ... | tri> ¬a ¬b c = record { gr = gr PD∋q ; pn<gr = λ y lt → subst (λ k → odef k y ) (sym *iso) (f3 y lt) ; x∈PP = L∋pq } where |
| 460 | 170 f3 : (y : Ordinal) → odef (* (find-p L C (gr PD∋q) (& p0))) y → odef (p ∩ q) y |
| 171 f3 y lt = ⟪ subst (λ k → odef k y) *iso (pn<gr PD∋p y (f5 lt)), subst (λ k → odef k y) *iso (pn<gr PD∋q y lt) ⟫ where | |
| 172 f5 : odef (* (find-p L C (gr PD∋q) (& p0))) y → odef (* (find-p L C (gr PD∋p) (& p0))) y | |
| 1096 | 173 f5 lt = subst (λ k → odef (* (find-p L C (gr PD∋p) (& p0))) k ) &iso ( (p-monotonic L p0 C {gr PD∋p} {gr PD∋q} (<to≤ c)) |
| 460 | 174 (subst (λ k → odef (* (find-p L C (gr PD∋q) (& p0))) k ) (sym &iso) lt) ) |
| 461 | 175 fdense : (D : Dense L⊆PP ) → (ctl-M C ) ∋ Dense.dense D → ¬ (filter.Dense.dense D ∩ PDHOD L p0 C) ≡ od∅ |
| 176 fdense D MD eq0 = ⊥-elim ( ∅< {Dense.dense D ∩ PDHOD L p0 C} fd01 (≡od∅→=od∅ eq0 )) where | |
| 448 | 177 open Dense |
| 462 | 178 fd09 : (i : Nat ) → odef L (find-p L C i (& p0)) |
| 179 fd09 Zero = Lp0 | |
| 180 fd09 (Suc i) with is-o∅ ( & ( PGHOD i L C (find-p L C i (& p0))) ) | |
| 181 ... | yes _ = fd09 i | |
| 463 | 182 ... | no not = fd17 where |
| 183 fd19 = ODC.minimal O ( PGHOD i L C (find-p L C i (& p0))) (λ eq → not (=od∅→≡o∅ eq)) | |
| 184 fd18 : PGHOD i L C (find-p L C i (& p0)) ∋ fd19 | |
| 185 fd18 = ODC.x∋minimal O (PGHOD i L C (find-p L C i (& p0))) (λ eq → not (=od∅→≡o∅ eq)) | |
| 186 fd17 : odef L ( & (ODC.minimal O ( PGHOD i L C (find-p L C i (& p0))) (λ eq → not (=od∅→≡o∅ eq))) ) | |
| 187 fd17 = proj1 fd18 | |
| 461 | 188 an : Nat |
| 189 an = ctl← C (& (dense D)) MD | |
| 190 pn : Ordinal | |
| 191 pn = find-p L C an (& p0) | |
| 192 pn+1 : Ordinal | |
| 193 pn+1 = find-p L C (Suc an) (& p0) | |
| 464 | 194 d=an : dense D ≡ * (ctl→ C an) |
| 195 d=an = begin dense D ≡⟨ sym *iso ⟩ | |
| 463 | 196 * ( & (dense D)) ≡⟨ cong (*) (sym (ctl-iso→ C MD )) ⟩ |
| 197 * (ctl→ C an) ∎ where open ≡-Reasoning | |
| 461 | 198 fd07 : odef (dense D) pn+1 |
| 199 fd07 with is-o∅ ( & ( PGHOD an L C (find-p L C an (& p0))) ) | |
| 462 | 200 ... | yes y = ⊥-elim ( ¬x<0 ( _==_.eq→ fd10 ⟪ fd13 , ⟪ fd14 , fd15 ⟫ ⟫ ) ) where |
| 201 fd12 : L ∋ * (find-p L C an (& p0)) | |
| 202 fd12 = subst (λ k → odef L k) (sym &iso) (fd09 an ) | |
| 203 fd11 : Ordinal | |
| 204 fd11 = & ( dense-f D fd12 ) | |
| 205 fd13 : L ∋ ( dense-f D fd12 ) | |
| 1096 | 206 fd13 = (d⊆P D) ( dense-d D fd12 ) |
| 462 | 207 fd14 : (* (ctl→ C an)) ∋ ( dense-f D fd12 ) |
| 464 | 208 fd14 = subst (λ k → odef k (& ( dense-f D fd12 ) )) d=an ( dense-d D fd12 ) |
| 462 | 209 fd15 : (y : Ordinal) → odef (* (& (dense-f D fd12))) y → odef (* (find-p L C an (& p0))) y |
| 1096 | 210 fd15 y lt = subst (λ k → odef (* (find-p L C an (& p0))) k ) &iso ( (dense-p D fd12 ) fd16 ) where |
| 462 | 211 fd16 : odef (dense-f D fd12) (& ( * y)) |
| 212 fd16 = subst₂ (λ j k → odef j k ) (*iso) (sym &iso) lt | |
| 213 fd10 : PGHOD an L C (find-p L C an (& p0)) =h= od∅ | |
| 214 fd10 = ≡o∅→=od∅ y | |
| 463 | 215 ... | no not = fd27 where |
| 216 fd29 = ODC.minimal O ( PGHOD an L C (find-p L C an (& p0))) (λ eq → not (=od∅→≡o∅ eq)) | |
| 217 fd28 : PGHOD an L C (find-p L C an (& p0)) ∋ fd29 | |
| 218 fd28 = ODC.x∋minimal O (PGHOD an L C (find-p L C an (& p0))) (λ eq → not (=od∅→≡o∅ eq)) | |
| 219 fd27 : odef (dense D) (& fd29) | |
| 464 | 220 fd27 = subst (λ k → odef k (& fd29)) (sym d=an) (proj1 (proj2 fd28)) |
| 461 | 221 fd03 : odef (PDHOD L p0 C) pn+1 |
| 222 fd03 = record { gr = Suc an ; pn<gr = λ y lt → lt ; x∈PP = fd09 (Suc an)} | |
| 223 fd01 : (dense D ∩ PDHOD L p0 C) ∋ (* pn+1) | |
| 224 fd01 = ⟪ subst (λ k → odef (dense D) k ) (sym &iso) fd07 , subst (λ k → odef (PDHOD L p0 C) k) (sym &iso) fd03 ⟫ | |
| 448 | 225 |
| 431 | 226 open GenericFilter |
| 227 open Filter | |
| 228 | |
| 461 | 229 record NonAtomic (L a : HOD ) (L∋a : L ∋ a ) : Set (suc (suc n)) where |
| 431 | 230 field |
| 461 | 231 b : HOD |
| 232 0<b : ¬ o∅ ≡ & b | |
| 233 b<a : b ⊆ a | |
| 431 | 234 |
| 461 | 235 lemma232 : (P L p : HOD ) (C : CountableModel ) |
| 236 → (LP : L ⊆ Power P ) → (Lp0 : L ∋ p ) | |
| 237 → ( {q : HOD} → (Lq : L ∋ q ) → NonAtomic L q Lq ) | |
| 238 → ¬ ( (ctl-M C) ∋ filter ( genf ( P-GenericFilter P L p LP Lp0 C )) ) | |
| 239 lemma232 P L p C LP Lp0 NA MG = {!!} | |
| 431 | 240 |
| 241 -- | |
| 242 -- val x G = { val y G | ∃ p → G ∋ p → x ∋ < y , p > } | |
| 243 -- | |
| 436 | 244 |
| 1096 | 245 record valR (x : HOD) {P L : HOD} {LP : L ⊆ Power P} (C : CountableModel ) (G : GenericFilter {L} {P} LP (ctl-M C) ) : Set (suc n) where |
| 437 | 246 field |
| 247 valx : HOD | |
| 436 | 248 |
| 437 | 249 record valS (ox oy oG : Ordinal) : Set n where |
| 436 | 250 field |
| 437 | 251 op : Ordinal |
| 252 p∈G : odef (* oG) op | |
| 253 is-val : odef (* ox) ( & < * oy , * op > ) | |
| 436 | 254 |
| 459 | 255 val : (x : HOD) {P L : HOD } {LP : L ⊆ Power P} |
| 1096 | 256 → (G : GenericFilter {L} {P} LP {!!} ) |
| 436 | 257 → HOD |
| 437 | 258 val x G = TransFinite {λ x → HOD } ind (& x) where |
| 259 ind : (x : Ordinal) → ((y : Ordinal) → y o< x → HOD) → HOD | |
| 439 | 260 ind x valy = record { od = record { def = λ y → valS x y (& (filter (genf G))) } ; odmax = {!!} ; <odmax = {!!} } |
| 437 | 261 |