Mercurial > hg > Members > kono > Proof > ZF-in-agda
annotate src/generic-filter.agda @ 446:eb4049abad70
...
| author | Shinji KONO <kono@ie.u-ryukyu.ac.jp> |
|---|---|
| date | Sun, 13 Mar 2022 08:05:15 +0900 |
| parents | d1c9f5ae5d0a |
| children | 364d738f871d |
| 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 | |
| 436 | 57 record CountableModel (P : HOD) : Set (suc (suc n)) where |
| 431 | 58 field |
| 434 | 59 ctl-M : Ordinal |
| 60 ctl→ : Nat → Ordinal | |
| 61 ctl← : (x : Ordinal )→ x o< ctl-M → Nat | |
| 446 | 62 ctl<M : (x : Nat) → ctl→ x o< ctl-M |
| 434 | 63 ctl-iso→ : { x : Ordinal } → (lt : x o< ctl-M) → ctl→ (ctl← x lt ) ≡ x |
| 446 | 64 ctl-iso← : { x : Nat } → ctl← (ctl→ x ) (ctl<M x) ≡ x |
| 438 | 65 ctl-P∈M : Power P ∈ * ctl-M |
| 446 | 66 -- |
| 67 -- almmost universe | |
| 68 -- find-p contains ∃ x : Ordinal → x o< & M → ∀ r ∈ M → ∈ Ord x | |
| 69 -- | |
| 436 | 70 |
| 446 | 71 |
| 72 -- we expect P ∈ * ctl-M ∧ G ⊆ Power P , ¬ G ∈ * ctl-M, | |
| 434 | 73 |
| 74 open CountableModel | |
| 431 | 75 |
| 76 ---- | |
| 77 -- a(n) ∈ M | |
| 78 -- ∃ q ∈ Power P → q ∈ a(n) ∧ p(n) ⊆ q | |
| 79 -- | |
| 436 | 80 PGHOD : (i : Nat) (P : HOD) (C : CountableModel P) → (p : Ordinal) → HOD |
| 81 PGHOD i P C p = record { od = record { def = λ x → | |
| 431 | 82 odef (Power P) x ∧ odef (* (ctl→ C i)) x ∧ ( (y : Ordinal ) → odef (* p) y → odef (* x) y ) } |
| 83 ; odmax = odmax (Power P) ; <odmax = λ {y} lt → <odmax (Power P) (proj1 lt) } | |
| 84 | |
| 85 --- | |
| 436 | 86 -- p(n+1) = if (f n) != ∅ then (f n) otherwise p(n) |
| 446 | 87 -- |
| 433 | 88 next-p : (p : Ordinal) → (f : HOD → HOD) → Ordinal |
| 89 next-p p f with is-o∅ ( & (f (* p))) | |
| 90 next-p p f | yes y = p | |
| 91 next-p p f | no not = & (ODC.minimal O (f (* p) ) (λ eq → not (=od∅→≡o∅ eq))) -- axiom of choice | |
| 431 | 92 |
| 93 --- | |
| 434 | 94 -- search on p(n) |
| 431 | 95 -- |
| 436 | 96 find-p : (P : HOD ) (C : CountableModel P) (i : Nat) → (x : Ordinal) → Ordinal |
| 97 find-p P C Zero x = x | |
| 98 find-p P C (Suc i) x = find-p P C i ( next-p x (λ p → PGHOD i P C (& p) )) | |
| 431 | 99 |
| 100 --- | |
| 446 | 101 -- G = { r ∈ Power P | ∃ n → p(n) ⊆ q } |
| 431 | 102 -- |
| 436 | 103 record PDN (P p : HOD ) (C : CountableModel P) (x : Ordinal) : Set n where |
| 431 | 104 field |
| 105 gr : Nat | |
| 446 | 106 pn<gr : (y : Ordinal) → odef (* (find-p P C gr (& p))) y → odef (* x) y |
| 431 | 107 x∈PP : odef (Power P) x |
| 108 | |
| 109 open PDN | |
| 110 | |
| 111 --- | |
| 112 -- G as a HOD | |
| 113 -- | |
| 436 | 114 PDHOD : (P p : HOD ) (C : CountableModel P ) → HOD |
| 115 PDHOD P p C = record { od = record { def = λ x → PDN P p C x } | |
| 431 | 116 ; odmax = odmax (Power P) ; <odmax = λ {y} lt → <odmax (Power P) {y} (PDN.x∈PP lt) } |
| 117 | |
| 118 open PDN | |
| 119 | |
| 120 ---- | |
| 121 -- Generic Filter on Power P for HOD's Countable Ordinal (G ⊆ Power P ≡ G i.e. Nat → P → Set ) | |
| 122 -- | |
| 123 -- p 0 ≡ ∅ | |
| 434 | 124 -- p (suc n) = if ∃ q ∈ M ∧ p n ⊆ q → q (by axiom of choice) ( q = * ( ctl→ n ) ) |
| 431 | 125 --- else p n |
| 126 | |
| 127 P∅ : {P : HOD} → odef (Power P) o∅ | |
| 128 P∅ {P} = subst (λ k → odef (Power P) k ) ord-od∅ (lemma o∅ o∅≡od∅) where | |
| 129 lemma : (x : Ordinal ) → * x ≡ od∅ → odef (Power P) (& od∅) | |
| 130 lemma x eq = power← P od∅ (λ {x} lt → ⊥-elim (¬x<0 lt )) | |
| 131 x<y→∋ : {x y : Ordinal} → odef (* x) y → * x ∋ * y | |
| 132 x<y→∋ {x} {y} lt = subst (λ k → odef (* x) k ) (sym &iso) lt | |
| 133 | |
| 446 | 134 open import Data.Nat.Properties |
| 135 open import nat | |
| 433 | 136 open _⊆_ |
| 137 | |
| 446 | 138 p-monotonic1 : (P p : HOD ) (C : CountableModel P ) → {n : Nat} → (* (find-p P C n (& p))) ⊆ (* (find-p P C (Suc n) (& p))) |
| 139 p-monotonic1 = {!!} | |
| 438 | 140 |
| 446 | 141 p-monotonic : (P p : HOD ) (C : CountableModel P ) → {n m : Nat} → n ≤ m → (* (find-p P C n (& p))) ⊆ (* (find-p P C m (& p))) |
| 142 p-monotonic P p C {Zero} {Zero} n≤m = refl-⊆ | |
| 143 p-monotonic P p C {Zero} {Suc m} z≤n = trans-⊆ (p-monotonic P p C {Zero} {m} z≤n ) (p-monotonic1 P p C {m} ) | |
| 144 p-monotonic P p C {Suc n} {Suc m} (s≤s n≤m) with <-cmp n m | |
| 145 ... | tri< a ¬b ¬c = trans-⊆ (p-monotonic P p C {Suc n} {m} {!!} ) (p-monotonic1 P p C {m} ) | |
| 146 ... | tri≈ ¬a refl ¬c = refl-⊆ | |
| 147 ... | tri> ¬a ¬b c = ⊥-elim ( nat-≤> n≤m c ) | |
| 438 | 148 |
|
440
d1c9f5ae5d0a
give up this generic filter definition
Shinji KONO <kono@ie.u-ryukyu.ac.jp>
parents:
439
diff
changeset
|
149 P-GenericFilter : (P p0 : HOD ) → Power P ∋ p0 → (C : CountableModel P) → GenericFilter P |
|
d1c9f5ae5d0a
give up this generic filter definition
Shinji KONO <kono@ie.u-ryukyu.ac.jp>
parents:
439
diff
changeset
|
150 P-GenericFilter P p0 Pp0 C = record { |
| 436 | 151 genf = record { filter = PDHOD P p0 C ; f⊆PL = f⊆PL ; filter1 = f1 ; filter2 = f2 } |
| 431 | 152 ; generic = λ D → {!!} |
| 153 } where | |
| 436 | 154 PGHOD∈PL : (i : Nat) → (x : Ordinal) → PGHOD i P C x ⊆ Power P |
| 434 | 155 PGHOD∈PL i x = record { incl = λ {x} p → proj1 p } |
| 436 | 156 find-p-⊆P : (i : Nat) → (x y : Ordinal) → odef (Power P) x → odef (* (find-p P C i x)) y → odef P y |
| 434 | 157 find-p-⊆P Zero x y Px Py = subst (λ k → odef P k ) &iso |
| 431 | 158 ( incl (ODC.power→⊆ O P (* x) (d→∋ (Power P) Px)) (x<y→∋ Py)) |
| 436 | 159 find-p-⊆P (Suc i) x y Px Py with is-o∅ ( & (PGHOD i P C (& (* x)))) |
| 434 | 160 ... | yes y1 = find-p-⊆P i x y Px Py |
| 161 ... | no not = find-p-⊆P i (& fmin) y pg-01 Py where | |
| 162 fmin : HOD | |
| 436 | 163 fmin = ODC.minimal O (PGHOD i P C (& (* x))) (λ eq → not (=od∅→≡o∅ eq)) |
| 164 fmin∈PGHOD : PGHOD i P C (& (* x)) ∋ fmin | |
| 165 fmin∈PGHOD = ODC.x∋minimal O (PGHOD i P C (& (* x))) (λ eq → not (=od∅→≡o∅ eq)) | |
| 434 | 166 pg-01 : Power P ∋ fmin |
| 436 | 167 pg-01 = incl (PGHOD∈PL i x ) (subst (λ k → PGHOD i P C k ∋ fmin ) &iso fmin∈PGHOD ) |
| 168 f⊆PL : PDHOD P p0 C ⊆ Power P | |
| 446 | 169 f⊆PL = record { incl = λ {x} lt → x∈PP lt } |
| 436 | 170 f1 : {p q : HOD} → q ⊆ P → PDHOD P p0 C ∋ p → p ⊆ q → PDHOD P p0 C ∋ q |
| 446 | 171 f1 {p} {q} q⊆P PD∋p p⊆q = record { gr = gr PD∋p ; pn<gr = f04 ; x∈PP = power← _ _ (incl q⊆P) } where |
| 435 | 172 f03 : {x : Ordinal} → odef p x → odef q x |
| 173 f03 {x} lt = subst (λ k → def (od q) k) &iso (incl p⊆q (subst (λ k → def (od p) k) (sym &iso) lt) ) | |
| 446 | 174 f04 : (y : Ordinal) → odef (* (find-p P C (gr PD∋p) (& p0))) y → odef (* (& q)) y |
| 175 f04 y lt1 = subst₂ (λ j k → odef j k ) (sym *iso) &iso (incl p⊆q (subst₂ (λ j k → odef k j ) (sym &iso) *iso ( pn<gr PD∋p y lt1 ))) | |
| 176 -- odef (* (find-p P C (gr PD∋p) (& p0))) y → odef (* (& q)) y | |
| 436 | 177 f2 : {p q : HOD} → PDHOD P p0 C ∋ p → PDHOD P p0 C ∋ q → PDHOD P p0 C ∋ (p ∩ q) |
| 434 | 178 f2 {p} {q} PD∋p PD∋q = {!!} |
| 179 | |
| 431 | 180 |
| 181 | |
| 182 open GenericFilter | |
| 183 open Filter | |
| 184 | |
| 185 record Incompatible (P : HOD ) : Set (suc (suc n)) where | |
| 186 field | |
| 434 | 187 q : {p : HOD } → Power P ∋ p → HOD |
| 188 r : {p : HOD } → Power P ∋ p → HOD | |
| 189 incompatible : { p : HOD } → (P∋p : Power P ∋ p) → Power P ∋ q P∋p → Power P ∋ r P∋p | |
| 190 → ( p ⊆ q P∋p) ∧ ( p ⊆ r P∋p) | |
| 191 → ∀ ( s : HOD ) → Power P ∋ s → ¬ (( q P∋p ⊆ s ) ∧ ( r P∋p ⊆ s )) | |
| 431 | 192 |
| 436 | 193 lemma725 : (P p : HOD ) (C : CountableModel P) |
| 194 → * (ctl-M C) ∋ Power P | |
|
440
d1c9f5ae5d0a
give up this generic filter definition
Shinji KONO <kono@ie.u-ryukyu.ac.jp>
parents:
439
diff
changeset
|
195 → Incompatible P → ¬ ( * (ctl-M C) ∋ filter ( genf ( P-GenericFilter P p {!!} C ))) |
| 431 | 196 lemma725 = {!!} |
| 197 | |
| 433 | 198 open import PFOD O |
| 199 | |
| 200 -- HODω2 : HOD | |
| 201 -- | |
| 202 -- ω→2 : HOD | |
| 203 -- ω→2 = Power infinite | |
| 204 | |
| 431 | 205 lemma725-1 : Incompatible HODω2 |
| 206 lemma725-1 = {!!} | |
| 207 | |
| 436 | 208 lemma726 : (C : CountableModel HODω2) |
|
440
d1c9f5ae5d0a
give up this generic filter definition
Shinji KONO <kono@ie.u-ryukyu.ac.jp>
parents:
439
diff
changeset
|
209 → Union ( Replace HODω2 (λ p → filter ( genf ( P-GenericFilter HODω2 p {!!} C )))) =h= ω→2 |
| 431 | 210 lemma726 = {!!} |
| 211 | |
| 212 -- | |
| 213 -- val x G = { val y G | ∃ p → G ∋ p → x ∋ < y , p > } | |
| 214 -- | |
| 436 | 215 |
| 437 | 216 record valR (x : HOD) {P : HOD} (G : GenericFilter P) : Set (suc n) where |
| 217 field | |
| 218 valx : HOD | |
| 436 | 219 |
| 437 | 220 record valS (ox oy oG : Ordinal) : Set n where |
| 436 | 221 field |
| 437 | 222 op : Ordinal |
| 223 p∈G : odef (* oG) op | |
| 224 is-val : odef (* ox) ( & < * oy , * op > ) | |
| 436 | 225 |
| 437 | 226 val : (x : HOD) {P : HOD } |
| 436 | 227 → (G : GenericFilter P) |
| 228 → HOD | |
| 437 | 229 val x G = TransFinite {λ x → HOD } ind (& x) where |
| 230 ind : (x : Ordinal) → ((y : Ordinal) → y o< x → HOD) → HOD | |
| 439 | 231 ind x valy = record { od = record { def = λ y → valS x y (& (filter (genf G))) } ; odmax = {!!} ; <odmax = {!!} } |
| 437 | 232 |
| 436 | 233 |
| 234 -- | |
| 431 | 235 -- W (ω , H ( ω , 2 )) = { p ∈ ( Nat → H (ω , 2) ) | { i ∈ Nat → p i ≠ i1 } is finite } |
| 236 -- | |
| 237 | |
| 238 | |
| 239 |