helm/software/matita/contribs/formal_topology/overlap/relations_to_o-algebra.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 "relations.ma".
  16 include "o-algebra.ma".
  17
  18 definition SUBSETS: objs1 SET → OAlgebra.
  19  intro A; constructor 1;
  20   [ apply (Ω \sup A);
  21   | apply subseteq;
  22   | apply overlaps;
  23   | apply big_intersects;
  24   | apply big_union;
  25   | apply ({x | True});
  26     simplify; intros; apply (refl1 ? (eq1 CPROP));
  27   | apply ({x | False});
  28     simplify; intros; apply (refl1 ? (eq1 CPROP));
  29   | intros; whd; intros; assumption
  30   | intros; whd; split; assumption
  31   | intros; apply transitive_subseteq_operator; [2: apply f; | skip | assumption]
  32   | intros; cases f; exists [apply w] assumption
  33   | intros; split; [ intros 4; apply (f ? f1 i); | intros 3; intro; apply (f i ? f1); ]
  34   | intros; split;
  35      [ intros 4; apply f; exists; [apply i] assumption;
  36      | intros 3; intros; cases f1; apply (f w a x); ]
  37   | intros 3; cases f;
  38   | intros 3; constructor 1;
  39   | intros; cases f; exists; [apply w]
  40      [ assumption
  41      | whd; intros; cases i; simplify; assumption]
  42   | intros; split; intro;
  43      [ cases f; cases x1; exists [apply w1] exists [apply w] assumption;
  44      | cases e; cases x; exists; [apply w1] [ assumption | exists; [apply w] assumption]]
  45   | intros; intros 2; cases (f (singleton ? a) ?);
  46      [ exists; [apply a] [assumption | change with (a = a); apply refl1;]
  47      | change in x1 with (a = w); change with (mem A a q); apply (. (x1‡#));
  48        assumption]]
  49 qed.
  50
  51 definition orelation_of_relation: ∀o1,o2:REL. arrows1 ? o1 o2 → arrows2 OA (SUBSETS o1) (SUBSETS o2).
  52  intros;
  53  constructor 1;
  54   [ constructor 1;
  55      [ apply (λU.image ?? c U);
  56      | intros; apply (#‡e); ]
  57   | constructor 1;
  58      [ apply (λU.minus_star_image ?? c U);
  59      | intros; apply (#‡e); ]
  60   | constructor 1;
  61      [ apply (λU.star_image ?? c U);
  62      | intros; apply (#‡e); ]
  63   | constructor 1;
  64      [ apply (λU.minus_image ?? c U);
  65      | intros; apply (#‡e); ]
  66   | intros; split; intro;
  67      [ change in f with (∀a. a ∈ image ?? c p → a ∈ q);
  68        change with (∀a:o1. a ∈ p → a ∈ star_image ?? c q);
  69        intros 4; apply f; exists; [apply a] split; assumption;
  70      | change in f with (∀a:o1. a ∈ p → a ∈ star_image ?? c q);
  71        change with (∀a. a ∈ image ?? c p → a ∈ q);
  72        intros; cases f1; cases x; clear f1 x; apply (f ? f3); assumption; ]
  73   | intros; split; intro;
  74      [ change in f with (∀a. a ∈ minus_image ?? c p → a ∈ q);
  75        change with (∀a:o2. a ∈ p → a ∈ minus_star_image ?? c q);
  76        intros 4; apply f; exists; [apply a] split; assumption;
  77      | change in f with (∀a:o2. a ∈ p → a ∈ minus_star_image ?? c q);
  78        change with (∀a. a ∈ minus_image ?? c p → a ∈ q);
  79        intros; cases f1; cases x; clear f1 x; apply (f ? f3); assumption; ]
  80   | intros; split; intro; cases f; clear f;
  81      [ cases x; cases x2; clear x x2; exists; [apply w1]
  82         [ assumption;
  83         | exists; [apply w] split; assumption]
  84      | cases x1; cases x2; clear x1 x2; exists; [apply w1]
  85         [ exists; [apply w] split; assumption;
  86         | assumption; ]]]
  87 qed.
  88
  89 lemma orelation_of_relation_preserves_equality:
  90  ∀o1,o2:REL.∀t,t': arrows1 ? o1 o2. t = t' → eq2 ? (orelation_of_relation ?? t) (orelation_of_relation ?? t').
  91  intros; split; unfold orelation_of_relation; simplify; intro; split; intro;
  92  simplify; whd in o1 o2;
  93   [ change with (a1 ∈ minus_star_image ?? t a → a1 ∈ minus_star_image ?? t' a);
  94     apply (. #‡(e^-1‡#));
  95   | change with (a1 ∈ minus_star_image ?? t' a → a1 ∈ minus_star_image ?? t a);
  96     apply (. #‡(e‡#));
  97   | change with (a1 ∈ minus_image ?? t a → a1 ∈ minus_image ?? t' a);
  98     apply (. #‡(e ^ -1‡#));
  99   | change with (a1 ∈ minus_image ?? t' a → a1 ∈ minus_image ?? t a);
 100     apply (. #‡(e‡#));
 101   | change with (a1 ∈ image ?? t a → a1 ∈ image ?? t' a);
 102     apply (. #‡(e ^ -1‡#));
 103   | change with (a1 ∈ image ?? t' a → a1 ∈ image ?? t a);
 104     apply (. #‡(e‡#));
 105   | change with (a1 ∈ star_image ?? t a → a1 ∈ star_image ?? t' a);
 106     apply (. #‡(e ^ -1‡#));
 107   | change with (a1 ∈ star_image ?? t' a → a1 ∈ star_image ?? t a);
 108     apply (. #‡(e‡#)); ]
 109 qed.
 110
 111 lemma orelation_of_relation_preserves_identity:
 112  ∀o1:REL. eq2 ? (orelation_of_relation ?? (id1 ? o1)) (id2 OA (SUBSETS o1)).
 113  intros; split; intro; split; whd; intro;
 114   [ change with ((∀x. x ♮(id1 REL o1) a1→x∈a) → a1 ∈ a); intros;
 115     apply (f a1); change with (a1 = a1); apply refl1;
 116   | change with (a1 ∈ a → ∀x. x ♮(id1 REL o1) a1→x∈a); intros;
 117     change in f1 with (x = a1); apply (. f1‡#); apply f;
 118   | alias symbol "and" = "and_morphism".
 119     change with ((∃y:o1.a1 ♮(id1 REL o1) y ∧ y∈a) → a1 ∈ a);
 120     intro; cases e; clear e; cases x; clear x; change in f with (a1=w);
 121     apply (. f‡#); apply f1;
 122   | change with (a1 ∈ a → ∃y:o1.a1 ♮(id1 REL o1) y ∧ y∈a);
 123     intro; exists; [apply a1]; split; [ change with (a1=a1); apply refl1; | apply f]
 124   | change with ((∃x:o1.x ♮(id1 REL o1) a1∧x∈a) → a1 ∈ a);
 125     intro; cases e; clear e; cases x; clear x; change in f with (w=a1);
 126     apply (. f^-1‡#); apply f1;
 127   | change with (a1 ∈ a → ∃x:o1.x ♮(id1 REL o1) a1∧x∈a);
 128     intro; exists; [apply a1]; split; [ change with (a1=a1); apply refl1; | apply f]
 129   | change with ((∀y.a1 ♮(id1 REL o1) y→y∈a) → a1 ∈ a); intros;
 130     apply (f a1); change with (a1 = a1); apply refl1;
 131   | change with (a1 ∈ a → ∀y.a1 ♮(id1 REL o1) y→y∈a); intros;
 132     change in f1 with (a1 = y); apply (. f1^-1‡#); apply f;]
 133 qed.
 134
 135 (* CSC: ???? forse un uncertain mancato *)
 136 alias symbol "eq" = "setoid2 eq".
 137 alias symbol "compose" = "category1 composition".
 138 lemma orelation_of_relation_preserves_composition:
 139  ∀o1,o2,o3:REL.∀F: arrows1 ? o1 o2.∀G: arrows1 ? o2 o3.
 140   orelation_of_relation ?? (G ∘ F) =
 141    comp2 OA (SUBSETS o1) (SUBSETS o2) (SUBSETS o3)
 142     ?? (*(orelation_of_relation ?? F) (orelation_of_relation ?? G)*).
 143  [ apply (orelation_of_relation ?? F); | apply (orelation_of_relation ?? G); ]
 144  intros; split; intro; split; whd; intro; whd in ⊢ (% → %); intros;
 145   [ whd; intros; apply f; exists; [ apply x] split; assumption;
 146   | cases f1; clear f1; cases x1; clear x1; apply (f w); assumption;
 147   | cases e; cases x; cases f; cases x1; clear e x f x1; exists; [ apply w1 ]
 148     split; [ assumption | exists; [apply w] split; assumption ]
 149   | cases e; cases x; cases f1; cases x1; clear e x f1 x1; exists; [apply w1 ]
 150     split; [ exists; [apply w] split; assumption | assumption ]
 151   | unfold arrows1_of_ORelation_setoid;
 152     cases e; cases x; cases f; cases x1; clear e x f x1; exists; [ apply w1 ]
 153     split; [ assumption | exists; [apply w] split; assumption ]
 154   | unfold arrows1_of_ORelation_setoid in e;
 155     cases e; cases x; cases f1; cases x1; clear e x f1 x1; exists; [apply w1 ]
 156     split; [ exists; [apply w] split; assumption | assumption ]
 157   | whd; intros; apply f; exists; [ apply y] split; assumption;
 158   | cases f1; clear f1; cases x; clear x; apply (f w); assumption;]
 159 qed.