helm/software/matita/library/formal_topology/subsets.ma

   1 (**************************************************************************)
   2 (*       ___                                                              *)
   3 (*      ||M||                                                             *)
   4 (*      ||A||       A project by Andrea Asperti                           *)
   5 (*      ||T||                                                             *)
   6 (*      ||I||       Developers:                                           *)
   7 (*      ||T||         The HELM team.                                      *)
   8 (*      ||A||         http://helm.cs.unibo.it                             *)
   9 (*      \   /                                                             *)
  10 (*       \ /        This file is distributed under the terms of the       *)
  11 (*        v         GNU General Public License Version 2                  *)
  12 (*                                                                        *)
  13 (**************************************************************************)
  14
  15 include "formal_topology/categories.ma".
  16
  17 record powerset_carrier (A: objs1 SET) : Type1 ≝ { mem_operator: A ⇒_1 CPROP }.
  18 interpretation "powerset low" 'powerset A = (powerset_carrier A).
  19 notation "hvbox(a break ∈. b)" non associative with precedence 45 for @{ 'mem_low $a $b }.
  20 interpretation "memlow" 'mem_low a S = (fun11 ?? (mem_operator ? S) a).
  21
  22 definition subseteq_operator: ∀A: objs1 SET. Ω^A → Ω^A → CProp0 ≝
  23  λA:objs1 SET.λU,V.∀a:A. a ∈. U → a ∈. V.
  24
  25 theorem transitive_subseteq_operator: ∀A. transitive2 ? (subseteq_operator A).
  26  intros 6; intros 2;
  27  apply s1; apply s;
  28  assumption.
  29 qed.
  30
  31 definition powerset_setoid1: SET → SET1.
  32  intros (T);
  33  constructor 1;
  34   [ apply (powerset_carrier T)
  35   | constructor 1;
  36      [ apply (λU,V. subseteq_operator ? U V ∧ subseteq_operator ? V U)
  37      | simplify; intros; split; intros 2; assumption
  38      | simplify; intros (x y H); cases H; split; assumption
  39      | simplify; intros (x y z H H1); cases H; cases H1; split;
  40        apply transitive_subseteq_operator; [1,4: apply y ]
  41        assumption ]]
  42 qed.
  43
  44 interpretation "powerset" 'powerset A = (powerset_setoid1 A).
  45
  46 interpretation "subset construction" 'subset \eta.x =
  47  (mk_powerset_carrier ? (mk_unary_morphism1 ? CPROP x ?)).
  48
  49 definition mem: ∀A. A × Ω^A ⇒_1 CPROP.
  50  intros;
  51  constructor 1;
  52   [ apply (λx,S. mem_operator ? S x)
  53   | intros 5;
  54     cases b; clear b; cases b'; clear b'; simplify; intros;
  55     apply (trans1 ????? (prop11 ?? u ?? e));
  56     cases e1; whd in s s1;
  57     split; intro;
  58      [ apply s; assumption
  59      | apply s1; assumption]]
  60 qed.
  61
  62 interpretation "mem" 'mem a S = (fun21 ??? (mem ?) a S).
  63
  64 definition subseteq: ∀A. Ω^A × Ω^A ⇒_1 CPROP.
  65  intros;
  66  constructor 1;
  67   [ apply (λU,V. subseteq_operator ? U V)
  68   | intros;
  69     cases e; cases e1;
  70     split; intros 1;
  71     [ apply (transitive_subseteq_operator ????? s2);
  72       apply (transitive_subseteq_operator ???? s1 s4)
  73     | apply (transitive_subseteq_operator ????? s3);
  74       apply (transitive_subseteq_operator ???? s s4) ]]
  75 qed.
  76
  77 interpretation "subseteq" 'subseteq U V = (fun21 ??? (subseteq ?) U V).
  78
  79 theorem subseteq_refl: ∀A.∀S:Ω^A.S ⊆ S.
  80  intros 4; assumption.
  81 qed.
  82
  83 theorem subseteq_trans: ∀A.∀S1,S2,S3: Ω^A. S1 ⊆ S2 → S2 ⊆ S3 → S1 ⊆ S3.
  84  intros; apply transitive_subseteq_operator; [apply S2] assumption.
  85 qed.
  86
  87 definition overlaps: ∀A. Ω^A × Ω^A ⇒_1 CPROP.
  88  intros;
  89  constructor 1;
  90   [ apply (λA:objs1 SET.λU,V:Ω^A.(exT2 ? (λx:A.x ∈ U) (λx:A.x ∈ V) : CProp0))
  91   | intros;
  92     constructor 1; intro; cases e2; exists; [1,4: apply w]
  93      [ apply (. #‡e^-1); assumption
  94      | apply (. #‡e1^-1); assumption
  95      | apply (. #‡e); assumption;
  96      | apply (. #‡e1); assumption]]
  97 qed.
  98
  99 interpretation "overlaps" 'overlaps U V = (fun21 ??? (overlaps ?) U V).
 100
 101 definition intersects: ∀A. Ω^A × Ω^A ⇒_1 Ω^A.
 102  intros;
 103  constructor 1;
 104   [ apply rule (λU,V. {x | x ∈ U ∧ x ∈ V });
 105     intros; simplify; apply (.= (e‡#)‡(e‡#)); apply refl1;
 106   | intros;
 107     split; intros 2; simplify in f ⊢ %;
 108     [ apply (. (#‡e^-1)‡(#‡e1^-1)); assumption
 109     | apply (. (#‡e)‡(#‡e1)); assumption]]
 110 qed.
 111
 112 interpretation "intersects" 'intersects U V = (fun21 ??? (intersects ?) U V).
 113
 114 definition union: ∀A. Ω^A × Ω^A ⇒_1 Ω^A.
 115  intros;
 116  constructor 1;
 117   [ apply (λU,V. {x | x ∈ U ∨ x ∈ V });
 118     intros; simplify; apply (.= (e‡#)‡(e‡#)); apply refl1
 119   | intros;
 120     split; intros 2; simplify in f ⊢ %;
 121     [ apply (. (#‡e^-1)‡(#‡e1^-1)); assumption
 122     | apply (. (#‡e)‡(#‡e1)); assumption]]
 123 qed.
 124
 125 interpretation "union" 'union U V = (fun21 ??? (union ?) U V).
 126
 127 (* qua non riesco a mettere set *)
 128 definition singleton: ∀A:setoid. A ⇒_1 Ω^A.
 129  intros; constructor 1;
 130   [ apply (λa:A.{b | a =_0 b}); unfold setoid1_of_setoid; simplify;
 131     intros; simplify;
 132     split; intro;
 133     apply (.= e1);
 134      [ apply e | apply (e^-1) ]
 135   | unfold setoid1_of_setoid; simplify;
 136     intros; split; intros 2; simplify in f ⊢ %; apply trans;
 137      [ apply a |4: apply a'] try assumption; apply sym; assumption]
 138 qed.
 139
 140 interpretation "singleton" 'singl a = (fun11 ?? (singleton ?) a).
 141 notation > "{ term 19 a : S }" with precedence 90 for @{fun11 ?? (singleton $S) $a}.
 142
 143 definition big_intersects: ∀A:SET.∀I:SET.(I ⇒_2 Ω^A) ⇒_2 Ω^A.
 144  intros; constructor 1;
 145   [ intro; whd; whd in I;
 146     apply ({x | ∀i:I. x ∈ c i});
 147     simplify; intros; split; intros; [ apply (. (e^-1‡#)); | apply (. e‡#); ]
 148     apply f;
 149   | intros; split; intros 2; simplify in f ⊢ %; intro;
 150      [ apply (. (#‡(e i)^-1)); apply f;
 151      | apply (. (#‡e i)); apply f]]
 152 qed.
 153
 154 definition big_union: ∀A:SET.∀I:SET.(I ⇒_2 Ω^A) ⇒_2 Ω^A.
 155  intros; constructor 1;
 156   [ intro; whd; whd in A; whd in I;
 157     apply ({x | ∃i:I. x ∈ c i });
 158     simplify; intros; split; intros; cases e1; clear e1; exists; [1,3:apply w]
 159     [ apply (. (e^-1‡#)); | apply (. (e‡#)); ]
 160     apply x;
 161   | intros; split; intros 2; simplify in f ⊢ %; cases f; clear f; exists; [1,3:apply w]
 162      [ apply (. (#‡(e w)^-1)); apply x;
 163      | apply (. (#‡e w)); apply x]]
 164 qed.
 165
 166 notation < "hovbox(mstyle scriptlevel 1 scriptsizemultiplier 1.7 (⋃) \below (\emsp) term 90 p)"
 167 non associative with precedence 50 for @{ 'bigcup $p }.
 168 notation < "hovbox(mstyle scriptlevel 1 scriptsizemultiplier 1.7 (⋃) \below (ident i ∈  I) break term 90 p)"
 169 non associative with precedence 50 for @{ 'bigcup_mk (λ${ident i}:$I.$p) }.
 170 notation > "hovbox(⋃ f)" non associative with precedence 60 for @{ 'bigcup $f }.
 171
 172 notation < "hovbox(mstyle scriptlevel 1 scriptsizemultiplier 1.7 (⋂) \below (\emsp) term 90 p)"
 173 non associative with precedence 50 for @{ 'bigcap $p }.
 174 notation < "hovbox(mstyle scriptlevel 1 scriptsizemultiplier 1.7 (⋂) \below (ident i ∈  I) break term 90 p)"
 175 non associative with precedence 50 for @{ 'bigcap_mk (λ${ident i}:$I.$p) }.
 176 notation > "hovbox(⋂ f)" non associative with precedence 60 for @{ 'bigcap $f }.
 177
 178 interpretation "bigcup" 'bigcup f = (fun12 ?? (big_union ??) f).
 179 interpretation "bigcap" 'bigcap f = (fun12 ?? (big_intersects ??) f).
 180 interpretation "bigcup mk" 'bigcup_mk f = (fun12 ?? (big_union ??) (mk_unary_morphism2 ?? f ?)).
 181 interpretation "bigcap mk" 'bigcap_mk f = (fun12 ?? (big_intersects ??) (mk_unary_morphism2 ?? f ?)).