757 apply (simp add: inverse_eq_divide real_sqrt_ge_0_iff field_simps) |
757 apply (simp add: inverse_eq_divide real_sqrt_ge_0_iff field_simps) |
758 done |
758 done |
759 |
759 |
760 text{* Hence derive more interesting properties of the norm. *} |
760 text{* Hence derive more interesting properties of the norm. *} |
761 |
761 |
762 lemma norm_0: "norm (0::real ^ 'n) = 0" |
762 lemma norm_0[simp]: "norm (0::real ^ 'n) = 0" |
763 by (rule norm_zero) |
763 by (rule norm_zero) |
764 |
764 |
765 lemma norm_mul: "norm(a *s x) = abs(a) * norm x" |
765 lemma norm_mul[simp]: "norm(a *s x) = abs(a) * norm x" |
766 by (simp add: vector_norm_def vector_component setL2_right_distrib |
766 by (simp add: vector_norm_def vector_component setL2_right_distrib |
767 abs_mult cong: strong_setL2_cong) |
767 abs_mult cong: strong_setL2_cong) |
768 lemma norm_eq_0_dot: "(norm x = 0) \<longleftrightarrow> (x \<bullet> x = (0::real))" |
768 lemma norm_eq_0_dot: "(norm x = 0) \<longleftrightarrow> (x \<bullet> x = (0::real))" |
769 by (simp add: vector_norm_def dot_def setL2_def power2_eq_square) |
769 by (simp add: vector_norm_def dot_def setL2_def power2_eq_square) |
770 lemma real_vector_norm_def: "norm x = sqrt (x \<bullet> x)" |
770 lemma real_vector_norm_def: "norm x = sqrt (x \<bullet> x)" |
771 by (simp add: vector_norm_def setL2_def dot_def power2_eq_square) |
771 by (simp add: vector_norm_def setL2_def dot_def power2_eq_square) |
772 lemma norm_pow_2: "norm x ^ 2 = x \<bullet> x" |
772 lemma norm_pow_2: "norm x ^ 2 = x \<bullet> x" |
773 by (simp add: real_vector_norm_def) |
773 by (simp add: real_vector_norm_def) |
774 lemma norm_eq_0_imp: "norm x = 0 ==> x = (0::real ^'n)" by (metis norm_eq_zero) |
774 lemma norm_eq_0_imp: "norm x = 0 ==> x = (0::real ^'n)" by (metis norm_eq_zero) |
775 lemma vector_mul_eq_0: "(a *s x = 0) \<longleftrightarrow> a = (0::'a::idom) \<or> x = 0" |
775 lemma vector_mul_eq_0[simp]: "(a *s x = 0) \<longleftrightarrow> a = (0::'a::idom) \<or> x = 0" |
776 by vector |
776 by vector |
777 lemma vector_mul_lcancel: "a *s x = a *s y \<longleftrightarrow> a = (0::real) \<or> x = y" |
777 lemma vector_mul_lcancel[simp]: "a *s x = a *s y \<longleftrightarrow> a = (0::real) \<or> x = y" |
778 by (metis eq_iff_diff_eq_0 vector_mul_eq_0 vector_ssub_ldistrib) |
778 by (metis eq_iff_diff_eq_0 vector_mul_eq_0 vector_ssub_ldistrib) |
779 lemma vector_mul_rcancel: "a *s x = b *s x \<longleftrightarrow> (a::real) = b \<or> x = 0" |
779 lemma vector_mul_rcancel[simp]: "a *s x = b *s x \<longleftrightarrow> (a::real) = b \<or> x = 0" |
780 by (metis eq_iff_diff_eq_0 vector_mul_eq_0 vector_sub_rdistrib) |
780 by (metis eq_iff_diff_eq_0 vector_mul_eq_0 vector_sub_rdistrib) |
781 lemma vector_mul_lcancel_imp: "a \<noteq> (0::real) ==> a *s x = a *s y ==> (x = y)" |
781 lemma vector_mul_lcancel_imp: "a \<noteq> (0::real) ==> a *s x = a *s y ==> (x = y)" |
782 by (metis vector_mul_lcancel) |
782 by (metis vector_mul_lcancel) |
783 lemma vector_mul_rcancel_imp: "x \<noteq> 0 \<Longrightarrow> (a::real) *s x = b *s x ==> a = b" |
783 lemma vector_mul_rcancel_imp: "x \<noteq> 0 \<Longrightarrow> (a::real) *s x = b *s x ==> a = b" |
784 by (metis vector_mul_rcancel) |
784 by (metis vector_mul_rcancel) |
812 lemma norm_triangle_le: "norm(x::real ^'n) + norm y <= e ==> norm(x + y) <= e" |
812 lemma norm_triangle_le: "norm(x::real ^'n) + norm y <= e ==> norm(x + y) <= e" |
813 by (metis order_trans norm_triangle_ineq) |
813 by (metis order_trans norm_triangle_ineq) |
814 lemma norm_triangle_lt: "norm(x::real ^'n) + norm(y) < e ==> norm(x + y) < e" |
814 lemma norm_triangle_lt: "norm(x::real ^'n) + norm(y) < e ==> norm(x + y) < e" |
815 by (metis basic_trans_rules(21) norm_triangle_ineq) |
815 by (metis basic_trans_rules(21) norm_triangle_ineq) |
816 |
816 |
817 lemma setsum_delta: |
|
818 assumes fS: "finite S" |
|
819 shows "setsum (\<lambda>k. if k=a then b k else 0) S = (if a \<in> S then b a else 0)" |
|
820 proof- |
|
821 let ?f = "(\<lambda>k. if k=a then b k else 0)" |
|
822 {assume a: "a \<notin> S" |
|
823 hence "\<forall> k\<in> S. ?f k = 0" by simp |
|
824 hence ?thesis using a by simp} |
|
825 moreover |
|
826 {assume a: "a \<in> S" |
|
827 let ?A = "S - {a}" |
|
828 let ?B = "{a}" |
|
829 have eq: "S = ?A \<union> ?B" using a by blast |
|
830 have dj: "?A \<inter> ?B = {}" by simp |
|
831 from fS have fAB: "finite ?A" "finite ?B" by auto |
|
832 have "setsum ?f S = setsum ?f ?A + setsum ?f ?B" |
|
833 using setsum_Un_disjoint[OF fAB dj, of ?f, unfolded eq[symmetric]] |
|
834 by simp |
|
835 then have ?thesis using a by simp} |
|
836 ultimately show ?thesis by blast |
|
837 qed |
|
838 |
|
839 lemma component_le_norm: "i \<in> {1 .. dimindex(UNIV :: 'n set)} ==> \<bar>x$i\<bar> <= norm (x::real ^ 'n)" |
817 lemma component_le_norm: "i \<in> {1 .. dimindex(UNIV :: 'n set)} ==> \<bar>x$i\<bar> <= norm (x::real ^ 'n)" |
840 apply (simp add: vector_norm_def) |
818 apply (simp add: vector_norm_def) |
841 apply (rule member_le_setL2, simp_all) |
819 apply (rule member_le_setL2, simp_all) |
842 done |
820 done |
843 |
821 |
850 by (metis component_le_norm basic_trans_rules(21)) |
828 by (metis component_le_norm basic_trans_rules(21)) |
851 |
829 |
852 lemma norm_le_l1: "norm (x:: real ^'n) <= setsum(\<lambda>i. \<bar>x$i\<bar>) {1..dimindex(UNIV::'n set)}" |
830 lemma norm_le_l1: "norm (x:: real ^'n) <= setsum(\<lambda>i. \<bar>x$i\<bar>) {1..dimindex(UNIV::'n set)}" |
853 by (simp add: vector_norm_def setL2_le_setsum) |
831 by (simp add: vector_norm_def setL2_le_setsum) |
854 |
832 |
855 lemma real_abs_norm: "\<bar> norm x\<bar> = norm (x :: real ^'n)" |
833 lemma real_abs_norm[simp]: "\<bar> norm x\<bar> = norm (x :: real ^'n)" |
856 by (rule abs_norm_cancel) |
834 by (rule abs_norm_cancel) |
857 lemma real_abs_sub_norm: "\<bar>norm(x::real ^'n) - norm y\<bar> <= norm(x - y)" |
835 lemma real_abs_sub_norm: "\<bar>norm(x::real ^'n) - norm y\<bar> <= norm(x - y)" |
858 by (rule norm_triangle_ineq3) |
836 by (rule norm_triangle_ineq3) |
859 lemma norm_le: "norm(x::real ^ 'n) <= norm(y) \<longleftrightarrow> x \<bullet> x <= y \<bullet> y" |
837 lemma norm_le: "norm(x::real ^ 'n) <= norm(y) \<longleftrightarrow> x \<bullet> x <= y \<bullet> y" |
860 by (simp add: real_vector_norm_def) |
838 by (simp add: real_vector_norm_def) |
975 |
954 |
976 |
955 |
977 |
956 |
978 text{* Hence more metric properties. *} |
957 text{* Hence more metric properties. *} |
979 |
958 |
980 lemma dist_refl: "dist x x = 0" by norm |
959 lemma dist_refl[simp]: "dist x x = 0" by norm |
981 |
960 |
982 lemma dist_sym: "dist x y = dist y x"by norm |
961 lemma dist_sym: "dist x y = dist y x"by norm |
983 |
962 |
984 lemma dist_pos_le: "0 <= dist x y" by norm |
963 lemma dist_pos_le[simp]: "0 <= dist x y" by norm |
985 |
964 |
986 lemma dist_triangle: "dist x z <= dist x y + dist y z" by norm |
965 lemma dist_triangle: "dist x z <= dist x y + dist y z" by norm |
987 |
966 |
988 lemma dist_triangle_alt: "dist y z <= dist x y + dist x z" by norm |
967 lemma dist_triangle_alt: "dist y z <= dist x y + dist x z" by norm |
989 |
968 |
990 lemma dist_eq_0: "dist x y = 0 \<longleftrightarrow> x = y" by norm |
969 lemma dist_eq_0[simp]: "dist x y = 0 \<longleftrightarrow> x = y" by norm |
991 |
970 |
992 lemma dist_pos_lt: "x \<noteq> y ==> 0 < dist x y" by norm |
971 lemma dist_pos_lt: "x \<noteq> y ==> 0 < dist x y" by norm |
993 lemma dist_nz: "x \<noteq> y \<longleftrightarrow> 0 < dist x y" by norm |
972 lemma dist_nz: "x \<noteq> y \<longleftrightarrow> 0 < dist x y" by norm |
994 |
973 |
995 lemma dist_triangle_le: "dist x z + dist y z <= e \<Longrightarrow> dist x y <= e" by norm |
974 lemma dist_triangle_le: "dist x z + dist y z <= e \<Longrightarrow> dist x y <= e" by norm |
1032 lemma setsum_component: |
1011 lemma setsum_component: |
1033 fixes f:: " 'a \<Rightarrow> ('b::semiring_1) ^'n" |
1012 fixes f:: " 'a \<Rightarrow> ('b::semiring_1) ^'n" |
1034 assumes i: "i \<in> {1 .. dimindex(UNIV:: 'n set)}" |
1013 assumes i: "i \<in> {1 .. dimindex(UNIV:: 'n set)}" |
1035 shows "(setsum f S)$i = setsum (\<lambda>x. (f x)$i) S" |
1014 shows "(setsum f S)$i = setsum (\<lambda>x. (f x)$i) S" |
1036 using i by (simp add: setsum_eq Cart_lambda_beta) |
1015 using i by (simp add: setsum_eq Cart_lambda_beta) |
1037 |
|
1038 (* This needs finiteness assumption due to the definition of fold!!! *) |
|
1039 |
|
1040 lemma setsum_superset: |
|
1041 assumes fb: "finite B" and ab: "A \<subseteq> B" |
|
1042 and f0: "\<forall>x \<in> B - A. f x = 0" |
|
1043 shows "setsum f B = setsum f A" |
|
1044 proof- |
|
1045 from ab fb have fa: "finite A" by (metis finite_subset) |
|
1046 from fb have fba: "finite (B - A)" by (metis finite_Diff) |
|
1047 have d: "A \<inter> (B - A) = {}" by blast |
|
1048 from ab have b: "B = A \<union> (B - A)" by blast |
|
1049 from setsum_Un_disjoint[OF fa fba d, of f] b |
|
1050 setsum_0'[OF f0] |
|
1051 show "setsum f B = setsum f A" by simp |
|
1052 qed |
|
1053 |
|
1054 lemma setsum_restrict_set: |
|
1055 assumes fA: "finite A" |
|
1056 shows "setsum f (A \<inter> B) = setsum (\<lambda>x. if x \<in> B then f x else 0) A" |
|
1057 proof- |
|
1058 from fA have fab: "finite (A \<inter> B)" by auto |
|
1059 have aba: "A \<inter> B \<subseteq> A" by blast |
|
1060 let ?g = "\<lambda>x. if x \<in> A\<inter>B then f x else 0" |
|
1061 from setsum_superset[OF fA aba, of ?g] |
|
1062 show ?thesis by simp |
|
1063 qed |
|
1064 |
|
1065 lemma setsum_cases: |
|
1066 assumes fA: "finite A" |
|
1067 shows "setsum (\<lambda>x. if x \<in> B then f x else g x) A = |
|
1068 setsum f (A \<inter> B) + setsum g (A \<inter> - B)" |
|
1069 proof- |
|
1070 have a: "A = A \<inter> B \<union> A \<inter> -B" "(A \<inter> B) \<inter> (A \<inter> -B) = {}" |
|
1071 by blast+ |
|
1072 from fA |
|
1073 have f: "finite (A \<inter> B)" "finite (A \<inter> -B)" by auto |
|
1074 let ?g = "\<lambda>x. if x \<in> B then f x else g x" |
|
1075 from setsum_Un_disjoint[OF f a(2), of ?g] a(1) |
|
1076 show ?thesis by simp |
|
1077 qed |
|
1078 |
1016 |
1079 lemma setsum_norm: |
1017 lemma setsum_norm: |
1080 fixes f :: "'a \<Rightarrow> 'b::real_normed_vector" |
1018 fixes f :: "'a \<Rightarrow> 'b::real_normed_vector" |
1081 assumes fS: "finite S" |
1019 assumes fS: "finite S" |
1082 shows "norm (setsum f S) <= setsum (\<lambda>x. norm(f x)) S" |
1020 shows "norm (setsum f S) <= setsum (\<lambda>x. norm(f x)) S" |
1171 have eq: "{m .. n+p} = ?A \<union> ?B" using mn by auto |
1109 have eq: "{m .. n+p} = ?A \<union> ?B" using mn by auto |
1172 have d: "?A \<inter> ?B = {}" by auto |
1110 have d: "?A \<inter> ?B = {}" by auto |
1173 from setsum_Un_disjoint[of "?A" "?B" f] eq d show ?thesis by auto |
1111 from setsum_Un_disjoint[of "?A" "?B" f] eq d show ?thesis by auto |
1174 qed |
1112 qed |
1175 |
1113 |
1176 lemma setsum_reindex_nonzero: |
|
1177 assumes fS: "finite S" |
|
1178 and nz: "\<And> x y. x \<in> S \<Longrightarrow> y \<in> S \<Longrightarrow> x \<noteq> y \<Longrightarrow> f x = f y \<Longrightarrow> h (f x) = 0" |
|
1179 shows "setsum h (f ` S) = setsum (h o f) S" |
|
1180 using nz |
|
1181 proof(induct rule: finite_induct[OF fS]) |
|
1182 case 1 thus ?case by simp |
|
1183 next |
|
1184 case (2 x F) |
|
1185 {assume fxF: "f x \<in> f ` F" hence "\<exists>y \<in> F . f y = f x" by auto |
|
1186 then obtain y where y: "y \<in> F" "f x = f y" by auto |
|
1187 from "2.hyps" y have xy: "x \<noteq> y" by auto |
|
1188 |
|
1189 from "2.prems"[of x y] "2.hyps" xy y have h0: "h (f x) = 0" by simp |
|
1190 have "setsum h (f ` insert x F) = setsum h (f ` F)" using fxF by auto |
|
1191 also have "\<dots> = setsum (h o f) (insert x F)" |
|
1192 using "2.hyps" "2.prems" h0 by auto |
|
1193 finally have ?case .} |
|
1194 moreover |
|
1195 {assume fxF: "f x \<notin> f ` F" |
|
1196 have "setsum h (f ` insert x F) = h (f x) + setsum h (f ` F)" |
|
1197 using fxF "2.hyps" by simp |
|
1198 also have "\<dots> = setsum (h o f) (insert x F)" |
|
1199 using "2.hyps" "2.prems" fxF |
|
1200 apply auto apply metis done |
|
1201 finally have ?case .} |
|
1202 ultimately show ?case by blast |
|
1203 qed |
|
1204 |
|
1205 lemma setsum_Un_nonzero: |
|
1206 assumes fS: "finite S" and fF: "finite F" |
|
1207 and f: "\<forall> x\<in> S \<inter> F . f x = (0::'a::ab_group_add)" |
|
1208 shows "setsum f (S \<union> F) = setsum f S + setsum f F" |
|
1209 using setsum_Un[OF fS fF, of f] setsum_0'[OF f] by simp |
|
1210 |
|
1211 lemma setsum_natinterval_left: |
1114 lemma setsum_natinterval_left: |
1212 assumes mn: "(m::nat) <= n" |
1115 assumes mn: "(m::nat) <= n" |
1213 shows "setsum f {m..n} = f m + setsum f {m + 1..n}" |
1116 shows "setsum f {m..n} = f m + setsum f {m + 1..n}" |
1214 proof- |
1117 proof- |
1215 from mn have "{m .. n} = insert m {m+1 .. n}" by auto |
1118 from mn have "{m .. n} = insert m {m+1 .. n}" by auto |
1247 lemma setsum_group: |
1150 lemma setsum_group: |
1248 assumes fS: "finite S" and fT: "finite T" and fST: "f ` S \<subseteq> T" |
1151 assumes fS: "finite S" and fT: "finite T" and fST: "f ` S \<subseteq> T" |
1249 shows "setsum (\<lambda>y. setsum g {x. x\<in> S \<and> f x = y}) T = setsum g S" |
1152 shows "setsum (\<lambda>y. setsum g {x. x\<in> S \<and> f x = y}) T = setsum g S" |
1250 |
1153 |
1251 apply (subst setsum_image_gen[OF fS, of g f]) |
1154 apply (subst setsum_image_gen[OF fS, of g f]) |
1252 apply (rule setsum_superset[OF fT fST]) |
1155 apply (rule setsum_mono_zero_right[OF fT fST]) |
1253 by (auto intro: setsum_0') |
1156 by (auto intro: setsum_0') |
1254 |
|
1255 (* FIXME: Change the name to fold_image\<dots> *) |
|
1256 lemma (in comm_monoid_mult) fold_1': "finite S \<Longrightarrow> (\<forall>x\<in>S. f x = 1) \<Longrightarrow> fold_image op * f 1 S = 1" |
|
1257 apply (induct set: finite) |
|
1258 apply simp by (auto simp add: fold_image_insert) |
|
1259 |
|
1260 lemma (in comm_monoid_mult) fold_union_nonzero: |
|
1261 assumes fS: "finite S" and fT: "finite T" |
|
1262 and I0: "\<forall>x \<in> S\<inter>T. f x = 1" |
|
1263 shows "fold_image (op *) f 1 (S \<union> T) = fold_image (op *) f 1 S * fold_image (op *) f 1 T" |
|
1264 proof- |
|
1265 have "fold_image op * f 1 (S \<inter> T) = 1" |
|
1266 apply (rule fold_1') |
|
1267 using fS fT I0 by auto |
|
1268 with fold_image_Un_Int[OF fS fT] show ?thesis by simp |
|
1269 qed |
|
1270 |
|
1271 lemma setsum_union_nonzero: |
|
1272 assumes fS: "finite S" and fT: "finite T" |
|
1273 and I0: "\<forall>x \<in> S\<inter>T. f x = 0" |
|
1274 shows "setsum f (S \<union> T) = setsum f S + setsum f T" |
|
1275 using fS fT |
|
1276 apply (simp add: setsum_def) |
|
1277 apply (rule comm_monoid_add.fold_union_nonzero) |
|
1278 using I0 by auto |
|
1279 |
|
1280 lemma setprod_union_nonzero: |
|
1281 assumes fS: "finite S" and fT: "finite T" |
|
1282 and I0: "\<forall>x \<in> S\<inter>T. f x = 1" |
|
1283 shows "setprod f (S \<union> T) = setprod f S * setprod f T" |
|
1284 using fS fT |
|
1285 apply (simp add: setprod_def) |
|
1286 apply (rule fold_union_nonzero) |
|
1287 using I0 by auto |
|
1288 |
|
1289 lemma setsum_unions_nonzero: |
|
1290 assumes fS: "finite S" and fSS: "\<forall>T \<in> S. finite T" |
|
1291 and f0: "\<And>T1 T2 x. T1\<in>S \<Longrightarrow> T2\<in>S \<Longrightarrow> T1 \<noteq> T2 \<Longrightarrow> x \<in> T1 \<Longrightarrow> x \<in> T2 \<Longrightarrow> f x = 0" |
|
1292 shows "setsum f (\<Union>S) = setsum (\<lambda>T. setsum f T) S" |
|
1293 using fSS f0 |
|
1294 proof(induct rule: finite_induct[OF fS]) |
|
1295 case 1 thus ?case by simp |
|
1296 next |
|
1297 case (2 T F) |
|
1298 then have fTF: "finite T" "\<forall>T\<in>F. finite T" "finite F" and TF: "T \<notin> F" |
|
1299 and H: "setsum f (\<Union> F) = setsum (setsum f) F" by (auto simp add: finite_insert) |
|
1300 from fTF have fUF: "finite (\<Union>F)" by (auto intro: finite_Union) |
|
1301 from "2.prems" TF fTF |
|
1302 show ?case |
|
1303 by (auto simp add: H[symmetric] intro: setsum_union_nonzero[OF fTF(1) fUF, of f]) |
|
1304 qed |
|
1305 |
|
1306 (* FIXME : Copied from Pocklington --- should be moved to Finite_Set!!!!!!!! *) |
|
1307 |
|
1308 |
|
1309 lemma (in comm_monoid_mult) fold_related: |
|
1310 assumes Re: "R e e" |
|
1311 and Rop: "\<forall>x1 y1 x2 y2. R x1 x2 \<and> R y1 y2 \<longrightarrow> R (x1 * y1) (x2 * y2)" |
|
1312 and fS: "finite S" and Rfg: "\<forall>x\<in>S. R (h x) (g x)" |
|
1313 shows "R (fold_image (op *) h e S) (fold_image (op *) g e S)" |
|
1314 using fS by (rule finite_subset_induct) (insert assms, auto) |
|
1315 |
|
1316 (* FIXME: I think we can get rid of the finite assumption!! *) |
|
1317 lemma (in comm_monoid_mult) |
|
1318 fold_eq_general: |
|
1319 assumes fS: "finite S" |
|
1320 and h: "\<forall>y\<in>S'. \<exists>!x. x\<in> S \<and> h(x) = y" |
|
1321 and f12: "\<forall>x\<in>S. h x \<in> S' \<and> f2(h x) = f1 x" |
|
1322 shows "fold_image (op *) f1 e S = fold_image (op *) f2 e S'" |
|
1323 proof- |
|
1324 from h f12 have hS: "h ` S = S'" by auto |
|
1325 {fix x y assume H: "x \<in> S" "y \<in> S" "h x = h y" |
|
1326 from f12 h H have "x = y" by auto } |
|
1327 hence hinj: "inj_on h S" unfolding inj_on_def Ex1_def by blast |
|
1328 from f12 have th: "\<And>x. x \<in> S \<Longrightarrow> (f2 \<circ> h) x = f1 x" by auto |
|
1329 from hS have "fold_image (op *) f2 e S' = fold_image (op *) f2 e (h ` S)" by simp |
|
1330 also have "\<dots> = fold_image (op *) (f2 o h) e S" |
|
1331 using fold_image_reindex[OF fS hinj, of f2 e] . |
|
1332 also have "\<dots> = fold_image (op *) f1 e S " using th fold_image_cong[OF fS, of "f2 o h" f1 e] |
|
1333 by blast |
|
1334 finally show ?thesis .. |
|
1335 qed |
|
1336 |
|
1337 lemma (in comm_monoid_mult) fold_eq_general_inverses: |
|
1338 assumes fS: "finite S" |
|
1339 and kh: "\<And>y. y \<in> T \<Longrightarrow> k y \<in> S \<and> h (k y) = y" |
|
1340 and hk: "\<And>x. x \<in> S \<Longrightarrow> h x \<in> T \<and> k (h x) = x \<and> g (h x) = f x" |
|
1341 shows "fold_image (op *) f e S = fold_image (op *) g e T" |
|
1342 using fold_eq_general[OF fS, of T h g f e] kh hk by metis |
|
1343 |
|
1344 lemma setsum_eq_general_reverses: |
|
1345 assumes fS: "finite S" and fT: "finite T" |
|
1346 and kh: "\<And>y. y \<in> T \<Longrightarrow> k y \<in> S \<and> h (k y) = y" |
|
1347 and hk: "\<And>x. x \<in> S \<Longrightarrow> h x \<in> T \<and> k (h x) = x \<and> g (h x) = f x" |
|
1348 shows "setsum f S = setsum g T" |
|
1349 apply (simp add: setsum_def fS fT) |
|
1350 apply (rule comm_monoid_add.fold_eq_general_inverses[OF fS]) |
|
1351 apply (erule kh) |
|
1352 apply (erule hk) |
|
1353 done |
|
1354 |
1157 |
1355 lemma vsum_norm_allsubsets_bound: |
1158 lemma vsum_norm_allsubsets_bound: |
1356 fixes f:: "'a \<Rightarrow> real ^'n" |
1159 fixes f:: "'a \<Rightarrow> real ^'n" |
1357 assumes fP: "finite P" and fPs: "\<And>Q. Q \<subseteq> P \<Longrightarrow> norm (setsum f Q) \<le> e" |
1160 assumes fP: "finite P" and fPs: "\<And>Q. Q \<subseteq> P \<Longrightarrow> norm (setsum f Q) \<le> e" |
1358 shows "setsum (\<lambda>x. norm (f x)) P \<le> 2 * real (dimindex(UNIV :: 'n set)) * e" |
1161 shows "setsum (\<lambda>x. norm (f x)) P \<le> 2 * real (dimindex(UNIV :: 'n set)) * e" |
1381 have Pne: "setsum (\<lambda>x. \<bar>f x $ i\<bar>) ?Pn \<le> e" |
1184 have Pne: "setsum (\<lambda>x. \<bar>f x $ i\<bar>) ?Pn \<le> e" |
1382 using i component_le_norm[OF i, of "setsum (\<lambda>x. - f x) ?Pn"] fPs[OF PnP] |
1185 using i component_le_norm[OF i, of "setsum (\<lambda>x. - f x) ?Pn"] fPs[OF PnP] |
1383 by (auto simp add: setsum_negf setsum_component vector_component intro: abs_le_D1) |
1186 by (auto simp add: setsum_negf setsum_component vector_component intro: abs_le_D1) |
1384 have "setsum (\<lambda>x. \<bar>f x $ i\<bar>) P = setsum (\<lambda>x. \<bar>f x $ i\<bar>) ?Pp + setsum (\<lambda>x. \<bar>f x $ i\<bar>) ?Pn" |
1187 have "setsum (\<lambda>x. \<bar>f x $ i\<bar>) P = setsum (\<lambda>x. \<bar>f x $ i\<bar>) ?Pp + setsum (\<lambda>x. \<bar>f x $ i\<bar>) ?Pn" |
1385 apply (subst thp) |
1188 apply (subst thp) |
1386 apply (rule setsum_Un_nonzero) |
1189 apply (rule setsum_Un_zero) |
1387 using fP thp0 by auto |
1190 using fP thp0 by auto |
1388 also have "\<dots> \<le> 2*e" using Pne Ppe by arith |
1191 also have "\<dots> \<le> 2*e" using Pne Ppe by arith |
1389 finally show "setsum (\<lambda>x. \<bar>f x $ i\<bar>) P \<le> 2*e" . |
1192 finally show "setsum (\<lambda>x. \<bar>f x $ i\<bar>) P \<le> 2*e" . |
1390 qed |
1193 qed |
1391 finally show ?thesis . |
1194 finally show ?thesis . |
1392 qed |
1195 qed |
1393 |
1196 |
1394 lemma dot_lsum: "finite S \<Longrightarrow> setsum f S \<bullet> (y::'a::{comm_ring}^'n) = setsum (\<lambda>x. f x \<bullet> y) S " |
1197 lemma dot_lsum: "finite S \<Longrightarrow> setsum f S \<bullet> (y::'a::{comm_ring}^'n) = setsum (\<lambda>x. f x \<bullet> y) S " |
1395 by (induct rule: finite_induct, auto simp add: dot_lzero dot_ladd) |
1198 by (induct rule: finite_induct, auto simp add: dot_lzero dot_ladd dot_radd) |
1396 |
1199 |
1397 lemma dot_rsum: "finite S \<Longrightarrow> (y::'a::{comm_ring}^'n) \<bullet> setsum f S = setsum (\<lambda>x. y \<bullet> f x) S " |
1200 lemma dot_rsum: "finite S \<Longrightarrow> (y::'a::{comm_ring}^'n) \<bullet> setsum f S = setsum (\<lambda>x. y \<bullet> f x) S " |
1398 by (induct rule: finite_induct, auto simp add: dot_rzero dot_radd) |
1201 by (induct rule: finite_induct, auto simp add: dot_rzero dot_radd) |
1399 |
1202 |
1400 subsection{* Basis vectors in coordinate directions. *} |
1203 subsection{* Basis vectors in coordinate directions. *} |
5292 {assume h: "?rhs" |
5096 {assume h: "?rhs" |
5293 then obtain c where c: "y = c*s x" using x y by blast |
5097 then obtain c where c: "y = c*s x" using x y by blast |
5294 have ?lhs unfolding collinear_def c |
5098 have ?lhs unfolding collinear_def c |
5295 apply (rule exI[where x=x]) |
5099 apply (rule exI[where x=x]) |
5296 apply auto |
5100 apply auto |
5297 apply (rule exI[where x=0], simp) |
|
5298 apply (rule exI[where x="- 1"], simp only: vector_smult_lneg vector_smult_lid) |
5101 apply (rule exI[where x="- 1"], simp only: vector_smult_lneg vector_smult_lid) |
5299 apply (rule exI[where x= "-c"], simp only: vector_smult_lneg) |
5102 apply (rule exI[where x= "-c"], simp only: vector_smult_lneg) |
5300 apply (rule exI[where x=1], simp) |
5103 apply (rule exI[where x=1], simp) |
5301 apply (rule exI[where x=0], simp) |
|
5302 apply (rule exI[where x="1 - c"], simp add: vector_smult_lneg vector_sub_rdistrib) |
5104 apply (rule exI[where x="1 - c"], simp add: vector_smult_lneg vector_sub_rdistrib) |
5303 apply (rule exI[where x="c - 1"], simp add: vector_smult_lneg vector_sub_rdistrib) |
5105 apply (rule exI[where x="c - 1"], simp add: vector_smult_lneg vector_sub_rdistrib) |
5304 apply (rule exI[where x=0], simp) |
|
5305 done} |
5106 done} |
5306 ultimately have ?thesis by blast} |
5107 ultimately have ?thesis by blast} |
5307 ultimately show ?thesis by blast |
5108 ultimately show ?thesis by blast |
5308 qed |
5109 qed |
5309 |
5110 |