X-Git-Url: http://matita.cs.unibo.it/gitweb/?a=blobdiff_plain;f=weblib%2Ftutorial%2Fchapter4.ma;h=be8ddaa594212f9b0dacba4a7d7ddb8c81a23982;hb=a2ba04cd90e76937720b16e37cb12a39b46181e3;hp=c159fa13db6b0dfe72246273c57a1db5ecab7236;hpb=bef004f9c2ab68f9f0f9c95536918681a61849fc;p=helm.git diff --git a/weblib/tutorial/chapter4.ma b/weblib/tutorial/chapter4.ma index c159fa13d..be8ddaa59 100644 --- a/weblib/tutorial/chapter4.ma +++ b/weblib/tutorial/chapter4.ma @@ -14,7 +14,7 @@ interpretation "empty set" 'empty_set = (empty_set ?). (* Similarly, a singleton set contaning containing an element a, is defined by by the characteristic function asserting equality with a *) -definition singleton ≝ λA.λx,a:A.xa title="leibnitz's equality" href="cic:/fakeuri.def(1)"=/aa. +definition singleton ≝ λA.λx,a:A.xa title="leibnitz's equality" href="cic:/fakeuri.def(1)"=/aspan class="error" title="Parse error: [term] expected after [sym=] (in [term])"/spana. (* notation "{x}" non associative with precedence 90 for @{'sing_lang $x}. *) interpretation "singleton" 'singl x = (singleton ? x). @@ -27,7 +27,7 @@ conjunction and negation *) definition union : ∀A:Type[0].∀P,Q.A → Prop ≝ λA,P,Q,a.P a a title="logical or" href="cic:/fakeuri.def(1)"∨/a Q a. interpretation "union" 'union a b = (union ? a b). -definition intersection : ∀A:Type[0].∀P,Q.A→Prop ≝ λA,P,Q,a.P a a title="logical and" href="cic:/fakeuri.def(1)"∧/a Q a. +definition intersection : ∀A:Type[0].∀P,Q.A→Prop ≝ λA,P,Q,a.P a a title="logical and" href="cic:/fakeuri.def(1)"∧/aspan class="error" title="Parse error: [term] expected after [sym∧] (in [term])"/span Q a. interpretation "intersection" 'intersects a b = (intersection ? a b). definition complement ≝ λU:Type[0].λA:U → Prop.λw.a title="logical not" href="cic:/fakeuri.def(1)"¬/a A w. @@ -45,7 +45,7 @@ interpretation "subset" 'subseteq a b = (subset ? a b). (* Two sets are equals if and only if they have the same elements, that is, if the two characteristic functions are extensionally equivalent: *) -definition eqP ≝ λA:Type[0].λP,Q:A → Prop.∀a:A.P a a title="iff" href="cic:/fakeuri.def(1)"↔/a Q a. +definition eqP ≝ λA:Type[0].λP,Q:A → Prop.∀a:A.P a a title="iff" href="cic:/fakeuri.def(1)"↔/aspan class="error" title="Parse error: [term] expected after [sym↔] (in [term])"/span Q a. notation "A =1 B" non associative with precedence 45 for @{'eqP $A $B}. interpretation "extensional equality" 'eqP a b = (eqP ? a b). @@ -65,7 +65,7 @@ lemma eqP_trans: ∀U.∀A,B,C:U →Prop. with respect to eqP: *) lemma eqP_union_r: ∀U.∀A,B,C:U →Prop. - A a title="extensional equality" href="cic:/fakeuri.def(1)"=/a1 C → A a title="union" href="cic:/fakeuri.def(1)"∪/a B a title="extensional equality" href="cic:/fakeuri.def(1)"=/a1 C a title="union" href="cic:/fakeuri.def(1)"∪/a B. + A a title="extensional equality" href="cic:/fakeuri.def(1)"=/aspan class="error" title="Parse error: NUMBER '1' or [term] expected after [sym=] (in [term])"/span1 C → A a title="union" href="cic:/fakeuri.def(1)"∪/a B a title="extensional equality" href="cic:/fakeuri.def(1)"=/a1 C a title="union" href="cic:/fakeuri.def(1)"∪/a B. #U #A #B #C #eqAB #a @a href="cic:/matita/basics/logic/iff_or_r.def(2)"iff_or_r/a @eqAB qed. lemma eqP_union_l: ∀U.∀A,B,C:U →Prop. @@ -77,7 +77,7 @@ lemma eqP_intersect_r: ∀U.∀A,B,C:U →Prop. #U #A #B #C #eqAB #a @a href="cic:/matita/basics/logic/iff_and_r.def(2)"iff_and_r/a @eqAB qed. lemma eqP_intersect_l: ∀U.∀A,B,C:U →Prop. - B a title="extensional equality" href="cic:/fakeuri.def(1)"=/a1 C → A a title="intersection" href="cic:/fakeuri.def(1)"∩/a B a title="extensional equality" href="cic:/fakeuri.def(1)"=/a1 A a title="intersection" href="cic:/fakeuri.def(1)"∩/a C. + B a title="extensional equality" href="cic:/fakeuri.def(1)"=/a1 C → A a title="intersection" href="cic:/fakeuri.def(1)"∩/aspan class="error" title="Parse error: [term] expected after [sym∩] (in [term])"/span B a title="extensional equality" href="cic:/fakeuri.def(1)"=/a1 A a title="intersection" href="cic:/fakeuri.def(1)"∩/a C. #U #A #B #C #eqBC #a @a href="cic:/matita/basics/logic/iff_and_l.def(2)"iff_and_l/a @eqBC qed. lemma eqP_substract_r: ∀U.∀A,B,C:U →Prop. @@ -103,7 +103,7 @@ lemma union_comm : ∀U.∀A,B:U →Prop. lemma union_assoc: ∀U.∀A,B,C:U → Prop. A a title="union" href="cic:/fakeuri.def(1)"∪/a B a title="union" href="cic:/fakeuri.def(1)"∪/a C a title="extensional equality" href="cic:/fakeuri.def(1)"=/a1 A a title="union" href="cic:/fakeuri.def(1)"∪/a (B a title="union" href="cic:/fakeuri.def(1)"∪/a C). -#S #A #B #C #w % [* [* /span class="autotactic"3span class="autotrace" trace a href="cic:/matita/basics/logic/Or.con(0,1,2)"or_introl/a, a href="cic:/matita/basics/logic/Or.con(0,2,2)"or_intror/a/span/span/ | /span class="autotactic"3span class="autotrace" trace a href="cic:/matita/basics/logic/Or.con(0,2,2)"or_intror/a/span/span/] | * [/span class="autotactic"3span class="autotrace" trace a href="cic:/matita/basics/logic/Or.con(0,1,2)"or_introl/a/span/span/ | * /span class="autotactic"3span class="autotrace" trace a href="cic:/matita/basics/logic/Or.con(0,1,2)"or_introl/a, a href="cic:/matita/basics/logic/Or.con(0,2,2)"or_intror/a/span/span/] +#S #A #B #C #w % [* [* /span class="autotactic"3span class="autotrace" trace a href="cic:/matita/basics/logic/Or.con(0,1,2)"or_introl/a, a href="cic:/matita/basics/logic/Or.con(0,2,2)"or_intror/a/span/span/ | /span class="autotactic"3span class="autotrace" trace a href="cic:/matita/basics/logic/Or.con(0,1,2)"or_introl/a, a href="cic:/matita/basics/logic/Or.con(0,2,2)"or_intror/a/span/span/ ] | * [/span class="autotactic"3span class="autotrace" trace a href="cic:/matita/basics/logic/Or.con(0,1,2)"or_introl/a/span/span/ | * /span class="autotactic"3span class="autotrace" trace a href="cic:/matita/basics/logic/Or.con(0,1,2)"or_introl/a, a href="cic:/matita/basics/logic/Or.con(0,2,2)"or_intror/a/span/span/] qed. (* In the same way we prove commutativity and associativity for set @@ -283,36 +283,36 @@ this, we must as usual define the boolen equality function, and prove it correctly reflects propositional equality. *) definition eq_pairs ≝ - λA,B:DeqSet.λp1,p2:A×B.(\fst p1 == \fst p2) ∧ (\snd p1 == \snd p2). + λA,B:a href="cic:/matita/tutorial/chapter4/DeqSet.ind(1,0,0)"DeqSet/a.λp1,p2:Aa title="Product" href="cic:/fakeuri.def(1)"×/aB.(a title="pair pi1" href="cic:/fakeuri.def(1)"\fst/a p1 a title="eqb" href="cic:/fakeuri.def(1)"=/a= a title="pair pi1" href="cic:/fakeuri.def(1)"\fst/a p2) a title="boolean and" href="cic:/fakeuri.def(1)"∧/a (a title="pair pi2" href="cic:/fakeuri.def(1)"\snd/a p1 a title="eqb" href="cic:/fakeuri.def(1)"=/a= a title="pair pi2" href="cic:/fakeuri.def(1)"\snd/a p2). -lemma eq_pairs_true: ∀A,B:DeqSet.∀p1,p2:A×B. - eq_pairs A B p1 p2 = true ↔ p1 = p2. +lemma eq_pairs_true: ∀A,B:a href="cic:/matita/tutorial/chapter4/DeqSet.ind(1,0,0)"DeqSet/a.∀p1,p2:Aa title="Product" href="cic:/fakeuri.def(1)"×/aB. + a href="cic:/matita/tutorial/chapter4/eq_pairs.def(4)"eq_pairs/a A B p1 p2 a title="leibnitz's equality" href="cic:/fakeuri.def(1)"=/a a href="cic:/matita/basics/bool/bool.con(0,1,0)"true/a a title="iff" href="cic:/fakeuri.def(1)"↔/a p1 a title="leibnitz's equality" href="cic:/fakeuri.def(1)"=/a p2. #A #B * #a1 #b1 * #a2 #b2 % - [#H cases (andb_true …H) normalize #eqa #eqb >(\P eqa) >(\P eqb) // - |#H destruct normalize >(\b (refl … a2)) >(\b (refl … b2)) // + [#H cases (a href="cic:/matita/basics/bool/andb_true.def(5)"andb_true/a …H) normalize #eqa #eqb >(\P eqa) >(\P eqb) // + |#H destruct normalize >(\b (a href="cic:/matita/basics/logic/eq.con(0,1,2)"refl/a … a2)) >(\b (a href="cic:/matita/basics/logic/eq.con(0,1,2)"refl/a … b2)) // ] qed. -definition DeqProd ≝ λA,B:DeqSet. - mk_DeqSet (A×B) (eq_pairs A B) (eq_pairs_true A B). +definition DeqProd ≝ λA,B:a href="cic:/matita/tutorial/chapter4/DeqSet.ind(1,0,0)"DeqSet/a. + a href="cic:/matita/tutorial/chapter4/DeqSet.con(0,1,0)"mk_DeqSet/a (Aa title="Product" href="cic:/fakeuri.def(1)"×/aB) (a href="cic:/matita/tutorial/chapter4/eq_pairs.def(4)"eq_pairs/a A B) (a href="cic:/matita/tutorial/chapter4/eq_pairs_true.def(6)"eq_pairs_true/a A B). (* Having an unification problem of the kind T1×T2 = carr X, what kind of hint can we give to the system? We expect T1 to be the carrier of a DeqSet C1, T2 to be the carrier of a DeqSet C2, and X to be DeqProd C1 C2. This is expressed by the following hint: *) -unification hint 0 ≔ C1,C2; - T1 ≟ carr C1, - T2 ≟ carr C2, - X ≟ DeqProd C1 C2 +unification hint 0 a href="cic:/fakeuri.def(1)" title="hint_decl_Type1"≔/a C1,C2; + T1 ≟ a href="cic:/matita/tutorial/chapter4/carr.fix(0,0,2)"carr/a C1, + T2 ≟ a href="cic:/matita/tutorial/chapter4/carr.fix(0,0,2)"carr/a C2, + X ≟ a href="cic:/matita/tutorial/chapter4/DeqProd.def(7)"DeqProd/a C1 C2 (* ---------------------------------------- *) ⊢ - T1×T2 ≡ carr X. + T1a title="Product" href="cic:/fakeuri.def(1)"×/aT2 ≡ a href="cic:/matita/tutorial/chapter4/carr.fix(0,0,2)"carr/a X. -unification hint 0 ≔ T1,T2,p1,p2; - X ≟ DeqProd T1 T2 +unification hint 0 a href="cic:/fakeuri.def(1)" title="hint_decl_Type0"≔/a T1,T2,p1,p2; + X ≟ a href="cic:/matita/tutorial/chapter4/DeqProd.def(7)"DeqProd/a T1 T2 (* ---------------------------------------- *) ⊢ - eq_pairs T1 T2 p1 p2 ≡ eqb X p1 p2. + a href="cic:/matita/tutorial/chapter4/eq_pairs.def(4)"eq_pairs/a T1 T2 p1 p2 ≡ a href="cic:/matita/tutorial/chapter4/eqb.fix(0,0,3)"eqb/a X p1 p2. example hint2: ∀b1,b2. - 〈b1,true〉==〈false,b2〉=true → 〈b1,true〉=〈false,b2〉. + a title="Pair construction" href="cic:/fakeuri.def(1)"〈/ab1,a href="cic:/matita/basics/bool/bool.con(0,1,0)"true/a〉a title="eqb" href="cic:/fakeuri.def(1)"=/a=a title="Pair construction" href="cic:/fakeuri.def(1)"〈/aa href="cic:/matita/basics/bool/bool.con(0,2,0)"false/a,b2〉a title="leibnitz's equality" href="cic:/fakeuri.def(1)"=/aa href="cic:/matita/basics/bool/bool.con(0,1,0)"true/a → a title="Pair construction" href="cic:/fakeuri.def(1)"〈/ab1,a href="cic:/matita/basics/bool/bool.con(0,1,0)"true/a〉a title="leibnitz's equality" href="cic:/fakeuri.def(1)"=/aa title="Pair construction" href="cic:/fakeuri.def(1)"〈/aa href="cic:/matita/basics/bool/bool.con(0,2,0)"false/a,b2〉. #b1 #b2 #H @(\P H). \ No newline at end of file