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 "relations.ma".
16 include "o-algebra.ma".
18 definition SUBSETS: objs1 SET → OAlgebra.
19 intro A; constructor 1;
23 | apply big_intersects;
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); ]
35 [ intros 4; apply f; exists; [apply i] assumption;
36 | intros 3; intros; cases f1; apply (f w a x); ]
38 | intros 3; constructor 1;
39 | intros; cases f; exists; [apply w]
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‡#));
51 definition orelation_of_relation: ∀o1,o2:REL. arrows1 ? o1 o2 → arrows2 OA (SUBSETS o1) (SUBSETS o2).
55 [ apply (λU.image ?? c U);
56 | intros; apply (#‡e); ]
58 [ apply (λU.minus_star_image ?? c U);
59 | intros; apply (#‡e); ]
61 [ apply (λU.star_image ?? c U);
62 | intros; apply (#‡e); ]
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]
83 | exists; [apply w] split; assumption]
84 | cases x1; cases x2; clear x1 x2; exists; [apply w1]
85 [ exists; [apply w] split; assumption;
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);
95 | change with (a1 ∈ minus_star_image ?? t' a → a1 ∈ minus_star_image ?? t a);
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);
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);
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);
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;]
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;]
161 definition SUBSETS': carr3 (arrows3 CAT2 (category2_of_category1 REL) OA).
164 | intros; constructor 1;
165 [ apply (orelation_of_relation S T);
166 | intros; apply (orelation_of_relation_preserves_equality S T a a' e); ]
167 | apply orelation_of_relation_preserves_identity;
169 apply (.= (orelation_of_relation_preserves_composition o1 o2 o4 f1 (f3∘f2)));
170 apply (#‡(orelation_of_relation_preserves_composition o2 o3 o4 f2 f3)); ]
173 theorem SUBSETS_faithful:
174 ∀S,T.∀f,g:arrows2 (category2_of_category1 REL) S T.
175 map_arrows2 ?? SUBSETS' ?? f = map_arrows2 ?? SUBSETS' ?? g → f=g.
176 intros; unfold SUBSETS' in e; simplify in e; cases e;
177 unfold orelation_of_relation in e3; simplify in e3; clear e e1 e2 e4;
178 intros 2; lapply (e3 (singleton ? x)); cases Hletin;
179 split; intro; [ lapply (s y); | lapply (s1 y); ]
180 [2,4: exists; [1,3:apply x] split; [1,3: assumption |*: change with (x=x); apply rule #]
181 |*: cases Hletin1; cases x1; change in f3 with (eq1 ? x w); apply (. f3‡#); assumption;]