helm/software/matita/library/datatypes/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 "datatypes/categories.ma".
  17
  18 record powerset_carrier (A: setoid) : Type ≝ { mem_operator: A ⇒ CPROP }.
  19
  20 definition subseteq_operator ≝
  21  λA:setoid.λU,V.∀a:A. mem_operator ? U a → mem_operator ? V a.
  22
  23 theorem transitive_subseteq_operator: ∀A. transitive ? (subseteq_operator A).
  24  intros 6; intros 2;
  25  apply s1; apply s;
  26  assumption.
  27 qed.
  28
  29 (*
  30
  31 definition powerset_setoid: setoid → setoid1.
  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_setoid A).
  45
  46 interpretation "subset construction" 'subset \eta.x =
  47  (mk_powerset_carrier _ (mk_unary_morphism _ CPROP x _)).
  48
  49 definition mem: ∀A. binary_morphism1 A (Ω \sup A) 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 ????? (prop_1 ?? u ?? H));
  56     cases H1; whd in s s1;
  57     split; intro;
  58      [ apply s; assumption
  59      | apply s1; assumption]]
  60 qed.
  61
  62 interpretation "mem" 'mem a S = (fun1 ??? (mem ?) a S).
  63
  64 definition subseteq: ∀A. binary_morphism1 (Ω \sup A) (Ω \sup A) CPROP.
  65  intros;
  66  constructor 1;
  67   [ apply (λU,V. subseteq_operator ? U V)
  68   | intros;
  69     cases H; cases H1;
  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 = (fun1 ??? (subseteq ?) U V).
  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   [ apply (λA.λU,V:Ω \sup A.exT2 ? (λx:A.x ∈ U) (λx:A.x ∈ V))
  91   | intros;
  92     constructor 1; intro; cases H2; exists; [1,4: apply w]
  93      [ apply (. #‡H); assumption
  94      | apply (. #‡H1); assumption
  95      | apply (. #‡(H \sup -1)); assumption;
  96      | apply (. #‡(H1 \sup -1)); assumption]]
  97 qed.
  98
  99 interpretation "overlaps" 'overlaps U V = (fun1 ??? (overlaps ?) U V).
 100
 101 definition intersects:
 102  ∀A. binary_morphism1 (powerset_setoid A) (powerset_setoid A) (powerset_setoid A).
 103  intros;
 104  constructor 1;
 105   [ apply (λU,V. {x | x ∈ U ∧ x ∈ V });
 106     intros; simplify; apply (.= (H‡#)‡(H‡#)); apply refl1;
 107   | intros;
 108     split; intros 2; simplify in f ⊢ %;
 109     [ apply (. (#‡H)‡(#‡H1)); assumption
 110     | apply (. (#‡(H \sup -1))‡(#‡(H1 \sup -1))); assumption]]
 111 qed.
 112
 113 interpretation "intersects" 'intersects U V = (fun1 ??? (intersects ?) U V).
 114
 115 definition union:
 116  ∀A. binary_morphism1 (powerset_setoid A) (powerset_setoid A) (powerset_setoid A).
 117  intros;
 118  constructor 1;
 119   [ apply (λU,V. {x | x ∈ U ∨ x ∈ V });
 120     intros; simplify; apply (.= (H‡#)‡(H‡#)); apply refl1
 121   | intros;
 122     split; intros 2; simplify in f ⊢ %;
 123     [ apply (. (#‡H)‡(#‡H1)); assumption
 124     | apply (. (#‡(H \sup -1))‡(#‡(H1 \sup -1))); assumption]]
 125 qed.
 126
 127 interpretation "union" 'union U V = (fun1 ??? (union ?) U V).
 128
 129 definition singleton: ∀A:setoid. unary_morphism A (Ω \sup A).
 130  intros; constructor 1;
 131   [ apply (λA:setoid.λa:A.{b | a=b});
 132     intros; simplify;
 133     split; intro;
 134     apply (.= H1);
 135      [ apply H | apply (H \sup -1) ]
 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 = (fun_1 ?? (singleton ?) a).
 141
 142 *)