diff -r 3ce6fb9db485 -r 227915e07891 src/HOL/Analysis/Infinite_Sum.thy --- a/src/HOL/Analysis/Infinite_Sum.thy Mon Nov 15 17:26:31 2021 +0100 +++ b/src/HOL/Analysis/Infinite_Sum.thy Mon Nov 15 18:04:07 2021 +0100 @@ -1,8 +1,9 @@ (* Title: HOL/Analysis/Infinite_Sum.thy Author: Dominique Unruh, University of Tartu + Manuel Eberl, University of Innsbruck - A theory of sums over possible infinite sets. + A theory of sums over possibly infinite sets. *) section \Infinite sums\ @@ -23,7 +24,7 @@ theory Infinite_Sum imports - "HOL-Analysis.Elementary_Topology" + Elementary_Topology "HOL-Library.Extended_Nonnegative_Real" "HOL-Library.Complex_Order" begin @@ -107,6 +108,14 @@ shows \infsum f A = 0\ by (simp add: assms infsum_def) +lemma summable_iff_has_sum_infsum: "f summable_on A \ has_sum f A (infsum f A)" + using infsumI summable_on_def by blast + +lemma has_sum_infsum[simp]: + assumes \f summable_on S\ + shows \has_sum f S (infsum f S)\ + using assms by (auto simp: summable_on_def infsum_def has_sum_def tendsto_Lim) + lemma has_sum_cong_neutral: fixes f g :: \'a \ 'b::{comm_monoid_add, topological_space}\ assumes \\x. x\T-S \ g x = 0\ @@ -131,8 +140,7 @@ also have \sum f ((F\S) \ (F0\S)) = sum g F\ apply (rule sum.mono_neutral_cong) using that \finite F0\ F0'_def assms by auto - finally show ?thesis - by - + finally show ?thesis . qed with \F0' \ T\ \finite F0'\ show \eventually P (filtermap (sum g) (finite_subsets_at_top T))\ by (metis (no_types, lifting) eventually_filtermap eventually_finite_subsets_at_top) @@ -151,8 +159,7 @@ also have \sum g ((F\T) \ (F0\T)) = sum f F\ apply (rule sum.mono_neutral_cong) using that \finite F0\ F0'_def assms by auto - finally show ?thesis - by - + finally show ?thesis . qed with \F0' \ S\ \finite F0'\ show \eventually P (filtermap (sum f) (finite_subsets_at_top S))\ by (metis (no_types, lifting) eventually_filtermap eventually_finite_subsets_at_top) @@ -186,7 +193,7 @@ lemma has_sum_cong: assumes "\x. x\A \ f x = g x" shows "has_sum f A x \ has_sum g A x" - by (smt (verit, best) DiffE IntD2 assms has_sum_cong_neutral) + using assms by (intro has_sum_cong_neutral) auto lemma summable_on_cong: assumes "\x. x\A \ f x = g x" @@ -361,9 +368,7 @@ assumes \\x. x \ A-B \ f x \ 0\ assumes \\x. x \ B-A \ g x \ 0\ shows "infsum f A \ infsum g B" - apply (rule has_sum_mono_neutral[of f A _ g B _]) - using assms apply auto - by (metis finite_subsets_at_top_neq_bot infsum_def summable_on_def has_sum_def tendsto_Lim)+ + by (rule has_sum_mono_neutral[of f A _ g B _]) (use assms in \auto intro: has_sum_infsum\) lemma has_sum_mono: fixes f :: "'a\'b::{ordered_comm_monoid_add,linorder_topology}" @@ -407,15 +412,20 @@ by (meson assms(1) has_sum_def) hence *: "\\<^sub>F F in (finite_subsets_at_top A). dist (sum f F) x < \" using assms(2) by (rule tendstoD) - show ?thesis - by (smt (verit) * eventually_finite_subsets_at_top order_refl) + thus ?thesis + unfolding eventually_finite_subsets_at_top by fastforce qed lemma infsum_finite_approximation: fixes f :: "'a \ 'b::{comm_monoid_add,metric_space}" assumes "f summable_on A" and "\ > 0" shows "\F. finite F \ F \ A \ dist (sum f F) (infsum f A) \ \" - by (metis assms(1) assms(2) finite_subsets_at_top_neq_bot infsum_def summable_on_def has_sum_finite_approximation has_sum_def tendsto_Lim) +proof - + from assms have "has_sum f A (infsum f A)" + by (simp add: summable_iff_has_sum_infsum) + from this and \\ > 0\ show ?thesis + by (rule has_sum_finite_approximation) +qed lemma abs_summable_summable: fixes f :: \'a \ 'b :: banach\ @@ -435,7 +445,7 @@ have ev_P: \eventually P (finite_subsets_at_top A)\ using lim by (auto simp add: P_def[abs_def] \0 < d\ eventually_conj_iff eventually_finite_subsets_at_top_weakI tendsto_iff) - + moreover have \dist (sum f F1) (sum f F2) < e\ if \P F1\ and \P F2\ for F1 F2 proof - from ev_P @@ -447,29 +457,26 @@ have dist_F: \dist (sum (\x. norm (f x)) F) L < d\ by (metis F_def \F \ A\ P_def P_sup_F' \finite F\ le_supE order_refl) - from dist_F have \dist (sum (\x. norm (f x)) F) (sum (\x. norm (f x)) F2) < 2*d\ - by (smt (verit, ccfv_threshold) P_def dist_norm real_norm_def that(2)) - then have \norm (sum (\x. norm (f x)) (F-F2)) < 2*d\ - unfolding dist_norm - by (metis F_def \finite F\ sum_diff sup_commute sup_ge1) - then have \norm (sum f (F-F2)) < 2*d\ - by (smt (verit, ccfv_threshold) real_norm_def sum_norm_le) - then have dist_F_F2: \dist (sum f F) (sum f F2) < 2*d\ - by (metis F_def \finite F\ dist_norm sum_diff sup_commute sup_ge1) + have dist_F_subset: \dist (sum f F) (sum f F') < 2*d\ if F': \F' \ F\ \P F'\ for F' + proof - + have \dist (sum f F) (sum f F') = norm (sum f (F-F'))\ + unfolding dist_norm using \finite F\ F' by (subst sum_diff) auto + also have \\ \ norm (\x\F-F'. norm (f x))\ + by (rule order.trans[OF sum_norm_le[OF order.refl]]) auto + also have \\ = dist (\x\F. norm (f x)) (\x\F'. norm (f x))\ + unfolding dist_norm using \finite F\ F' by (subst sum_diff) auto + also have \\ < 2 * d\ + using dist_F F' unfolding P_def dist_norm real_norm_def by linarith + finally show \dist (sum f F) (sum f F') < 2*d\ . + qed - from dist_F have \dist (sum (\x. norm (f x)) F) (sum (\x. norm (f x)) F1) < 2*d\ - by (smt (verit, best) P_def dist_norm real_norm_def that(1)) - then have \norm (sum (\x. norm (f x)) (F-F1)) < 2*d\ - unfolding dist_norm - by (metis F_def \finite F\ inf_sup_ord(3) order_trans sum_diff sup_ge2) - then have \norm (sum f (F-F1)) < 2*d\ - by (smt (verit, ccfv_threshold) real_norm_def sum_norm_le) - then have dist_F_F1: \dist (sum f F) (sum f F1) < 2*d\ - by (metis F_def \finite F\ dist_norm inf_sup_ord(3) le_supE sum_diff) - - from dist_F_F2 dist_F_F1 show \dist (sum f F1) (sum f F2) < e\ - unfolding d_def apply auto - by (meson dist_triangle_half_r less_divide_eq_numeral1(1)) + have \dist (sum f F1) (sum f F2) \ dist (sum f F) (sum f F1) + dist (sum f F) (sum f F2)\ + by (rule dist_triangle3) + also have \\ < 2 * d + 2 * d\ + by (intro add_strict_mono dist_F_subset that) (auto simp: F_def) + also have \\ \ e\ + by (auto simp: d_def) + finally show \dist (sum f F1) (sum f F2) < e\ . qed then show ?thesis using ev_P by blast @@ -583,11 +590,6 @@ using False by auto qed -lemma has_sum_infsum[simp]: - assumes \f summable_on S\ - shows \has_sum f S (infsum f S)\ - using assms by (auto simp: summable_on_def infsum_def has_sum_def tendsto_Lim) - lemma infsum_tendsto: assumes \f summable_on S\ shows \((\F. sum f F) \ infsum f S) (finite_subsets_at_top S)\ @@ -692,8 +694,13 @@ assumes "f summable_on B" assumes disj: "A \ B = {}" shows \infsum f (A \ B) = infsum f A + infsum f B\ - by (smt (verit, ccfv_threshold) assms(1) assms(2) disj finite_subsets_at_top_neq_bot summable_on_def has_sum_Un_disjoint has_sum_def has_sum_infsum tendsto_Lim) + by (intro infsumI has_sum_Un_disjoint has_sum_infsum assms) +(* TODO move *) +lemma (in uniform_space) cauchy_filter_complete_converges: + assumes "cauchy_filter F" "complete A" "F \ principal A" "F \ bot" + shows "\c. F \ nhds c" + using assms unfolding complete_uniform by blast text \The following lemma indeed needs a complete space (as formalized by the premise \<^term>\complete UNIV\). The following two counterexamples show this: @@ -720,68 +727,71 @@ assumes \B \ A\ shows \f summable_on B\ proof - + let ?filter_fB = \filtermap (sum f) (finite_subsets_at_top B)\ from \f summable_on A\ obtain S where \(sum f \ S) (finite_subsets_at_top A)\ (is \(sum f \ S) ?filter_A\) using summable_on_def has_sum_def by blast then have cauchy_fA: \cauchy_filter (filtermap (sum f) (finite_subsets_at_top A))\ (is \cauchy_filter ?filter_fA\) by (auto intro!: nhds_imp_cauchy_filter simp: filterlim_def) - let ?filter_fB = \filtermap (sum f) (finite_subsets_at_top B)\ - have \cauchy_filter (filtermap (sum f) (finite_subsets_at_top B))\ proof (unfold cauchy_filter_def, rule filter_leI) fix E :: \('b\'b) \ bool\ assume \eventually E uniformity\ then obtain E' where \eventually E' uniformity\ and E'E'E: \E' (x, y) \ E' (y, z) \ E (x, z)\ for x y z using uniformity_trans by blast - from plus_cont[simplified uniformly_continuous_on_uniformity filterlim_def le_filter_def, rule_format, - OF \eventually E' uniformity\] obtain D where \eventually D uniformity\ and DE: \D (x, y) \ E' (x+c, y+c)\ for x y c - apply atomize_elim - by (auto simp: case_prod_beta eventually_filtermap uniformity_prod_def - eventually_prod_same uniformity_refl) - with cauchy_fA have \eventually D (?filter_fA \\<^sub>F ?filter_fA)\ + using plus_cont \eventually E' uniformity\ + unfolding uniformly_continuous_on_uniformity filterlim_def le_filter_def uniformity_prod_def + by (auto simp: case_prod_beta eventually_filtermap eventually_prod_same uniformity_refl) + have DE': "E' (x, y)" if "D (x + c, y + c)" for x y c + using DE[of "x + c" "y + c" "-c"] that by simp + + from \eventually D uniformity\ and cauchy_fA have \eventually D (?filter_fA \\<^sub>F ?filter_fA)\ unfolding cauchy_filter_def le_filter_def by simp - then obtain P1 P2 where ev_P1: \eventually (\F. P1 (sum f F)) ?filter_A\ and ev_P2: \eventually (\F. P2 (sum f F)) ?filter_A\ - and P1P2E: \P1 x \ P2 y \ D (x, y)\ for x y + then obtain P1 P2 + where ev_P1: \eventually (\F. P1 (sum f F)) ?filter_A\ + and ev_P2: \eventually (\F. P2 (sum f F)) ?filter_A\ + and P1P2E: \P1 x \ P2 y \ D (x, y)\ for x y unfolding eventually_prod_filter eventually_filtermap by auto - from ev_P1 obtain F1 where \finite F1\ and \F1 \ A\ and \\F. F\F1 \ finite F \ F\A \ P1 (sum f F)\ + from ev_P1 obtain F1 where F1: \finite F1\ \F1 \ A\ \\F. F\F1 \ finite F \ F\A \ P1 (sum f F)\ by (metis eventually_finite_subsets_at_top) - from ev_P2 obtain F2 where \finite F2\ and \F2 \ A\ and \\F. F\F2 \ finite F \ F\A \ P2 (sum f F)\ + from ev_P2 obtain F2 where F2: \finite F2\ \F2 \ A\ \\F. F\F2 \ finite F \ F\A \ P2 (sum f F)\ by (metis eventually_finite_subsets_at_top) define F0 F0A F0B where \F0 \ F1 \ F2\ and \F0A \ F0 - B\ and \F0B \ F0 \ B\ have [simp]: \finite F0\ \F0 \ A\ - apply (simp add: F0_def \finite F1\ \finite F2\) - by (simp add: F0_def \F1 \ A\ \F2 \ A\) - have [simp]: \finite F0A\ - by (simp add: F0A_def) - have \\F1 F2. F1\F0 \ F2\F0 \ finite F1 \ finite F2 \ F1\A \ F2\A \ D (sum f F1, sum f F2)\ - by (simp add: F0_def P1P2E \\F. F1 \ F \ finite F \ F \ A \ P1 (sum f F)\ \\F. F2 \ F \ finite F \ F \ A \ P2 (sum f F)\) - then have \\F1 F2. F1\F0B \ F2\F0B \ finite F1 \ finite F2 \ F1\B \ F2\B \ - D (sum f (F1 \ F0A), sum f (F2 \ F0A))\ - by (smt (verit) Diff_Diff_Int Diff_subset_conv F0A_def F0B_def \F0 \ A\ \finite F0A\ assms(4) finite_UnI sup.absorb_iff1 sup.mono sup_commute) - then have \\F1 F2. F1\F0B \ F2\F0B \ finite F1 \ finite F2 \ F1\B \ F2\B \ - D (sum f F1 + sum f F0A, sum f F2 + sum f F0A)\ - by (metis Diff_disjoint F0A_def \finite F0A\ inf.absorb_iff1 inf_assoc inf_bot_right sum.union_disjoint) - then have *: \\F1 F2. F1\F0B \ F2\F0B \ finite F1 \ finite F2 \ F1\B \ F2\B \ - E' (sum f F1, sum f F2)\ - using DE[where c=\- sum f F0A\] - apply auto by (metis add.commute add_diff_cancel_left') + using \F1 \ A\ \F2 \ A\ \finite F1\ \finite F2\ unfolding F0_def by blast+ + + have *: "E' (sum f F1', sum f F2')" + if "F1'\F0B" "F2'\F0B" "finite F1'" "finite F2'" "F1'\B" "F2'\B" for F1' F2' + proof (intro DE'[where c = "sum f F0A"] P1P2E) + have "P1 (sum f (F1' \ F0A))" + using that assms F1(1,2) F2(1,2) by (intro F1) (auto simp: F0A_def F0B_def F0_def) + thus "P1 (sum f F1' + sum f F0A)" + by (subst (asm) sum.union_disjoint) (use that in \auto simp: F0A_def\) + next + have "P2 (sum f (F2' \ F0A))" + using that assms F1(1,2) F2(1,2) by (intro F2) (auto simp: F0A_def F0B_def F0_def) + thus "P2 (sum f F2' + sum f F0A)" + by (subst (asm) sum.union_disjoint) (use that in \auto simp: F0A_def\) + qed + show \eventually E (?filter_fB \\<^sub>F ?filter_fB)\ - apply (subst eventually_prod_filter) - apply (rule exI[of _ \\x. E' (x, sum f F0B)\]) - apply (rule exI[of _ \\x. E' (sum f F0B, x)\]) - apply (auto simp: eventually_filtermap) - using * apply (metis (no_types, lifting) F0B_def Int_lower2 \finite F0\ eventually_finite_subsets_at_top finite_Int order_refl) - using * apply (metis (no_types, lifting) F0B_def Int_lower2 \finite F0\ eventually_finite_subsets_at_top finite_Int order_refl) - using E'E'E by auto + unfolding eventually_prod_filter + proof (safe intro!: exI) + show "eventually (\x. E' (x, sum f F0B)) (filtermap (sum f) (finite_subsets_at_top B))" + and "eventually (\x. E' (sum f F0B, x)) (filtermap (sum f) (finite_subsets_at_top B))" + unfolding eventually_filtermap eventually_finite_subsets_at_top + by (rule exI[of _ F0B]; use * in \force simp: F0B_def\)+ + next + show "E (x, y)" if "E' (x, sum f F0B)" and "E' (sum f F0B, y)" for x y + using E'E'E that by blast + qed qed - then obtain x where \filtermap (sum f) (finite_subsets_at_top B) \ nhds x\ - apply atomize_elim - apply (rule complete_uniform[where S=UNIV, THEN iffD1, rule_format, simplified]) - using assms by (auto simp add: filtermap_bot_iff) - + then obtain x where \?filter_fB \ nhds x\ + using cauchy_filter_complete_converges[of ?filter_fB UNIV] \complete (UNIV :: _)\ + by (auto simp: filtermap_bot_iff) then have \(sum f \ x) (finite_subsets_at_top B)\ by (auto simp: filterlim_def) then show ?thesis @@ -795,9 +805,8 @@ assumes \f summable_on A\ assumes \B \ A\ shows \f summable_on B\ - apply (rule summable_on_subset) - using assms apply auto - by (metis Cauchy_convergent UNIV_I complete_def convergent_def) + by (rule summable_on_subset[OF _ _ assms]) + (auto simp: complete_def convergent_def dest!: Cauchy_convergent) lemma has_sum_empty[simp]: \has_sum f {} 0\ by (meson ex_in_conv has_sum_0) @@ -847,9 +856,8 @@ assumes conv: \\a. a \ A \ f summable_on (B a)\ assumes disj: \\a a'. a\A \ a'\A \ a\a' \ B a \ B a' = {}\ shows \sum (\a. infsum f (B a)) A = infsum f (\a\A. B a)\ - using sum_has_sum[of A f B \\a. infsum f (B a)\] - using assms apply auto - by (metis finite_subsets_at_top_neq_bot infsum_def summable_on_def has_sum_def tendsto_Lim) + by (rule sym, rule infsumI) + (use sum_has_sum[of A f B \\a. infsum f (B a)\] assms in auto) text \The lemmas \infsum_comm_additive_general\ and \infsum_comm_additive\ (and variants) below both state that the infinite sum commutes with a continuous additive function. \infsum_comm_additive_general\ is stated more for more general type classes @@ -897,7 +905,8 @@ assumes \isCont f (infsum g S)\ assumes \g summable_on S\ shows \infsum (f o g) S = f (infsum g S)\ - by (smt (verit) assms(2) assms(3) continuous_within f_sum finite_subsets_at_top_neq_bot summable_on_comm_additive_general has_sum_comm_additive_general has_sum_def has_sum_infsum tendsto_Lim) + using assms + by (intro infsumI has_sum_comm_additive_general has_sum_infsum) (auto simp: isCont_def) lemma has_sum_comm_additive: fixes f :: \'b :: {ab_group_add,topological_space} \ 'c :: {ab_group_add,topological_space}\ @@ -906,7 +915,8 @@ \ \For \<^class>\t2_space\, this is equivalent to \isCont f x\ by @{thm [source] isCont_def}.\ assumes infsum: \has_sum g S x\ shows \has_sum (f o g) S (f x)\ - by (smt (verit, best) additive.sum assms(1) assms(2) comp_eq_dest_lhs continuous_within finite_subsets_at_top_neq_bot infsum summable_on_def has_sum_comm_additive_general has_sum_def has_sum_infsum sum.cong tendsto_Lim) + using assms + by (intro has_sum_comm_additive_general has_sum_infsum) (auto simp: isCont_def additive.sum) lemma summable_on_comm_additive: fixes f :: \'b :: {ab_group_add,t2_space} \ 'c :: {ab_group_add,topological_space}\ @@ -924,8 +934,7 @@ shows \infsum (f o g) S = f (infsum g S)\ by (rule infsum_comm_additive_general; auto simp: assms additive.sum) - -lemma pos_has_sum: +lemma nonneg_bdd_above_has_sum: fixes f :: \'a \ 'b :: {conditionally_complete_linorder, ordered_comm_monoid_add, linorder_topology}\ assumes \\x. x\A \ f x \ 0\ assumes \bdd_above (sum f ` {F. F\A \ finite F})\ @@ -938,14 +947,24 @@ by (metis (mono_tags, lifting) Collect_cong Collect_empty_eq assms(2) empty_subsetI finite.emptyI less_cSUP_iff mem_Collect_eq) show \\\<^sub>F x in finite_subsets_at_top A. a < sum f x\ unfolding eventually_finite_subsets_at_top - apply (rule exI[of _ F]) - using \a < sum f F\ and \finite F\ and \F \ A\ - apply auto - by (smt (verit, best) Diff_iff assms(1) less_le_trans subset_iff sum_mono2) + proof (rule exI[of _ F], safe) + fix Y assume Y: "finite Y" "F \ Y" "Y \ A" + have "a < sum f F" + by fact + also have "\ \ sum f Y" + using assms Y by (intro sum_mono2) auto + finally show "a < sum f Y" . + qed (use \finite F\ \F \ A\ in auto) next - fix a assume \(SUP F\{F. finite F \ F\A}. sum f F) < a\ - then have \sum f F < a\ if \F\A\ and \finite F\ for F - by (smt (verit, best) Collect_cong antisym_conv assms(2) cSUP_upper dual_order.trans le_less_linear less_le mem_Collect_eq that(1) that(2)) + fix a assume *: \(SUP F\{F. finite F \ F\A}. sum f F) < a\ + have \sum f F < a\ if \F\A\ and \finite F\ for F + proof - + have "sum f F \ (SUP F\{F. finite F \ F\A}. sum f F)" + by (rule cSUP_upper) (use that assms(2) in \auto simp: conj_commute\) + also have "\ < a" + by fact + finally show ?thesis . + qed then show \\\<^sub>F x in finite_subsets_at_top A. sum f x < a\ by (rule eventually_finite_subsets_at_top_weakI) qed @@ -953,38 +972,37 @@ using has_sum_def by blast qed -lemma pos_summable_on: +lemma nonneg_bdd_above_summable_on: fixes f :: \'a \ 'b :: {conditionally_complete_linorder, ordered_comm_monoid_add, linorder_topology}\ assumes \\x. x\A \ f x \ 0\ assumes \bdd_above (sum f ` {F. F\A \ finite F})\ shows \f summable_on A\ - using assms(1) assms(2) summable_on_def pos_has_sum by blast + using assms(1) assms(2) summable_on_def nonneg_bdd_above_has_sum by blast - -lemma pos_infsum: +lemma nonneg_bdd_above_infsum: fixes f :: \'a \ 'b :: {conditionally_complete_linorder, ordered_comm_monoid_add, linorder_topology}\ assumes \\x. x\A \ f x \ 0\ assumes \bdd_above (sum f ` {F. F\A \ finite F})\ shows \infsum f A = (SUP F\{F. finite F \ F\A}. sum f F)\ - using assms by (auto intro!: infsumI pos_has_sum) + using assms by (auto intro!: infsumI nonneg_bdd_above_has_sum) -lemma pos_has_sum_complete: +lemma nonneg_has_sum_complete: fixes f :: \'a \ 'b :: {complete_linorder, ordered_comm_monoid_add, linorder_topology}\ assumes \\x. x\A \ f x \ 0\ shows \has_sum f A (SUP F\{F. finite F \ F\A}. sum f F)\ - using assms pos_has_sum by blast + using assms nonneg_bdd_above_has_sum by blast -lemma pos_summable_on_complete: +lemma nonneg_summable_on_complete: fixes f :: \'a \ 'b :: {complete_linorder, ordered_comm_monoid_add, linorder_topology}\ assumes \\x. x\A \ f x \ 0\ shows \f summable_on A\ - using assms pos_summable_on by blast + using assms nonneg_bdd_above_summable_on by blast -lemma pos_infsum_complete: +lemma nonneg_infsum_complete: fixes f :: \'a \ 'b :: {complete_linorder, ordered_comm_monoid_add, linorder_topology}\ assumes \\x. x\A \ f x \ 0\ shows \infsum f A = (SUP F\{F. finite F \ F\A}. sum f F)\ - using assms pos_infsum by blast + using assms nonneg_bdd_above_infsum by blast lemma has_sum_nonneg: fixes f :: "'a \ 'b::{ordered_comm_monoid_add,linorder_topology}" @@ -995,10 +1013,51 @@ lemma infsum_nonneg: fixes f :: "'a \ 'b::{ordered_comm_monoid_add,linorder_topology}" - assumes "f summable_on M" - and "\x. x \ M \ 0 \ f x" + assumes "\x. x \ M \ 0 \ f x" shows "infsum f M \ 0" (is "?lhs \ _") - by (metis assms infsum_0_simp summable_on_0_simp infsum_mono) + apply (cases \f summable_on M\) + apply (metis assms infsum_0_simp summable_on_0_simp infsum_mono) + using assms by (auto simp add: infsum_not_exists) + +lemma has_sum_mono2: + fixes f :: "'a \ 'b::{topological_ab_group_add, ordered_comm_monoid_add,linorder_topology}" + assumes "has_sum f A S" "has_sum f B S'" "A \ B" + assumes "\x. x \ B - A \ f x \ 0" + shows "S \ S'" +proof - + have "has_sum f (B - A) (S' - S)" + by (rule has_sum_Diff) fact+ + hence "S' - S \ 0" + by (rule has_sum_nonneg) (use assms(4) in auto) + thus ?thesis + by (metis add_0 add_mono_thms_linordered_semiring(3) diff_add_cancel) +qed + +lemma infsum_mono2: + fixes f :: "'a \ 'b::{topological_ab_group_add, ordered_comm_monoid_add,linorder_topology}" + assumes "f summable_on A" "f summable_on B" "A \ B" + assumes "\x. x \ B - A \ f x \ 0" + shows "infsum f A \ infsum f B" + by (rule has_sum_mono2[OF has_sum_infsum has_sum_infsum]) (use assms in auto) + +lemma finite_sum_le_has_sum: + fixes f :: "'a \ 'b::{topological_ab_group_add, ordered_comm_monoid_add,linorder_topology}" + assumes "has_sum f A S" "finite B" "B \ A" + assumes "\x. x \ A - B \ f x \ 0" + shows "sum f B \ S" +proof (rule has_sum_mono2) + show "has_sum f A S" + by fact + show "has_sum f B (sum f B)" + by (rule has_sum_finite) fact+ +qed (use assms in auto) + +lemma finite_sum_le_infsum: + fixes f :: "'a \ 'b::{topological_ab_group_add, ordered_comm_monoid_add,linorder_topology}" + assumes "f summable_on A" "finite B" "B \ A" + assumes "\x. x \ A - B \ f x \ 0" + shows "sum f B \ infsum f A" + by (rule finite_sum_le_has_sum[OF has_sum_infsum]) (use assms in auto) lemma has_sum_reindex: assumes \inj_on h A\ @@ -1016,11 +1075,9 @@ using assms subset_inj_on by blast also have \\ \ has_sum (g \ h) A x\ by (simp add: has_sum_def) - finally show ?thesis - by - + finally show ?thesis . qed - lemma summable_on_reindex: assumes \inj_on h A\ shows \g summable_on (h ` A) \ (g \ h) summable_on A\ @@ -1029,8 +1086,32 @@ lemma infsum_reindex: assumes \inj_on h A\ shows \infsum g (h ` A) = infsum (g \ h) A\ - by (metis (no_types, opaque_lifting) assms finite_subsets_at_top_neq_bot infsum_def summable_on_reindex has_sum_def has_sum_infsum has_sum_reindex tendsto_Lim) + by (metis (no_types, opaque_lifting) assms finite_subsets_at_top_neq_bot infsum_def + summable_on_reindex has_sum_def has_sum_infsum has_sum_reindex tendsto_Lim) +lemma summable_on_reindex_bij_betw: + assumes "bij_betw g A B" + shows "(\x. f (g x)) summable_on A \ f summable_on B" +proof - + thm summable_on_reindex + have \(\x. f (g x)) summable_on A \ f summable_on g ` A\ + apply (rule summable_on_reindex[symmetric, unfolded o_def]) + using assms bij_betw_imp_inj_on by blast + also have \\ \ f summable_on B\ + using assms bij_betw_imp_surj_on by blast + finally show ?thesis . +qed + +lemma infsum_reindex_bij_betw: + assumes "bij_betw g A B" + shows "infsum (\x. f (g x)) A = infsum f B" +proof - + have \infsum (\x. f (g x)) A = infsum f (g ` A)\ + by (metis (mono_tags, lifting) assms bij_betw_imp_inj_on infsum_cong infsum_reindex o_def) + also have \\ = infsum f B\ + using assms bij_betw_imp_surj_on by blast + finally show ?thesis . +qed lemma sum_uniformity: assumes plus_cont: \uniformly_continuous_on UNIV (\(x::'b::{uniform_space,comm_monoid_add},y). x+y)\ @@ -1152,7 +1233,7 @@ from sum_b[unfolded tendsto_iff_uniformity, rule_format, OF _ D'_uni[THEN uniformity_sym]] obtain Ha0 where \finite (Ha0 a)\ and \Ha0 a \ B a\ and \Ha0 a \ L \ L \ B a \ finite L \ D' (b a, sum (\b. f (a,b)) L)\ if \a \ A\ for a L - unfolding FB_def eventually_finite_subsets_at_top apply auto by metis + unfolding FB_def eventually_finite_subsets_at_top unfolding prod.case by metis moreover define Ha where \Ha a = Ha0 a \ Ga a\ for a ultimately show ?thesis using that[where Ha=Ha] @@ -1180,19 +1261,23 @@ moreover have \Sigma M Ha \ Sigma M B\ using Ha_B \M \ A\ by auto ultimately show ?thesis - apply (simp add: FMB_def eventually_finite_subsets_at_top) - by (metis Ha_fin finite_SigmaI subsetD that(2) that(3)) + unfolding FMB_def eventually_finite_subsets_at_top + by (intro exI[of _ "Sigma M Ha"]) + (use Ha_fin that(2,3) in \fastforce intro!: finite_SigmaI\) qed moreover have \eventually (\H. D (\(a,b)\H. f (a,b), a)) FMB\ unfolding FMB_def eventually_finite_subsets_at_top - apply (rule exI[of _ G]) - using \G \ Sigma A B\ \finite G\ that G_sum apply auto - by (meson Sigma_mono dual_order.refl order_trans) + proof (rule exI[of _ G], safe) + fix Y assume Y: "finite Y" "G \ Y" "Y \ Sigma M B" + have "Y \ Sigma A B" + using Y \M \ A\ by blast + thus "D (\(a,b)\Y. f (a, b), a)" + using G_sum[of Y] Y by auto + qed (use \finite G\ \G \ Sigma A B\ that in auto) ultimately have \\\<^sub>F x in FMB. E (sum b M, a)\ - by (smt (verit, best) DDE' eventually_elim2) + by eventually_elim (use DDE' in auto) then show \E (sum b M, a)\ - apply (rule eventually_const[THEN iffD1, rotated]) - using FMB_def by force + by (rule eventually_const[THEN iffD1, rotated]) (force simp: FMB_def) qed then show \\\<^sub>F x in FA. E (sum b x, a)\ using \finite (fst ` G)\ and \fst ` G \ A\ @@ -1277,7 +1362,8 @@ and f :: \'a \ 'b \ 'c::banach\ assumes [simp]: "f summable_on (Sigma A B)" shows \infsum (\x. infsum (\y. f (x,y)) (B x)) A = infsum f (Sigma A B)\ - by (smt (verit, best) SigmaE assms infsum_Sigma'_banach infsum_cong summable_on_cong old.prod.case) + using assms + by (subst infsum_Sigma'_banach) auto lemma infsum_swap: fixes A :: "'a set" and B :: "'b set" @@ -1302,8 +1388,7 @@ also have \\ = infsum (\y. infsum (\x. f x y) A) B\ apply (subst infsum_Sigma) using assms by auto - finally show ?thesis - by - + finally show ?thesis . qed lemma infsum_swap_banach: @@ -1326,11 +1411,10 @@ also have \\ = infsum (\y. infsum (\x. f x y) A) B\ apply (subst infsum_Sigma'_banach) using assms by auto - finally show ?thesis - by - + finally show ?thesis . qed -lemma infsum_0D: +lemma nonneg_infsum_le_0D: fixes f :: "'a \ 'b::{topological_ab_group_add,ordered_ab_group_add,linorder_topology}" assumes "infsum f A \ 0" and abs_sum: "f summable_on A" @@ -1340,34 +1424,31 @@ proof (rule ccontr) assume \f x \ 0\ have ex: \f summable_on (A-{x})\ - apply (rule summable_on_cofin_subset) - using assms by auto - then have pos: \infsum f (A - {x}) \ 0\ - apply (rule infsum_nonneg) - using nneg by auto + by (rule summable_on_cofin_subset) (use assms in auto) + have pos: \infsum f (A - {x}) \ 0\ + by (rule infsum_nonneg) (use nneg in auto) have [trans]: \x \ y \ y > z \ x > z\ for x y z :: 'b by auto have \infsum f A = infsum f (A-{x}) + infsum f {x}\ - apply (subst infsum_Un_disjoint[symmetric]) - using assms ex apply auto by (metis insert_absorb) + by (subst infsum_Un_disjoint[symmetric]) (use assms ex in \auto simp: insert_absorb\) also have \\ \ infsum f {x}\ (is \_ \ \\) - using pos apply (rule add_increasing) by simp + using pos by (rule add_increasing) simp also have \\ = f x\ (is \_ = \\) - apply (subst infsum_finite) by auto + by (subst infsum_finite) auto also have \\ > 0\ using \f x \ 0\ assms(4) nneg by fastforce finally show False using assms by auto qed -lemma has_sum_0D: +lemma nonneg_has_sum_le_0D: fixes f :: "'a \ 'b::{topological_ab_group_add,ordered_ab_group_add,linorder_topology}" assumes "has_sum f A a" \a \ 0\ and nneg: "\x. x \ A \ f x \ 0" and "x \ A" shows "f x = 0" - by (metis assms(1) assms(2) assms(4) infsumI infsum_0D summable_on_def nneg) + by (metis assms(1) assms(2) assms(4) infsumI nonneg_infsum_le_0D summable_on_def nneg) lemma has_sum_cmult_left: fixes f :: "'a \ 'b :: {topological_semigroup_mult, semiring_0}" @@ -1563,8 +1644,7 @@ also have \\ \ infsum (\_. 1::'a) A\ apply (rule infsum_mono_neutral) using \finite F\ \F \ A\ by auto - finally show ?thesis - by - + finally show ?thesis . qed then show False by (meson linordered_field_no_ub not_less) @@ -1596,13 +1676,548 @@ shows \infsum (\x. - f x) A = - infsum f A\ by (metis (full_types) add.inverse_inverse add.inverse_neutral infsumI infsum_def has_sum_infsum has_sum_uminus) +lemma has_sum_le_finite_sums: + fixes a :: \'a::{comm_monoid_add,topological_space,linorder_topology}\ + assumes \has_sum f A a\ + assumes \\F. finite F \ F \ A \ sum f F \ b\ + shows \a \ b\ +proof - + from assms(1) + have 1: \(sum f \ a) (finite_subsets_at_top A)\ + unfolding has_sum_def . + from assms(2) + have 2: \\\<^sub>F F in finite_subsets_at_top A. sum f F \ b\ + by (rule_tac eventually_finite_subsets_at_top_weakI) + show \a \ b\ + using _ _ 1 2 + apply (rule tendsto_le[where f=\\_. b\]) + by auto +qed + +lemma infsum_le_finite_sums: + fixes b :: \'a::{comm_monoid_add,topological_space,linorder_topology}\ + assumes \f summable_on A\ + assumes \\F. finite F \ F \ A \ sum f F \ b\ + shows \infsum f A \ b\ + by (meson assms(1) assms(2) has_sum_infsum has_sum_le_finite_sums) + + +lemma summable_on_scaleR_left [intro]: + fixes c :: \'a :: real_normed_vector\ + assumes "c \ 0 \ f summable_on A" + shows "(\x. f x *\<^sub>R c) summable_on A" + apply (cases \c \ 0\) + apply (subst asm_rl[of \(\x. f x *\<^sub>R c) = (\y. y *\<^sub>R c) o f\], simp add: o_def) + apply (rule summable_on_comm_additive) + using assms by (auto simp add: scaleR_left.additive_axioms) + + +lemma summable_on_scaleR_right [intro]: + fixes f :: \'a \ 'b :: real_normed_vector\ + assumes "c \ 0 \ f summable_on A" + shows "(\x. c *\<^sub>R f x) summable_on A" + apply (cases \c \ 0\) + apply (subst asm_rl[of \(\x. c *\<^sub>R f x) = (\y. c *\<^sub>R y) o f\], simp add: o_def) + apply (rule summable_on_comm_additive) + using assms by (auto simp add: scaleR_right.additive_axioms) + +lemma infsum_scaleR_left: + fixes c :: \'a :: real_normed_vector\ + assumes "c \ 0 \ f summable_on A" + shows "infsum (\x. f x *\<^sub>R c) A = infsum f A *\<^sub>R c" + apply (cases \c \ 0\) + apply (subst asm_rl[of \(\x. f x *\<^sub>R c) = (\y. y *\<^sub>R c) o f\], simp add: o_def) + apply (rule infsum_comm_additive) + using assms by (auto simp add: scaleR_left.additive_axioms) + +lemma infsum_scaleR_right: + fixes f :: \'a \ 'b :: real_normed_vector\ + shows "infsum (\x. c *\<^sub>R f x) A = c *\<^sub>R infsum f A" +proof - + consider (summable) \f summable_on A\ | (c0) \c = 0\ | (not_summable) \\ f summable_on A\ \c \ 0\ + by auto + then show ?thesis + proof cases + case summable + then show ?thesis + apply (subst asm_rl[of \(\x. c *\<^sub>R f x) = (\y. c *\<^sub>R y) o f\], simp add: o_def) + apply (rule infsum_comm_additive) + using summable by (auto simp add: scaleR_right.additive_axioms) + next + case c0 + then show ?thesis by auto + next + case not_summable + have \\ (\x. c *\<^sub>R f x) summable_on A\ + proof (rule notI) + assume \(\x. c *\<^sub>R f x) summable_on A\ + then have \(\x. inverse c *\<^sub>R c *\<^sub>R f x) summable_on A\ + using summable_on_scaleR_right by blast + then have \f summable_on A\ + using not_summable by auto + with not_summable show False + by simp + qed + then show ?thesis + by (simp add: infsum_not_exists not_summable(1)) + qed +qed + + +lemma infsum_Un_Int: + fixes f :: "'a \ 'b::{topological_ab_group_add, t2_space}" + assumes [simp]: "f summable_on A - B" "f summable_on B - A" \f summable_on A \ B\ + shows "infsum f (A \ B) = infsum f A + infsum f B - infsum f (A \ B)" +proof - + have [simp]: \f summable_on A\ + apply (subst asm_rl[of \A = (A-B) \ (A\B)\]) apply auto[1] + apply (rule summable_on_Un_disjoint) + by auto + have \infsum f (A \ B) = infsum f A + infsum f (B - A)\ + apply (subst infsum_Un_disjoint[symmetric]) + by auto + moreover have \infsum f (B - A \ A \ B) = infsum f (B - A) + infsum f (A \ B)\ + by (rule infsum_Un_disjoint) auto + moreover have "B - A \ A \ B = B" + by blast + ultimately show ?thesis + by auto +qed + +lemma inj_combinator': + assumes "x \ F" + shows \inj_on (\(g, y). g(x := y)) (Pi\<^sub>E F B \ B x)\ +proof - + have "inj_on ((\(y, g). g(x := y)) \ prod.swap) (Pi\<^sub>E F B \ B x)" + using inj_combinator[of x F B] assms by (intro comp_inj_on) (auto simp: product_swap) + thus ?thesis + by (simp add: o_def) +qed + +lemma infsum_prod_PiE: + \ \See also \infsum_prod_PiE_abs\ below with incomparable premises.\ + fixes f :: "'a \ 'b \ 'c :: {comm_monoid_mult, topological_semigroup_mult, division_ring, banach}" + assumes finite: "finite A" + assumes "\x. x \ A \ f x summable_on B x" + assumes "(\g. \x\A. f x (g x)) summable_on (PiE A B)" + shows "infsum (\g. \x\A. f x (g x)) (PiE A B) = (\x\A. infsum (f x) (B x))" +proof (use finite assms(2-) in induction) + case empty + then show ?case + by auto +next + case (insert x F) + have pi: \Pi\<^sub>E (insert x F) B = (\(g,y). g(x:=y)) ` (Pi\<^sub>E F B \ B x)\ + unfolding PiE_insert_eq + by (subst swap_product [symmetric]) (simp add: image_image case_prod_unfold) + have prod: \(\x'\F. f x' ((p(x:=y)) x')) = (\x'\F. f x' (p x'))\ for p y + by (rule prod.cong) (use insert.hyps in auto) + have inj: \inj_on (\(g, y). g(x := y)) (Pi\<^sub>E F B \ B x)\ + using \x \ F\ by (rule inj_combinator') + + have summable1: \(\g. \x\insert x F. f x (g x)) summable_on Pi\<^sub>E (insert x F) B\ + using insert.prems(2) . + also have \Pi\<^sub>E (insert x F) B = (\(g,y). g(x:=y)) ` (Pi\<^sub>E F B \ B x)\ + by (simp only: pi) + also have "(\g. \x\insert x F. f x (g x)) summable_on \ \ + ((\g. \x\insert x F. f x (g x)) \ (\(g,y). g(x:=y))) summable_on (Pi\<^sub>E F B \ B x)" + using inj by (rule summable_on_reindex) + also have "(\z\F. f z ((g(x := y)) z)) = (\z\F. f z (g z))" for g y + using insert.hyps by (intro prod.cong) auto + hence "((\g. \x\insert x F. f x (g x)) \ (\(g,y). g(x:=y))) = + (\(p, y). f x y * (\x'\F. f x' (p x')))" + using insert.hyps by (auto simp: fun_eq_iff cong: prod.cong_simp) + finally have summable2: \(\(p, y). f x y * (\x'\F. f x' (p x'))) summable_on Pi\<^sub>E F B \ B x\ . + + then have \(\p. \\<^sub>\y\B x. f x y * (\x'\F. f x' (p x'))) summable_on Pi\<^sub>E F B\ + by (rule summable_on_Sigma_banach) + then have \(\p. (\\<^sub>\y\B x. f x y) * (\x'\F. f x' (p x'))) summable_on Pi\<^sub>E F B\ + apply (subst infsum_cmult_left[symmetric]) + using insert.prems(1) by blast + then have summable3: \(\p. (\x'\F. f x' (p x'))) summable_on Pi\<^sub>E F B\ if \(\\<^sub>\y\B x. f x y) \ 0\ + apply (subst (asm) summable_on_cmult_right') + using that by auto + + have \(\\<^sub>\g\Pi\<^sub>E (insert x F) B. \x\insert x F. f x (g x)) + = (\\<^sub>\(p,y)\Pi\<^sub>E F B \ B x. \x'\insert x F. f x' ((p(x:=y)) x'))\ + apply (subst pi) + apply (subst infsum_reindex) + using inj by (auto simp: o_def case_prod_unfold) + also have \\ = (\\<^sub>\(p, y)\Pi\<^sub>E F B \ B x. f x y * (\x'\F. f x' ((p(x:=y)) x')))\ + apply (subst prod.insert) + using insert by auto + also have \\ = (\\<^sub>\(p, y)\Pi\<^sub>E F B \ B x. f x y * (\x'\F. f x' (p x')))\ + apply (subst prod) by rule + also have \\ = (\\<^sub>\p\Pi\<^sub>E F B. \\<^sub>\y\B x. f x y * (\x'\F. f x' (p x')))\ + apply (subst infsum_Sigma_banach[symmetric]) + using summable2 apply blast + by fastforce + also have \\ = (\\<^sub>\y\B x. f x y) * (\\<^sub>\p\Pi\<^sub>E F B. \x'\F. f x' (p x'))\ + apply (subst infsum_cmult_left') + apply (subst infsum_cmult_right') + by (rule refl) + also have \\ = (\x\insert x F. infsum (f x) (B x))\ + apply (subst prod.insert) + using \finite F\ \x \ F\ apply auto[2] + apply (cases \infsum (f x) (B x) = 0\) + apply simp + apply (subst insert.IH) + apply (simp add: insert.prems(1)) + apply (rule summable3) + by auto + finally show ?case + by simp +qed + +lemma infsum_prod_PiE_abs: + \ \See also @{thm [source] infsum_prod_PiE} above with incomparable premises.\ + fixes f :: "'a \ 'b \ 'c :: {banach, real_normed_div_algebra, comm_semiring_1}" + assumes finite: "finite A" + assumes "\x. x \ A \ f x abs_summable_on B x" + shows "infsum (\g. \x\A. f x (g x)) (PiE A B) = (\x\A. infsum (f x) (B x))" +proof (use finite assms(2) in induction) + case empty + then show ?case + by auto +next + case (insert x F) + + have pi: \Pi\<^sub>E (insert x F) B = (\(g,y). g(x:=y)) ` (Pi\<^sub>E F B \ B x)\ for x F and B :: "'a \ 'b set" + unfolding PiE_insert_eq + by (subst swap_product [symmetric]) (simp add: image_image case_prod_unfold) + have prod: \(\x'\F. f x' ((p(x:=y)) x')) = (\x'\F. f x' (p x'))\ for p y + by (rule prod.cong) (use insert.hyps in auto) + have inj: \inj_on (\(g, y). g(x := y)) (Pi\<^sub>E F B \ B x)\ + using \x \ F\ by (rule inj_combinator') + + define s where \s x = infsum (\y. norm (f x y)) (B x)\ for x + + have *: \(\p\P. norm (\x\F. f x (p x))) \ prod s F\ + if P: \P \ Pi\<^sub>E F B\ and [simp]: \finite P\ \finite F\ + and sum: \\x. x \ F \ f x abs_summable_on B x\ for P F + proof - + define B' where \B' x = {p x| p. p\P}\ for x + have [simp]: \finite (B' x)\ for x + using that by (auto simp: B'_def) + have [simp]: \finite (Pi\<^sub>E F B')\ + by (simp add: finite_PiE) + have [simp]: \P \ Pi\<^sub>E F B'\ + using that by (auto simp: B'_def) + have B'B: \B' x \ B x\ if \x \ F\ for x + unfolding B'_def using P that + by auto + have s_bound: \(\y\B' x. norm (f x y)) \ s x\ if \x \ F\ for x + apply (simp_all add: s_def flip: infsum_finite) + apply (rule infsum_mono_neutral) + using that sum B'B by auto + have \(\p\P. norm (\x\F. f x (p x))) \ (\p\Pi\<^sub>E F B'. norm (\x\F. f x (p x)))\ + apply (rule sum_mono2) + by auto + also have \\ = (\p\Pi\<^sub>E F B'. \x\F. norm (f x (p x)))\ + apply (subst prod_norm[symmetric]) + by simp + also have \\ = (\x\F. \y\B' x. norm (f x y))\ + proof (use \finite F\ in induction) + case empty + then show ?case by simp + next + case (insert x F) + have aux: \a = b \ c * a = c * b\ for a b c :: real + by auto + have inj: \inj_on (\(g, y). g(x := y)) (Pi\<^sub>E F B' \ B' x)\ + by (rule inj_combinator') (use insert.hyps in auto) + have \(\p\Pi\<^sub>E (insert x F) B'. \x\insert x F. norm (f x (p x))) + = (\(p,y)\Pi\<^sub>E F B' \ B' x. \x'\insert x F. norm (f x' ((p(x := y)) x')))\ + apply (subst pi) + apply (subst sum.reindex) + using inj by (auto simp: case_prod_unfold) + also have \\ = (\(p,y)\Pi\<^sub>E F B' \ B' x. norm (f x y) * (\x'\F. norm (f x' ((p(x := y)) x'))))\ + apply (subst prod.insert) + using insert.hyps by (auto simp: case_prod_unfold) + also have \\ = (\(p, y)\Pi\<^sub>E F B' \ B' x. norm (f x y) * (\x'\F. norm (f x' (p x'))))\ + apply (rule sum.cong) + apply blast + unfolding case_prod_unfold + apply (rule aux) + apply (rule prod.cong) + using insert.hyps(2) by auto + also have \\ = (\y\B' x. norm (f x y)) * (\p\Pi\<^sub>E F B'. \x'\F. norm (f x' (p x')))\ + apply (subst sum_product) + apply (subst sum.swap) + apply (subst sum.cartesian_product) + by simp + also have \\ = (\y\B' x. norm (f x y)) * (\x\F. \y\B' x. norm (f x y))\ + by (simp add: insert.IH) + also have \\ = (\x\insert x F. \y\B' x. norm (f x y))\ + using insert.hyps(1) insert.hyps(2) by force + finally show ?case . + qed + also have \\ = (\x\F. \\<^sub>\y\B' x. norm (f x y))\ + by auto + also have \\ \ (\x\F. s x)\ + apply (rule prod_mono) + apply auto + apply (simp add: sum_nonneg) + using s_bound by presburger + finally show ?thesis . + qed + have \(\g. \x\insert x F. f x (g x)) abs_summable_on Pi\<^sub>E (insert x F) B\ + apply (rule nonneg_bdd_above_summable_on) + apply (simp; fail) + apply (rule bdd_aboveI[where M=\\x'\insert x F. s x'\]) + using * insert.hyps insert.prems by blast + + also have \Pi\<^sub>E (insert x F) B = (\(g,y). g(x:=y)) ` (Pi\<^sub>E F B \ B x)\ + by (simp only: pi) + also have "(\g. \x\insert x F. f x (g x)) abs_summable_on \ \ + ((\g. \x\insert x F. f x (g x)) \ (\(g,y). g(x:=y))) abs_summable_on (Pi\<^sub>E F B \ B x)" + using inj by (subst summable_on_reindex) (auto simp: o_def) + also have "(\z\F. f z ((g(x := y)) z)) = (\z\F. f z (g z))" for g y + using insert.hyps by (intro prod.cong) auto + hence "((\g. \x\insert x F. f x (g x)) \ (\(g,y). g(x:=y))) = + (\(p, y). f x y * (\x'\F. f x' (p x')))" + using insert.hyps by (auto simp: fun_eq_iff cong: prod.cong_simp) + finally have summable2: \(\(p, y). f x y * (\x'\F. f x' (p x'))) abs_summable_on Pi\<^sub>E F B \ B x\ . + + have \(\\<^sub>\g\Pi\<^sub>E (insert x F) B. \x\insert x F. f x (g x)) + = (\\<^sub>\(p,y)\Pi\<^sub>E F B \ B x. \x'\insert x F. f x' ((p(x:=y)) x'))\ + apply (subst pi) + apply (subst infsum_reindex) + using inj by (auto simp: o_def case_prod_unfold) + also have \\ = (\\<^sub>\(p, y)\Pi\<^sub>E F B \ B x. f x y * (\x'\F. f x' ((p(x:=y)) x')))\ + apply (subst prod.insert) + using insert by auto + also have \\ = (\\<^sub>\(p, y)\Pi\<^sub>E F B \ B x. f x y * (\x'\F. f x' (p x')))\ + apply (subst prod) by rule + also have \\ = (\\<^sub>\p\Pi\<^sub>E F B. \\<^sub>\y\B x. f x y * (\x'\F. f x' (p x')))\ + apply (subst infsum_Sigma_banach[symmetric]) + using summable2 abs_summable_summable apply blast + by fastforce + also have \\ = (\\<^sub>\y\B x. f x y) * (\\<^sub>\p\Pi\<^sub>E F B. \x'\F. f x' (p x'))\ + apply (subst infsum_cmult_left') + apply (subst infsum_cmult_right') + by (rule refl) + also have \\ = (\x\insert x F. infsum (f x) (B x))\ + apply (subst prod.insert) + using \finite F\ \x \ F\ apply auto[2] + apply (cases \infsum (f x) (B x) = 0\) + apply (simp; fail) + apply (subst insert.IH) + apply (auto simp add: insert.prems(1)) + done + finally show ?case + by simp +qed + + + +subsection \Absolute convergence\ + +lemma abs_summable_countable: + assumes \f abs_summable_on A\ + shows \countable {x\A. f x \ 0}\ +proof - + have fin: \finite {x\A. norm (f x) \ t}\ if \t > 0\ for t + proof (rule ccontr) + assume *: \infinite {x \ A. t \ norm (f x)}\ + have \infsum (\x. norm (f x)) A \ b\ for b + proof - + obtain b' where b': \of_nat b' \ b / t\ + by (meson real_arch_simple) + from * + obtain F where cardF: \card F \ b'\ and \finite F\ and F: \F \ {x \ A. t \ norm (f x)}\ + by (meson finite_if_finite_subsets_card_bdd nle_le) + have \b \ of_nat b' * t\ + using b' \t > 0\ by (simp add: field_simps split: if_splits) + also have \\ \ of_nat (card F) * t\ + by (simp add: cardF that) + also have \\ = sum (\x. t) F\ + by simp + also have \\ \ sum (\x. norm (f x)) F\ + by (metis (mono_tags, lifting) F in_mono mem_Collect_eq sum_mono) + also have \\ = infsum (\x. norm (f x)) F\ + using \finite F\ by (rule infsum_finite[symmetric]) + also have \\ \ infsum (\x. norm (f x)) A\ + by (rule infsum_mono_neutral) (use \finite F\ assms F in auto) + finally show ?thesis . + qed + then show False + by (meson gt_ex linorder_not_less) + qed + have \countable (\i\{1..}. {x\A. norm (f x) \ 1/of_nat i})\ + by (rule countable_UN) (use fin in \auto intro!: countable_finite\) + also have \\ = {x\A. f x \ 0}\ + proof safe + fix x assume x: "x \ A" "f x \ 0" + define i where "i = max 1 (nat (ceiling (1 / norm (f x))))" + have "i \ 1" + by (simp add: i_def) + moreover have "real i \ 1 / norm (f x)" + unfolding i_def by linarith + hence "1 / real i \ norm (f x)" using \f x \ 0\ + by (auto simp: divide_simps mult_ac) + ultimately show "x \ (\i\{1..}. {x \ A. 1 / real i \ norm (f x)})" + using \x \ A\ by auto + qed auto + finally show ?thesis . +qed + +(* Logically belongs in the section about reals, but needed as a dependency here *) +lemma summable_on_iff_abs_summable_on_real: + fixes f :: \'a \ real\ + shows \f summable_on A \ f abs_summable_on A\ +proof (rule iffI) + assume \f summable_on A\ + define n A\<^sub>p A\<^sub>n + where \n x = norm (f x)\ and \A\<^sub>p = {x\A. f x \ 0}\ and \A\<^sub>n = {x\A. f x < 0}\ for x + have [simp]: \A\<^sub>p \ A\<^sub>n = A\ \A\<^sub>p \ A\<^sub>n = {}\ + by (auto simp: A\<^sub>p_def A\<^sub>n_def) + from \f summable_on A\ have [simp]: \f summable_on A\<^sub>p\ \f summable_on A\<^sub>n\ + using A\<^sub>p_def A\<^sub>n_def summable_on_subset_banach by fastforce+ + then have [simp]: \n summable_on A\<^sub>p\ + apply (subst summable_on_cong[where g=f]) + by (simp_all add: A\<^sub>p_def n_def) + moreover have [simp]: \n summable_on A\<^sub>n\ + apply (subst summable_on_cong[where g=\\x. - f x\]) + apply (simp add: A\<^sub>n_def n_def[abs_def]) + by (simp add: summable_on_uminus) + ultimately have [simp]: \n summable_on (A\<^sub>p \ A\<^sub>n)\ + apply (rule summable_on_Un_disjoint) by simp + then show \n summable_on A\ + by simp +next + show \f abs_summable_on A \ f summable_on A\ + using abs_summable_summable by blast +qed + +lemma abs_summable_on_Sigma_iff: + shows "f abs_summable_on Sigma A B \ + (\x\A. (\y. f (x, y)) abs_summable_on B x) \ + ((\x. infsum (\y. norm (f (x, y))) (B x)) abs_summable_on A)" +proof (intro iffI conjI ballI) + assume asm: \f abs_summable_on Sigma A B\ + then have \(\x. infsum (\y. norm (f (x,y))) (B x)) summable_on A\ + apply (rule_tac summable_on_Sigma_banach) + by (auto simp: case_prod_unfold) + then show \(\x. \\<^sub>\y\B x. norm (f (x, y))) abs_summable_on A\ + using summable_on_iff_abs_summable_on_real by force + + show \(\y. f (x, y)) abs_summable_on B x\ if \x \ A\ for x + proof - + from asm have \f abs_summable_on Pair x ` B x\ + apply (rule summable_on_subset_banach) + using that by auto + then show ?thesis + apply (subst (asm) summable_on_reindex) + by (auto simp: o_def inj_on_def) + qed +next + assume asm: \(\x\A. (\xa. f (x, xa)) abs_summable_on B x) \ + (\x. \\<^sub>\y\B x. norm (f (x, y))) abs_summable_on A\ + have \(\xy\F. norm (f xy)) \ (\\<^sub>\x\A. \\<^sub>\y\B x. norm (f (x, y)))\ + if \F \ Sigma A B\ and [simp]: \finite F\ for F + proof - + have [simp]: \(SIGMA x:fst ` F. {y. (x, y) \ F}) = F\ + by (auto intro!: set_eqI simp add: Domain.DomainI fst_eq_Domain) + have [simp]: \finite {y. (x, y) \ F}\ for x + by (metis \finite F\ Range.intros finite_Range finite_subset mem_Collect_eq subsetI) + have \(\xy\F. norm (f xy)) = (\x\fst ` F. \y\{y. (x,y)\F}. norm (f (x,y)))\ + apply (subst sum.Sigma) + by auto + also have \\ = (\\<^sub>\x\fst ` F. \\<^sub>\y\{y. (x,y)\F}. norm (f (x,y)))\ + apply (subst infsum_finite) + by auto + also have \\ \ (\\<^sub>\x\fst ` F. \\<^sub>\y\B x. norm (f (x,y)))\ + apply (rule infsum_mono) + apply (simp; fail) + apply (simp; fail) + apply (rule infsum_mono_neutral) + using asm that(1) by auto + also have \\ \ (\\<^sub>\x\A. \\<^sub>\y\B x. norm (f (x,y)))\ + by (rule infsum_mono_neutral) (use asm that(1) in \auto simp add: infsum_nonneg\) + finally show ?thesis . + qed + then show \f abs_summable_on Sigma A B\ + by (intro nonneg_bdd_above_summable_on) (auto simp: bdd_above_def) +qed + +lemma abs_summable_on_comparison_test: + assumes "g abs_summable_on A" + assumes "\x. x \ A \ norm (f x) \ norm (g x)" + shows "f abs_summable_on A" +proof (rule nonneg_bdd_above_summable_on) + show "bdd_above (sum (\x. norm (f x)) ` {F. F \ A \ finite F})" + proof (rule bdd_aboveI2) + fix F assume F: "F \ {F. F \ A \ finite F}" + have \sum (\x. norm (f x)) F \ sum (\x. norm (g x)) F\ + using assms F by (intro sum_mono) auto + also have \\ = infsum (\x. norm (g x)) F\ + using F by simp + also have \\ \ infsum (\x. norm (g x)) A\ + proof (rule infsum_mono_neutral) + show "g abs_summable_on F" + by (rule summable_on_subset_banach[OF assms(1)]) (use F in auto) + qed (use F assms in auto) + finally show "(\x\F. norm (f x)) \ (\\<^sub>\x\A. norm (g x))" . + qed +qed auto + +lemma abs_summable_iff_bdd_above: + fixes f :: \'a \ 'b::real_normed_vector\ + shows \f abs_summable_on A \ bdd_above (sum (\x. norm (f x)) ` {F. F\A \ finite F})\ +proof (rule iffI) + assume \f abs_summable_on A\ + show \bdd_above (sum (\x. norm (f x)) ` {F. F \ A \ finite F})\ + proof (rule bdd_aboveI2) + fix F assume F: "F \ {F. F \ A \ finite F}" + show "(\x\F. norm (f x)) \ (\\<^sub>\x\A. norm (f x))" + by (rule finite_sum_le_infsum) (use \f abs_summable_on A\ F in auto) + qed +next + assume \bdd_above (sum (\x. norm (f x)) ` {F. F\A \ finite F})\ + then show \f abs_summable_on A\ + by (simp add: nonneg_bdd_above_summable_on) +qed + +lemma abs_summable_product: + fixes x :: "'a \ 'b::{real_normed_div_algebra,banach,second_countable_topology}" + assumes x2_sum: "(\i. (x i) * (x i)) abs_summable_on A" + and y2_sum: "(\i. (y i) * (y i)) abs_summable_on A" + shows "(\i. x i * y i) abs_summable_on A" +proof (rule nonneg_bdd_above_summable_on) + show "bdd_above (sum (\xa. norm (x xa * y xa)) ` {F. F \ A \ finite F})" + proof (rule bdd_aboveI2) + fix F assume F: \F \ {F. F \ A \ finite F}\ + then have r1: "finite F" and b4: "F \ A" + by auto + + have a1: "(\\<^sub>\i\F. norm (x i * x i)) \ (\\<^sub>\i\A. norm (x i * x i))" + apply (rule infsum_mono_neutral) + using b4 r1 x2_sum by auto + + have "norm (x i * y i) \ norm (x i * x i) + norm (y i * y i)" for i + unfolding norm_mult by (smt mult_left_mono mult_nonneg_nonneg mult_right_mono norm_ge_zero) + hence "(\i\F. norm (x i * y i)) \ (\i\F. norm (x i * x i) + norm (y i * y i))" + by (simp add: sum_mono) + also have "\ = (\i\F. norm (x i * x i)) + (\i\F. norm (y i * y i))" + by (simp add: sum.distrib) + also have "\ = (\\<^sub>\i\F. norm (x i * x i)) + (\\<^sub>\i\F. norm (y i * y i))" + by (simp add: \finite F\) + also have "\ \ (\\<^sub>\i\A. norm (x i * x i)) + (\\<^sub>\i\A. norm (y i * y i))" + using F assms + by (intro add_mono infsum_mono2) auto + finally show \(\xa\F. norm (x xa * y xa)) \ (\\<^sub>\i\A. norm (x i * x i)) + (\\<^sub>\i\A. norm (y i * y i))\ + by simp + qed +qed auto + subsection \Extended reals and nats\ lemma summable_on_ennreal[simp]: \(f::_ \ ennreal) summable_on S\ - apply (rule pos_summable_on_complete) by simp + by (rule nonneg_summable_on_complete) simp lemma summable_on_enat[simp]: \(f::_ \ enat) summable_on S\ - apply (rule pos_summable_on_complete) by simp + by (rule nonneg_summable_on_complete) simp lemma has_sum_superconst_infinite_ennreal: fixes f :: \'a \ ennreal\ @@ -1629,8 +2244,7 @@ by (simp add: mult.commute) also have \\ \ sum f Y\ using geqb by (meson subset_eq sum_mono that(3)) - finally show ?thesis - by - + finally show ?thesis . qed ultimately show \\\<^sub>F x in finite_subsets_at_top S. y < sum f x\ unfolding eventually_finite_subsets_at_top @@ -1657,19 +2271,20 @@ proof - obtain b' where b': \e2ennreal b' = b\ and \b' > 0\ using b by blast - have *: \infsum (e2ennreal o f) S = \\ - apply (rule infsum_superconst_infinite_ennreal[where b=b']) - using assms \b' > 0\ b' e2ennreal_mono apply auto - by (metis dual_order.strict_iff_order enn2ereal_e2ennreal le_less_linear zero_ennreal_def) + have "0 < e2ennreal b" + using b' b + by (metis dual_order.refl enn2ereal_e2ennreal gr_zeroI order_less_le zero_ennreal.abs_eq) + hence *: \infsum (e2ennreal o f) S = \\ + using assms b' + by (intro infsum_superconst_infinite_ennreal[where b=b']) (auto intro!: e2ennreal_mono) have \infsum f S = infsum (enn2ereal o (e2ennreal o f)) S\ - by (smt (verit, best) b comp_apply dual_order.trans enn2ereal_e2ennreal geqb infsum_cong less_imp_le) + using geqb b by (intro infsum_cong) (fastforce simp: enn2ereal_e2ennreal) also have \\ = enn2ereal \\ apply (subst infsum_comm_additive_general) using * by (auto simp: continuous_at_enn2ereal) also have \\ = \\ by simp - finally show ?thesis - by - + finally show ?thesis . qed lemma has_sum_superconst_infinite_ereal: @@ -1704,7 +2319,7 @@ assumes \b > 0\ assumes \infinite S\ shows "has_sum f S \" - by (metis assms i0_lb has_sum_infsum infsum_superconst_infinite_enat pos_summable_on_complete) + by (metis assms i0_lb has_sum_infsum infsum_superconst_infinite_enat nonneg_summable_on_complete) text \This lemma helps to relate a real-valued infsum to a supremum over extended nonnegative reals.\ @@ -1719,12 +2334,11 @@ apply (subst sum_ennreal[symmetric]) using assms by auto also have \\ = (SUP F\{F. finite F \ F \ A}. (ennreal (sum f F)))\ - apply (subst pos_infsum_complete, simp) + apply (subst nonneg_infsum_complete, simp) apply (rule SUP_cong, blast) apply (subst sum_ennreal[symmetric]) using fnn by auto - finally show ?thesis - by - + finally show ?thesis . qed text \This lemma helps to related a real-valued infsum to a supremum over extended reals.\ @@ -1739,10 +2353,8 @@ apply (rule infsum_comm_additive_general[symmetric]) using assms by auto also have \\ = (SUP F\{F. finite F \ F \ A}. (ereal (sum f F)))\ - apply (subst pos_infsum_complete) - by (simp_all add: assms)[2] - finally show ?thesis - by - + by (subst nonneg_infsum_complete) (simp_all add: assms) + finally show ?thesis . qed @@ -1776,33 +2388,11 @@ shows "has_sum f A (SUP F\{F. finite F \ F \ A}. (sum f F))" by (metis (mono_tags, lifting) assms has_sum_infsum infsum_nonneg_is_SUPREMUM_real) - -lemma summable_on_iff_abs_summable_on_real: +lemma summable_countable_real: fixes f :: \'a \ real\ - shows \f summable_on A \ f abs_summable_on A\ -proof (rule iffI) - assume \f summable_on A\ - define n A\<^sub>p A\<^sub>n - where \n x = norm (f x)\ and \A\<^sub>p = {x\A. f x \ 0}\ and \A\<^sub>n = {x\A. f x < 0}\ for x - have [simp]: \A\<^sub>p \ A\<^sub>n = A\ \A\<^sub>p \ A\<^sub>n = {}\ - by (auto simp: A\<^sub>p_def A\<^sub>n_def) - from \f summable_on A\ have [simp]: \f summable_on A\<^sub>p\ \f summable_on A\<^sub>n\ - using A\<^sub>p_def A\<^sub>n_def summable_on_subset_banach by fastforce+ - then have [simp]: \n summable_on A\<^sub>p\ - apply (subst summable_on_cong[where g=f]) - by (simp_all add: A\<^sub>p_def n_def) - moreover have [simp]: \n summable_on A\<^sub>n\ - apply (subst summable_on_cong[where g=\\x. - f x\]) - apply (simp add: A\<^sub>n_def n_def[abs_def]) - by (simp add: summable_on_uminus) - ultimately have [simp]: \n summable_on (A\<^sub>p \ A\<^sub>n)\ - apply (rule summable_on_Un_disjoint) by simp - then show \n summable_on A\ - by simp -next - show \f abs_summable_on A \ f summable_on A\ - using abs_summable_summable by blast -qed + assumes \f summable_on A\ + shows \countable {x\A. f x \ 0}\ + using abs_summable_countable assms summable_on_iff_abs_summable_on_real by blast subsection \Complex numbers\ @@ -1854,7 +2444,7 @@ apply (rule summable_on_comm_additive[where f=Im, unfolded o_def]) using assms by (auto intro!: additive.intro) -lemma infsum_0D_complex: +lemma nonneg_infsum_le_0D_complex: fixes f :: "'a \ complex" assumes "infsum f A \ 0" and abs_sum: "f summable_on A" @@ -1863,22 +2453,22 @@ shows "f x = 0" proof - have \Im (f x) = 0\ - apply (rule infsum_0D[where A=A]) + apply (rule nonneg_infsum_le_0D[where A=A]) using assms by (auto simp add: infsum_Im summable_on_Im less_eq_complex_def) moreover have \Re (f x) = 0\ - apply (rule infsum_0D[where A=A]) + apply (rule nonneg_infsum_le_0D[where A=A]) using assms by (auto simp add: summable_on_Re infsum_Re less_eq_complex_def) ultimately show ?thesis by (simp add: complex_eqI) qed -lemma has_sum_0D_complex: +lemma nonneg_has_sum_le_0D_complex: fixes f :: "'a \ complex" assumes "has_sum f A a" and \a \ 0\ and "\x. x \ A \ f x \ 0" and "x \ A" shows "f x = 0" - by (metis assms infsumI infsum_0D_complex summable_on_def) + by (metis assms infsumI nonneg_infsum_le_0D_complex summable_on_def) text \The lemma @{thm [source] infsum_mono_neutral} above applies to various linear ordered monoids such as the reals but not to the complex numbers. Thus we have a separate corollary for those:\ @@ -1929,14 +2519,16 @@ shows "infsum (\x. cmod (f x)) M = cmod (infsum f M)" proof - have \complex_of_real (infsum (\x. cmod (f x)) M) = infsum (\x. complex_of_real (cmod (f x))) M\ - apply (rule infsum_comm_additive[symmetric, unfolded o_def]) - apply auto - apply (simp add: additive.intro) - by (smt (verit, best) assms(1) cmod_eq_Re fnn summable_on_Re summable_on_cong less_eq_complex_def zero_complex.simps(1) zero_complex.simps(2)) + proof (rule infsum_comm_additive[symmetric, unfolded o_def]) + have "(\z. Re (f z)) summable_on M" + using assms summable_on_Re by blast + also have "?this \ f abs_summable_on M" + using fnn by (intro summable_on_cong) (auto simp: less_eq_complex_def cmod_def) + finally show \ . + qed (auto simp: additive_def) also have \\ = infsum f M\ apply (rule infsum_cong) - using fnn - using cmod_eq_Re complex_is_Real_iff less_eq_complex_def by force + using fnn cmod_eq_Re complex_is_Real_iff less_eq_complex_def by force finally show ?thesis by (metis abs_of_nonneg infsum_def le_less_trans norm_ge_zero norm_infsum_bound norm_of_real not_le order_refl) qed @@ -1965,8 +2557,8 @@ have *: \(\x. nr x + ni x) summable_on A\ apply (rule summable_on_add) by auto show \n summable_on A\ - apply (rule pos_summable_on) - apply (simp add: n_def) + apply (rule nonneg_bdd_above_summable_on) + apply (simp add: n_def; fail) apply (rule bdd_aboveI[where M=\infsum (\x. nr x + ni x) A\]) using * n_sum by (auto simp flip: infsum_finite simp: ni_def[abs_def] nr_def[abs_def] intro!: infsum_mono_neutral) next @@ -1974,4 +2566,11 @@ using abs_summable_summable by blast qed +lemma summable_countable_complex: + fixes f :: \'a \ complex\ + assumes \f summable_on A\ + shows \countable {x\A. f x \ 0}\ + using abs_summable_countable assms summable_on_iff_abs_summable_on_complex by blast + end +