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 "formal_topology/relations.ma".
16 include "formal_topology/o-algebra.ma".
18 definition POW': 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 [ (** screenshot "screen-pow". *) 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 {(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 powerset_of_POW': ∀A.oa_P (POW' A) → Ω^A ≝ λA,x.x.
52 coercion powerset_of_POW'.
54 definition orelation_of_relation: ∀o1,o2:REL. o1 ⇒_\r1 o2 → (POW' o1) ⇒_\o2 (POW' o2).
58 [ apply (λU.image ?? c U);
59 | intros; apply (#‡e); ]
61 [ apply (λU.minus_star_image ?? c U);
62 | intros; apply (#‡e); ]
64 [ apply (λU.star_image ?? c U);
65 | intros; apply (#‡e); ]
67 [ apply (λU.minus_image ?? c U);
68 | intros; apply (#‡e); ]
69 | intros; split; intro;
70 [ change in f with (∀a. a ∈ image ?? c p → a ∈ q);
71 change with (∀a:o1. a ∈ p → a ∈ star_image ?? c q);
72 intros 4; apply f; exists; [apply a] split; assumption;
73 | change in f with (∀a:o1. a ∈ p → a ∈ star_image ?? c q);
74 change with (∀a. a ∈ image ?? c p → a ∈ q);
75 intros; cases f1; cases x; clear f1 x; apply (f ? f3); assumption; ]
76 | intros; split; intro;
77 [ change in f with (∀a. a ∈ minus_image ?? c p → a ∈ q);
78 change with (∀a:o2. a ∈ p → a ∈ minus_star_image ?? c q);
79 intros 4; apply f; exists; [apply a] split; assumption;
80 | change in f with (∀a:o2. a ∈ p → a ∈ minus_star_image ?? c q);
81 change with (∀a. a ∈ minus_image ?? c p → a ∈ q);
82 intros; cases f1; cases x; clear f1 x; apply (f ? f3); assumption; ]
83 | intros; split; intro; cases f; clear f;
84 [ cases x; cases x2; clear x x2; exists; [apply w1]
86 | exists; [apply w] split; assumption]
87 | cases x1; cases x2; clear x1 x2; exists; [apply w1]
88 [ exists; [apply w] split; assumption;
92 lemma orelation_of_relation_preserves_equality:
93 ∀o1,o2:REL.∀t,t': o1 ⇒_\r1 o2.
94 t = t' → orelation_of_relation ?? t =_2 orelation_of_relation ?? t'.
95 intros; split; unfold orelation_of_relation; simplify; intro; split; intro;
96 simplify; whd in o1 o2;
97 [ change with (a1 ∈ minus_star_image ?? t a → a1 ∈ minus_star_image ?? t' a);
99 | change with (a1 ∈ minus_star_image ?? t' a → a1 ∈ minus_star_image ?? t a);
101 | change with (a1 ∈ minus_image ?? t a → a1 ∈ minus_image ?? t' a);
102 apply (. #‡(e ^ -1‡#));
103 | change with (a1 ∈ minus_image ?? t' a → a1 ∈ minus_image ?? t a);
105 | change with (a1 ∈ image ?? t a → a1 ∈ image ?? t' a);
106 apply (. #‡(e ^ -1‡#));
107 | change with (a1 ∈ image ?? t' a → a1 ∈ image ?? t a);
109 | change with (a1 ∈ star_image ?? t a → a1 ∈ star_image ?? t' a);
110 apply (. #‡(e ^ -1‡#));
111 | change with (a1 ∈ star_image ?? t' a → a1 ∈ star_image ?? t a);
115 lemma orelation_of_relation_preserves_identity:
116 ∀o1:REL. orelation_of_relation ?? (id1 ? o1) =_2 id2 OA (POW' o1).
117 intros; split; intro; split; whd; intro;
118 [ change with ((∀x. x ♮(id1 REL o1) a1→x∈a) → a1 ∈ a); intros;
119 apply (f a1); change with (a1 = a1); apply refl1;
120 | change with (a1 ∈ a → ∀x. x ♮(id1 REL o1) a1→x∈a); intros;
121 change in f1 with (x = a1); apply (. f1‡#); apply f;
122 | alias symbol "and" = "and_morphism".
123 change with ((∃y:o1.a1 ♮(id1 REL o1) y ∧ y∈a) → a1 ∈ a);
124 intro; cases e; clear e; cases x; clear x; change in f with (a1=w);
125 apply (. f‡#); apply f1;
126 | change with (a1 ∈ a → ∃y:o1.a1 ♮(id1 REL o1) y ∧ y∈a);
127 intro; exists; [apply a1]; split; [ change with (a1=a1); apply refl1; | apply f]
128 | change with ((∃x:o1.x ♮(id1 REL o1) a1∧x∈a) → a1 ∈ a);
129 intro; cases e; clear e; cases x; clear x; change in f with (w=a1);
130 apply (. f^-1‡#); apply f1;
131 | change with (a1 ∈ a → ∃x:o1.x ♮(id1 REL o1) a1∧x∈a);
132 intro; exists; [apply a1]; split; [ change with (a1=a1); apply refl1; | apply f]
133 | change with ((∀y.a1 ♮(id1 REL o1) y→y∈a) → a1 ∈ a); intros;
134 apply (f a1); change with (a1 = a1); apply refl1;
135 | change with (a1 ∈ a → ∀y.a1 ♮(id1 REL o1) y→y∈a); intros;
136 change in f1 with (a1 = y); apply (. f1^-1‡#); apply f;]
139 (* CSC: ???? forse un uncertain mancato *)
140 alias symbol "eq" = "setoid2 eq".
141 alias symbol "compose" = "category1 composition".
142 lemma orelation_of_relation_preserves_composition:
143 ∀o1,o2,o3:REL.∀F: o1 ⇒_\r1 o2.∀G: o2 ⇒_\r1 o3.
144 orelation_of_relation ?? (G ∘ F) =
145 comp2 OA ??? (orelation_of_relation ?? F) (orelation_of_relation ?? G).
146 intros; split; intro; split; whd; intro; whd in ⊢ (% → %); intros;
147 [ whd; intros; apply f; exists; [ apply x] split; assumption;
148 | cases f1; clear f1; cases x1; clear x1; apply (f w); assumption;
149 | cases e; cases x; cases f; cases x1; clear e x f x1; exists; [ apply w1 ]
150 split; [ assumption | exists; [apply w] split; assumption ]
151 | cases e; cases x; cases f1; cases x1; clear e x f1 x1; exists; [apply w1 ]
152 split; [ exists; [apply w] split; assumption | assumption ]
153 | unfold arrows1_of_ORelation_setoid;
154 cases e; cases x; cases f; cases x1; clear e x f x1; exists; [ apply w1 ]
155 split; [ assumption | exists; [apply w] split; assumption ]
156 | unfold arrows1_of_ORelation_setoid in e;
157 cases e; cases x; cases f1; cases x1; clear e x f1 x1; exists; [apply w1 ]
158 split; [ exists; [apply w] split; assumption | assumption ]
159 | whd; intros; apply f; exists; [ apply y] split; assumption;
160 | cases f1; clear f1; cases x; clear x; apply (f w); assumption;]
163 definition POW: carr3 (arrows3 CAT2 (category2_of_category1 REL) OA).
166 | intros; constructor 1;
167 [ apply (orelation_of_relation S T);
168 | intros; apply (orelation_of_relation_preserves_equality S T a a' e); ]
169 | apply orelation_of_relation_preserves_identity;
170 | apply orelation_of_relation_preserves_composition; ]
173 theorem POW_faithful: faithful2 ?? POW.
174 intros 5; unfold POW in e; simplify in e; cases e;
175 unfold orelation_of_relation in e3; simplify in e3; clear e e1 e2 e4;
176 intros 2; cases (e3 {(x)});
177 split; intro; [ lapply (s y); | lapply (s1 y); ]
178 [2,4: exists; [1,3:apply x] split; [1,3: assumption |*: change with (x=x); apply rule #]
179 |*: cases Hletin; cases x1; change in f3 with (x =_1 w); apply (. f3‡#); assumption;]
183 lemma currify: ∀A,B,C. (A × B ⇒_1 C) → A → (B ⇒_1 C).
184 intros; constructor 1; [ apply (b c); | intros; apply (#‡e);]
188 theorem POW_full: full2 ?? POW.
189 intros 3 (S T); exists;
190 [ constructor 1; constructor 1;
191 [ apply (λx:carr S.λy:carr T. y ∈ f {(x)});
192 | intros; unfold FunClass_1_OF_carr2; lapply (.= e1‡#);
193 [4: apply mem; |6: apply Hletin;|1,2,3,5: skip]
194 lapply (#‡prop11 ?? f ?? (†e)); [6: apply Hletin; |*:skip ]]
195 | whd; split; whd; intro; simplify; unfold map_arrows2; simplify;
197 [ change with (∀a1.(∀x. a1 ∈ (f {(x):S}) → x ∈ a) → a1 ∈ f⎻* a);
198 | change with (∀a1.a1 ∈ f⎻* a → (∀x.a1 ∈ f {(x):S} → x ∈ a)); ]
200 [ change with (∀a1.(∃y:carr T. y ∈ f {(a1):S} ∧ y ∈ a) → a1 ∈ f⎻ a);
201 | change with (∀a1.a1 ∈ f⎻ a → (∃y:carr T.y ∈ f {(a1):S} ∧ y ∈ a)); ]
203 [ change with (∀a1.(∃x:carr S. a1 ∈ f {(x):S} ∧ x ∈ a) → a1 ∈ f a);
204 | change with (∀a1.a1 ∈. f a → (∃x:carr S. a1 ∈ f {(x):S} ∧ x ∈ a)); ]
206 [ change with (∀a1.(∀y. y ∈ f {(a1):S} → y ∈ a) → a1 ∈ f* a);
207 | change with (∀a1.a1 ∈ f* a → (∀y. y ∈ f {(a1):S} → y ∈ a)); ]]
208 [ intros; apply ((. (or_prop2 ?? f (singleton ? a1) a)^-1) ? a1);
209 [ intros 2; apply (f1 a2); change in f2 with (a2 ∈ f⎻ (singleton ? a1));
210 lapply (. (or_prop3 ?? f (singleton ? a2) (singleton ? a1)));
211 [ cases Hletin; change in x1 with (eq1 ? a1 w);
212 apply (. x1‡#); assumption;
213 | exists; [apply a2] [change with (a2=a2); apply rule #; | assumption]]
214 | change with (a1 = a1); apply rule #; ]
215 | intros; apply ((. (or_prop2 ?? f (singleton ? a1) a)) ? x);
216 [ intros 2; change in f3 with (eq1 ? a1 a2); change with (a2 ∈ f⎻* a); apply (. f3^-1‡#);
218 | lapply (. (or_prop3 ?? f (singleton ? x) (singleton ? a1))^-1);
219 [ cases Hletin; change in x1 with (eq1 ? x w);
220 change with (x ∈ f⎻ (singleton ? a1)); apply (. x1‡#); assumption;
221 | exists; [apply a1] [assumption | change with (a1=a1); apply rule #; ]]]
222 | intros; cases e; cases x; clear e x;
223 lapply (. (or_prop3 ?? f (singleton ? a1) a)^-1);
224 [ cases Hletin; change in x with (eq1 ? a1 w1); apply (. x‡#); assumption;
225 | exists; [apply w] assumption ]
226 | intros; lapply (. (or_prop3 ?? f (singleton ? a1) a));
227 [ cases Hletin; exists; [apply w] split; assumption;
228 | exists; [apply a1] [change with (a1=a1); apply rule #; | assumption ]]
229 | intros; cases e; cases x; clear e x;
230 apply (f_image_monotone ?? f (singleton ? w) a ? a1);
231 [ intros 2; change in f3 with (eq1 ? w a2); change with (a2 ∈ a);
232 apply (. f3^-1‡#); assumption;
234 | intros; lapply (. (or_prop3 ?? f a (singleton ? a1))^-1);
235 [ cases Hletin; exists; [apply w] split;
236 [ lapply (. (or_prop3 ?? f (singleton ? w) (singleton ? a1)));
237 [ cases Hletin1; change in x3 with (eq1 ? a1 w1); apply (. x3‡#); assumption;
238 | exists; [apply w] [change with (w=w); apply rule #; | assumption ]]
240 | exists; [apply a1] [ assumption; | change with (a1=a1); apply rule #;]]
241 | intros; apply ((. (or_prop1 ?? f (singleton ? a1) a)^-1) ? a1);
242 [ apply f1; | change with (a1=a1); apply rule #; ]
243 | intros; apply ((. (or_prop1 ?? f (singleton ? a1) a)) ? y);
244 [ intros 2; change in f3 with (eq1 ? a1 a2); change with (a2 ∈ f* a);
245 apply (. f3^-1‡#); assumption;