helm/software/matita/nlibrary/topology/igft.ma

   1 (*DOCBEGIN
   2
   3 Matita Tutorial: inductively generated formal topologies
   4 ========================================================
   5
   6 Small intro...
   7
   8 Initial setup
   9 -------------
  10
  11 The library, inclusion of `sets/sets.ma`, notation defined: Ω^A.
  12 Symbols (see menu: View ▹ TeX/UTF-8 Table):
  13
  14 - `Ω` can be typed \Omega
  15 - `∀` \Forall
  16 - `λ` \lambda
  17 - `≝` \def
  18 - `→` ->
  19
  20 Virtuals, ALT-L, for example I changes into 𝕀, finally 𝐈.
  21
  22 DOCEND*)
  23
  24 include "sets/sets.ma".
  25
  26 (*DOCBEGIN
  27
  28 Axiom set
  29 ---------
  30
  31 records, ...
  32
  33 DOCEND*)
  34
  35 nrecord Ax : Type[1] ≝ {
  36   S:> setoid;
  37   I: S → Type[0];
  38   C: ∀a:S. I a → Ω ^ S
  39 }.
  40
  41 (*HIDE*)
  42 notation "𝐈  \sub( ❨a❩ )" non associative with precedence 70 for @{ 'I $a }.
  43 notation "𝐂 \sub ( ❨a,\emsp i❩ )" non associative with precedence 70 for @{ 'C $a $i }.
  44 (*UNHIDE*)
  45
  46 (*DOCBEGIN
  47
  48 Notation for the axiom set
  49 --------------------------
  50
  51 bla bla
  52
  53 DOCEND*)
  54
  55 notation > "𝐈 term 90 a" non associative with precedence 70 for @{ 'I $a }.
  56 notation > "𝐂 term 90 a term 90 i" non associative with precedence 70 for @{ 'C $a $i }.
  57
  58 interpretation "I" 'I a = (I ? a).
  59 interpretation "C" 'C a i = (C ? a i).
  60
  61 (*DOCBEGIN
  62
  63 The first definition
  64 --------------------
  65
  66 ![bla bla][def-fish-rec]
  67
  68 DOCEND*)
  69
  70 ndefinition cover_set ≝ λc:∀A:Ax.Ω^A → A → CProp[0].λA,C,U.
  71   ∀y.y ∈ C → c A U y.
  72
  73 (* a \ltri b *)
  74 notation "hvbox(a break ◃ b)" non associative with precedence 45
  75 for @{ 'covers $a $b }.
  76
  77 interpretation "covers set temp" 'covers C U = (cover_set ?? C U).
  78
  79 ninductive cover (A : Ax) (U : Ω^A) : A → CProp[0] ≝
  80 | creflexivity : ∀a:A. a ∈ U → cover ? U a
  81 | cinfinity    : ∀a:A.∀i:𝐈 a. 𝐂 a i ◃ U → cover ? U a.
  82 napply cover;
  83 nqed.
  84
  85 interpretation "covers" 'covers a U = (cover ? U a).
  86 interpretation "covers set" 'covers a U = (cover_set cover ? a U).
  87
  88 ndefinition fish_set ≝ λf:∀A:Ax.Ω^A → A → CProp[0].
  89  λA,U,V.
  90   ∃a.a ∈ V ∧ f A U a.
  91
  92 (* a \ltimes b *)
  93 notation "hvbox(a break ⋉ b)" non associative with precedence 45
  94 for @{ 'fish $a $b }.
  95
  96 interpretation "fish set temp" 'fish A U = (fish_set ?? U A).
  97
  98 ncoinductive fish (A : Ax) (F : Ω^A) : A → CProp[0] ≝
  99 | cfish : ∀a. a ∈ F → (∀i:𝐈 a .𝐂  a i ⋉ F) → fish A F a.
 100 napply fish;
 101 nqed.
 102
 103 interpretation "fish set" 'fish A U = (fish_set fish ? U A).
 104 interpretation "fish" 'fish a U = (fish ? U a).
 105
 106 nlet corec fish_rec (A:Ax) (U: Ω^A)
 107  (P: Ω^A) (H1: P ⊆ U)
 108   (H2: ∀a:A. a ∈ P → ∀j: 𝐈 a. 𝐂 a j ≬ P):
 109    ∀a:A. ∀p: a ∈ P. a ⋉ U ≝ ?.
 110 #a; #p; napply cfish; (** screenshot "def-fish-rec". *)
 111 ##[ napply H1; napply p;
 112 ##| #i; ncases (H2 a p i); #x; *; #xC; #xP; @; ##[napply x]
 113     @; ##[ napply xC ] napply (fish_rec ? U P); nassumption;
 114 ##]
 115 nqed.
 116
 117 notation "◃U" non associative with precedence 55
 118 for @{ 'coverage $U }.
 119
 120 ndefinition coverage : ∀A:Ax.∀U:Ω^A.Ω^A ≝ λA,U.{ a | a ◃ U }.
 121
 122 interpretation "coverage cover" 'coverage U = (coverage ? U).
 123
 124 ndefinition cover_equation : ∀A:Ax.∀U,X:Ω^A.CProp[0] ≝  λA,U,X.
 125   ∀a.a ∈ X ↔ (a ∈ U ∨ ∃i:𝐈 a.∀y.y ∈ 𝐂 a i → y ∈ X).
 126
 127 ntheorem coverage_cover_equation : ∀A,U. cover_equation A U (◃U).
 128 #A; #U; #a; @; #H;
 129 ##[ nelim H; #b; (* manca clear *)
 130     ##[ #bU; @1; nassumption;
 131     ##| #i; #CaiU; #IH; @2; @ i; #c; #cCbi; ncases (IH ? cCbi);
 132         ##[ #E; @; napply E;
 133         ##| #_; napply CaiU; nassumption; ##] ##]
 134 ##| ncases H; ##[ #E; @; nassumption]
 135     *; #j; #Hj; @2 j; #w; #wC; napply Hj; nassumption;
 136 ##]
 137 nqed.
 138
 139 ntheorem coverage_min_cover_equation :
 140   ∀A,U,W. cover_equation A U W → ◃U ⊆ W.
 141 #A; #U; #W; #H; #a; #aU; nelim aU; #b;
 142 ##[ #bU; ncases (H b); #_; #H1; napply H1; @1; nassumption;
 143 ##| #i; #CbiU; #IH; ncases (H b); #_; #H1; napply H1; @2; @i; napply IH;
 144 ##]
 145 nqed.
 146
 147 notation "⋉F" non associative with precedence 55
 148 for @{ 'fished $F }.
 149
 150 ndefinition fished : ∀A:Ax.∀F:Ω^A.Ω^A ≝ λA,F.{ a | a ⋉ F }.
 151
 152 interpretation "fished fish" 'fished F = (fished ? F).
 153
 154 ndefinition fish_equation : ∀A:Ax.∀F,X:Ω^A.CProp[0] ≝ λA,F,X.
 155   ∀a. a ∈ X ↔ a ∈ F ∧ ∀i:𝐈 a.∃y.y ∈ 𝐂 a i ∧ y ∈ X.
 156
 157 ntheorem fised_fish_equation : ∀A,F. fish_equation A F (⋉F).
 158 #A; #F; #a; @; (* bug, fare case sotto diverso da farlo sopra *) #H; ncases H;
 159 ##[ #b; #bF; #H2; @ bF; #i; ncases (H2 i); #c; *; #cC; #cF; @c; @ cC;
 160     napply cF;
 161 ##| #aF; #H1; @ aF; napply H1;
 162 ##]
 163 nqed.
 164
 165 ntheorem fised_max_fish_equation : ∀A,F,G. fish_equation A F G → G ⊆ ⋉F.
 166 #A; #F; #G; #H; #a; #aG; napply (fish_rec … aG);
 167 #b; ncases (H b); #H1; #_; #bG; ncases (H1 bG); #E1; #E2; nassumption;
 168 nqed.
 169
 170 nrecord nAx : Type[2] ≝ {
 171   nS:> setoid; (*Type[0];*)
 172   nI: nS → Type[0];
 173   nD: ∀a:nS. nI a → Type[0];
 174   nd: ∀a:nS. ∀i:nI a. nD a i → nS
 175 }.
 176
 177 (*
 178 TYPE f A → B, g : B → A, f ∘ g = id, g ∘ g = id.
 179
 180 a = b → I a = I b
 181 *)
 182
 183 notation "𝐃 \sub ( ❨a,\emsp i❩ )" non associative with precedence 70 for @{ 'D $a $i }.
 184 notation "𝐝 \sub ( ❨a,\emsp i,\emsp j❩ )" non associative with precedence 70 for @{ 'd $a $i $j}.
 185
 186 notation > "𝐃 term 90 a term 90 i" non associative with precedence 70 for @{ 'D $a $i }.
 187 notation > "𝐝 term 90 a term 90 i term 90 j" non associative with precedence 70 for @{ 'd $a $i $j}.
 188
 189 interpretation "D" 'D a i = (nD ? a i).
 190 interpretation "d" 'd a i j = (nd ? a i j).
 191 interpretation "new I" 'I a = (nI ? a).
 192
 193 ndefinition image ≝ λA:nAx.λa:A.λi. { x | ∃j:𝐃 a i. x = 𝐝 a i j }.
 194
 195 notation > "𝐈𝐦  [𝐝 term 90 a term 90 i]" non associative with precedence 70 for @{ 'Im $a $i }.
 196 notation "𝐈𝐦  [𝐝 \sub ( ❨a,\emsp i❩ )]" non associative with precedence 70 for @{ 'Im $a $i }.
 197
 198 interpretation "image" 'Im a i = (image ? a i).
 199
 200 ndefinition Ax_of_nAx : nAx → Ax.
 201 #A; @ A (nI ?); #a; #i; napply (𝐈𝐦 [𝐝 a i]);
 202 nqed.
 203
 204 ninductive sigma (A : Type[0]) (P : A → CProp[0]) : Type[0] ≝
 205  sig_intro : ∀x:A.P x → sigma A P.
 206
 207 interpretation "sigma" 'sigma \eta.p = (sigma ? p).
 208
 209 ndefinition nAx_of_Ax : Ax → nAx.
 210 #A; @ A (I ?);
 211 ##[ #a; #i; napply (Σx:A.x ∈ 𝐂 a i);
 212 ##| #a; #i; *; #x; #_; napply x;
 213 ##]
 214 nqed.
 215
 216 ninductive Ord (A : nAx) : Type[0] ≝
 217  | oO : Ord A
 218  | oS : Ord A → Ord A
 219  | oL : ∀a:A.∀i.∀f:𝐃 a i → Ord A. Ord A.
 220
 221 notation "Λ term 90 f" non associative with precedence 50 for @{ 'oL $f }.
 222 notation "x+1" non associative with precedence 50 for @{'oS $x }.
 223
 224 interpretation "ordinals Lambda" 'oL f = (oL ? ? ? f).
 225 interpretation "ordinals Succ" 'oS x = (oS ? x).
 226
 227 nlet rec famU (A : nAx) (U : Ω^A) (x : Ord A) on x : Ω^A ≝
 228   match x with
 229   [ oO ⇒ U
 230   | oS y ⇒ let Un ≝ famU A U y in Un ∪ { x | ∃i.𝐈𝐦[𝐝 x i] ⊆ Un}
 231   | oL a i f ⇒ { x | ∃j.x ∈ famU A U (f j) } ].
 232
 233 notation < "term 90 U \sub (term 90 x)" non associative with precedence 50 for @{ 'famU $U $x }.
 234 notation > "U ⎽ term 90 x" non associative with precedence 50 for @{ 'famU $U $x }.
 235
 236 interpretation "famU" 'famU U x = (famU ? U x).
 237
 238 ndefinition ord_coverage : ∀A:nAx.∀U:Ω^A.Ω^A ≝ λA,U.{ y | ∃x:Ord A. y ∈ famU ? U x }.
 239
 240 ndefinition ord_cover_set ≝ λc:∀A:nAx.Ω^A → Ω^A.λA,C,U.
 241   ∀y.y ∈ C → y ∈ c A U.
 242
 243 interpretation "coverage new cover" 'coverage U = (ord_coverage ? U).
 244 interpretation "new covers set" 'covers a U = (ord_cover_set ord_coverage ? a U).
 245 interpretation "new covers" 'covers a U = (mem ? (ord_coverage ? U) a).
 246
 247 ntheorem new_coverage_reflexive:
 248   ∀A:nAx.∀U:Ω^A.∀a. a ∈ U → a ◃ U.
 249 #A; #U; #a; #H; @ (oO A); napply H;
 250 nqed.
 251
 252 nlemma ord_subset:
 253   ∀A:nAx.∀a:A.∀i,f,U.∀j:𝐃 a i.U⎽(f j) ⊆ U⎽(Λ f).
 254 #A; #a; #i; #f; #U; #j; #b; #bUf; @ j; nassumption;
 255 nqed.
 256
 257 naxiom AC : ∀A,a,i,U.(∀j:𝐃 a i.∃x:Ord A.𝐝 a i j ∈ U⎽x) → (Σf.∀j:𝐃 a i.𝐝 a i j ∈ U⎽(f j)).
 258
 259 naxiom setoidification :
 260   ∀A:nAx.∀a,b:A.∀U.a=b → b ∈ U → a ∈ U.
 261
 262 (*DOCBEGIN
 263
 264 Bla Bla,
 265
 266 <div id="figure1" class="img" ><img src="figure1.png"/>foo</div>
 267
 268 DOCEND*)
 269
 270 alias symbol "covers" = "new covers".
 271 alias symbol "covers" = "new covers set".
 272 alias symbol "covers" = "new covers".
 273 alias symbol "covers" = "new covers set".
 274 alias symbol "covers" = "new covers".
 275 alias symbol "covers" = "new covers set".
 276 alias symbol "covers" = "new covers".
 277 ntheorem new_coverage_infinity:
 278   ∀A:nAx.∀U:Ω^A.∀a:A. (∃i:𝐈 a. 𝐈𝐦[𝐝 a i] ◃ U) → a ◃ U.
 279 #A; #U; #a;(** screenshot "topology/figure1". *)
 280 *; #i; #H; nnormalize in H;
 281 ncut (∀y:𝐃 a i.∃x:Ord A.𝐝 a i y ∈ U⎽x); ##[
 282   #y; napply H; @ y; napply #; ##] #H';
 283 ncases (AC … H'); #f; #Hf;
 284 ncut (∀j.𝐝 a i j ∈ U⎽(Λ f));
 285   ##[ #j; napply (ord_subset … f … (Hf j));##] #Hf';
 286 @ ((Λ f)+1); @2; nwhd; @i; #x; *; #d; #Hd;
 287 napply (setoidification … Hd); napply Hf';
 288 nqed.
 289
 290 (* move away *)
 291 nlemma subseteq_union: ∀A.∀U,V,W:Ω^A.U ⊆ W → V ⊆ W → U ∪ V ⊆ W.
 292 #A; #U; #V; #W; #H; #H1; #x; *; #Hx; ##[ napply H; ##| napply H1; ##] nassumption;
 293 nqed.
 294
 295 nlemma new_coverage_min :
 296   ∀A:nAx.∀U:qpowerclass A.∀V.U ⊆ V → (∀a:A.∀i.𝐈𝐦[𝐝 a i] ⊆ V → a ∈ V) → ◃(pc ? U) ⊆ V.
 297 #A; #U; #V; #HUV; #Im;  #b; *; #o; ngeneralize in match b; nchange with ((pc ? U)⎽o ⊆ V);
 298 nelim o;
 299 ##[ #b; #bU0; napply HUV; napply bU0;
 300 ##| #p; #IH; napply subseteq_union; ##[ nassumption; ##]
 301     #x; *; #i; #H; napply (Im ? i); napply (subseteq_trans … IH); napply H;
 302 ##| #a; #i; #f; #IH; #x; *; #d; napply IH; ##]
 303 nqed.
 304
 305 nlet rec famF (A: nAx) (F : Ω^A) (x : Ord A) on x : Ω^A ≝
 306   match x with
 307   [ oO ⇒ F
 308   | oS o ⇒ let Fo ≝ famF A F o in Fo ∩ { x | ∀i:𝐈 x.∃j:𝐃 x i.𝐝 x i j ∈ Fo }
 309   | oL a i f ⇒ { x | ∀j:𝐃 a i.x ∈ famF A F (f j) }
 310   ].
 311
 312 interpretation "famF" 'famU U x = (famF ? U x).
 313
 314 ndefinition ord_fished : ∀A:nAx.∀F:Ω^A.Ω^A ≝ λA,F.{ y | ∀x:Ord A. y ∈ F⎽x }.
 315
 316 interpretation "fished new fish" 'fished U = (ord_fished ? U).
 317 interpretation "new fish" 'fish a U = (mem ? (ord_fished ? U) a).
 318
 319 ntheorem new_fish_antirefl:
 320  ∀A:nAx.∀F:Ω^A.∀a. a ⋉ F → a ∈ F.
 321 #A; #F; #a; #H; nlapply (H (oO ?)); #aFo; napply aFo;
 322 nqed.
 323
 324 nlemma co_ord_subset:
 325  ∀A:nAx.∀F:Ω^A.∀a,i.∀f:𝐃 a i → Ord A.∀j. F⎽(Λ f) ⊆ F⎽(f j).
 326 #A; #F; #a; #i; #f; #j; #x; #H; napply H;
 327 nqed.
 328
 329 naxiom AC_dual :
 330   ∀A:nAx.∀a:A.∀i,F. (∀f:𝐃 a i → Ord A.∃x:𝐃 a i.𝐝 a i x ∈ F⎽(f x)) → ∃j:𝐃 a i.∀x:Ord A.𝐝 a i j ∈ F⎽x.
 331
 332
 333 ntheorem new_fish_compatible:
 334  ∀A:nAx.∀F:Ω^A.∀a. a ⋉ F → ∀i:𝐈 a.∃j:𝐃 a i.𝐝 a i j ⋉ F.
 335 #A; #F; #a; #aF; #i; nnormalize;
 336 napply AC_dual; #f;
 337 nlapply (aF (Λf+1)); #aLf;
 338 nchange in aLf with (a ∈ F⎽(Λ f) ∧ ∀i:𝐈 a.∃j:𝐃 a i.𝐝 a i j ∈ F⎽(Λ f));
 339 ncut (∃j:𝐃 a i.𝐝 a i j ∈ F⎽(f j));##[
 340   ncases aLf; #_; #H; nlapply (H i); *; #j; #Hj; @j; napply Hj;##] #aLf';
 341 napply aLf';
 342 nqed.
 343
 344 (* move away *)
 345 nlemma subseteq_intersection_l: ∀A.∀U,V,W:Ω^A.U ⊆ W ∨ V ⊆ W → U ∩ V ⊆ W.
 346 #A; #U; #V; #W; *; #H; #x; *; #xU; #xV; napply H; nassumption;
 347 nqed.
 348
 349 nlemma subseteq_intersection_r: ∀A.∀U,V,W:Ω^A.W ⊆ U → W ⊆ V → W ⊆ U ∩ V.
 350 #A; #U; #V; #W; #H1; #H2; #x; #Hx; @; ##[ napply H1; ##| napply H2; ##] nassumption;
 351 nqed.
 352
 353 ntheorem max_new_fished:
 354   ∀A:nAx.∀G,F:Ω^A.G ⊆ F → (∀a.a ∈ G → ∀i.𝐈𝐦[𝐝 a i] ≬ G) → G ⊆ ⋉F.
 355 #A; #G; #F; #GF; #H; #b; #HbG; #o; ngeneralize in match HbG; ngeneralize in match b;
 356 nchange with (G ⊆ F⎽o);
 357 nelim o;
 358 ##[ napply GF;
 359 ##| #p; #IH; napply (subseteq_intersection_r … IH);
 360     #x; #Hx; #i; ncases (H … Hx i); #c; *; *; #d; #Ed; #cG;
 361     @d; napply IH; napply (setoidification … Ed^-1); napply cG;
 362 ##| #a; #i; #f; #Hf; nchange with (G ⊆ { y | ∀x. y ∈ F⎽(f x) });
 363     #b; #Hb; #d; napply (Hf d); napply Hb;
 364 ##]
 365 nqed.
 366