1 (**************************************************************************)
4 (* ||A|| A project by Andrea Asperti *)
6 (* ||I|| Developers: *)
7 (* ||T|| The HELM team. *)
8 (* ||A|| http://helm.cs.unibo.it *)
10 (* \ / This file is distributed under the terms of the *)
11 (* v GNU General Public License Version 2 *)
13 (**************************************************************************)
15 include "o-basic_pairs.ma".
16 include "o-saturations.ma".
18 notation "□ \sub b" non associative with precedence 90 for @{'box $b}.
19 notation > "□_term 90 b" non associative with precedence 90 for @{'box $b}.
20 interpretation "Universal image ⊩⎻*" 'box x = (fun_1 _ _ (or_f_minus_star _ _) (rel x)).
22 notation "◊ \sub b" non associative with precedence 90 for @{'diamond $b}.
23 notation > "◊_term 90 b" non associative with precedence 90 for @{'diamond $b}.
24 interpretation "Existential image ⊩" 'diamond x = (fun_1 _ _ (or_f _ _) (rel x)).
26 notation "'Rest' \sub b" non associative with precedence 90 for @{'rest $b}.
27 notation > "'Rest'⎽term 90 b" non associative with precedence 90 for @{'rest $b}.
28 interpretation "Universal pre-image ⊩*" 'rest x = (fun_1 _ _ (or_f_star _ _) (rel x)).
30 notation "'Ext' \sub b" non associative with precedence 90 for @{'ext $b}.
31 notation > "'Ext'⎽term 90 b" non associative with precedence 90 for @{'ext $b}.
32 interpretation "Existential pre-image ⊩⎻" 'ext x = (fun_1 _ _ (or_f_minus _ _) (rel x)).
34 lemma hint : ∀p,q.arrows1 OA p q → ORelation_setoid p q.
38 coercion hint nocomposites.
40 definition A : ∀b:BP. unary_morphism (oa_P (form b)) (oa_P (form b)).
41 intros; constructor 1;
42 [ apply (λx.□_b (Ext⎽b x));
43 | do 2 unfold uncurry_arrows; intros; apply (†(†H));]
46 lemma xxx : ∀x.carr x → carr1 (setoid1_of_setoid x). intros; assumption; qed.
47 coercion xxx nocomposites.
49 lemma down_p : ∀S,I:SET.∀u:S⇒S.∀c:arrows1 SET I S.∀a:I.∀a':I.a=a'→u (c a)=u (c a').
50 intros; unfold uncurry_arrows; apply (†(†H));
53 alias symbol "eq" = "setoid eq".
54 alias symbol "and" = "o-algebra binary meet".
55 record concrete_space : Type ≝
57 (*distr : is_distributive (form bp);*)
58 downarrow: unary_morphism (oa_P (form bp)) (oa_P (form bp));
59 downarrow_is_sat: is_saturation ? downarrow;
61 (Ext⎽bp q1 ∧ (Ext⎽bp q2)) = (Ext⎽bp ((downarrow q1) ∧ (downarrow q2)));
62 all_covered: Ext⎽bp (oa_one (form bp)) = oa_one (concr bp);
63 il2: ∀I:SET.∀p:arrows1 SET I (oa_P (form bp)).
64 downarrow (∨ { x ∈ I | downarrow (p x) | down_p ???? }) =
65 ∨ { x ∈ I | downarrow (p x) | down_p ???? };
66 il1: ∀q.downarrow (A ? q) = A ? q
69 interpretation "o-concrete space downarrow" 'downarrow x =
70 (fun_1 __ (downarrow _) x).
72 definition bp': concrete_space → basic_pair ≝ λc.bp c.
75 lemma setoid_OF_OA : OA → setoid.
76 intros; apply (oa_P o);
79 coercion setoid_OF_OA.
81 definition binary_downarrow :
82 ∀C:concrete_space.binary_morphism1 (form C) (form C) (form C).
83 intros; constructor 1;
84 [ intros; apply (↓ c ∧ ↓ c1);
85 | intros; apply ((†H)‡(†H1));]
88 interpretation "concrete_space binary ↓" 'fintersects a b = (fun1 _ _ _ (binary_downarrow _) a b).
90 record convergent_relation_pair (CS1,CS2: concrete_space) : Type ≝
91 { rp:> arrows1 ? CS1 CS2;
93 ∀b,c. eq1 ? (rp\sub\c⎻ (Ext⎽CS2 (b ↓ c))) (Ext⎽CS1 (rp\sub\f⎻ b ↓ rp\sub\f⎻ c));
95 eq1 ? (rp\sub\c⎻ (Ext⎽CS2 (oa_one (form CS2))))
96 (Ext⎽CS1 (oa_one (form CS1)))
99 definition rp' : ∀CS1,CS2. convergent_relation_pair CS1 CS2 → relation_pair CS1 CS2 ≝
100 λCS1,CS2,c. rp CS1 CS2 c.
104 definition convergent_relation_space_setoid: concrete_space → concrete_space → setoid1.
107 [ apply (convergent_relation_pair c c1)
110 apply (relation_pair_equality c c1 c2 c3);
111 | intros 1; apply refl1;
112 | intros 2; apply sym1;
113 | intros 3; apply trans1]]
116 definition rp'': ∀CS1,CS2.convergent_relation_space_setoid CS1 CS2 → arrows1 BP CS1 CS2 ≝
121 definition convergent_relation_space_composition:
122 ∀o1,o2,o3: concrete_space.
124 (convergent_relation_space_setoid o1 o2)
125 (convergentin ⊢ (? (? ? ? (? ? ? (? ? ? ? ? (? ? ? (? ? ? (% ? ?))) ?)) ?) ? ? ?)_relation_space_setoid o2 o3)
126 (convergent_relation_space_setoid o1 o3).
127 intros; constructor 1;
128 [ intros; whd in c c1 ⊢ %;
132 change in ⊢ (? ? ? % ?) with (c\sub\c⎻ (c1\sub\c⎻ (Ext⎽o3 (b↓c2))));
133 alias symbol "trans" = "trans1".
134 apply (.= († (respects_converges : ?)));
135 apply (.= (respects_converges : ?));
137 | change in ⊢ (? ? ? % ?) with (c\sub\c⎻ (c1\sub\c⎻ (Ext⎽o3 (oa_one (form o3)))));
138 apply (.= (†(respects_all_covered :?)));
139 apply (.= (respects_all_covered :?));
142 change with (b ∘ a = b' ∘ a');
143 change in H with (rp'' ?? a = rp'' ?? a');
144 change in H1 with (rp'' ?? b = rp ?? b');
148 definition CSPA: category1.
150 [ apply concrete_space
151 | apply convergent_relation_space_setoid
152 | intro; constructor 1;
154 | intros; apply refl1;
156 | apply convergent_relation_space_composition
158 change with (a34 ∘ (a23 ∘ a12) = (a34 ∘ a23) ∘ a12);
161 change with (a ∘ id1 ? o1 = a);
162 apply (id_neutral_right1 : ?);
164 change with (id1 ? o2 ∘ a = a);
165 apply (id_neutral_left1 : ?);]