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/categories.ma".
17 record powerset_carrier (A: objs1 SET) : Type[1] ≝ { mem_operator: A ⇒_1 CPROP }.
18 interpretation "powerset low" 'powerset A = (powerset_carrier A).
19 notation "hvbox(a break ∈. b)" non associative with precedence 45 for @{ 'mem_low $a $b }.
20 interpretation "memlow" 'mem_low a S = (fun11 ?? (mem_operator ? S) a).
22 definition subseteq_operator: ∀A: objs1 SET. Ω^A → Ω^A → CProp[0] ≝
23 λA:objs1 SET.λU,V.∀a:A. a ∈. U → a ∈. V.
25 theorem transitive_subseteq_operator: ∀A. transitive2 ? (subseteq_operator A).
31 definition powerset_setoid1: SET → SET1.
34 [ apply (powerset_carrier T)
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 ]
44 interpretation "powerset" 'powerset A = (powerset_setoid1 A).
46 interpretation "subset construction" 'subset \eta.x =
47 (mk_powerset_carrier ? (mk_unary_morphism1 ? CPROP x ?)).
49 definition mem: ∀A. A × Ω^A ⇒_1 CPROP.
52 [ apply (λx,S. mem_operator ? S x)
54 cases b; clear b; cases b'; clear b'; simplify; intros;
55 apply (trans1 ????? (prop11 ?? u ?? e));
56 cases e1; whd in s s1;
59 | apply s1; assumption]]
62 interpretation "mem" 'mem a S = (fun21 ??? (mem ?) a S).
64 definition subseteq: ∀A. Ω^A × Ω^A ⇒_1 CPROP.
67 [ apply (λU,V. subseteq_operator ? U V)
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) ]]
77 interpretation "subseteq" 'subseteq U V = (fun21 ??? (subseteq ?) U V).
79 theorem subseteq_refl: ∀A.∀S:Ω^A.S ⊆ S.
83 theorem subseteq_trans: ∀A.∀S1,S2,S3: Ω^A. S1 ⊆ S2 → S2 ⊆ S3 → S1 ⊆ S3.
84 intros; apply transitive_subseteq_operator; [apply S2] assumption.
87 definition overlaps: ∀A. Ω^A × Ω^A ⇒_1 CPROP.
90 [ apply (λA:objs1 SET.λU,V:Ω^A.(exT2 ? (λx:A.x ∈ U) (λx:A.x ∈ V) : CProp[0]))
92 constructor 1; intro; cases e2; exists; [1,4: apply w]
93 [ apply (. #‡e^-1); assumption
94 | apply (. #‡e1^-1); assumption
95 | apply (. #‡e); assumption;
96 | apply (. #‡e1); assumption]]
99 interpretation "overlaps" 'overlaps U V = (fun21 ??? (overlaps ?) U V).
101 definition intersects: ∀A. Ω^A × Ω^A ⇒_1 Ω^A.
104 [ apply rule (λU,V. {x | x ∈ U ∧ x ∈ V });
105 intros; simplify; apply (.= (e‡#)‡(e‡#)); apply refl1;
107 split; intros 2; simplify in f ⊢ %;
108 [ apply (. (#‡e^-1)‡(#‡e1^-1)); assumption
109 | apply (. (#‡e)‡(#‡e1)); assumption]]
112 interpretation "intersects" 'intersects U V = (fun21 ??? (intersects ?) U V).
114 definition union: ∀A. Ω^A × Ω^A ⇒_1 Ω^A.
117 [ apply (λU,V. {x | x ∈ U ∨ x ∈ V });
118 intros; simplify; apply (.= (e‡#)‡(e‡#)); apply refl1
120 split; intros 2; simplify in f ⊢ %;
121 [ apply (. (#‡e^-1)‡(#‡e1^-1)); assumption
122 | apply (. (#‡e)‡(#‡e1)); assumption]]
125 interpretation "union" 'union U V = (fun21 ??? (union ?) U V).
127 (* qua non riesco a mettere set *)
128 definition singleton: ∀A:setoid. A ⇒_1 Ω^A.
129 intros; constructor 1;
130 [ apply (λa:A.{b | a =_0 b}); unfold setoid1_of_setoid; simplify;
134 [ apply e | apply (e^-1) ]
135 | unfold setoid1_of_setoid; simplify;
136 intros; split; intros 2; simplify in f ⊢ %; apply trans;
137 [ apply a |4: apply a'] try assumption; apply sym; assumption]
140 interpretation "singleton" 'singl a = (fun11 ?? (singleton ?) a).
141 notation > "{ term 19 a : S }" with precedence 90 for @{fun11 ?? (singleton $S) $a}.
143 definition big_intersects: ∀A:SET.∀I:SET.(I ⇒_2 Ω^A) ⇒_2 Ω^A.
144 intros; constructor 1;
145 [ intro; whd; whd in I;
146 apply ({x | ∀i:I. x ∈ c i});
147 simplify; intros; split; intros; [ apply (. (e^-1‡#)); | apply (. e‡#); ]
149 | intros; split; intros 2; simplify in f ⊢ %; intro;
150 [ apply (. (#‡(e i)^-1)); apply f;
151 | apply (. (#‡e i)); apply f]]
154 definition big_union: ∀A:SET.∀I:SET.(I ⇒_2 Ω^A) ⇒_2 Ω^A.
155 intros; constructor 1;
156 [ intro; whd; whd in A; whd in I;
157 apply ({x | ∃i:I. x ∈ c i });
158 simplify; intros; split; intros; cases e1; clear e1; exists; [1,3:apply w]
159 [ apply (. (e^-1‡#)); | apply (. (e‡#)); ]
161 | intros; split; intros 2; simplify in f ⊢ %; cases f; clear f; exists; [1,3:apply w]
162 [ apply (. (#‡(e w)^-1)); apply x;
163 | apply (. (#‡e w)); apply x]]
166 notation < "hovbox(mstyle scriptlevel 1 scriptsizemultiplier 1.7 (⋃) \below (\emsp) term 90 p)"
167 non associative with precedence 50 for @{ 'bigcup $p }.
168 notation < "hovbox(mstyle scriptlevel 1 scriptsizemultiplier 1.7 (⋃) \below (ident i ∈ I) break term 90 p)"
169 non associative with precedence 50 for @{ 'bigcup_mk (λ${ident i}:$I.$p) }.
170 notation > "hovbox(⋃ f)" non associative with precedence 60 for @{ 'bigcup $f }.
172 notation < "hovbox(mstyle scriptlevel 1 scriptsizemultiplier 1.7 (⋂) \below (\emsp) term 90 p)"
173 non associative with precedence 50 for @{ 'bigcap $p }.
174 notation < "hovbox(mstyle scriptlevel 1 scriptsizemultiplier 1.7 (⋂) \below (ident i ∈ I) break term 90 p)"
175 non associative with precedence 50 for @{ 'bigcap_mk (λ${ident i}:$I.$p) }.
176 notation > "hovbox(⋂ f)" non associative with precedence 60 for @{ 'bigcap $f }.
178 interpretation "bigcup" 'bigcup f = (fun12 ?? (big_union ??) f).
179 interpretation "bigcap" 'bigcap f = (fun12 ?? (big_intersects ??) f).
180 interpretation "bigcup mk" 'bigcup_mk f = (fun12 ?? (big_union ??) (mk_unary_morphism2 ?? f ?)).
181 interpretation "bigcap mk" 'bigcap_mk f = (fun12 ?? (big_intersects ??) (mk_unary_morphism2 ?? f ?)).