helm/software/matita/contribs/formal_topology/overlap/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 "logic/cprop_connectives.ma".
  16 include "categories.ma".
  17
  18 record powerset_carrier (A: objs1 SET) : Type1 ≝ { mem_operator: unary_morphism1 A CPROP }.
  19
  20 definition subseteq_operator: ∀A: SET. powerset_carrier A → powerset_carrier A → CProp1 ≝
  21  λA:objs1 SET.λU,V.∀a:A. mem_operator ? U a → mem_operator ? V a.
  22
  23 theorem transitive_subseteq_operator: ∀A. transitive2 ? (subseteq_operator A).
  24  intros 6; intros 2;
  25  apply s1; apply s;
  26  assumption.
  27 qed.
  28
  29 definition powerset_setoid1: SET → SET1.
  30  intros (T);
  31  constructor 1;
  32   [ apply (powerset_carrier T)
  33   | constructor 1;
  34      [ apply (λU,V. subseteq_operator ? U V ∧ subseteq_operator ? V U)
  35      | simplify; intros; split; intros 2; assumption
  36      | simplify; intros (x y H); cases H; split; assumption
  37      | simplify; intros (x y z H H1); cases H; cases H1; split;
  38        apply transitive_subseteq_operator; [1,4: apply y ]
  39        assumption ]]
  40 qed.
  41
  42 interpretation "powerset" 'powerset A = (powerset_setoid1 A).
  43
  44 interpretation "subset construction" 'subset \eta.x =
  45  (mk_powerset_carrier _ (mk_unary_morphism1 _ CPROP x _)).
  46
  47 definition mem: ∀A. binary_morphism1 A (Ω \sup A) CPROP.
  48  intros;
  49  constructor 1;
  50   [ apply (λx,S. mem_operator ? S x)
  51   | intros 5;
  52     cases b; clear b; cases b'; clear b'; simplify; intros;
  53     apply (trans1 ????? (prop11 ?? u ?? e));
  54     cases e1; whd in s s1;
  55     split; intro;
  56      [ apply s; assumption
  57      | apply s1; assumption]]
  58 qed.
  59
  60 interpretation "mem" 'mem a S = (fun21 ___ (mem _) a S).
  61
  62 definition subseteq: ∀A. binary_morphism1 (Ω \sup A) (Ω \sup A) CPROP.
  63  intros;
  64  constructor 1;
  65   [ apply (λU,V. subseteq_operator ? U V)
  66   | intros;
  67     cases e; cases e1;
  68     split; intros 1;
  69     [ apply (transitive_subseteq_operator ????? s2);
  70       apply (transitive_subseteq_operator ???? s1 s4)
  71     | apply (transitive_subseteq_operator ????? s3);
  72       apply (transitive_subseteq_operator ???? s s4) ]]
  73 qed.
  74
  75 interpretation "subseteq" 'subseteq U V = (fun21 ___ (subseteq _) U V).
  76
  77
  78
  79 theorem subseteq_refl: ∀A.∀S:Ω \sup A.S ⊆ S.
  80  intros 4; assumption.
  81 qed.
  82
  83 theorem subseteq_trans: ∀A.∀S1,S2,S3: Ω \sup A. S1 ⊆ S2 → S2 ⊆ S3 → S1 ⊆ S3.
  84  intros; apply transitive_subseteq_operator; [apply S2] assumption.
  85 qed.
  86
  87 definition overlaps: ∀A. binary_morphism1 (Ω \sup A) (Ω \sup A) CPROP.
  88  intros;
  89  constructor 1;
  90   (* Se metto x al posto di ? ottengo una universe inconsistency *)
  91   [ apply (λA:objs1 SET.λU,V:Ω \sup A.(exT2 ? (λx:A.?(*x*) ∈ U) (λx:A.?(*x*) ∈ V) : CProp0))
  92   | intros;
  93     constructor 1; intro; cases e2; exists; [1,4: apply w]
  94      [ apply (. #‡e); assumption
  95      | apply (. #‡e1); assumption
  96      | apply (. #‡(e \sup -1)); assumption;
  97      | apply (. #‡(e1 \sup -1)); assumption]]
  98 qed.
  99
 100 interpretation "overlaps" 'overlaps U V = (fun21 ___ (overlaps _) U V).
 101
 102 definition intersects:
 103  ∀A. binary_morphism1 (Ω \sup A) (Ω \sup A) (Ω \sup A).
 104  intros;
 105  constructor 1;
 106   [ apply rule (λU,V. {x | x ∈ U ∧ x ∈ V });
 107     intros; simplify; apply (.= (e‡#)‡(e‡#)); apply refl1;
 108   | intros;
 109     split; intros 2; simplify in f ⊢ %;
 110     [ apply (. (#‡e)‡(#‡e1)); assumption
 111     | apply (. (#‡(e \sup -1))‡(#‡(e1 \sup -1))); assumption]]
 112 qed.
 113
 114 interpretation "intersects" 'intersects U V = (fun21 ___ (intersects _) U V).
 115
 116 definition union:
 117  ∀A. binary_morphism1 (Ω \sup A) (Ω \sup A) (Ω \sup A).
 118  intros;
 119  constructor 1;
 120   [ apply (λU,V. {x | x ∈ U ∨ x ∈ V });
 121     intros; simplify; apply (.= (e‡#)‡(e‡#)); apply refl1
 122   | intros;
 123     split; intros 2; simplify in f ⊢ %;
 124     [ apply (. (#‡e)‡(#‡e1)); assumption
 125     | apply (. (#‡(e \sup -1))‡(#‡(e1 \sup -1))); assumption]]
 126 qed.
 127
 128 interpretation "union" 'union U V = (fun21 ___ (union _) U V).
 129
 130 (* qua non riesco a mettere set *)
 131 definition singleton: ∀A:setoid. unary_morphism1 A (Ω \sup A).
 132  intros; constructor 1;
 133   [ apply (λa:A.{b | eq ? a b}); unfold setoid1_of_setoid; simplify;
 134     intros; simplify;
 135     split; intro;
 136     apply (.= e1);
 137      [ apply e | apply (e \sup -1) ]
 138   | unfold setoid1_of_setoid; simplify;
 139     intros; split; intros 2; simplify in f ⊢ %; apply trans;
 140      [ apply a |4: apply a'] try assumption; apply sym; assumption]
 141 qed.
 142
 143 interpretation "singleton" 'singl a = (fun11 __ (singleton _) a).