src/HOL/Library/Groups_Big_Fun.thy
author wenzelm
Mon Nov 09 15:48:17 2015 +0100 (2015-11-09)
changeset 61605 1bf7b186542e
parent 61424 c3658c18b7bc
child 61670 301e0b4ecd45
permissions -rw-r--r--
qualifier is mandatory by default;
haftmann@58197
     1
(* Author: Florian Haftmann, TU Muenchen *)
haftmann@58197
     2
wenzelm@58881
     3
section \<open>Big sum and product over function bodies\<close>
haftmann@58197
     4
haftmann@58197
     5
theory Groups_Big_Fun
haftmann@58197
     6
imports
haftmann@58197
     7
  Main
haftmann@58197
     8
  "~~/src/Tools/Permanent_Interpretation"
haftmann@58197
     9
begin
haftmann@58197
    10
haftmann@58197
    11
subsection \<open>Abstract product\<close>
haftmann@58197
    12
haftmann@58197
    13
no_notation times (infixl "*" 70)
haftmann@58197
    14
no_notation Groups.one ("1")
haftmann@58197
    15
haftmann@58197
    16
locale comm_monoid_fun = comm_monoid
haftmann@58197
    17
begin
haftmann@58197
    18
haftmann@58197
    19
definition G :: "('b \<Rightarrow> 'a) \<Rightarrow> 'a"
haftmann@58197
    20
where
haftmann@58197
    21
  expand_set: "G g = comm_monoid_set.F f 1 g {a. g a \<noteq> 1}"
haftmann@58197
    22
wenzelm@61605
    23
interpretation F: comm_monoid_set f 1
haftmann@58197
    24
  ..
haftmann@58197
    25
haftmann@58197
    26
lemma expand_superset:
haftmann@58197
    27
  assumes "finite A" and "{a. g a \<noteq> 1} \<subseteq> A"
haftmann@58197
    28
  shows "G g = F.F g A"
haftmann@58197
    29
  apply (simp add: expand_set)
haftmann@58197
    30
  apply (rule F.same_carrierI [of A])
haftmann@58197
    31
  apply (simp_all add: assms)
haftmann@58197
    32
  done
haftmann@58197
    33
haftmann@58197
    34
lemma conditionalize:
haftmann@58197
    35
  assumes "finite A"
haftmann@58197
    36
  shows "F.F g A = G (\<lambda>a. if a \<in> A then g a else 1)"
haftmann@58197
    37
  using assms
haftmann@58197
    38
  apply (simp add: expand_set)
haftmann@58197
    39
  apply (rule F.same_carrierI [of A])
haftmann@58197
    40
  apply auto
haftmann@58197
    41
  done
haftmann@58197
    42
haftmann@58197
    43
lemma neutral [simp]:
haftmann@58197
    44
  "G (\<lambda>a. 1) = 1"
haftmann@58197
    45
  by (simp add: expand_set)
haftmann@58197
    46
haftmann@58197
    47
lemma update [simp]:
haftmann@58197
    48
  assumes "finite {a. g a \<noteq> 1}"
haftmann@58197
    49
  assumes "g a = 1"
haftmann@58197
    50
  shows "G (g(a := b)) = b * G g"
haftmann@58197
    51
proof (cases "b = 1")
wenzelm@60500
    52
  case True with \<open>g a = 1\<close> show ?thesis
haftmann@58197
    53
    by (simp add: expand_set) (rule F.cong, auto)
haftmann@58197
    54
next
haftmann@58197
    55
  case False
haftmann@58197
    56
  moreover have "{a'. a' \<noteq> a \<longrightarrow> g a' \<noteq> 1} = insert a {a. g a \<noteq> 1}"
haftmann@58197
    57
    by auto
wenzelm@60500
    58
  moreover from \<open>g a = 1\<close> have "a \<notin> {a. g a \<noteq> 1}"
haftmann@58197
    59
    by simp
haftmann@58197
    60
  moreover have "F.F (\<lambda>a'. if a' = a then b else g a') {a. g a \<noteq> 1} = F.F g {a. g a \<noteq> 1}"
wenzelm@60500
    61
    by (rule F.cong) (auto simp add: \<open>g a = 1\<close>)
wenzelm@60500
    62
  ultimately show ?thesis using \<open>finite {a. g a \<noteq> 1}\<close> by (simp add: expand_set)
haftmann@58197
    63
qed
haftmann@58197
    64
haftmann@58197
    65
lemma infinite [simp]:
haftmann@58197
    66
  "\<not> finite {a. g a \<noteq> 1} \<Longrightarrow> G g = 1"
haftmann@58197
    67
  by (simp add: expand_set)
haftmann@58197
    68
haftmann@58197
    69
lemma cong:
haftmann@58197
    70
  assumes "\<And>a. g a = h a"
haftmann@58197
    71
  shows "G g = G h"
haftmann@58197
    72
  using assms by (simp add: expand_set)
haftmann@58197
    73
haftmann@58197
    74
lemma strong_cong [cong]:
haftmann@58197
    75
  assumes "\<And>a. g a = h a"
haftmann@58197
    76
  shows "G (\<lambda>a. g a) = G (\<lambda>a. h a)"
haftmann@58197
    77
  using assms by (fact cong)
haftmann@58197
    78
haftmann@58197
    79
lemma not_neutral_obtains_not_neutral:
haftmann@58197
    80
  assumes "G g \<noteq> 1"
haftmann@58197
    81
  obtains a where "g a \<noteq> 1"
haftmann@58197
    82
  using assms by (auto elim: F.not_neutral_contains_not_neutral simp add: expand_set)
haftmann@58197
    83
haftmann@58197
    84
lemma reindex_cong:
haftmann@58197
    85
  assumes "bij l"
haftmann@58197
    86
  assumes "g \<circ> l = h"
haftmann@58197
    87
  shows "G g = G h"
haftmann@58197
    88
proof -
haftmann@58197
    89
  from assms have unfold: "h = g \<circ> l" by simp
wenzelm@60500
    90
  from \<open>bij l\<close> have "inj l" by (rule bij_is_inj)
haftmann@58197
    91
  then have "inj_on l {a. h a \<noteq> 1}" by (rule subset_inj_on) simp
wenzelm@60500
    92
  moreover from \<open>bij l\<close> have "{a. g a \<noteq> 1} = l ` {a. h a \<noteq> 1}"
haftmann@58197
    93
    by (auto simp add: image_Collect unfold elim: bij_pointE)
haftmann@58197
    94
  moreover have "\<And>x. x \<in> {a. h a \<noteq> 1} \<Longrightarrow> g (l x) = h x"
haftmann@58197
    95
    by (simp add: unfold)
haftmann@58197
    96
  ultimately have "F.F g {a. g a \<noteq> 1} = F.F h {a. h a \<noteq> 1}"
haftmann@58197
    97
    by (rule F.reindex_cong)
haftmann@58197
    98
  then show ?thesis by (simp add: expand_set)
haftmann@58197
    99
qed
haftmann@58197
   100
haftmann@58197
   101
lemma distrib:
haftmann@58197
   102
  assumes "finite {a. g a \<noteq> 1}" and "finite {a. h a \<noteq> 1}"
haftmann@58197
   103
  shows "G (\<lambda>a. g a * h a) = G g * G h"
haftmann@58197
   104
proof -
haftmann@58197
   105
  from assms have "finite ({a. g a \<noteq> 1} \<union> {a. h a \<noteq> 1})" by simp
haftmann@58197
   106
  moreover have "{a. g a * h a \<noteq> 1} \<subseteq> {a. g a \<noteq> 1} \<union> {a. h a \<noteq> 1}"
haftmann@58197
   107
    by auto (drule sym, simp)
haftmann@58197
   108
  ultimately show ?thesis
haftmann@58197
   109
    using assms
haftmann@58197
   110
    by (simp add: expand_superset [of "{a. g a \<noteq> 1} \<union> {a. h a \<noteq> 1}"] F.distrib)
haftmann@58197
   111
qed
haftmann@58197
   112
haftmann@58197
   113
lemma commute:
haftmann@58197
   114
  assumes "finite C"
haftmann@58197
   115
  assumes subset: "{a. \<exists>b. g a b \<noteq> 1} \<times> {b. \<exists>a. g a b \<noteq> 1} \<subseteq> C" (is "?A \<times> ?B \<subseteq> C")
haftmann@58197
   116
  shows "G (\<lambda>a. G (g a)) = G (\<lambda>b. G (\<lambda>a. g a b))"
haftmann@58197
   117
proof -
wenzelm@60500
   118
  from \<open>finite C\<close> subset
haftmann@58197
   119
    have "finite ({a. \<exists>b. g a b \<noteq> 1} \<times> {b. \<exists>a. g a b \<noteq> 1})"
haftmann@58197
   120
    by (rule rev_finite_subset)
haftmann@58197
   121
  then have fins:
haftmann@58197
   122
    "finite {b. \<exists>a. g a b \<noteq> 1}" "finite {a. \<exists>b. g a b \<noteq> 1}"
haftmann@58197
   123
    by (auto simp add: finite_cartesian_product_iff)
haftmann@58197
   124
  have subsets: "\<And>a. {b. g a b \<noteq> 1} \<subseteq> {b. \<exists>a. g a b \<noteq> 1}"
haftmann@58197
   125
    "\<And>b. {a. g a b \<noteq> 1} \<subseteq> {a. \<exists>b. g a b \<noteq> 1}"
haftmann@58197
   126
    "{a. F.F (g a) {b. \<exists>a. g a b \<noteq> 1} \<noteq> 1} \<subseteq> {a. \<exists>b. g a b \<noteq> 1}"
haftmann@58197
   127
    "{a. F.F (\<lambda>aa. g aa a) {a. \<exists>b. g a b \<noteq> 1} \<noteq> 1} \<subseteq> {b. \<exists>a. g a b \<noteq> 1}"
haftmann@58197
   128
    by (auto elim: F.not_neutral_contains_not_neutral)
haftmann@58197
   129
  from F.commute have
haftmann@58197
   130
    "F.F (\<lambda>a. F.F (g a) {b. \<exists>a. g a b \<noteq> 1}) {a. \<exists>b. g a b \<noteq> 1} =
haftmann@58197
   131
      F.F (\<lambda>b. F.F (\<lambda>a. g a b) {a. \<exists>b. g a b \<noteq> 1}) {b. \<exists>a. g a b \<noteq> 1}" .
haftmann@58197
   132
  with subsets fins have "G (\<lambda>a. F.F (g a) {b. \<exists>a. g a b \<noteq> 1}) =
haftmann@58197
   133
    G (\<lambda>b. F.F (\<lambda>a. g a b) {a. \<exists>b. g a b \<noteq> 1})"
haftmann@58197
   134
    by (auto simp add: expand_superset [of "{b. \<exists>a. g a b \<noteq> 1}"]
haftmann@58197
   135
      expand_superset [of "{a. \<exists>b. g a b \<noteq> 1}"])
haftmann@58197
   136
  with subsets fins show ?thesis
haftmann@58197
   137
    by (auto simp add: expand_superset [of "{b. \<exists>a. g a b \<noteq> 1}"]
haftmann@58197
   138
      expand_superset [of "{a. \<exists>b. g a b \<noteq> 1}"])
haftmann@58197
   139
qed
haftmann@58197
   140
haftmann@58197
   141
lemma cartesian_product:
haftmann@58197
   142
  assumes "finite C"
haftmann@58197
   143
  assumes subset: "{a. \<exists>b. g a b \<noteq> 1} \<times> {b. \<exists>a. g a b \<noteq> 1} \<subseteq> C" (is "?A \<times> ?B \<subseteq> C")
haftmann@58197
   144
  shows "G (\<lambda>a. G (g a)) = G (\<lambda>(a, b). g a b)"
haftmann@58197
   145
proof -
wenzelm@60500
   146
  from subset \<open>finite C\<close> have fin_prod: "finite (?A \<times> ?B)"
haftmann@58197
   147
    by (rule finite_subset)
haftmann@58197
   148
  from fin_prod have "finite ?A" and "finite ?B"
haftmann@58197
   149
    by (auto simp add: finite_cartesian_product_iff)
haftmann@58197
   150
  have *: "G (\<lambda>a. G (g a)) =
haftmann@58197
   151
    (F.F (\<lambda>a. F.F (g a) {b. \<exists>a. g a b \<noteq> 1}) {a. \<exists>b. g a b \<noteq> 1})"
haftmann@58197
   152
    apply (subst expand_superset [of "?B"])
wenzelm@60500
   153
    apply (rule \<open>finite ?B\<close>)
haftmann@58197
   154
    apply auto
haftmann@58197
   155
    apply (subst expand_superset [of "?A"])
wenzelm@60500
   156
    apply (rule \<open>finite ?A\<close>)
haftmann@58197
   157
    apply auto
haftmann@58197
   158
    apply (erule F.not_neutral_contains_not_neutral)
haftmann@58197
   159
    apply auto
haftmann@58197
   160
    done
haftmann@58197
   161
  have "{p. (case p of (a, b) \<Rightarrow> g a b) \<noteq> 1} \<subseteq> ?A \<times> ?B"
haftmann@58197
   162
    by auto
haftmann@58197
   163
  with subset have **: "{p. (case p of (a, b) \<Rightarrow> g a b) \<noteq> 1} \<subseteq> C"
haftmann@58197
   164
    by blast
haftmann@58197
   165
  show ?thesis
haftmann@58197
   166
    apply (simp add: *)
haftmann@58197
   167
    apply (simp add: F.cartesian_product)
haftmann@58197
   168
    apply (subst expand_superset [of C])
wenzelm@60500
   169
    apply (rule \<open>finite C\<close>)
haftmann@58197
   170
    apply (simp_all add: **)
haftmann@58197
   171
    apply (rule F.same_carrierI [of C])
wenzelm@60500
   172
    apply (rule \<open>finite C\<close>)
haftmann@58197
   173
    apply (simp_all add: subset)
haftmann@58197
   174
    apply auto
haftmann@58197
   175
    done
haftmann@58197
   176
qed
haftmann@58197
   177
haftmann@58197
   178
lemma cartesian_product2:
haftmann@58197
   179
  assumes fin: "finite D"
haftmann@58197
   180
  assumes subset: "{(a, b). \<exists>c. g a b c \<noteq> 1} \<times> {c. \<exists>a b. g a b c \<noteq> 1} \<subseteq> D" (is "?AB \<times> ?C \<subseteq> D")
haftmann@58197
   181
  shows "G (\<lambda>(a, b). G (g a b)) = G (\<lambda>(a, b, c). g a b c)"
haftmann@58197
   182
proof -
haftmann@58197
   183
  have bij: "bij (\<lambda>(a, b, c). ((a, b), c))"
haftmann@58197
   184
    by (auto intro!: bijI injI simp add: image_def)
haftmann@58197
   185
  have "{p. \<exists>c. g (fst p) (snd p) c \<noteq> 1} \<times> {c. \<exists>p. g (fst p) (snd p) c \<noteq> 1} \<subseteq> D"
haftmann@61424
   186
    by auto (insert subset, blast)
haftmann@58197
   187
  with fin have "G (\<lambda>p. G (g (fst p) (snd p))) = G (\<lambda>(p, c). g (fst p) (snd p) c)"
haftmann@58197
   188
    by (rule cartesian_product)
haftmann@58197
   189
  then have "G (\<lambda>(a, b). G (g a b)) = G (\<lambda>((a, b), c). g a b c)"
haftmann@58197
   190
    by (auto simp add: split_def)
haftmann@58197
   191
  also have "G (\<lambda>((a, b), c). g a b c) = G (\<lambda>(a, b, c). g a b c)"
haftmann@58197
   192
    using bij by (rule reindex_cong [of "\<lambda>(a, b, c). ((a, b), c)"]) (simp add: fun_eq_iff)
haftmann@58197
   193
  finally show ?thesis .
haftmann@58197
   194
qed
haftmann@58197
   195
haftmann@58197
   196
lemma delta [simp]:
haftmann@58197
   197
  "G (\<lambda>b. if b = a then g b else 1) = g a"
haftmann@58197
   198
proof -
haftmann@58197
   199
  have "{b. (if b = a then g b else 1) \<noteq> 1} \<subseteq> {a}" by auto
haftmann@58197
   200
  then show ?thesis by (simp add: expand_superset [of "{a}"])
haftmann@58197
   201
qed
haftmann@58197
   202
haftmann@58197
   203
lemma delta' [simp]:
haftmann@58197
   204
  "G (\<lambda>b. if a = b then g b else 1) = g a"
haftmann@58197
   205
proof -
haftmann@58197
   206
  have "(\<lambda>b. if a = b then g b else 1) = (\<lambda>b. if b = a then g b else 1)"
haftmann@58197
   207
    by (simp add: fun_eq_iff)
haftmann@58197
   208
  then have "G (\<lambda>b. if a = b then g b else 1) = G (\<lambda>b. if b = a then g b else 1)"
haftmann@58197
   209
    by (simp cong del: strong_cong)
haftmann@58197
   210
  then show ?thesis by simp
haftmann@58197
   211
qed
haftmann@58197
   212
haftmann@58197
   213
end
haftmann@58197
   214
haftmann@58197
   215
notation times (infixl "*" 70)
haftmann@58197
   216
notation Groups.one ("1")
haftmann@58197
   217
haftmann@58197
   218
haftmann@58197
   219
subsection \<open>Concrete sum\<close>
haftmann@58197
   220
haftmann@58197
   221
context comm_monoid_add
haftmann@58197
   222
begin
haftmann@58197
   223
haftmann@58197
   224
definition Sum_any :: "('b \<Rightarrow> 'a) \<Rightarrow> 'a"
haftmann@58197
   225
where
haftmann@58197
   226
  "Sum_any = comm_monoid_fun.G plus 0"
haftmann@58197
   227
wenzelm@61605
   228
permanent_interpretation Sum_any: comm_monoid_fun plus 0
haftmann@58197
   229
where
haftmann@58197
   230
  "comm_monoid_fun.G plus 0 = Sum_any" and
haftmann@58197
   231
  "comm_monoid_set.F plus 0 = setsum"
haftmann@58197
   232
proof -
haftmann@58197
   233
  show "comm_monoid_fun plus 0" ..
wenzelm@61605
   234
  then interpret Sum_any: comm_monoid_fun plus 0 .
haftmann@58197
   235
  from Sum_any_def show "comm_monoid_fun.G plus 0 = Sum_any" by rule
haftmann@58197
   236
  from setsum_def show "comm_monoid_set.F plus 0 = setsum" by rule
haftmann@58197
   237
qed
haftmann@58197
   238
haftmann@58197
   239
end
haftmann@58197
   240
haftmann@58197
   241
syntax
haftmann@58197
   242
  "_Sum_any" :: "pttrn \<Rightarrow> 'a \<Rightarrow> 'a::comm_monoid_add"    ("(3SUM _. _)" [0, 10] 10)
haftmann@58197
   243
syntax (xsymbols)
haftmann@58197
   244
  "_Sum_any" :: "pttrn \<Rightarrow> 'a \<Rightarrow> 'a::comm_monoid_add"    ("(3\<Sum>_. _)" [0, 10] 10)
haftmann@58197
   245
translations
haftmann@58197
   246
  "\<Sum>a. b" == "CONST Sum_any (\<lambda>a. b)"
haftmann@58197
   247
haftmann@58197
   248
lemma Sum_any_left_distrib:
haftmann@58197
   249
  fixes r :: "'a :: semiring_0"
haftmann@58197
   250
  assumes "finite {a. g a \<noteq> 0}"
haftmann@58197
   251
  shows "Sum_any g * r = (\<Sum>n. g n * r)"
haftmann@58197
   252
proof -
haftmann@58197
   253
  note assms
haftmann@58197
   254
  moreover have "{a. g a * r \<noteq> 0} \<subseteq> {a. g a \<noteq> 0}" by auto
haftmann@58197
   255
  ultimately show ?thesis
haftmann@58197
   256
    by (simp add: setsum_left_distrib Sum_any.expand_superset [of "{a. g a \<noteq> 0}"])
haftmann@58197
   257
qed  
haftmann@58197
   258
haftmann@58197
   259
lemma Sum_any_right_distrib:
haftmann@58197
   260
  fixes r :: "'a :: semiring_0"
haftmann@58197
   261
  assumes "finite {a. g a \<noteq> 0}"
haftmann@58197
   262
  shows "r * Sum_any g = (\<Sum>n. r * g n)"
haftmann@58197
   263
proof -
haftmann@58197
   264
  note assms
haftmann@58197
   265
  moreover have "{a. r * g a \<noteq> 0} \<subseteq> {a. g a \<noteq> 0}" by auto
haftmann@58197
   266
  ultimately show ?thesis
haftmann@58197
   267
    by (simp add: setsum_right_distrib Sum_any.expand_superset [of "{a. g a \<noteq> 0}"])
haftmann@58197
   268
qed
haftmann@58197
   269
haftmann@58197
   270
lemma Sum_any_product:
haftmann@58197
   271
  fixes f g :: "'b \<Rightarrow> 'a::semiring_0"
haftmann@58197
   272
  assumes "finite {a. f a \<noteq> 0}" and "finite {b. g b \<noteq> 0}"
haftmann@58197
   273
  shows "Sum_any f * Sum_any g = (\<Sum>a. \<Sum>b. f a * g b)"
haftmann@58197
   274
proof -
haftmann@58197
   275
  have subset_f: "{a. (\<Sum>b. f a * g b) \<noteq> 0} \<subseteq> {a. f a \<noteq> 0}"
haftmann@58197
   276
    by rule (simp, rule, auto)
haftmann@58197
   277
  moreover have subset_g: "\<And>a. {b. f a * g b \<noteq> 0} \<subseteq> {b. g b \<noteq> 0}"
haftmann@58197
   278
    by rule (simp, rule, auto)
haftmann@58197
   279
  ultimately show ?thesis using assms
haftmann@58197
   280
    by (auto simp add: Sum_any.expand_set [of f] Sum_any.expand_set [of g]
haftmann@58197
   281
      Sum_any.expand_superset [of "{a. f a \<noteq> 0}"] Sum_any.expand_superset [of "{b. g b \<noteq> 0}"]
haftmann@58197
   282
      setsum_product)
haftmann@58197
   283
qed
haftmann@58197
   284
haftmann@58437
   285
lemma Sum_any_eq_zero_iff [simp]: 
haftmann@58437
   286
  fixes f :: "'a \<Rightarrow> nat"
haftmann@58437
   287
  assumes "finite {a. f a \<noteq> 0}"
haftmann@58437
   288
  shows "Sum_any f = 0 \<longleftrightarrow> f = (\<lambda>_. 0)"
haftmann@58437
   289
  using assms by (simp add: Sum_any.expand_set fun_eq_iff)
haftmann@58437
   290
haftmann@58197
   291
haftmann@58197
   292
subsection \<open>Concrete product\<close>
haftmann@58197
   293
haftmann@58197
   294
context comm_monoid_mult
haftmann@58197
   295
begin
haftmann@58197
   296
haftmann@58197
   297
definition Prod_any :: "('b \<Rightarrow> 'a) \<Rightarrow> 'a"
haftmann@58197
   298
where
haftmann@58197
   299
  "Prod_any = comm_monoid_fun.G times 1"
haftmann@58197
   300
wenzelm@61605
   301
permanent_interpretation Prod_any: comm_monoid_fun times 1
haftmann@58197
   302
where
haftmann@58197
   303
  "comm_monoid_fun.G times 1 = Prod_any" and
haftmann@58197
   304
  "comm_monoid_set.F times 1 = setprod"
haftmann@58197
   305
proof -
haftmann@58197
   306
  show "comm_monoid_fun times 1" ..
wenzelm@61605
   307
  then interpret Prod_any: comm_monoid_fun times 1 .
haftmann@58197
   308
  from Prod_any_def show "comm_monoid_fun.G times 1 = Prod_any" by rule
haftmann@58197
   309
  from setprod_def show "comm_monoid_set.F times 1 = setprod" by rule
haftmann@58197
   310
qed
haftmann@58197
   311
haftmann@58197
   312
end
haftmann@58197
   313
haftmann@58197
   314
syntax
haftmann@58197
   315
  "_Prod_any" :: "pttrn \<Rightarrow> 'a \<Rightarrow> 'a::comm_monoid_mult"    ("(3PROD _. _)" [0, 10] 10)
haftmann@58197
   316
syntax (xsymbols)
haftmann@58197
   317
  "_Prod_any" :: "pttrn \<Rightarrow> 'a \<Rightarrow> 'a::comm_monoid_mult"    ("(3\<Prod>_. _)" [0, 10] 10)
haftmann@58197
   318
translations
haftmann@58197
   319
  "\<Prod>a. b" == "CONST Prod_any (\<lambda>a. b)"
haftmann@58197
   320
haftmann@58197
   321
lemma Prod_any_zero:
haftmann@58197
   322
  fixes f :: "'b \<Rightarrow> 'a :: comm_semiring_1"
haftmann@58197
   323
  assumes "finite {a. f a \<noteq> 1}"
haftmann@58197
   324
  assumes "f a = 0"
haftmann@58197
   325
  shows "(\<Prod>a. f a) = 0"
haftmann@58197
   326
proof -
wenzelm@60500
   327
  from \<open>f a = 0\<close> have "f a \<noteq> 1" by simp
wenzelm@60500
   328
  with \<open>f a = 0\<close> have "\<exists>a. f a \<noteq> 1 \<and> f a = 0" by blast
wenzelm@60500
   329
  with \<open>finite {a. f a \<noteq> 1}\<close> show ?thesis
haftmann@58197
   330
    by (simp add: Prod_any.expand_set setprod_zero)
haftmann@58197
   331
qed
haftmann@58197
   332
haftmann@58197
   333
lemma Prod_any_not_zero:
haftmann@58197
   334
  fixes f :: "'b \<Rightarrow> 'a :: comm_semiring_1"
haftmann@58197
   335
  assumes "finite {a. f a \<noteq> 1}"
haftmann@58197
   336
  assumes "(\<Prod>a. f a) \<noteq> 0"
haftmann@58197
   337
  shows "f a \<noteq> 0"
haftmann@58197
   338
  using assms Prod_any_zero [of f] by blast
haftmann@58197
   339
haftmann@58437
   340
lemma power_Sum_any:
haftmann@58437
   341
  assumes "finite {a. f a \<noteq> 0}"
haftmann@58437
   342
  shows "c ^ (\<Sum>a. f a) = (\<Prod>a. c ^ f a)"
haftmann@58437
   343
proof -
haftmann@58437
   344
  have "{a. c ^ f a \<noteq> 1} \<subseteq> {a. f a \<noteq> 0}"
haftmann@58437
   345
    by (auto intro: ccontr)
haftmann@58437
   346
  with assms show ?thesis
haftmann@58437
   347
    by (simp add: Sum_any.expand_set Prod_any.expand_superset power_setsum)
haftmann@58437
   348
qed
haftmann@58437
   349
haftmann@58197
   350
end
haftmann@58437
   351