# HG changeset patch # User paulson # Date 1532258964 -7200 # Node ID 22d10f94811ed2b29872b572a9883b49eddef1a3 # Parent 205749fba102de5f2ab7f65b2f06a02fad5aa905 de-applying diff -r 205749fba102 -r 22d10f94811e src/HOL/Algebra/QuotRing.thy --- a/src/HOL/Algebra/QuotRing.thy Sat Jul 21 23:25:22 2018 +0200 +++ b/src/HOL/Algebra/QuotRing.thy Sun Jul 22 13:29:24 2018 +0200 @@ -16,61 +16,34 @@ where "rcoset_mult R I A B = (\a\A. \b\B. I +>\<^bsub>R\<^esub> (a \\<^bsub>R\<^esub> b))" -text \@{const "rcoset_mult"} fulfils the properties required by - congruences\ +text \@{const "rcoset_mult"} fulfils the properties required by congruences\ lemma (in ideal) rcoset_mult_add: - "x \ carrier R \ y \ carrier R \ [mod I:] (I +> x) \ (I +> y) = I +> (x \ y)" - apply rule - apply (rule, simp add: rcoset_mult_def, clarsimp) - defer 1 - apply (rule, simp add: rcoset_mult_def) - defer 1 + assumes "x \ carrier R" "y \ carrier R" + shows "[mod I:] (I +> x) \ (I +> y) = I +> (x \ y)" proof - - fix z x' y' - assume carr: "x \ carrier R" "y \ carrier R" - and x'rcos: "x' \ I +> x" - and y'rcos: "y' \ I +> y" - and zrcos: "z \ I +> x' \ y'" - - from x'rcos have "\h\I. x' = h \ x" - by (simp add: a_r_coset_def r_coset_def) - then obtain hx where hxI: "hx \ I" and x': "x' = hx \ x" - by fast+ - - from y'rcos have "\h\I. y' = h \ y" - by (simp add: a_r_coset_def r_coset_def) - then obtain hy where hyI: "hy \ I" and y': "y' = hy \ y" - by fast+ - - from zrcos have "\h\I. z = h \ (x' \ y')" - by (simp add: a_r_coset_def r_coset_def) - then obtain hz where hzI: "hz \ I" and z: "z = hz \ (x' \ y')" - by fast+ - - note carr = carr hxI[THEN a_Hcarr] hyI[THEN a_Hcarr] hzI[THEN a_Hcarr] - - from z have "z = hz \ (x' \ y')" . - also from x' y' have "\ = hz \ ((hx \ x) \ (hy \ y))" by simp - also from carr have "\ = (hz \ (hx \ (hy \ y)) \ x \ hy) \ x \ y" by algebra - finally have z2: "z = (hz \ (hx \ (hy \ y)) \ x \ hy) \ x \ y" . - - from hxI hyI hzI carr have "hz \ (hx \ (hy \ y)) \ x \ hy \ I" - by (simp add: I_l_closed I_r_closed) - - with z2 have "\h\I. z = h \ x \ y" by fast - then show "z \ I +> x \ y" by (simp add: a_r_coset_def r_coset_def) -next - fix z - assume xcarr: "x \ carrier R" - and ycarr: "y \ carrier R" - and zrcos: "z \ I +> x \ y" - from xcarr have xself: "x \ I +> x" by (intro a_rcos_self) - from ycarr have yself: "y \ I +> y" by (intro a_rcos_self) - show "\a\I +> x. \b\I +> y. z \ I +> a \ b" - using xself and yself and zrcos by fast + have 1: "z \ I +> x \ y" + if x'rcos: "x' \ I +> x" and y'rcos: "y' \ I +> y" and zrcos: "z \ I +> x' \ y'" for z x' y' + proof - + from that + obtain hx hy hz where hxI: "hx \ I" and x': "x' = hx \ x" and hyI: "hy \ I" and y': "y' = hy \ y" + and hzI: "hz \ I" and z: "z = hz \ (x' \ y')" + by (auto simp: a_r_coset_def r_coset_def) + note carr = assms hxI[THEN a_Hcarr] hyI[THEN a_Hcarr] hzI[THEN a_Hcarr] + from z x' y' have "z = hz \ ((hx \ x) \ (hy \ y))" by simp + also from carr have "\ = (hz \ (hx \ (hy \ y)) \ x \ hy) \ x \ y" by algebra + finally have z2: "z = (hz \ (hx \ (hy \ y)) \ x \ hy) \ x \ y" . + from hxI hyI hzI carr have "hz \ (hx \ (hy \ y)) \ x \ hy \ I" + by (simp add: I_l_closed I_r_closed) + with z2 show ?thesis + by (auto simp add: a_r_coset_def r_coset_def) + qed + have 2: "\a\I +> x. \b\I +> y. z \ I +> a \ b" if "z \ I +> x \ y" for z + using assms a_rcos_self that by blast + show ?thesis + unfolding rcoset_mult_def using assms + by (auto simp: intro!: 1 2) qed - subsection \Quotient Ring Definition\ definition FactRing :: "[('a,'b) ring_scheme, 'a set] \ ('a set) ring" @@ -79,59 +52,30 @@ \carrier = a_rcosets\<^bsub>R\<^esub> I, mult = rcoset_mult R I, one = (I +>\<^bsub>R\<^esub> \\<^bsub>R\<^esub>), zero = I, add = set_add R\" +lemmas FactRing_simps = FactRing_def A_RCOSETS_defs a_r_coset_def[symmetric] subsection \Factorization over General Ideals\ text \The quotient is a ring\ lemma (in ideal) quotient_is_ring: "ring (R Quot I)" -apply (rule ringI) - \ \abelian group\ - apply (rule comm_group_abelian_groupI) - apply (simp add: FactRing_def) - apply (rule a_factorgroup_is_comm_group[unfolded A_FactGroup_def']) - \ \mult monoid\ - apply (rule monoidI) - apply (simp_all add: FactRing_def A_RCOSETS_def RCOSETS_def - a_r_coset_def[symmetric]) - \ \mult closed\ - apply (clarify) - apply (simp add: rcoset_mult_add, fast) - \ \mult \one_closed\\ - apply force - \ \mult assoc\ - apply clarify - apply (simp add: rcoset_mult_add m_assoc) - \ \mult one\ - apply clarify - apply (simp add: rcoset_mult_add) - apply clarify - apply (simp add: rcoset_mult_add) - \ \distr\ - apply clarify - apply (simp add: rcoset_mult_add a_rcos_sum l_distr) -apply clarify -apply (simp add: rcoset_mult_add a_rcos_sum r_distr) -done +proof (rule ringI) + show "abelian_group (R Quot I)" + apply (rule comm_group_abelian_groupI) + apply (simp add: FactRing_def a_factorgroup_is_comm_group[unfolded A_FactGroup_def']) + done + show "Group.monoid (R Quot I)" + by (rule monoidI) + (auto simp add: FactRing_simps rcoset_mult_add m_assoc) +qed (auto simp: FactRing_simps rcoset_mult_add a_rcos_sum l_distr r_distr) text \This is a ring homomorphism\ lemma (in ideal) rcos_ring_hom: "((+>) I) \ ring_hom R (R Quot I)" -apply (rule ring_hom_memI) - apply (simp add: FactRing_def a_rcosetsI[OF a_subset]) - apply (simp add: FactRing_def rcoset_mult_add) - apply (simp add: FactRing_def a_rcos_sum) -apply (simp add: FactRing_def) -done + by (simp add: ring_hom_memI FactRing_def a_rcosetsI[OF a_subset] rcoset_mult_add a_rcos_sum) lemma (in ideal) rcos_ring_hom_ring: "ring_hom_ring R (R Quot I) ((+>) I)" -apply (rule ring_hom_ringI) - apply (rule is_ring, rule quotient_is_ring) - apply (simp add: FactRing_def a_rcosetsI[OF a_subset]) - apply (simp add: FactRing_def rcoset_mult_add) - apply (simp add: FactRing_def a_rcos_sum) -apply (simp add: FactRing_def) -done + by (simp add: local.ring_axioms quotient_is_ring rcos_ring_hom ring_hom_ringI2) text \The quotient of a cring is also commutative\ lemma (in ideal) quotient_is_cring: @@ -140,12 +84,9 @@ proof - interpret cring R by fact show ?thesis - apply (intro cring.intro comm_monoid.intro comm_monoid_axioms.intro) - apply (rule quotient_is_ring) + apply (intro cring.intro comm_monoid.intro comm_monoid_axioms.intro quotient_is_ring) apply (rule ring.axioms[OF quotient_is_ring]) - apply (simp add: FactRing_def A_RCOSETS_defs a_r_coset_def[symmetric]) - apply clarify - apply (simp add: rcoset_mult_add m_comm) + apply (auto simp add: FactRing_simps rcoset_mult_add m_comm) done qed @@ -169,37 +110,19 @@ text \The quotient ring generated by a prime ideal is a domain\ lemma (in primeideal) quotient_is_domain: "domain (R Quot I)" - apply (rule domain.intro) - apply (rule quotient_is_cring, rule is_cring) - apply (rule domain_axioms.intro) - apply (simp add: FactRing_def) defer 1 - apply (simp add: FactRing_def A_RCOSETS_defs a_r_coset_def[symmetric], clarify) - apply (simp add: rcoset_mult_add) defer 1 -proof (rule ccontr, clarsimp) - assume "I +> \ = I" - then have "\ \ I" by (simp only: a_coset_join1 one_closed a_subgroup) - then have "carrier R \ I" by (subst one_imp_carrier, simp, fast) - with a_subset have "I = carrier R" by fast - with I_notcarr show False by fast -next - fix x y - assume carr: "x \ carrier R" "y \ carrier R" +proof - + have 1: "I +> \ = I \ False" + using I_notcarr a_rcos_self one_imp_carrier by blast + have 2: "I +> x = I" + if carr: "x \ carrier R" "y \ carrier R" and a: "I +> x \ y = I" - and b: "I +> y \ I" - - have ynI: "y \ I" - proof (rule ccontr, simp) - assume "y \ I" - then have "I +> y = I" by (rule a_rcos_const) - with b show False by simp - qed - - from carr have "x \ y \ I +> x \ y" by (simp add: a_rcos_self) - then have xyI: "x \ y \ I" by (simp add: a) - - from xyI and carr have xI: "x \ I \ y \ I" by (simp add: I_prime) - with ynI have "x \ I" by fast - then show "I +> x = I" by (rule a_rcos_const) + and b: "I +> y \ I" for x y + by (metis I_prime a a_rcos_const a_rcos_self b m_closed that) + show ?thesis + apply (intro domain.intro quotient_is_cring is_cring domain_axioms.intro) + apply (metis "1" FactRing_def monoid.simps(2) ring.simps(1)) + apply (simp add: FactRing_simps) + by (metis "2" rcoset_mult_add) qed text \Generating right cosets of a prime ideal is a homomorphism @@ -210,88 +133,58 @@ subsection \Factorization over Maximal Ideals\ -text \In a commutative ring, the quotient ring over a maximal ideal - is a field. - The proof follows ``W. Adkins, S. Weintraub: Algebra -- - An Approach via Module Theory''\ -lemma (in maximalideal) quotient_is_field: +text \In a commutative ring, the quotient ring over a maximal ideal is a field. + The proof follows ``W. Adkins, S. Weintraub: Algebra -- An Approach via Module Theory''\ +proposition (in maximalideal) quotient_is_field: assumes "cring R" shows "field (R Quot I)" proof - interpret cring R by fact - show ?thesis - apply (intro cring.cring_fieldI2) - apply (rule quotient_is_cring, rule is_cring) - defer 1 - apply (simp add: FactRing_def A_RCOSETS_defs a_r_coset_def[symmetric], clarsimp) - apply (simp add: rcoset_mult_add) defer 1 - proof (rule ccontr, simp) - \ \Quotient is not empty\ + have 1: "\\<^bsub>R Quot I\<^esub> \ \\<^bsub>R Quot I\<^esub>" \ \Quotient is not empty\ + proof assume "\\<^bsub>R Quot I\<^esub> = \\<^bsub>R Quot I\<^esub>" then have II1: "I = I +> \" by (simp add: FactRing_def) - from a_rcos_self[OF one_closed] have "\ \ I" - by (simp add: II1[symmetric]) - then have "I = carrier R" by (rule one_imp_carrier) + then have "I = carrier R" + using a_rcos_self one_imp_carrier by blast with I_notcarr show False by simp - next + qed + have 2: "\y\carrier R. I +> a \ y = I +> \" if IanI: "I +> a \ I" and acarr: "a \ carrier R" for a \ \Existence of Inverse\ - fix a - assume IanI: "I +> a \ I" and acarr: "a \ carrier R" - + proof - \ \Helper ideal \J\\ define J :: "'a set" where "J = (carrier R #> a) <+> I" have idealJ: "ideal J R" - apply (unfold J_def, rule add_ideals) - apply (simp only: cgenideal_eq_rcos[symmetric], rule cgenideal_ideal, rule acarr) - apply (rule is_ideal) - done - - \ \Showing @{term "J"} not smaller than @{term "I"}\ + using J_def acarr add_ideals cgenideal_eq_rcos cgenideal_ideal is_ideal by auto have IinJ: "I \ J" - proof (rule, simp add: J_def r_coset_def set_add_defs) + proof (clarsimp simp: J_def r_coset_def set_add_defs) fix x assume xI: "x \ I" - have Zcarr: "\ \ carrier R" by fast - from xI[THEN a_Hcarr] acarr - have "x = \ \ a \ x" by algebra - with Zcarr and xI show "\xa\carrier R. \k\I. x = xa \ a \ k" by fast - qed - - \ \Showing @{term "J \ I"}\ - have anI: "a \ I" - proof (rule ccontr, simp) - assume "a \ I" - then have "I +> a = I" by (rule a_rcos_const) - with IanI show False by simp + have "x = \ \ a \ x" + by (simp add: acarr xI) + with xI show "\xa\carrier R. \k\I. x = xa \ a \ k" by fast qed - - have aJ: "a \ J" - proof (simp add: J_def r_coset_def set_add_defs) - from acarr - have "a = \ \ a \ \" by algebra - with one_closed and additive_subgroup.zero_closed[OF is_additive_subgroup] - show "\x\carrier R. \k\I. a = x \ a \ k" by fast + have JnI: "J \ I" + proof - + have "a \ I" + using IanI a_rcos_const by blast + moreover have "a \ J" + proof (simp add: J_def r_coset_def set_add_defs) + from acarr + have "a = \ \ a \ \" by algebra + with one_closed and additive_subgroup.zero_closed[OF is_additive_subgroup] + show "\x\carrier R. \k\I. a = x \ a \ k" by fast + qed + ultimately show ?thesis by blast qed - - from aJ and anI have JnI: "J \ I" by fast - - \ \Deducing @{term "J = carrier R"} because @{term "I"} is maximal\ - from idealJ and IinJ have "J = I \ J = carrier R" - proof (rule I_maximal, unfold J_def) - have "carrier R #> a \ carrier R" - using subset_refl acarr by (rule r_coset_subset_G) - then show "carrier R #> a <+> I \ carrier R" - using a_subset by (rule set_add_closed) - qed - - with JnI have Jcarr: "J = carrier R" by simp + then have Jcarr: "J = carrier R" + using I_maximal IinJ additive_subgroup.a_subset idealJ ideal_def by blast \ \Calculating an inverse for @{term "a"}\ from one_closed[folded Jcarr] - have "\r\carrier R. \i\I. \ = r \ a \ i" - by (simp add: J_def r_coset_def set_add_defs) - then obtain r i where rcarr: "r \ carrier R" - and iI: "i \ I" and one: "\ = r \ a \ i" by fast + obtain r i where rcarr: "r \ carrier R" + and iI: "i \ I" and one: "\ = r \ a \ i" + by (auto simp add: J_def r_coset_def set_add_defs) + from one and rcarr and acarr and iI[THEN a_Hcarr] have rai1: "a \ r = \i \ \" by algebra @@ -305,6 +198,10 @@ from rcarr and this[symmetric] show "\r\carrier R. I +> a \ r = I +> \" by fast qed + show ?thesis + apply (intro cring.cring_fieldI2 quotient_is_cring is_cring 1) + apply (clarsimp simp add: FactRing_simps rcoset_mult_add 2) + done qed @@ -916,7 +813,7 @@ proof - fix X assume "X \ carrier (R Quot (a_kernel R S h))" thus "\x \ carrier R. X = (a_kernel R S h) +> x" - unfolding FactRing_def RCOSETS_def A_RCOSETS_def by (simp add: a_r_coset_def) + unfolding FactRing_simps by (simp add: a_r_coset_def) qed lemma (in ring_hom_ring) the_elem_wf: @@ -989,7 +886,7 @@ by (metis image_iff) hence "the_elem (h ` ((a_kernel R S h) +> x)) = y" by simp moreover have "(a_kernel R S h) +> x \ carrier (R Quot (a_kernel R S h))" - unfolding FactRing_def RCOSETS_def A_RCOSETS_def by (auto simp add: x a_r_coset_def) + unfolding FactRing_simps by (auto simp add: x a_r_coset_def) ultimately show "y \ (\X. (the_elem (h ` X))) ` carrier (R Quot (a_kernel R S h))" by blast qed qed diff -r 205749fba102 -r 22d10f94811e src/HOL/Algebra/Ring.thy --- a/src/HOL/Algebra/Ring.thy Sat Jul 21 23:25:22 2018 +0200 +++ b/src/HOL/Algebra/Ring.thy Sun Jul 22 13:29:24 2018 +0200 @@ -332,7 +332,7 @@ assumes "cring R" shows "comm_monoid R" and "\x y z. \ x \ carrier R; y \ carrier R; z \ carrier R \ \ (x \ y) \ z = x \ z \ y \ z" - using assms cring_def apply auto by (simp add: assms cring.axioms(1) ringE(3)) + using assms cring_def by auto (simp add: assms cring.axioms(1) ringE(3)) lemma (in cring) is_cring: "cring R" by (rule cring_axioms) @@ -481,10 +481,7 @@ qed lemma carrier_one_zero: "(carrier R = {\}) = (\ = \)" - apply rule - apply (erule one_zeroI) - apply (erule one_zeroD) - done + using one_zeroD by blast lemma carrier_one_not_zero: "(carrier R \ {\}) = (\ \ \)" by (simp add: carrier_one_zero) @@ -687,19 +684,22 @@ text \Another variant to show that something is a field\ lemma (in cring) cring_fieldI2: assumes notzero: "\ \ \" - and invex: "\a. \a \ carrier R; a \ \\ \ \b\carrier R. a \ b = \" + and invex: "\a. \a \ carrier R; a \ \\ \ \b\carrier R. a \ b = \" shows "field R" - apply (rule cring_fieldI, simp add: Units_def) - apply (rule, clarsimp) - apply (simp add: notzero) -proof (clarsimp) - fix x - assume xcarr: "x \ carrier R" - and "x \ \" - then have "\y\carrier R. x \ y = \" by (rule invex) - then obtain y where ycarr: "y \ carrier R" and xy: "x \ y = \" by fast - from xy xcarr ycarr have "y \ x = \" by (simp add: m_comm) - with ycarr and xy show "\y\carrier R. y \ x = \ \ x \ y = \" by fast +proof - + have *: "carrier R - {\} \ {y \ carrier R. \x\carrier R. x \ y = \ \ y \ x = \}" + proof (clarsimp) + fix x + assume xcarr: "x \ carrier R" and "x \ \" + obtain y where ycarr: "y \ carrier R" and xy: "x \ y = \" + using \x \ \\ invex xcarr by blast + with ycarr and xy show "\y\carrier R. y \ x = \ \ x \ y = \" + using m_comm xcarr by fastforce + qed + show ?thesis + apply (rule cring_fieldI, simp add: Units_def) + using * + using group_l_invI notzero set_diff_eq by auto qed @@ -859,57 +859,36 @@ subsection\Jeremy Avigad's @{text"More_Ring"} material\ -lemma (in cring) field_intro2: "\\<^bsub>R\<^esub> \ \\<^bsub>R\<^esub> \ \x \ carrier R - {\\<^bsub>R\<^esub>}. x \ Units R \ field R" - apply (unfold_locales) - apply (use cring_axioms in auto) - apply (rule trans) - apply (subgoal_tac "a = (a \ b) \ inv b") - apply assumption - apply (subst m_assoc) - apply auto - apply (unfold Units_def) - apply auto - done +lemma (in cring) field_intro2: + assumes "\\<^bsub>R\<^esub> \ \\<^bsub>R\<^esub>" and un: "\x. x \ carrier R - {\\<^bsub>R\<^esub>} \ x \ Units R" + shows "field R" +proof unfold_locales + show "\ \ \" using assms by auto + show "\a \ b = \; a \ carrier R; + b \ carrier R\ + \ a = \ \ b = \" for a b + by (metis un Units_l_cancel insert_Diff_single insert_iff r_null zero_closed) +qed (use assms in \auto simp: Units_def\) lemma (in monoid) inv_char: - "x \ carrier G \ y \ carrier G \ x \ y = \ \ y \ x = \ \ inv x = y" - apply (subgoal_tac "x \ Units G") - apply (subgoal_tac "y = inv x \ \") - apply simp - apply (erule subst) - apply (subst m_assoc [symmetric]) - apply auto - apply (unfold Units_def) - apply auto - done + assumes "x \ carrier G" "y \ carrier G" "x \ y = \" "y \ x = \" + shows "inv x = y" + using assms inv_unique' by auto lemma (in comm_monoid) comm_inv_char: "x \ carrier G \ y \ carrier G \ x \ y = \ \ inv x = y" by (simp add: inv_char m_comm) lemma (in ring) inv_neg_one [simp]: "inv (\ \) = \ \" - apply (rule inv_char) - apply (auto simp add: l_minus r_minus) - done + by (simp add: inv_char local.ring_axioms ring.r_minus) lemma (in monoid) inv_eq_imp_eq: "x \ Units G \ y \ Units G \ inv x = inv y \ x = y" - apply (subgoal_tac "inv (inv x) = inv (inv y)") - apply (subst (asm) Units_inv_inv)+ - apply auto - done + by (metis Units_inv_inv) lemma (in ring) Units_minus_one_closed [intro]: "\ \ \ Units R" - apply (unfold Units_def) - apply auto - apply (rule_tac x = "\ \" in bexI) - apply auto - apply (simp add: l_minus r_minus) - done + by (simp add: Units_def) (metis add.l_inv_ex local.minus_minus minus_equality one_closed r_minus r_one) lemma (in ring) inv_eq_neg_one_eq: "x \ Units R \ inv x = \ \ \ x = \ \" - apply auto - apply (subst Units_inv_inv [symmetric]) - apply auto - done + by (metis Units_inv_inv inv_neg_one) lemma (in monoid) inv_eq_one_eq: "x \ Units G \ inv x = \ \ x = \" by (metis Units_inv_inv inv_one)