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 "logic/cprop_connectives.ma".
16 include "datatypes/categories.ma".
18 record powerset_carrier (A: setoid) : Type ≝ { mem_operator: A ⇒ CPROP }.
20 definition subseteq_operator ≝
21 λA:setoid.λU,V.∀a:A. mem_operator ? U a → mem_operator ? V a.
23 theorem transitive_subseteq_operator: ∀A. transitive ? (subseteq_operator A).
29 definition powerset_setoid: setoid → setoid1.
32 [ apply (powerset_carrier T)
34 [ apply (λU,V. subseteq_operator ? U V ∧ subseteq_operator ? V U)
35 | simplify; intros; split; intros 2; assumption
36 | simplify; intros (x y H); cases H; split; assumption
37 | simplify; intros (x y z H H1); cases H; cases H1; split;
38 apply transitive_subseteq_operator; [1,4: apply y ]
42 interpretation "powerset" 'powerset A = (powerset_setoid A).
44 interpretation "subset construction" 'subset \eta.x =
45 (mk_powerset_carrier _ (mk_unary_morphism _ CPROP x _)).
47 definition mem: ∀A. binary_morphism1 A (Ω \sup A) CPROP.
50 [ apply (λx,S. mem_operator ? S x)
52 cases b; clear b; cases b'; clear b'; simplify; intros;
53 apply (trans1 ????? (prop_1 ?? u ?? H));
54 cases H1; whd in s s1;
57 | apply s1; assumption]]
60 interpretation "mem" 'mem a S = (fun1 ___ (mem _) a S).
62 definition subseteq: ∀A. binary_morphism1 (Ω \sup A) (Ω \sup A) CPROP.
65 [ apply (λU,V. subseteq_operator ? U V)
69 [ apply (transitive_subseteq_operator ????? s2);
70 apply (transitive_subseteq_operator ???? s1 s4)
71 | apply (transitive_subseteq_operator ????? s3);
72 apply (transitive_subseteq_operator ???? s s4) ]]
75 interpretation "subseteq" 'subseteq U V = (fun1 ___ (subseteq _) U V).
77 theorem subseteq_refl: ∀A.∀S:Ω \sup A.S ⊆ S.
81 theorem subseteq_trans: ∀A.∀S1,S2,S3: Ω \sup A. S1 ⊆ S2 → S2 ⊆ S3 → S1 ⊆ S3.
82 intros; apply transitive_subseteq_operator; [apply S2] assumption.
85 definition overlaps: ∀A. binary_morphism1 (Ω \sup A) (Ω \sup A) CPROP.
88 [ apply (λA.λU,V:Ω \sup A.exT2 ? (λx:A.x ∈ U) (λx:A.x ∈ V))
90 constructor 1; intro; cases H2; exists; [1,4: apply w]
91 [ apply (. #‡H); assumption
92 | apply (. #‡H1); assumption
93 | apply (. #‡(H \sup -1)); assumption;
94 | apply (. #‡(H1 \sup -1)); assumption]]
97 interpretation "overlaps" 'overlaps U V = (fun1 ___ (overlaps _) U V).
99 definition intersects:
100 ∀A. binary_morphism1 (powerset_setoid A) (powerset_setoid A) (powerset_setoid A).
103 [ apply (λU,V. {x | x ∈ U ∧ x ∈ V });
104 intros; simplify; apply (.= (H‡#)‡(H‡#)); apply refl1;
106 split; intros 2; simplify in f ⊢ %;
107 [ apply (. (#‡H)‡(#‡H1)); assumption
108 | apply (. (#‡(H \sup -1))‡(#‡(H1 \sup -1))); assumption]]
111 interpretation "intersects" 'intersects U V = (fun1 ___ (intersects _) U V).
114 ∀A. binary_morphism1 (powerset_setoid A) (powerset_setoid A) (powerset_setoid A).
117 [ apply (λU,V. {x | x ∈ U ∨ x ∈ V });
118 intros; simplify; apply (.= (H‡#)‡(H‡#)); apply refl1
120 split; intros 2; simplify in f ⊢ %;
121 [ apply (. (#‡H)‡(#‡H1)); assumption
122 | apply (. (#‡(H \sup -1))‡(#‡(H1 \sup -1))); assumption]]
125 interpretation "union" 'union U V = (fun1 ___ (union _) U V).
127 definition singleton: ∀A:setoid. unary_morphism A (Ω \sup A).
128 intros; constructor 1;
129 [ apply (λA:setoid.λa:A.{b | a=b});
133 [ apply H | apply (H \sup -1) ]
134 | intros; split; intros 2; simplify in f ⊢ %; apply trans;
135 [ apply a |4: apply a'] try assumption; apply sym; assumption]
138 interpretation "singleton" 'singl a = (fun_1 __ (singleton _) a).