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

   1 include "sets/sets.ma".
   2
   3 nrecord Ax : Type[1] ≝ {
   4   S:> setoid; (* Type[0]; *)
   5   I: S → Type[0];
   6   C: ∀a:S. I a → Ω ^ S
   7 }.
   8
   9 notation "𝐈  \sub( ❨a❩ )" non associative with precedence 70 for @{ 'I $a }.
  10 notation "𝐂 \sub ( ❨a,\emsp i❩ )" non associative with precedence 70 for @{ 'C $a $i }.
  11
  12 notation > "𝐈 term 90 a" non associative with precedence 70 for @{ 'I $a }.
  13 notation > "𝐂 term 90 a term 90 i" non associative with precedence 70 for @{ 'C $a $i }.
  14
  15 interpretation "I" 'I a = (I ? a).
  16 interpretation "C" 'C a i = (C ? a i).
  17
  18 ndefinition cover_set ≝ λc:∀A:Ax.Ω^A → A → CProp[0].λA,C,U.
  19   ∀y.y ∈ C → c A U y.
  20
  21 (* a \ltri b *)
  22 notation "hvbox(a break ◃ b)" non associative with precedence 45
  23 for @{ 'covers $a $b }.
  24
  25 interpretation "covers set temp" 'covers C U = (cover_set ?? C U).
  26
  27 ninductive cover (A : Ax) (U : Ω^A) : A → CProp[0] ≝
  28 | creflexivity : ∀a:A. a ∈ U → cover ? U a
  29 | cinfinity    : ∀a:A.∀i:𝐈 a. 𝐂 a i ◃ U → cover ? U a.
  30 napply cover;
  31 nqed.
  32
  33 interpretation "covers" 'covers a U = (cover ? U a).
  34 interpretation "covers set" 'covers a U = (cover_set cover ? a U).
  35
  36 ndefinition fish_set ≝ λf:∀A:Ax.Ω^A → A → CProp[0].
  37  λA,U,V.
  38   ∃a.a ∈ V ∧ f A U a.
  39
  40 (* a \ltimes b *)
  41 notation "hvbox(a break ⋉ b)" non associative with precedence 45
  42 for @{ 'fish $a $b }.
  43
  44 interpretation "fish set temp" 'fish A U = (fish_set ?? U A).
  45
  46 ncoinductive fish (A : Ax) (F : Ω^A) : A → CProp[0] ≝
  47 | cfish : ∀a. a ∈ F → (∀i:𝐈 a .𝐂  a i ⋉ F) → fish A F a.
  48 napply fish;
  49 nqed.
  50
  51 interpretation "fish set" 'fish A U = (fish_set fish ? U A).
  52 interpretation "fish" 'fish a U = (fish ? U a).
  53
  54 nlet corec fish_rec (A:Ax) (U: Ω^A)
  55  (P: Ω^A) (H1: P ⊆ U)
  56   (H2: ∀a:A. a ∈ P → ∀j: 𝐈 a. 𝐂 a j ≬ P):
  57    ∀a:A. ∀p: a ∈ P. a ⋉ U ≝ ?.
  58 #a; #p; napply cfish;
  59 ##[ napply H1; napply p;
  60 ##| #i; ncases (H2 a p i); #x; *; #xC; #xP; @; ##[napply x]
  61     @; ##[ napply xC ] napply (fish_rec ? U P); nassumption;
  62 ##]
  63 nqed.
  64
  65 notation "◃U" non associative with precedence 55
  66 for @{ 'coverage $U }.
  67
  68 ndefinition coverage : ∀A:Ax.∀U:Ω^A.Ω^A ≝ λA,U.{ a | a ◃ U }.
  69
  70 interpretation "coverage cover" 'coverage U = (coverage ? U).
  71
  72 ndefinition cover_equation : ∀A:Ax.∀U,X:Ω^A.CProp[0] ≝  λA,U,X.
  73   ∀a.a ∈ X ↔ (a ∈ U ∨ ∃i:𝐈 a.∀y.y ∈ 𝐂 a i → y ∈ X).
  74
  75 ntheorem coverage_cover_equation : ∀A,U. cover_equation A U (◃U).
  76 #A; #U; #a; @; #H;
  77 ##[ nelim H; #b; (* manca clear *)
  78     ##[ #bU; @1; nassumption;
  79     ##| #i; #CaiU; #IH; @2; @ i; #c; #cCbi; ncases (IH ? cCbi);
  80         ##[ #E; @; napply E;
  81         ##| #_; napply CaiU; nassumption; ##] ##]
  82 ##| ncases H; ##[ #E; @; nassumption]
  83     *; #j; #Hj; @2 j; #w; #wC; napply Hj; nassumption;
  84 ##]
  85 nqed.
  86
  87 ntheorem coverage_min_cover_equation :
  88   ∀A,U,W. cover_equation A U W → ◃U ⊆ W.
  89 #A; #U; #W; #H; #a; #aU; nelim aU; #b;
  90 ##[ #bU; ncases (H b); #_; #H1; napply H1; @1; nassumption;
  91 ##| #i; #CbiU; #IH; ncases (H b); #_; #H1; napply H1; @2; @i; napply IH;
  92 ##]
  93 nqed.
  94
  95 notation "⋉F" non associative with precedence 55
  96 for @{ 'fished $F }.
  97
  98 ndefinition fished : ∀A:Ax.∀F:Ω^A.Ω^A ≝ λA,F.{ a | a ⋉ F }.
  99
 100 interpretation "fished fish" 'fished F = (fished ? F).
 101
 102 ndefinition fish_equation : ∀A:Ax.∀F,X:Ω^A.CProp[0] ≝ λA,F,X.
 103   ∀a. a ∈ X ↔ a ∈ F ∧ ∀i:𝐈 a.∃y.y ∈ 𝐂 a i ∧ y ∈ X.
 104
 105 ntheorem fised_fish_equation : ∀A,F. fish_equation A F (⋉F).
 106 #A; #F; #a; @; (* bug, fare case sotto diverso da farlo sopra *) #H; ncases H;
 107 ##[ #b; #bF; #H2; @ bF; #i; ncases (H2 i); #c; *; #cC; #cF; @c; @ cC;
 108     napply cF;
 109 ##| #aF; #H1; @ aF; napply H1;
 110 ##]
 111 nqed.
 112
 113 ntheorem fised_max_fish_equation : ∀A,F,G. fish_equation A F G → G ⊆ ⋉F.
 114 #A; #F; #G; #H; #a; #aG; napply (fish_rec … aG);
 115 #b; ncases (H b); #H1; #_; #bG; ncases (H1 bG); #E1; #E2; nassumption;
 116 nqed.
 117
 118 nrecord nAx : Type[2] ≝ {
 119   nS:> setoid; (*Type[0];*)
 120   nI: nS → Type[0];
 121   nD: ∀a:nS. nI a → Type[0];
 122   nd: ∀a:nS. ∀i:nI a. nD a i → nS
 123 }.
 124
 125 notation "𝐃 \sub ( ❨a,\emsp i❩ )" non associative with precedence 70 for @{ 'D $a $i }.
 126 notation "𝐝 \sub ( ❨a,\emsp i,\emsp j❩ )" non associative with precedence 70 for @{ 'd $a $i $j}.
 127
 128 notation > "𝐃 term 90 a term 90 i" non associative with precedence 70 for @{ 'D $a $i }.
 129 notation > "𝐝 term 90 a term 90 i term 90 j" non associative with precedence 70 for @{ 'd $a $i $j}.
 130
 131 interpretation "D" 'D a i = (nD ? a i).
 132 interpretation "d" 'd a i j = (nd ? a i j).
 133 interpretation "new I" 'I a = (nI ? a).
 134
 135 ndefinition image ≝ λA:nAx.λa:A.λi. { x | ∃j:𝐃 a i. x = 𝐝 a i j }.
 136
 137 notation > "𝐈𝐦  [𝐝 term 90 a term 90 i]" non associative with precedence 70 for @{ 'Im $a $i }.
 138 notation "𝐈𝐦  [𝐝 \sub ( ❨a,\emsp i❩ )]" non associative with precedence 70 for @{ 'Im $a $i }.
 139
 140 interpretation "image" 'Im a i = (image ? a i).
 141
 142 (*
 143 ndefinition Ax_of_nAx : nAx → Ax.
 144 #A; @ A (nI ?); #a; #i; napply (𝐈𝐦 [𝐝 a i]);
 145 nqed.
 146
 147 ninductive sigma (A : Type[0]) (P : A → CProp[0]) : Type[0] ≝
 148  sig_intro : ∀x:A.P x → sigma A P.
 149
 150 interpretation "sigma" 'sigma \eta.p = (sigma ? p).
 151
 152 ndefinition nAx_of_Ax : Ax → nAx.
 153 #A; @ A (I ?);
 154 ##[ #a; #i; napply (Σx:A.x ∈ 𝐂 a i);
 155 ##| #a; #i; *; #x; #_; napply x;
 156 ##]
 157 nqed.
 158 *)
 159
 160 ninductive Ord (A : nAx) : Type[0] ≝
 161  | oO : Ord A
 162  | oS : Ord A → Ord A
 163  | oL : ∀a:A.∀i.∀f:𝐃 a i → Ord A. Ord A.
 164
 165 notation "Λ term 90 f" non associative with precedence 50 for @{ 'oL $f }.
 166 notation "x+1" non associative with precedence 50 for @{'oS $x }.
 167
 168 interpretation "ordinals Lambda" 'oL f = (oL ? ? ? f).
 169 interpretation "ordinals Succ" 'oS x = (oS ? x).
 170
 171 nlet rec famU (A : nAx) (U : Ω^A) (x : Ord A) on x : Ω^A ≝
 172   match x with
 173   [ oO ⇒ U
 174   | oS y ⇒ let Un ≝ famU A U y in Un ∪ { x | ∃i.𝐈𝐦[𝐝 x i] ⊆ Un}
 175   | oL a i f ⇒ { x | ∃j.x ∈ famU A U (f j) } ].
 176
 177 naxiom XXX : False.
 178
 179 ndefinition qp_famU : ∀A:nAx.∀U:qpowerclass A.∀x:Ord A.qpowerclass A ≝
 180   λA,U,x.?.
 181 @ (famU ? (pc ? U) x); nelim x;
 182 ##[ #a; #b; #E; nnormalize; @; #H; ##[ napply (. E^-1‡#); napply H; ##| napply (. E‡#); napply H; ##]
 183 ##| #o; #IH; #a; #b; #E; @; nnormalize; *; #H;
 184     ##[##1,3: @1; nlapply (IH … E); *; #G; #G';
 185               ##[ napply G | napply G'] nassumption;
 186     ##|##2,4: @2; ncases H; #i_a; #H_ia; @;
 187  nelim XXX; ##]
 188 ##| nelim XXX;
 189 ##]
 190 nqed.
 191
 192 unification hint 0 ≔
 193   A,U,x; UU ≟ (pc ? U) ⊢ pc ? (qp_famU A U x) ≡ famU A UU x.
 194
 195 notation < "term 90 U \sub (term 90 x)" non associative with precedence 50 for @{ 'famU $U $x }.
 196 notation > "U ⎽ term 90 x" non associative with precedence 50 for @{ 'famU $U $x }.
 197
 198 interpretation "famU" 'famU U x = (famU ? U x).
 199
 200 ndefinition ord_coverage : ∀A:nAx.∀U:Ω^A.Ω^A ≝ λA,U.{ y | ∃x:Ord A. y ∈ famU ? U x }.
 201
 202 ndefinition ord_cover_set ≝ λc:∀A:nAx.Ω^A → Ω^A.λA,C,U.
 203   ∀y.y ∈ C → y ∈ c A U.
 204
 205 interpretation "coverage new cover" 'coverage U = (ord_coverage ? U).
 206 interpretation "new covers set" 'covers a U = (ord_cover_set ord_coverage ? a U).
 207 interpretation "new covers" 'covers a U = (mem ? (ord_coverage ? U) a).
 208
 209 ntheorem new_coverage_reflexive:
 210   ∀A:nAx.∀U:Ω^A.∀a. a ∈ U → a ◃ U.
 211 #A; #U; #a; #H; @ (oO A); napply H;
 212 nqed.
 213
 214 nlemma ord_subset:
 215   ∀A:nAx.∀a:A.∀i,f,U.∀j:𝐃 a i.U⎽(f j) ⊆ U⎽(Λ f).
 216 #A; #a; #i; #f; #U; #j; #b; #bUf; @ j; nassumption;
 217 nqed.
 218
 219 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)).
 220
 221 naxiom setoidification :
 222   ∀A:nAx.∀a,b:A.∀U.a=b → b ∈ U → a ∈ U.
 223
 224 alias symbol "covers" = "new covers set".
 225 alias symbol "covers" = "new covers".
 226 alias symbol "covers" = "new covers set".
 227 alias symbol "covers" = "new covers".
 228 alias symbol "covers" = "new covers set".
 229 alias symbol "covers" = "new covers".
 230 ntheorem new_coverage_infinity:
 231   ∀A:nAx.∀U:Ω^A.∀a:A. (∃i:𝐈 a. 𝐈𝐦[𝐝 a i] ◃ U) → a ◃ U.
 232 #A; #U; #a; *; #i; #H; nnormalize in H;
 233 ncut (∀y:𝐃 a i.∃x:Ord A.𝐝 a i y ∈ U⎽x); ##[
 234   #y; napply H; @ y; napply #; ##] #H';
 235 ncases (AC … H'); #f; #Hf;
 236 ncut (∀j.𝐝 a i j ∈ U⎽(Λ f));
 237   ##[ #j; napply (ord_subset … f … (Hf j));##] #Hf';
 238 @ ((Λ f)+1); @2; nwhd; @i; #x; *; #d; #Hd; napply (setoidification … Hd); napply Hf';
 239 nqed.
 240
 241 (* move away *)
 242 nlemma subseteq_union: ∀A.∀U,V,W:Ω^A.U ⊆ W → V ⊆ W → U ∪ V ⊆ W.
 243 #A; #U; #V; #W; #H; #H1; #x; *; #Hx; ##[ napply H; ##| napply H1; ##] nassumption;
 244 nqed.
 245
 246 nlemma new_coverage_min :
 247   ∀A:nAx.∀U:qpowerclass A.∀V.U ⊆ V → (∀a:A.∀i.𝐈𝐦[𝐝 a i] ⊆ V → a ∈ V) → ◃(pc ? U) ⊆ V.
 248 #A; #U; #V; #HUV; #Im;  #b; *; #o; ngeneralize in match b; nchange with ((pc ? U)⎽o ⊆ V);
 249 nelim o;
 250 ##[ #b; #bU0; napply HUV; napply bU0;
 251 ##| #p; #IH; napply subseteq_union; ##[ nassumption; ##]
 252     #x; *; #i; #H; napply (Im ? i); napply (subseteq_trans … IH); napply H;
 253 ##| #a; #i; #f; #IH; #x; *; #d; napply IH; ##]
 254 nqed.
 255
 256