# HG changeset patch # User paulson # Date 1530042529 -3600 # Node ID 6b5f15387353f99c43210b5792a4008cd8c3da85 # Parent 0854edc4d415b4fad6d8751cafa74702fa79e71f a few new lemmas diff -r 0854edc4d415 -r 6b5f15387353 src/HOL/Algebra/Coset.thy --- a/src/HOL/Algebra/Coset.thy Tue Jun 26 19:29:14 2018 +0200 +++ b/src/HOL/Algebra/Coset.thy Tue Jun 26 20:48:49 2018 +0100 @@ -50,13 +50,9 @@ shows "H #> x = H <#> {x}" unfolding r_coset_def set_mult_def by simp -(* ************************************************************************** *) - - -(* ************************************************************************** *) (* Next five lemmas contributed by Paulo Emílio de Vilhena. *) -lemma (in subgroup) rcosets_not_empty: +lemma (in subgroup) rcosets_non_empty: assumes "R \ rcosets H" shows "R \ {}" proof - @@ -87,6 +83,9 @@ thus "r1 \ inv r2 \ H" by (metis assms(1) h1(1) h2(1) subgroup_def) qed +lemma mono_set_mult: "\ H \ H'; K \ K' \ \ H <#>\<^bsub>G\<^esub> K \ H' <#>\<^bsub>G\<^esub> K'" + unfolding set_mult_def by (simp add: UN_mono) + subsection \Stable Operations for Subgroups\ @@ -105,7 +104,17 @@ shows "h <#\<^bsub>G \ carrier := H \\<^esub> I = h <# I" using subgroup_set_mult_equality by (simp add: l_coset_eq_set_mult assms) - +lemma set_mult_consistent [simp]: + "N <#>\<^bsub>(G \ carrier := H \)\<^esub> K = N <#>\<^bsub>G\<^esub> K" + unfolding set_mult_def by simp + +lemma r_coset_consistent [simp]: + "I #>\<^bsub>G \ carrier := H \\<^esub> h = I #>\<^bsub>G\<^esub> h" + unfolding r_coset_def by simp + +lemma l_coset_consistent [simp]: + "h <#\<^bsub>G \ carrier := H \\<^esub> I = h <#\<^bsub>G\<^esub> I" + unfolding l_coset_def by simp subsection \Basic Properties of set multiplication\ @@ -1123,15 +1132,15 @@ unfolding r_coset_def Sigma_def DirProd_def FactGroup_def RCOSETS_def apply simp by blast moreover have "(\x\carrier (G Mod H). \y\carrier (K Mod N). \xa\carrier (G Mod H). \ya\carrier (K Mod N). (x <#> xa) \ (y <#>\<^bsub>K\<^esub> ya) = x \ y <#>\<^bsub>G \\ K\<^esub> xa \ ya)" - unfolding set_mult_def apply auto apply blast+. + unfolding set_mult_def by force moreover have "(\x\carrier (G Mod H). \y\carrier (K Mod N). \xa\carrier (G Mod H). \ya\carrier (K Mod N). x \ y = xa \ ya \ x = xa \ y = ya)" - unfolding FactGroup_def using times_eq_iff subgroup.rcosets_not_empty + unfolding FactGroup_def using times_eq_iff subgroup.rcosets_non_empty by (metis assms(2) assms(3) normal_def partial_object.select_convs(1)) moreover have "(\(X, Y). X \ Y) ` (carrier (G Mod H) \ carrier (K Mod N)) = carrier (G \\ K Mod H \ N)" unfolding image_def apply auto using R apply force - unfolding DirProd_def FactGroup_def RCOSETS_def r_coset_def apply auto apply force. + unfolding DirProd_def FactGroup_def RCOSETS_def r_coset_def by force ultimately show ?thesis unfolding iso_def hom_def bij_betw_def inj_on_def by simp qed diff -r 0854edc4d415 -r 6b5f15387353 src/HOL/Algebra/FiniteProduct.thy --- a/src/HOL/Algebra/FiniteProduct.thy Tue Jun 26 19:29:14 2018 +0200 +++ b/src/HOL/Algebra/FiniteProduct.thy Tue Jun 26 20:48:49 2018 +0100 @@ -31,9 +31,7 @@ foldD :: "['a set, 'b \ 'a \ 'a, 'a, 'b set] \ 'a" where "foldD D f e A = (THE x. (A, x) \ foldSetD D f e)" -lemma foldSetD_closed: - "\(A, z) \ foldSetD D f e; e \ D; \x y. \x \ A; y \ D\ \ f x y \ D\ - \ z \ D" +lemma foldSetD_closed: "(A, z) \ foldSetD D f e \ z \ D" by (erule foldSetD.cases) auto lemma Diff1_foldSetD: @@ -58,8 +56,12 @@ then show ?case .. qed +lemma foldSetD_backwards: + assumes "A \ {}" "(A, z) \ foldSetD D f e" + shows "\x y. x \ A \ (A - { x }, y) \ foldSetD D f e \ z = f x y" + using assms(2) by (cases) (simp add: assms(1), metis Diff_insert_absorb insertI1) -text \Left-Commutative Operations\ +subsubsection \Left-Commutative Operations\ locale LCD = fixes B :: "'b set" @@ -392,9 +394,9 @@ \ finprod G g (A Un B) = finprod G g A \ finprod G g B" by (metis Pi_split_domain finprod_Un_Int finprod_closed finprod_empty r_one) -lemma finprod_multf: +lemma finprod_multf [simp]: "\f \ A \ carrier G; g \ A \ carrier G\ \ - finprod G (%x. f x \ g x) A = (finprod G f A \ finprod G g A)" + finprod G (\x. f x \ g x) A = (finprod G f A \ finprod G g A)" proof (induct A rule: infinite_finite_induct) case empty show ?case by simp next @@ -472,7 +474,20 @@ lemma finprod_0 [simp]: "f \ {0::nat} \ carrier G \ finprod G f {..0} = f 0" -by (simp add: Pi_def) + by (simp add: Pi_def) + +lemma finprod_0': + "f \ {..n} \ carrier G \ (f 0) \ finprod G f {Suc 0..n} = finprod G f {..n}" +proof - + assume A: "f \ {.. n} \ carrier G" + hence "(f 0) \ finprod G f {Suc 0..n} = finprod G f {..0} \ finprod G f {Suc 0..n}" + using finprod_0[of f] by (simp add: funcset_mem) + also have " ... = finprod G f ({..0} \ {Suc 0..n})" + using finprod_Un_disjoint[of "{..0}" "{Suc 0..n}" f] A by (simp add: funcset_mem) + also have " ... = finprod G f {..n}" + by (simp add: atLeastAtMost_insertL atMost_atLeast0) + finally show ?thesis . +qed lemma finprod_Suc [simp]: "f \ {..Suc n} \ carrier G \ @@ -488,11 +503,19 @@ case Suc thus ?case by (simp add: m_assoc Pi_def) qed -lemma finprod_mult [simp]: - "\f \ {..n} \ carrier G; g \ {..n} \ carrier G\ \ - finprod G (%i. f i \ g i) {..n::nat} = - finprod G f {..n} \ finprod G g {..n}" - by (induct n) (simp_all add: m_ac Pi_def) +lemma finprod_Suc3: + assumes "f \ {..n :: nat} \ carrier G" + shows "finprod G f {.. n} = (f n) \ finprod G f {..< n}" +proof (cases "n = 0") + case True thus ?thesis + using assms atMost_Suc by simp +next + case False + then obtain k where "n = Suc k" + using not0_implies_Suc by blast + thus ?thesis + using finprod_Suc[of f k] assms atMost_Suc lessThan_Suc_atMost by simp +qed (* The following two were contributed by Jeremy Avigad. *) @@ -546,7 +569,6 @@ also have "(\x\carrier G. a) = a [^] card(carrier G)" by (auto simp add: finprod_const) finally show ?thesis -(* uses the preceeding lemma *) by auto qed @@ -573,8 +595,6 @@ lemma (in comm_monoid) finprod_Union_disjoint: "\finite C; \A. A \ C \ finite A \ (\x\A. f x \ carrier G); pairwise disjnt C\ \ finprod G f (\C) = finprod G (finprod G f) C" - apply (frule finprod_UN_disjoint [of C id f]) - apply auto - done + by (frule finprod_UN_disjoint [of C id f]) auto end diff -r 0854edc4d415 -r 6b5f15387353 src/HOL/Algebra/Group.thy --- a/src/HOL/Algebra/Group.thy Tue Jun 26 19:29:14 2018 +0200 +++ b/src/HOL/Algebra/Group.thy Tue Jun 26 20:48:49 2018 +0100 @@ -535,6 +535,32 @@ show "\ \ H " using monoid.one_closed[OF assms(2)] assms by simp qed +lemma (in monoid) inv_unique': + assumes "x \ carrier G" "y \ carrier G" + shows "\ x \ y = \; y \ x = \ \ \ y = inv x" +proof - + assume "x \ y = \" and l_inv: "y \ x = \" + hence unit: "x \ Units G" + using assms unfolding Units_def by auto + show "y = inv x" + using inv_unique[OF l_inv Units_r_inv[OF unit] assms Units_inv_closed[OF unit]] . +qed + +lemma (in monoid) m_inv_monoid_consistent: (* contributed by Paulo *) + assumes "x \ Units (G \ carrier := H \)" and "submonoid H G" + shows "inv\<^bsub>(G \ carrier := H \)\<^esub> x = inv x" +proof - + have monoid: "monoid (G \ carrier := H \)" + using submonoid.submonoid_is_monoid[OF assms(2) monoid_axioms] . + obtain y where y: "y \ H" "x \ y = \" "y \ x = \" + using assms(1) unfolding Units_def by auto + have x: "x \ H" and in_carrier: "x \ carrier G" "y \ carrier G" + using y(1) submonoid.subset[OF assms(2)] assms(1) unfolding Units_def by auto + show ?thesis + using monoid.inv_unique'[OF monoid, of x y] x y + using inv_unique'[OF in_carrier y(2-3)] by auto +qed + subsection \Subgroups\ locale subgroup = @@ -620,16 +646,13 @@ show "\ \ H" by (rule one_in_subset) (auto simp only: assms) qed - lemma (in group) subgroupE: assumes "subgroup H G" shows "H \ carrier G" and "H \ {}" and "\a. a \ H \ inv a \ H" - and "\a b. \a \ H; b \ H\ \ a \ b \ H" - using assms subgroup.subset apply blast - using assms subgroup_def apply auto[1] - by (simp add: assms subgroup.m_closed subgroup.m_inv_closed)+ + and "\a b. \ a \ H; b \ H \ \ a \ b \ H" + using assms unfolding subgroup_def[of H G] by auto declare monoid.one_closed [iff] group.inv_closed [simp] monoid.l_one [simp] monoid.r_one [simp] group.inv_inv [simp] @@ -638,14 +661,8 @@ "\ subgroup {} G" by (blast dest: subgroup.one_closed) -lemma (in subgroup) finite_imp_card_positive: - "finite (carrier G) ==> 0 < card H" -proof (rule classical) - assume "finite (carrier G)" and a: "\ 0 < card H" - then have "finite H" by (blast intro: finite_subset [OF subset]) - with is_subgroup a have "subgroup {} G" by simp - with subgroup_nonempty show ?thesis by contradiction -qed +lemma (in subgroup) finite_imp_card_positive: "finite (carrier G) \ 0 < card H" + using subset one_closed card_gt_0_iff finite_subset by blast (*Following 3 lemmas contributed by Martin Baillon*) @@ -1219,21 +1236,24 @@ finally show "x \\<^bsub>(?h_img)\<^esub> y = y \\<^bsub>(?h_img)\<^esub> x" . qed +lemma (in comm_group) hom_imp_img_comm_group: + assumes "h \ hom G H" + shows "comm_group (H \ carrier := h ` (carrier G), one := h \\<^bsub>G\<^esub> \)" + unfolding comm_group_def + using hom_imp_img_group[OF assms] hom_imp_img_comm_monoid[OF assms] by simp + lemma (in comm_group) iso_imp_img_comm_group: assumes "h \ iso G H" shows "comm_group (H \ one := h \\<^bsub>G\<^esub> \)" proof - let ?h_img = "H \ carrier := h ` (carrier G), one := h \ \" - have "comm_monoid ?h_img" - using hom_imp_img_comm_monoid[of h H] assms unfolding iso_def by simp + have "comm_group ?h_img" + using hom_imp_img_comm_group[of h H] assms unfolding iso_def by auto moreover have "carrier H = carrier ?h_img" using assms unfolding iso_def bij_betw_def by simp hence "H \ one := h \ \ = ?h_img" by simp - ultimately have "comm_monoid (H \ one := h \\<^bsub>G\<^esub> \)" - by simp - thus ?thesis - unfolding comm_group_def using iso_imp_img_group[OF assms] by simp + ultimately show ?thesis by simp qed lemma (in comm_group) iso_imp_comm_group: diff -r 0854edc4d415 -r 6b5f15387353 src/HOL/Algebra/Group_Action.thy --- a/src/HOL/Algebra/Group_Action.thy Tue Jun 26 19:29:14 2018 +0200 +++ b/src/HOL/Algebra/Group_Action.thy Tue Jun 26 20:48:49 2018 +0100 @@ -319,7 +319,7 @@ corollary (in group_action) stab_rcosets_not_empty: assumes "x \ E" "R \ rcosets (stabilizer G \ x)" shows "R \ {}" - using subgroup.rcosets_not_empty[OF stabilizer_subgroup[OF assms(1)] assms(2)] by simp + using subgroup.rcosets_non_empty[OF stabilizer_subgroup[OF assms(1)] assms(2)] by simp corollary (in group_action) diff_stabilizes: assumes "x \ E" "R \ rcosets (stabilizer G \ x)" diff -r 0854edc4d415 -r 6b5f15387353 src/HOL/Algebra/Ring.thy --- a/src/HOL/Algebra/Ring.thy Tue Jun 26 19:29:14 2018 +0200 +++ b/src/HOL/Algebra/Ring.thy Tue Jun 26 20:48:49 2018 +0100 @@ -103,7 +103,7 @@ lemma (in abelian_monoid) a_monoid: "monoid (add_monoid G)" -by (rule comm_monoid.axioms, rule a_comm_monoid) +by (rule comm_monoid.axioms, rule a_comm_monoid) lemma (in abelian_group) a_group: "group (add_monoid G)" @@ -125,7 +125,7 @@ context abelian_monoid begin -lemmas a_closed = add.m_closed +lemmas a_closed = add.m_closed lemmas zero_closed = add.one_closed lemmas a_assoc = add.m_assoc lemmas l_zero = add.l_one @@ -160,7 +160,6 @@ lemmas finsum_0 = add.finprod_0 lemmas finsum_Suc = add.finprod_Suc lemmas finsum_Suc2 = add.finprod_Suc2 -lemmas finsum_add = add.finprod_mult lemmas finsum_infinite = add.finprod_infinite lemmas finsum_cong = add.finprod_cong @@ -228,7 +227,7 @@ by (rule a_comm_group) (auto simp: m_inv_def a_inv_def finsum_def add_pow_def) lemmas (in abelian_group) minus_add = add.inv_mult - + text \Derive an \abelian_group\ from a \comm_group\\ lemma comm_group_abelian_groupI: @@ -316,7 +315,7 @@ note [simp] = comm_monoid.axioms [OF comm_monoid] abelian_group.axioms [OF abelian_group] abelian_monoid.a_closed - + from R have "z \ (x \ y) = (x \ y) \ z" by (simp add: comm_monoid.m_comm [OF comm_monoid.intro]) also from R have "... = x \ z \ y \ z" by (simp add: l_distr) @@ -351,7 +350,7 @@ "\ x \ carrier G; y \ carrier G \ \ (\ x) \ (x \ y) = y" proof - assume G: "x \ carrier G" "y \ carrier G" - then have "(\ x \ x) \ y = y" + then have "(\ x \ x) \ y = y" by (simp only: l_neg l_zero) with G show ?thesis by (simp add: a_ac) qed @@ -439,7 +438,7 @@ [algebra ring "zero R" "add R" "a_inv R" "a_minus R" "one R" "mult R"] = a_closed zero_closed m_closed one_closed a_assoc l_zero a_comm m_assoc l_one l_distr r_zero - a_lcomm r_distr l_null r_null + a_lcomm r_distr l_null r_null lemmas (in ring) ring_simprules [algebra ring "zero R" "add R" "a_inv R" "a_minus R" "one R" "mult R"] = @@ -549,7 +548,7 @@ by (simp add: add_pow_def int_pow_def nat_pow_def) lemma add_pow_int_lt: "(k :: int) < 0 \ [ k ] \\<^bsub>R\<^esub> a = \\<^bsub>R\<^esub> ([ nat (- k) ] \\<^bsub>R\<^esub> a)" - by (simp add: int_pow_def nat_pow_def a_inv_def add_pow_def) + by (simp add: int_pow_def nat_pow_def a_inv_def add_pow_def) corollary (in semiring) add_pow_ldistr: assumes "a \ carrier R" "b \ carrier R" @@ -575,7 +574,7 @@ also have " ... = [k] \ (a \ b)" using add.finprod_const[of "a \ b" "{.. b"] - add_pow_ldistr[OF assms, of "nat (- k)"] assms l_minus by auto + add_pow_ldistr[OF assms, of "nat (- k)"] assms l_minus by auto qed lemma (in ring) add_pow_rdistr_int: @@ -599,7 +598,7 @@ next case False thus ?thesis using add_pow_int_lt[of k R b] add_pow_int_lt[of k R "a \ b"] - add_pow_rdistr[OF assms, of "nat (- k)"] assms r_minus by auto + add_pow_rdistr[OF assms, of "nat (- k)"] assms r_minus by auto qed @@ -628,7 +627,7 @@ assume eq: "a \ b = a \ c" with R have "a \ (b \ c) = \" by algebra with R have "a = \ \ (b \ c) = \" by (simp add: integral_iff) - with prem and R have "b \ c = \" by auto + with prem and R have "b \ c = \" by auto with R have "b = b \ (b \ c)" by algebra also from R have "b \ (b \ c) = c" by algebra finally show "b = c" . diff -r 0854edc4d415 -r 6b5f15387353 src/HOL/Analysis/Complex_Transcendental.thy --- a/src/HOL/Analysis/Complex_Transcendental.thy Tue Jun 26 19:29:14 2018 +0200 +++ b/src/HOL/Analysis/Complex_Transcendental.thy Tue Jun 26 20:48:49 2018 +0100 @@ -777,6 +777,23 @@ definition Arg2pi :: "complex \ real" where "Arg2pi z \ if z = 0 then 0 else THE t. 0 \ t \ t < 2*pi \ is_Arg z t" +lemma is_Arg_2pi_iff: "is_Arg z (r + of_int k * (2 * pi)) \ is_Arg z r" + by (simp add: algebra_simps is_Arg_def) + +lemma is_Arg_eqI: + assumes r: "is_Arg z r" and s: "is_Arg z s" and rs: "abs (r-s) < 2*pi" and "z \ 0" + shows "r = s" +proof - + have zr: "z = (cmod z) * exp (\ * r)" and zs: "z = (cmod z) * exp (\ * s)" + using r s by (auto simp: is_Arg_def) + with \z \ 0\ have eq: "exp (\ * r) = exp (\ * s)" + by (metis mult_eq_0_iff vector_space_over_itself.scale_left_imp_eq) + have "\ * r = \ * s" + by (rule exp_complex_eqI) (use rs in \auto simp: eq exp_complex_eqI\) + then show ?thesis + by simp +qed + text\This function returns the angle of a complex number from its representation in polar coordinates. Due to periodicity, its range is arbitrary. @{term Arg2pi} follows HOL Light in adopting the interval $[0,2\pi)$. But we have the same periodicity issue with logarithms, and it is usual to adopt the same interval @@ -924,9 +941,6 @@ using Arg2pi_eq_0 Arg2pi_ge_0 assms dual_order.strict_iff_order unfolding nonneg_Reals_def by fastforce -lemma Arg2pi_of_real: "Arg2pi(of_real x) = 0 \ 0 \ x" - by (simp add: Arg2pi_eq_0) - lemma Arg2pi_eq_pi: "Arg2pi z = pi \ z \ \ \ Re z < 0" using Arg2pi_le_pi [of z] Arg2pi_lt_pi [of z] Arg2pi_eq_0 [of z] Arg2pi_ge_0 [of z] by (fastforce simp: complex_is_Real_iff) @@ -934,6 +948,9 @@ lemma Arg2pi_eq_0_pi: "Arg2pi z = 0 \ Arg2pi z = pi \ z \ \" using Arg2pi_eq_0 Arg2pi_eq_pi not_le by auto +lemma Arg2pi_of_real: "Arg2pi (of_real r) = (if r<0 then pi else 0)" + using Arg2pi_eq_0_pi Arg2pi_eq_pi by fastforce + lemma Arg2pi_real: "z \ \ \ Arg2pi z = (if 0 \ Re z then 0 else pi)" using Arg2pi_eq_0 Arg2pi_eq_0_pi by auto @@ -1654,8 +1671,8 @@ corollary Arg_ne_0: assumes "z \ \\<^sub>\\<^sub>0" shows "Arg z \ 0" using assms by (auto simp: nonneg_Reals_def Arg_eq_0) -lemma Arg_of_real: "Arg(of_real x) = 0 \ 0 \ x" - by (simp add: Arg_eq_0) +lemma Arg_of_real: "Arg (of_real r) = (if r<0 then pi else 0)" + by (simp add: Im_Ln_eq_pi Arg_def) lemma Arg_eq_pi_iff: "Arg z = pi \ z \ \ \ Re z < 0" proof (cases "z=0") @@ -1712,6 +1729,22 @@ lemma Ln_Arg: "z\0 \ Ln(z) = ln(norm z) + \ * Arg(z)" by (metis Arg_def Re_Ln complex_eq) +lemma continuous_at_Arg: + assumes "z \ \\<^sub>\\<^sub>0" + shows "continuous (at z) Arg" +proof - + have [simp]: "(\z. Im (Ln z)) \z\ Arg z" + using Arg_def assms continuous_at by fastforce + show ?thesis + unfolding continuous_at + proof (rule Lim_transform_within_open) + show "\w. \w \ - \\<^sub>\\<^sub>0; w \ z\ \ Im (Ln w) = Arg w" + by (metis Arg_def Compl_iff nonpos_Reals_zero_I) + qed (use assms in auto) +qed + +lemma continuous_within_Arg: "z \ \\<^sub>\\<^sub>0 \ continuous (at z within S) Arg" + using continuous_at_Arg continuous_at_imp_continuous_within by blast subsection\Relation between Ln and Arg2pi, and hence continuity of Arg2pi\ @@ -4061,10 +4094,8 @@ moreover have "\z\sphere 0 1. \ x = \ (Arg2pi z / (2*pi))" if "0 \ x" "x \ 1" for x proof (cases "x=1") case True - then show ?thesis - apply (rule_tac x=1 in bexI) - apply (metis loop Arg2pi_of_real divide_eq_0_iff of_real_1 pathfinish_def pathstart_def \0 \ x\, auto) - done + with Arg2pi_of_real [of 1] loop show ?thesis + by (rule_tac x=1 in bexI) (auto simp: pathfinish_def pathstart_def \0 \ x\) next case False then have *: "(Arg2pi (exp (\*(2* of_real pi* of_real x))) / (2*pi)) = x" diff -r 0854edc4d415 -r 6b5f15387353 src/HOL/Analysis/Infinite_Products.thy --- a/src/HOL/Analysis/Infinite_Products.thy Tue Jun 26 19:29:14 2018 +0200 +++ b/src/HOL/Analysis/Infinite_Products.thy Tue Jun 26 20:48:49 2018 +0100 @@ -1418,14 +1418,16 @@ assumes ge0:"\n. f n \ 0" and ac: "abs_convergent_prod (\n. exp (f n))" shows "prodinf (\i. exp (f i)) = exp (suminf f)" proof - - have "summable f" + have "summable f" using ac unfolding abs_convergent_prod_conv_summable proof (elim summable_comparison_test') fix n - show "norm (f n) \ norm (exp (f n) - 1)" - using ge0[of n] - by (metis abs_of_nonneg add.commute diff_add_cancel diff_ge_0_iff_ge exp_ge_add_one_self - exp_le_cancel_iff one_le_exp_iff real_norm_def) + have "\f n\ = f n" + by (simp add: ge0) + also have "\ \ exp (f n) - 1" + by (metis diff_diff_add exp_ge_add_one_self ge_iff_diff_ge_0) + finally show "norm (f n) \ norm (exp (f n) - 1)" + by simp qed then show ?thesis by (simp add: prodinf_exp)