X-Git-Url: http://matita.cs.unibo.it/gitweb/?a=blobdiff_plain;f=helm%2Fsoftware%2Fmatita%2Fcontribs%2Fformal_topology%2Foverlap%2Fcategories.ma;h=af58968fc14043110c6d220d3858fe2effc0e435;hb=8844ee999e40d69795aa73fbeb198997a46fcf04;hp=f09e0ee6c109af1f9ee1572aeaa77ca394634d97;hpb=1c406089d385be2d444308a783bc051bd28be463;p=helm.git diff --git a/helm/software/matita/contribs/formal_topology/overlap/categories.ma b/helm/software/matita/contribs/formal_topology/overlap/categories.ma index f09e0ee6c..af58968fc 100644 --- a/helm/software/matita/contribs/formal_topology/overlap/categories.ma +++ b/helm/software/matita/contribs/formal_topology/overlap/categories.ma @@ -12,34 +12,7 @@ (* *) (**************************************************************************) -include "logic/cprop_connectives.ma". - -definition Type0 := Type. -definition Type1 := Type. -definition Type2 := Type. -definition Type3 := Type. -definition Type0_lt_Type1 := (Type0 : Type1). -definition Type1_lt_Type2 := (Type1 : Type2). -definition Type2_lt_Type3 := (Type2 : Type3). - -definition Type_OF_Type0: Type0 → Type := λx.x. -definition Type_OF_Type1: Type1 → Type := λx.x. -definition Type_OF_Type2: Type2 → Type := λx.x. -definition Type_OF_Type3: Type3 → Type := λx.x. -coercion Type_OF_Type0. -coercion Type_OF_Type1. -coercion Type_OF_Type2. -coercion Type_OF_Type3. - -definition CProp0 := CProp. -definition CProp1 := CProp. -definition CProp2 := CProp. -definition CProp0_lt_CProp1 := (CProp0 : CProp1). -definition CProp1_lt_CProp2 := (CProp1 : CProp2). - -definition CProp_OF_CProp0: CProp0 → CProp := λx.x. -definition CProp_OF_CProp1: CProp1 → CProp := λx.x. -definition CProp_OF_CProp2: CProp2 → CProp := λx.x. +include "cprop_connectives.ma". record equivalence_relation (A:Type0) : Type1 ≝ { eq_rel:2> A → A → CProp0; @@ -53,10 +26,6 @@ record setoid : Type1 ≝ eq: equivalence_relation carr }. -definition reflexive1 ≝ λA:Type1.λR:A→A→CProp1.∀x:A.R x x. -definition symmetric1 ≝ λC:Type1.λlt:C→C→CProp1. ∀x,y:C.lt x y → lt y x. -definition transitive1 ≝ λA:Type1.λR:A→A→CProp1.∀x,y,z:A.R x y → R y z → R x z. - record equivalence_relation1 (A:Type1) : Type2 ≝ { eq_rel1:2> A → A → CProp1; refl1: reflexive1 ? eq_rel1; @@ -81,12 +50,8 @@ definition setoid1_of_setoid: setoid → setoid1. | apply (trans s)]] qed. -(* questa coercion e' necessaria per problemi di unificazione *) coercion setoid1_of_setoid. - -definition reflexive2 ≝ λA:Type2.λR:A→A→CProp2.∀x:A.R x x. -definition symmetric2 ≝ λC:Type2.λlt:C→C→CProp2. ∀x,y:C.lt x y → lt y x. -definition transitive2 ≝ λA:Type2.λR:A→A→CProp2.∀x,y,z:A.R x y → R y z → R x z. +prefer coercion Type_OF_setoid. record equivalence_relation2 (A:Type2) : Type3 ≝ { eq_rel2:2> A → A → CProp2; @@ -112,33 +77,35 @@ definition setoid2_of_setoid1: setoid1 → setoid2. | apply (trans1 s)]] qed. -(*coercion setoid2_of_setoid1.*) +coercion setoid2_of_setoid1. +prefer coercion Type_OF_setoid2. +prefer coercion Type_OF_setoid. +prefer coercion Type_OF_setoid1. +(* we prefer 0 < 1 < 2 *) + +record equivalence_relation3 (A:Type3) : Type4 ≝ + { eq_rel3:2> A → A → CProp3; + refl3: reflexive3 ? eq_rel3; + sym3: symmetric3 ? eq_rel3; + trans3: transitive3 ? eq_rel3 + }. -(* -definition Leibniz: Type → setoid. - intro; - constructor 1; - [ apply T - | constructor 1; - [ apply (λx,y:T.cic:/matita/logic/equality/eq.ind#xpointer(1/1) ? x y) - | alias id "refl_eq" = "cic:/matita/logic/equality/eq.ind#xpointer(1/1/1)". - apply refl_eq - | alias id "sym_eq" = "cic:/matita/logic/equality/sym_eq.con". - apply sym_eq - | alias id "trans_eq" = "cic:/matita/logic/equality/trans_eq.con". - apply trans_eq ]] -qed. +record setoid3: Type4 ≝ + { carr3:> Type3; + eq3: equivalence_relation3 carr3 + }. -coercion Leibniz. -*) +interpretation "setoid3 eq" 'eq x y = (eq_rel3 _ (eq3 _) x y). interpretation "setoid2 eq" 'eq x y = (eq_rel2 _ (eq2 _) x y). interpretation "setoid1 eq" 'eq x y = (eq_rel1 _ (eq1 _) x y). interpretation "setoid eq" 'eq x y = (eq_rel _ (eq _) x y). +interpretation "setoid3 symmetry" 'invert r = (sym3 ____ r). interpretation "setoid2 symmetry" 'invert r = (sym2 ____ r). interpretation "setoid1 symmetry" 'invert r = (sym1 ____ r). interpretation "setoid symmetry" 'invert r = (sym ____ r). notation ".= r" with precedence 50 for @{'trans $r}. +interpretation "trans3" 'trans r = (trans3 _____ r). interpretation "trans2" 'trans r = (trans2 _____ r). interpretation "trans1" 'trans r = (trans1 _____ r). interpretation "trans" 'trans r = (trans _____ r). @@ -158,6 +125,11 @@ record unary_morphism2 (A,B: setoid2) : Type2 ≝ prop12: ∀a,a'. eq2 ? a a' → eq2 ? (fun12 a) (fun12 a') }. +record unary_morphism3 (A,B: setoid3) : Type3 ≝ + { fun13:1> A → B; + prop13: ∀a,a'. eq3 ? a a' → eq3 ? (fun13 a) (fun13 a') + }. + record binary_morphism (A,B,C:setoid) : Type0 ≝ { fun2:2> A → B → C; prop2: ∀a,a',b,b'. eq ? a a' → eq ? b b' → eq ? (fun2 a b) (fun2 a' b') @@ -173,18 +145,33 @@ record binary_morphism2 (A,B,C:setoid2) : Type2 ≝ prop22: ∀a,a',b,b'. eq2 ? a a' → eq2 ? b b' → eq2 ? (fun22 a b) (fun22 a' b') }. +record binary_morphism3 (A,B,C:setoid3) : Type3 ≝ + { fun23:2> A → B → C; + prop23: ∀a,a',b,b'. eq3 ? a a' → eq3 ? b b' → eq3 ? (fun23 a b) (fun23 a' b') + }. + notation "† c" with precedence 90 for @{'prop1 $c }. notation "l ‡ r" with precedence 90 for @{'prop2 $l $r }. notation "#" with precedence 90 for @{'refl}. interpretation "prop1" 'prop1 c = (prop1 _____ c). interpretation "prop11" 'prop1 c = (prop11 _____ c). interpretation "prop12" 'prop1 c = (prop12 _____ c). +interpretation "prop13" 'prop1 c = (prop13 _____ c). interpretation "prop2" 'prop2 l r = (prop2 ________ l r). interpretation "prop21" 'prop2 l r = (prop21 ________ l r). interpretation "prop22" 'prop2 l r = (prop22 ________ l r). +interpretation "prop23" 'prop2 l r = (prop23 ________ l r). interpretation "refl" 'refl = (refl ___). interpretation "refl1" 'refl = (refl1 ___). interpretation "refl2" 'refl = (refl2 ___). +interpretation "refl3" 'refl = (refl3 ___). + +definition unary_morphism2_of_unary_morphism1: ∀S,T.unary_morphism1 S T → unary_morphism2 S T. + intros; + constructor 1; + [ apply (fun11 ?? u); + | apply (prop11 ?? u); ] +qed. definition CPROP: setoid1. constructor 1; @@ -192,26 +179,29 @@ definition CPROP: setoid1. | constructor 1; [ apply Iff | intros 1; split; intro; assumption - | intros 3; cases H; split; assumption - | intros 5; cases H; cases H1; split; intro; - [ apply (H4 (H2 x1)) | apply (H3 (H5 z1))]]] + | intros 3; cases i; split; assumption + | intros 5; cases i; cases i1; split; intro; + [ apply (f2 (f x1)) | apply (f1 (f3 z1))]]] qed. +definition CProp0_of_CPROP: carr1 CPROP → CProp0 ≝ λx.x. +coercion CProp0_of_CPROP. + alias symbol "eq" = "setoid1 eq". -definition if': ∀A,B:CPROP. A = B → A → B. - intros; apply (if ?? e); assumption. +definition fi': ∀A,B:CPROP. A = B → B → A. + intros; apply (fi ?? e); assumption. qed. -notation ". r" with precedence 50 for @{'if $r}. -interpretation "if" 'if r = (if' __ r). +notation ". r" with precedence 50 for @{'fi $r}. +interpretation "fi" 'fi r = (fi' __ r). definition and_morphism: binary_morphism1 CPROP CPROP CPROP. constructor 1; [ apply And - | intros; split; intro; cases H; split; - [ apply (if ?? e a1) + | intros; split; intro; cases a1; split; + [ apply (if ?? e a2) | apply (if ?? e1 b1) - | apply (fi ?? e a1) + | apply (fi ?? e a2) | apply (fi ?? e1 b1)]] qed. @@ -220,7 +210,7 @@ interpretation "and_morphism" 'and a b = (fun21 ___ and_morphism a b). definition or_morphism: binary_morphism1 CPROP CPROP CPROP. constructor 1; [ apply Or - | intros; split; intro; cases H; [1,3:left |2,4: right] + | intros; split; intro; cases o; [1,3:left |2,4: right] [ apply (if ?? e a1) | apply (fi ?? e a1) | apply (if ?? e1 b1) @@ -233,30 +223,16 @@ definition if_morphism: binary_morphism1 CPROP CPROP CPROP. constructor 1; [ apply (λA,B. A → B) | intros; split; intros; - [ apply (if ?? e1); apply H; apply (fi ?? e); assumption - | apply (fi ?? e1); apply H; apply (if ?? e); assumption]] + [ apply (if ?? e1); apply f; apply (fi ?? e); assumption + | apply (fi ?? e1); apply f; apply (if ?? e); assumption]] qed. -(* -definition eq_morphism: ∀S:setoid. binary_morphism S S CPROP. - intro; - constructor 1; - [ apply (eq_rel ? (eq S)) - | intros; split; intro; - [ apply (.= H \sup -1); - apply (.= H2); - assumption - | apply (.= H); - apply (.= H2); - apply (H1 \sup -1)]] -qed. -*) record category : Type1 ≝ { objs:> Type0; arrows: objs → objs → setoid; id: ∀o:objs. arrows o o; - comp: ∀o1,o2,o3. binary_morphism1 (arrows o1 o2) (arrows o2 o3) (arrows o1 o3); + comp: ∀o1,o2,o3. binary_morphism (arrows o1 o2) (arrows o2 o3) (arrows o1 o3); comp_assoc: ∀o1,o2,o3,o4. ∀a12,a23,a34. comp o1 o3 o4 (comp o1 o2 o3 a12 a23) a34 = comp o1 o2 o4 a12 (comp o2 o3 o4 a23 a34); id_neutral_left: ∀o1,o2. ∀a: arrows o1 o2. comp ??? (id o1) a = a; @@ -285,36 +261,121 @@ record category2 : Type3 ≝ id_neutral_left2: ∀o1,o2. ∀a: arrows2 o1 o2. comp2 ??? a (id2 o2) = a }. +record category3 : Type4 ≝ + { objs3:> Type3; + arrows3: objs3 → objs3 → setoid3; + id3: ∀o:objs3. arrows3 o o; + comp3: ∀o1,o2,o3. binary_morphism3 (arrows3 o1 o2) (arrows3 o2 o3) (arrows3 o1 o3); + comp_assoc3: ∀o1,o2,o3,o4. ∀a12,a23,a34. + comp3 o1 o3 o4 (comp3 o1 o2 o3 a12 a23) a34 = comp3 o1 o2 o4 a12 (comp3 o2 o3 o4 a23 a34); + id_neutral_right3: ∀o1,o2. ∀a: arrows3 o1 o2. comp3 ??? (id3 o1) a = a; + id_neutral_left3: ∀o1,o2. ∀a: arrows3 o1 o2. comp3 ??? a (id3 o2) = a + }. + notation "'ASSOC'" with precedence 90 for @{'assoc}. -notation "'ASSOC1'" with precedence 90 for @{'assoc1}. -notation "'ASSOC2'" with precedence 90 for @{'assoc2}. interpretation "category2 composition" 'compose x y = (fun22 ___ (comp2 ____) y x). -interpretation "category2 assoc" 'assoc1 = (comp_assoc2 ________). +interpretation "category2 assoc" 'assoc = (comp_assoc2 ________). interpretation "category1 composition" 'compose x y = (fun21 ___ (comp1 ____) y x). -interpretation "category1 assoc" 'assoc1 = (comp_assoc1 ________). +interpretation "category1 assoc" 'assoc = (comp_assoc1 ________). interpretation "category composition" 'compose x y = (fun2 ___ (comp ____) y x). interpretation "category assoc" 'assoc = (comp_assoc ________). -(* bug grande come una casa? - Ma come fa a passare la quantificazione larga??? *) -definition unary_morphism_setoid: setoid → setoid → setoid1. +definition category2_of_category1: category1 → category2. + intro; + constructor 1; + [ apply (objs1 c); + | intros; apply (setoid2_of_setoid1 (arrows1 c o o1)); + | apply (id1 c); + | intros; + constructor 1; + [ intros; apply (comp1 c o1 o2 o3 c1 c2); + | intros; whd in e e1 a a' b b'; change with (eq1 ? (b∘a) (b'∘a')); apply (e‡e1); ] + | intros; simplify; whd in a12 a23 a34; whd; apply rule (ASSOC); + | intros; simplify; whd in a; whd; apply id_neutral_right1; + | intros; simplify; whd in a; whd; apply id_neutral_left1; ] +qed. +(*coercion category2_of_category1.*) + +record functor2 (C1: category2) (C2: category2) : Type3 ≝ + { map_objs2:1> C1 → C2; + map_arrows2: ∀S,T. unary_morphism2 (arrows2 ? S T) (arrows2 ? (map_objs2 S) (map_objs2 T)); + respects_id2: ∀o:C1. map_arrows2 ?? (id2 ? o) = id2 ? (map_objs2 o); + respects_comp2: + ∀o1,o2,o3.∀f1:arrows2 ? o1 o2.∀f2:arrows2 ? o2 o3. + map_arrows2 ?? (f2 ∘ f1) = map_arrows2 ?? f2 ∘ map_arrows2 ?? f1}. + +definition functor2_setoid: category2 → category2 → setoid3. + intros (C1 C2); + constructor 1; + [ apply (functor2 C1 C2); + | constructor 1; + [ intros (f g); + apply (∀c:C1. cic:/matita/logic/equality/eq.ind#xpointer(1/1) ? (f c) (g c)); + | simplify; intros; apply cic:/matita/logic/equality/eq.ind#xpointer(1/1/1); + | simplify; intros; apply cic:/matita/logic/equality/sym_eq.con; apply H; + | simplify; intros; apply cic:/matita/logic/equality/trans_eq.con; + [2: apply H; | skip | apply H1;]]] +qed. + +definition functor2_of_functor2_setoid: ∀S,T. functor2_setoid S T → functor2 S T ≝ λS,T,x.x. +coercion functor2_of_functor2_setoid. + +definition CAT2: category3. + constructor 1; + [ apply category2; + | apply functor2_setoid; + | intros; constructor 1; + [ apply (λx.x); + | intros; constructor 1; + [ apply (λx.x); + | intros; assumption;] + | intros; apply rule #; + | intros; apply rule #; ] + | intros; constructor 1; + [ intros; constructor 1; + [ intros; apply (c1 (c o)); + | intros; constructor 1; + [ intro; apply (map_arrows2 ?? c1 ?? (map_arrows2 ?? c ?? c2)); + | intros; apply (††e); ] + | intros; simplify; + apply (.= †(respects_id2 : ?)); + apply (respects_id2 : ?); + | intros; simplify; + apply (.= †(respects_comp2 : ?)); + apply (respects_comp2 : ?); ] + | intros; intro; simplify; + apply (cic:/matita/logic/equality/eq_ind.con ????? (e ?)); + apply (cic:/matita/logic/equality/eq_ind.con ????? (e1 ?)); + constructor 1; ] + | intros; intro; simplify; constructor 1; + | intros; intro; simplify; constructor 1; + | intros; intro; simplify; constructor 1; ] +qed. + +definition category2_of_objs3_CAT2: objs3 CAT2 → category2 ≝ λx.x. +coercion category2_of_objs3_CAT2. + +definition functor2_setoid_of_arrows3_CAT2: ∀S,T. arrows3 CAT2 S T → functor2_setoid S T ≝ λS,T,x.x. +coercion functor2_setoid_of_arrows3_CAT2. + +definition unary_morphism_setoid: setoid → setoid → setoid. intros; constructor 1; [ apply (unary_morphism s s1); | constructor 1; [ intros (f g); apply (∀a:s. eq ? (f a) (g a)); | intros 1; simplify; intros; apply refl; - | simplify; intros; apply sym; apply H; - | simplify; intros; apply trans; [2: apply H; | skip | apply H1]]] + | simplify; intros; apply sym; apply f; + | simplify; intros; apply trans; [2: apply f; | skip | apply f1]]] qed. definition SET: category1. constructor 1; [ apply setoid; - | apply rule (λS,T:setoid.unary_morphism_setoid S T); + | apply rule (λS,T:setoid.setoid1_of_setoid (unary_morphism_setoid S T)); | intros; constructor 1; [ apply (λx:carr o.x); | intros; assumption ] - | intros; constructor 1; [ intros; constructor 1; [ apply (λx. t1 (t x)); | intros; + | intros; constructor 1; [ intros; constructor 1; [ apply (λx. c1 (c x)); | intros; apply († (†e));] | intros; whd; intros; simplify; whd in H1; whd in H; apply trans; [ apply (b (a' a1)); | lapply (prop1 ?? b (a a1) (a' a1)); @@ -325,29 +386,17 @@ definition SET: category1. ] qed. -definition setoid_of_SET: objs1 SET → setoid. - intros; apply o; qed. +definition setoid_of_SET: objs1 SET → setoid ≝ λx.x. coercion setoid_of_SET. -definition setoid1_of_SET: SET → setoid1. - intro; whd in t; apply setoid1_of_setoid; apply t. -qed. -coercion setoid1_of_SET. - -definition eq': ∀w:SET.equivalence_relation ? := λw.eq w. - -definition prop1_SET : - ∀A,B:SET.∀w:arrows1 SET A B.∀a,b:Type_OF_objs1 A.eq' ? a b→eq' ? (w a) (w b). -intros; apply (prop1 A B w a b e); -qed. - +definition unary_morphism_setoid_of_arrows1_SET: + ∀P,Q.arrows1 SET P Q → unary_morphism_setoid P Q ≝ λP,Q,x.x. +coercion unary_morphism_setoid_of_arrows1_SET. -interpretation "SET dagger" 'prop1 h = (prop1_SET _ _ _ _ _ h). notation "hbox(a break ⇒ b)" right associative with precedence 20 for @{ 'Imply $a $b }. interpretation "unary morphism" 'Imply a b = (arrows1 SET a b). -interpretation "SET eq" 'eq x y = (eq_rel _ (eq' _) x y). -definition unary_morphism1_setoid1: setoid1 → setoid1 → setoid2. +definition unary_morphism1_setoid1: setoid1 → setoid1 → setoid1. intros; constructor 1; [ apply (unary_morphism1 s s1); @@ -356,16 +405,20 @@ definition unary_morphism1_setoid1: setoid1 → setoid1 → setoid2. alias symbol "eq" = "setoid1 eq". apply (∀a: carr1 s. f a = g a); | intros 1; simplify; intros; apply refl1; - | simplify; intros; apply sym1; apply H; - | simplify; intros; apply trans1; [2: apply H; | skip | apply H1]]] + | simplify; intros; apply sym1; apply f; + | simplify; intros; apply trans1; [2: apply f; | skip | apply f1]]] qed. -definition SET1: category2. +definition unary_morphism1_of_unary_morphism1_setoid1 : + ∀S,T. unary_morphism1_setoid1 S T → unary_morphism1 S T ≝ λP,Q,x.x. +coercion unary_morphism1_of_unary_morphism1_setoid1. + +definition SET1: objs3 CAT2. constructor 1; [ apply setoid1; - | apply rule (λS,T.unary_morphism1_setoid1 S T); + | apply rule (λS,T.setoid2_of_setoid1 (unary_morphism1_setoid1 S T)); | intros; constructor 1; [ apply (λx.x); | intros; assumption ] - | intros; constructor 1; [ intros; constructor 1; [ apply (λx. t1 (t x)); | intros; + | intros; constructor 1; [ intros; constructor 1; [ apply (λx. c1 (c x)); | intros; apply († (†e));] | intros; whd; intros; simplify; whd in H1; whd in H; apply trans1; [ apply (b (a' a1)); | lapply (prop11 ?? b (a a1) (a' a1)); @@ -376,31 +429,17 @@ definition SET1: category2. ] qed. -definition setoid1_OF_SET1: objs2 SET1 → setoid1. - intros; apply o; qed. +definition setoid1_of_SET1: objs2 SET1 → setoid1 ≝ λx.x. +coercion setoid1_of_SET1. -coercion setoid1_OF_SET1. +definition unary_morphism1_setoid1_of_arrows2_SET1: + ∀P,Q.arrows2 SET1 P Q → unary_morphism1_setoid1 P Q ≝ λP,Q,x.x. +coercion unary_morphism1_setoid1_of_arrows2_SET1. + +variant objs2_of_category1: objs1 SET → objs2 SET1 ≝ setoid1_of_setoid. +coercion objs2_of_category1. -definition eq'': ∀w:SET1.equivalence_relation1 ? := λw.eq1 w. - -definition prop11_SET1 : - ∀A,B:SET1.∀w:arrows2 SET1 A B.∀a,b:Type_OF_objs2 A.eq'' ? a b→eq'' ? (w a) (w b). -intros; apply (prop11 A B w a b e); -qed. - -definition setoid2_OF_category2: Type_OF_category2 SET1 → setoid2. - intro; apply (setoid2_of_setoid1 t); qed. -coercion setoid2_OF_category2. - -definition objs2_OF_category1: Type_OF_category1 SET → objs2 SET1. - intro; apply (setoid1_of_setoid t); qed. -coercion objs2_OF_category1. - -definition Type1_OF_SET1: Type_OF_category2 SET1 → Type1. - intro; whd in t; apply (carr1 t); -qed. -coercion Type1_OF_SET1. +prefer coercion Type_OF_setoid. (* we prefer the lower carrier projection *) +prefer coercion Type_OF_objs1. -interpretation "SET dagger" 'prop1 h = (prop11_SET1 _ _ _ _ _ h). -interpretation "unary morphism1" 'Imply a b = (arrows2 SET1 a b). -interpretation "SET1 eq" 'eq x y = (eq_rel1 _ (eq'' _) x y). +interpretation "unary morphism1" 'Imply a b = (arrows2 SET1 a b). \ No newline at end of file