Mercurial > hg > Members > kono > Proof > ZF-in-agda
annotate src/generic-filter.agda @ 448:81691a6b352b
...
author | Shinji KONO <kono@ie.u-ryukyu.ac.jp> |
---|---|
date | Sun, 13 Mar 2022 19:03:33 +0900 |
parents | 364d738f871d |
children | be685f338fdc |
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 -- |
436 | 88 find-p : (P : HOD ) (C : CountableModel P) (i : Nat) → (x : Ordinal) → Ordinal |
89 find-p P C Zero x = x | |
447 | 90 find-p P C (Suc i) x with is-o∅ ( & ( PGHOD i P C (find-p P C i x)) ) |
91 ... | yes y = find-p P C i x | |
92 ... | no not = & (ODC.minimal O ( PGHOD i P C (find-p P C i x)) (λ eq → not (=od∅→≡o∅ eq))) -- axiom of choice | |
431 | 93 |
94 --- | |
446 | 95 -- G = { r ∈ Power P | ∃ n → p(n) ⊆ q } |
431 | 96 -- |
436 | 97 record PDN (P p : HOD ) (C : CountableModel P) (x : Ordinal) : Set n where |
431 | 98 field |
99 gr : Nat | |
446 | 100 pn<gr : (y : Ordinal) → odef (* (find-p P C gr (& p))) y → odef (* x) y |
431 | 101 x∈PP : odef (Power P) x |
102 | |
103 open PDN | |
104 | |
105 --- | |
106 -- G as a HOD | |
107 -- | |
436 | 108 PDHOD : (P p : HOD ) (C : CountableModel P ) → HOD |
109 PDHOD P p C = record { od = record { def = λ x → PDN P p C x } | |
431 | 110 ; odmax = odmax (Power P) ; <odmax = λ {y} lt → <odmax (Power P) {y} (PDN.x∈PP lt) } |
111 | |
112 open PDN | |
113 | |
114 ---- | |
115 -- Generic Filter on Power P for HOD's Countable Ordinal (G ⊆ Power P ≡ G i.e. Nat → P → Set ) | |
116 -- | |
117 -- p 0 ≡ ∅ | |
434 | 118 -- p (suc n) = if ∃ q ∈ M ∧ p n ⊆ q → q (by axiom of choice) ( q = * ( ctl→ n ) ) |
431 | 119 --- else p n |
120 | |
121 P∅ : {P : HOD} → odef (Power P) o∅ | |
122 P∅ {P} = subst (λ k → odef (Power P) k ) ord-od∅ (lemma o∅ o∅≡od∅) where | |
123 lemma : (x : Ordinal ) → * x ≡ od∅ → odef (Power P) (& od∅) | |
124 lemma x eq = power← P od∅ (λ {x} lt → ⊥-elim (¬x<0 lt )) | |
125 x<y→∋ : {x y : Ordinal} → odef (* x) y → * x ∋ * y | |
126 x<y→∋ {x} {y} lt = subst (λ k → odef (* x) k ) (sym &iso) lt | |
127 | |
446 | 128 open import Data.Nat.Properties |
129 open import nat | |
433 | 130 open _⊆_ |
131 | |
446 | 132 p-monotonic1 : (P p : HOD ) (C : CountableModel P ) → {n : Nat} → (* (find-p P C n (& p))) ⊆ (* (find-p P C (Suc n) (& p))) |
447 | 133 p-monotonic1 P p C {n} with is-o∅ (& (PGHOD n P C (find-p P C n (& p)))) |
134 ... | yes y = refl-⊆ | |
135 ... | no not = record { incl = λ {x} lt → proj2 (proj2 fmin∈PGHOD) (& x) lt } where | |
136 fmin : HOD | |
137 fmin = ODC.minimal O (PGHOD n P C (find-p P C n (& p))) (λ eq → not (=od∅→≡o∅ eq)) | |
138 fmin∈PGHOD : PGHOD n P C (find-p P C n (& p)) ∋ fmin | |
139 fmin∈PGHOD = ODC.x∋minimal O (PGHOD n P C (find-p P C n (& p))) (λ eq → not (=od∅→≡o∅ eq)) | |
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 | |
447 | 145 ... | tri< a ¬b ¬c = trans-⊆ (p-monotonic P p C {Suc n} {m} a) (p-monotonic1 P p C {m} ) |
446 | 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 } |
448 | 152 ; generic = fdense |
431 | 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 f⊆PL : PDHOD P p0 C ⊆ Power P |
446 | 157 f⊆PL = record { incl = λ {x} lt → x∈PP lt } |
436 | 158 f1 : {p q : HOD} → q ⊆ P → PDHOD P p0 C ∋ p → p ⊆ q → PDHOD P p0 C ∋ q |
446 | 159 f1 {p} {q} q⊆P PD∋p p⊆q = record { gr = gr PD∋p ; pn<gr = f04 ; x∈PP = power← _ _ (incl q⊆P) } where |
160 f04 : (y : Ordinal) → odef (* (find-p P C (gr PD∋p) (& p0))) y → odef (* (& q)) y | |
161 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 ))) | |
162 -- odef (* (find-p P C (gr PD∋p) (& p0))) y → odef (* (& q)) y | |
436 | 163 f2 : {p q : HOD} → PDHOD P p0 C ∋ p → PDHOD P p0 C ∋ q → PDHOD P p0 C ∋ (p ∩ q) |
447 | 164 f2 {p} {q} PD∋p PD∋q with <-cmp (gr PD∋p) (gr PD∋q) |
165 ... | 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 = ODC.power-∩ O (x∈PP PD∋p) (x∈PP PD∋q) } where | |
166 f3 : (y : Ordinal) → odef (* (find-p P C (gr PD∋p) (& p0))) y → odef (p ∩ q) y | |
448 | 167 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 |
168 f5 : odef (* (find-p P C (gr PD∋p) (& p0))) y → odef (* (find-p P C (gr PD∋q) (& p0))) y | |
169 f5 lt = subst (λ k → odef (* (find-p P C (gr PD∋q) (& p0))) k ) &iso ( incl (p-monotonic P p0 C {gr PD∋p} {gr PD∋q} (<to≤ a)) | |
170 (subst (λ k → odef (* (find-p P C (gr PD∋p) (& p0))) k ) (sym &iso) lt) ) | |
171 -- subst (λ k → odef k y) *iso (pn<gr PD∋q y (subst (λ k → odef _ k ) &iso (incl (p-monotonic _ _ C a ) (subst (λ k → odef _ k) &iso lt) ))) ⟫ | |
447 | 172 ... | 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 = ODC.power-∩ O (x∈PP PD∋p) (x∈PP PD∋q) } where |
173 f4 : (y : Ordinal) → odef (* (find-p P C (gr PD∋p) (& p0))) y → odef (p ∩ q) y | |
174 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) ⟫ | |
448 | 175 ... | 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 = ODC.power-∩ O (x∈PP PD∋p) (x∈PP PD∋q) } where |
176 f3 : (y : Ordinal) → odef (* (find-p P C (gr PD∋q) (& p0))) y → odef (p ∩ q) y | |
177 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 | |
178 f5 : odef (* (find-p P C (gr PD∋q) (& p0))) y → odef (* (find-p P C (gr PD∋p) (& p0))) y | |
179 f5 lt = subst (λ k → odef (* (find-p P C (gr PD∋p) (& p0))) k ) &iso ( incl (p-monotonic P p0 C {gr PD∋q} {gr PD∋p} (<to≤ c)) | |
180 (subst (λ k → odef (* (find-p P C (gr PD∋q) (& p0))) k ) (sym &iso) lt) ) | |
181 fdense : (D : Dense P ) → ¬ (filter.Dense.dense D ∩ PDHOD P p0 C) ≡ od∅ | |
182 fdense D eq0 = ⊥-elim ( ∅< {Dense.dense D ∩ PDHOD P p0 C} fd01 (≡od∅→=od∅ eq0 )) where | |
183 open Dense | |
184 fd : HOD | |
185 fd = dense-f D p0 | |
186 PP∋D : dense D ⊆ Power P | |
187 PP∋D = d⊆P D | |
188 fd02 : dense D ∋ dense-f D p0 | |
189 fd02 = dense-d D (ODC.power→⊆ O _ _ Pp0 ) | |
190 fd03 : PDHOD P p0 C ∋ dense-f D p0 | |
191 fd03 = f1 {p0} {dense-f D p0} {!!} {!!} ( dense-p D {!!} ) | |
192 fd01 : (dense D ∩ PDHOD P p0 C) ∋ fd | |
193 fd01 = ⟪ fd02 , fd03 ⟫ | |
194 | |
434 | 195 |
431 | 196 |
197 | |
198 open GenericFilter | |
199 open Filter | |
200 | |
201 record Incompatible (P : HOD ) : Set (suc (suc n)) where | |
202 field | |
434 | 203 q : {p : HOD } → Power P ∋ p → HOD |
204 r : {p : HOD } → Power P ∋ p → HOD | |
205 incompatible : { p : HOD } → (P∋p : Power P ∋ p) → Power P ∋ q P∋p → Power P ∋ r P∋p | |
206 → ( p ⊆ q P∋p) ∧ ( p ⊆ r P∋p) | |
207 → ∀ ( s : HOD ) → Power P ∋ s → ¬ (( q P∋p ⊆ s ) ∧ ( r P∋p ⊆ s )) | |
431 | 208 |
436 | 209 lemma725 : (P p : HOD ) (C : CountableModel P) |
210 → * (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
|
211 → Incompatible P → ¬ ( * (ctl-M C) ∋ filter ( genf ( P-GenericFilter P p {!!} C ))) |
431 | 212 lemma725 = {!!} |
213 | |
433 | 214 open import PFOD O |
215 | |
216 -- HODω2 : HOD | |
217 -- | |
218 -- ω→2 : HOD | |
219 -- ω→2 = Power infinite | |
220 | |
431 | 221 lemma725-1 : Incompatible HODω2 |
222 lemma725-1 = {!!} | |
223 | |
436 | 224 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
|
225 → Union ( Replace HODω2 (λ p → filter ( genf ( P-GenericFilter HODω2 p {!!} C )))) =h= ω→2 |
431 | 226 lemma726 = {!!} |
227 | |
228 -- | |
229 -- val x G = { val y G | ∃ p → G ∋ p → x ∋ < y , p > } | |
230 -- | |
436 | 231 |
437 | 232 record valR (x : HOD) {P : HOD} (G : GenericFilter P) : Set (suc n) where |
233 field | |
234 valx : HOD | |
436 | 235 |
437 | 236 record valS (ox oy oG : Ordinal) : Set n where |
436 | 237 field |
437 | 238 op : Ordinal |
239 p∈G : odef (* oG) op | |
240 is-val : odef (* ox) ( & < * oy , * op > ) | |
436 | 241 |
437 | 242 val : (x : HOD) {P : HOD } |
436 | 243 → (G : GenericFilter P) |
244 → HOD | |
437 | 245 val x G = TransFinite {λ x → HOD } ind (& x) where |
246 ind : (x : Ordinal) → ((y : Ordinal) → y o< x → HOD) → HOD | |
439 | 247 ind x valy = record { od = record { def = λ y → valS x y (& (filter (genf G))) } ; odmax = {!!} ; <odmax = {!!} } |
437 | 248 |
436 | 249 |
250 -- | |
431 | 251 -- W (ω , H ( ω , 2 )) = { p ∈ ( Nat → H (ω , 2) ) | { i ∈ Nat → p i ≠ i1 } is finite } |
252 -- | |
253 | |
254 | |
255 |