src/HOL/Algebra/FiniteProduct.thy
changeset 63167 0909deb8059b
parent 62105 686681f69d5e
child 67091 1393c2340eec
equal deleted inserted replaced
63166:143f58bb34f9 63167:0909deb8059b
    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