equal
deleted
inserted
replaced
10 |
10 |
11 subsection \<open>Product Operator for Commutative Monoids\<close> |
11 subsection \<open>Product Operator for Commutative Monoids\<close> |
12 |
12 |
13 subsubsection \<open>Inductive Definition of a Relation for Products over Sets\<close> |
13 subsubsection \<open>Inductive Definition of a Relation for Products over Sets\<close> |
14 |
14 |
15 text \<open>Instantiation of locale @{text LC} of theory @{text Finite_Set} is not |
15 text \<open>Instantiation of locale \<open>LC\<close> of theory \<open>Finite_Set\<close> is not |
16 possible, because here we have explicit typing rules like |
16 possible, because here we have explicit typing rules like |
17 @{text "x \<in> carrier G"}. We introduce an explicit argument for the domain |
17 \<open>x \<in> carrier G\<close>. We introduce an explicit argument for the domain |
18 @{text D}.\<close> |
18 \<open>D\<close>.\<close> |
19 |
19 |
20 inductive_set |
20 inductive_set |
21 foldSetD :: "['a set, 'b => 'a => 'a, 'a] => ('b set * 'a) set" |
21 foldSetD :: "['a set, 'b => 'a => 'a, 'a] => ('b set * 'a) set" |
22 for D :: "'a set" and f :: "'b => 'a => 'a" and e :: 'a |
22 for D :: "'a set" and f :: "'b => 'a => 'a" and e :: 'a |
23 where |
23 where |
109 apply (erule foldSetD.cases) |
109 apply (erule foldSetD.cases) |
110 apply blast |
110 apply blast |
111 apply (erule foldSetD.cases) |
111 apply (erule foldSetD.cases) |
112 apply blast |
112 apply blast |
113 apply clarify |
113 apply clarify |
114 txt \<open>force simplification of @{text "card A < card (insert ...)"}.\<close> |
114 txt \<open>force simplification of \<open>card A < card (insert ...)\<close>.\<close> |
115 apply (erule rev_mp) |
115 apply (erule rev_mp) |
116 apply (simp add: less_Suc_eq_le) |
116 apply (simp add: less_Suc_eq_le) |
117 apply (rule impI) |
117 apply (rule impI) |
118 apply (rename_tac xa Aa ya xb Ab yb, case_tac "xa = xb") |
118 apply (rename_tac xa Aa ya xb Ab yb, case_tac "xa = xb") |
119 apply (subgoal_tac "Aa = Ab") |
119 apply (subgoal_tac "Aa = Ab") |
219 lemma (in LCD) foldD_nest_Un_disjoint: |
219 lemma (in LCD) foldD_nest_Un_disjoint: |
220 "[| finite A; finite B; A Int B = {}; e \<in> D; A \<subseteq> B; C \<subseteq> B |] |
220 "[| finite A; finite B; A Int B = {}; e \<in> D; A \<subseteq> B; C \<subseteq> B |] |
221 ==> foldD D f e (A Un B) = foldD D f (foldD D f e B) A" |
221 ==> foldD D f e (A Un B) = foldD D f (foldD D f e B) A" |
222 by (simp add: foldD_nest_Un_Int) |
222 by (simp add: foldD_nest_Un_Int) |
223 |
223 |
224 -- \<open>Delete rules to do with @{text foldSetD} relation.\<close> |
224 \<comment> \<open>Delete rules to do with \<open>foldSetD\<close> relation.\<close> |
225 |
225 |
226 declare foldSetD_imp_finite [simp del] |
226 declare foldSetD_imp_finite [simp del] |
227 empty_foldSetDE [rule del] |
227 empty_foldSetDE [rule del] |
228 foldSetD.intros [rule del] |
228 foldSetD.intros [rule del] |
229 declare (in LCD) |
229 declare (in LCD) |
231 |
231 |
232 |
232 |
233 text \<open>Commutative Monoids\<close> |
233 text \<open>Commutative Monoids\<close> |
234 |
234 |
235 text \<open> |
235 text \<open> |
236 We enter a more restrictive context, with @{text "f :: 'a => 'a => 'a"} |
236 We enter a more restrictive context, with \<open>f :: 'a => 'a => 'a\<close> |
237 instead of @{text "'b => 'a => 'a"}. |
237 instead of \<open>'b => 'a => 'a\<close>. |
238 \<close> |
238 \<close> |
239 |
239 |
240 locale ACeD = |
240 locale ACeD = |
241 fixes D :: "'a set" |
241 fixes D :: "'a set" |
242 and f :: "'a => 'a => 'a" (infixl "\<cdot>" 70) |
242 and f :: "'a => 'a => 'a" (infixl "\<cdot>" 70) |
297 syntax |
297 syntax |
298 "_finprod" :: "index => idt => 'a set => 'b => 'b" |
298 "_finprod" :: "index => idt => 'a set => 'b => 'b" |
299 ("(3\<Otimes>__\<in>_. _)" [1000, 0, 51, 10] 10) |
299 ("(3\<Otimes>__\<in>_. _)" [1000, 0, 51, 10] 10) |
300 translations |
300 translations |
301 "\<Otimes>\<^bsub>G\<^esub>i\<in>A. b" \<rightleftharpoons> "CONST finprod G (%i. b) A" |
301 "\<Otimes>\<^bsub>G\<^esub>i\<in>A. b" \<rightleftharpoons> "CONST finprod G (%i. b) A" |
302 -- \<open>Beware of argument permutation!\<close> |
302 \<comment> \<open>Beware of argument permutation!\<close> |
303 |
303 |
304 lemma (in comm_monoid) finprod_empty [simp]: |
304 lemma (in comm_monoid) finprod_empty [simp]: |
305 "finprod G f {} = \<one>" |
305 "finprod G f {} = \<one>" |
306 by (simp add: finprod_def) |
306 by (simp add: finprod_def) |
307 |
307 |
365 |
365 |
366 lemma finprod_Un_Int: |
366 lemma finprod_Un_Int: |
367 "[| finite A; finite B; g \<in> A \<rightarrow> carrier G; g \<in> B \<rightarrow> carrier G |] ==> |
367 "[| finite A; finite B; g \<in> A \<rightarrow> carrier G; g \<in> B \<rightarrow> carrier G |] ==> |
368 finprod G g (A Un B) \<otimes> finprod G g (A Int B) = |
368 finprod G g (A Un B) \<otimes> finprod G g (A Int B) = |
369 finprod G g A \<otimes> finprod G g B" |
369 finprod G g A \<otimes> finprod G g B" |
370 -- \<open>The reversed orientation looks more natural, but LOOPS as a simprule!\<close> |
370 \<comment> \<open>The reversed orientation looks more natural, but LOOPS as a simprule!\<close> |
371 proof (induct set: finite) |
371 proof (induct set: finite) |
372 case empty then show ?case by simp |
372 case empty then show ?case by simp |
373 next |
373 next |
374 case (insert a A) |
374 case (insert a A) |
375 then have a: "g a \<in> carrier G" by fast |
375 then have a: "g a \<in> carrier G" by fast |
449 !!i. i \<in> B =simp=> f i = g i |] ==> finprod G f A = finprod G g B" |
449 !!i. i \<in> B =simp=> f i = g i |] ==> finprod G f A = finprod G g B" |
450 (* This order of prems is slightly faster (3%) than the last two swapped. *) |
450 (* This order of prems is slightly faster (3%) than the last two swapped. *) |
451 by (rule finprod_cong') (auto simp add: simp_implies_def) |
451 by (rule finprod_cong') (auto simp add: simp_implies_def) |
452 |
452 |
453 text \<open>Usually, if this rule causes a failed congruence proof error, |
453 text \<open>Usually, if this rule causes a failed congruence proof error, |
454 the reason is that the premise @{text "g \<in> B \<rightarrow> carrier G"} cannot be shown. |
454 the reason is that the premise \<open>g \<in> B \<rightarrow> carrier G\<close> cannot be shown. |
455 Adding @{thm [source] Pi_def} to the simpset is often useful. |
455 Adding @{thm [source] Pi_def} to the simpset is often useful. |
456 For this reason, @{thm [source] finprod_cong} |
456 For this reason, @{thm [source] finprod_cong} |
457 is not added to the simpset by default. |
457 is not added to the simpset by default. |
458 \<close> |
458 \<close> |
459 |
459 |