src/HOL/Algebra/QuotRing.thy
 author haftmann Sun Jun 23 21:16:07 2013 +0200 (2013-06-23) changeset 52435 6646bb548c6b parent 45005 0d2d59525912 child 61382 efac889fccbc permissions -rw-r--r--
migration from code_(const|type|class|instance) to code_printing and from code_module to code_identifier
1 (*  Title:      HOL/Algebra/QuotRing.thy
2     Author:     Stephan Hohe
3 *)
5 theory QuotRing
6 imports RingHom
7 begin
9 section {* Quotient Rings *}
11 subsection {* Multiplication on Cosets *}
13 definition rcoset_mult :: "[('a, _) ring_scheme, 'a set, 'a set, 'a set] \<Rightarrow> 'a set"
14     ("[mod _:] _ \<Otimes>\<index> _" [81,81,81] 80)
15   where "rcoset_mult R I A B = (\<Union>a\<in>A. \<Union>b\<in>B. I +>\<^bsub>R\<^esub> (a \<otimes>\<^bsub>R\<^esub> b))"
18 text {* @{const "rcoset_mult"} fulfils the properties required by
19   congruences *}
20 lemma (in ideal) rcoset_mult_add:
21     "x \<in> carrier R \<Longrightarrow> y \<in> carrier R \<Longrightarrow> [mod I:] (I +> x) \<Otimes> (I +> y) = I +> (x \<otimes> y)"
22   apply rule
23   apply (rule, simp add: rcoset_mult_def, clarsimp)
24   defer 1
25   apply (rule, simp add: rcoset_mult_def)
26   defer 1
27 proof -
28   fix z x' y'
29   assume carr: "x \<in> carrier R" "y \<in> carrier R"
30     and x'rcos: "x' \<in> I +> x"
31     and y'rcos: "y' \<in> I +> y"
32     and zrcos: "z \<in> I +> x' \<otimes> y'"
34   from x'rcos have "\<exists>h\<in>I. x' = h \<oplus> x"
35     by (simp add: a_r_coset_def r_coset_def)
36   then obtain hx where hxI: "hx \<in> I" and x': "x' = hx \<oplus> x"
37     by fast+
39   from y'rcos have "\<exists>h\<in>I. y' = h \<oplus> y"
40     by (simp add: a_r_coset_def r_coset_def)
41   then obtain hy where hyI: "hy \<in> I" and y': "y' = hy \<oplus> y"
42     by fast+
44   from zrcos have "\<exists>h\<in>I. z = h \<oplus> (x' \<otimes> y')"
45     by (simp add: a_r_coset_def r_coset_def)
46   then obtain hz where hzI: "hz \<in> I" and z: "z = hz \<oplus> (x' \<otimes> y')"
47     by fast+
49   note carr = carr hxI[THEN a_Hcarr] hyI[THEN a_Hcarr] hzI[THEN a_Hcarr]
51   from z have "z = hz \<oplus> (x' \<otimes> y')" .
52   also from x' y' have "\<dots> = hz \<oplus> ((hx \<oplus> x) \<otimes> (hy \<oplus> y))" by simp
53   also from carr have "\<dots> = (hz \<oplus> (hx \<otimes> (hy \<oplus> y)) \<oplus> x \<otimes> hy) \<oplus> x \<otimes> y" by algebra
54   finally have z2: "z = (hz \<oplus> (hx \<otimes> (hy \<oplus> y)) \<oplus> x \<otimes> hy) \<oplus> x \<otimes> y" .
56   from hxI hyI hzI carr have "hz \<oplus> (hx \<otimes> (hy \<oplus> y)) \<oplus> x \<otimes> hy \<in> I"
57     by (simp add: I_l_closed I_r_closed)
59   with z2 have "\<exists>h\<in>I. z = h \<oplus> x \<otimes> y" by fast
60   then show "z \<in> I +> x \<otimes> y" by (simp add: a_r_coset_def r_coset_def)
61 next
62   fix z
63   assume xcarr: "x \<in> carrier R"
64     and ycarr: "y \<in> carrier R"
65     and zrcos: "z \<in> I +> x \<otimes> y"
66   from xcarr have xself: "x \<in> I +> x" by (intro a_rcos_self)
67   from ycarr have yself: "y \<in> I +> y" by (intro a_rcos_self)
68   show "\<exists>a\<in>I +> x. \<exists>b\<in>I +> y. z \<in> I +> a \<otimes> b"
69     using xself and yself and zrcos by fast
70 qed
73 subsection {* Quotient Ring Definition *}
75 definition FactRing :: "[('a,'b) ring_scheme, 'a set] \<Rightarrow> ('a set) ring"
76     (infixl "Quot" 65)
77   where "FactRing R I =
78     \<lparr>carrier = a_rcosets\<^bsub>R\<^esub> I, mult = rcoset_mult R I,
79       one = (I +>\<^bsub>R\<^esub> \<one>\<^bsub>R\<^esub>), zero = I, add = set_add R\<rparr>"
82 subsection {* Factorization over General Ideals *}
84 text {* The quotient is a ring *}
85 lemma (in ideal) quotient_is_ring: "ring (R Quot I)"
86 apply (rule ringI)
87    --{* abelian group *}
88    apply (rule comm_group_abelian_groupI)
89    apply (simp add: FactRing_def)
90    apply (rule a_factorgroup_is_comm_group[unfolded A_FactGroup_def'])
91   --{* mult monoid *}
92   apply (rule monoidI)
93       apply (simp_all add: FactRing_def A_RCOSETS_def RCOSETS_def
94              a_r_coset_def[symmetric])
95       --{* mult closed *}
96       apply (clarify)
98      --{* mult @{text one_closed} *}
99      apply force
100     --{* mult assoc *}
101     apply clarify
103    --{* mult one *}
104    apply clarify
106   apply clarify
108  --{* distr *}
109  apply clarify
110  apply (simp add: rcoset_mult_add a_rcos_sum l_distr)
111 apply clarify
112 apply (simp add: rcoset_mult_add a_rcos_sum r_distr)
113 done
116 text {* This is a ring homomorphism *}
118 lemma (in ideal) rcos_ring_hom: "(op +> I) \<in> ring_hom R (R Quot I)"
119 apply (rule ring_hom_memI)
120    apply (simp add: FactRing_def a_rcosetsI[OF a_subset])
122  apply (simp add: FactRing_def a_rcos_sum)
123 apply (simp add: FactRing_def)
124 done
126 lemma (in ideal) rcos_ring_hom_ring: "ring_hom_ring R (R Quot I) (op +> I)"
127 apply (rule ring_hom_ringI)
128      apply (rule is_ring, rule quotient_is_ring)
129    apply (simp add: FactRing_def a_rcosetsI[OF a_subset])
131  apply (simp add: FactRing_def a_rcos_sum)
132 apply (simp add: FactRing_def)
133 done
135 text {* The quotient of a cring is also commutative *}
136 lemma (in ideal) quotient_is_cring:
137   assumes "cring R"
138   shows "cring (R Quot I)"
139 proof -
140   interpret cring R by fact
141   show ?thesis
142     apply (intro cring.intro comm_monoid.intro comm_monoid_axioms.intro)
143       apply (rule quotient_is_ring)
144      apply (rule ring.axioms[OF quotient_is_ring])
145     apply (simp add: FactRing_def A_RCOSETS_defs a_r_coset_def[symmetric])
146     apply clarify
148     done
149 qed
151 text {* Cosets as a ring homomorphism on crings *}
152 lemma (in ideal) rcos_ring_hom_cring:
153   assumes "cring R"
154   shows "ring_hom_cring R (R Quot I) (op +> I)"
155 proof -
156   interpret cring R by fact
157   show ?thesis
158     apply (rule ring_hom_cringI)
159       apply (rule rcos_ring_hom_ring)
160      apply (rule is_cring)
161     apply (rule quotient_is_cring)
162    apply (rule is_cring)
163    done
164 qed
167 subsection {* Factorization over Prime Ideals *}
169 text {* The quotient ring generated by a prime ideal is a domain *}
170 lemma (in primeideal) quotient_is_domain: "domain (R Quot I)"
171   apply (rule domain.intro)
172    apply (rule quotient_is_cring, rule is_cring)
173   apply (rule domain_axioms.intro)
174    apply (simp add: FactRing_def) defer 1
175     apply (simp add: FactRing_def A_RCOSETS_defs a_r_coset_def[symmetric], clarify)
176     apply (simp add: rcoset_mult_add) defer 1
177 proof (rule ccontr, clarsimp)
178   assume "I +> \<one> = I"
179   then have "\<one> \<in> I" by (simp only: a_coset_join1 one_closed a_subgroup)
180   then have "carrier R \<subseteq> I" by (subst one_imp_carrier, simp, fast)
181   with a_subset have "I = carrier R" by fast
182   with I_notcarr show False by fast
183 next
184   fix x y
185   assume carr: "x \<in> carrier R" "y \<in> carrier R"
186     and a: "I +> x \<otimes> y = I"
187     and b: "I +> y \<noteq> I"
189   have ynI: "y \<notin> I"
190   proof (rule ccontr, simp)
191     assume "y \<in> I"
192     then have "I +> y = I" by (rule a_rcos_const)
193     with b show False by simp
194   qed
196   from carr have "x \<otimes> y \<in> I +> x \<otimes> y" by (simp add: a_rcos_self)
197   then have xyI: "x \<otimes> y \<in> I" by (simp add: a)
199   from xyI and carr have xI: "x \<in> I \<or> y \<in> I" by (simp add: I_prime)
200   with ynI have "x \<in> I" by fast
201   then show "I +> x = I" by (rule a_rcos_const)
202 qed
204 text {* Generating right cosets of a prime ideal is a homomorphism
205         on commutative rings *}
206 lemma (in primeideal) rcos_ring_hom_cring: "ring_hom_cring R (R Quot I) (op +> I)"
207   by (rule rcos_ring_hom_cring) (rule is_cring)
210 subsection {* Factorization over Maximal Ideals *}
212 text {* In a commutative ring, the quotient ring over a maximal ideal
213         is a field.
214         The proof follows ``W. Adkins, S. Weintraub: Algebra --
215         An Approach via Module Theory'' *}
216 lemma (in maximalideal) quotient_is_field:
217   assumes "cring R"
218   shows "field (R Quot I)"
219 proof -
220   interpret cring R by fact
221   show ?thesis
222     apply (intro cring.cring_fieldI2)
223       apply (rule quotient_is_cring, rule is_cring)
224      defer 1
225      apply (simp add: FactRing_def A_RCOSETS_defs a_r_coset_def[symmetric], clarsimp)
226      apply (simp add: rcoset_mult_add) defer 1
227   proof (rule ccontr, simp)
228     --{* Quotient is not empty *}
229     assume "\<zero>\<^bsub>R Quot I\<^esub> = \<one>\<^bsub>R Quot I\<^esub>"
230     then have II1: "I = I +> \<one>" by (simp add: FactRing_def)
231     from a_rcos_self[OF one_closed] have "\<one> \<in> I"
232       by (simp add: II1[symmetric])
233     then have "I = carrier R" by (rule one_imp_carrier)
234     with I_notcarr show False by simp
235   next
236     --{* Existence of Inverse *}
237     fix a
238     assume IanI: "I +> a \<noteq> I" and acarr: "a \<in> carrier R"
240     --{* Helper ideal @{text "J"} *}
241     def J \<equiv> "(carrier R #> a) <+> I :: 'a set"
242     have idealJ: "ideal J R"
243       apply (unfold J_def, rule add_ideals)
244        apply (simp only: cgenideal_eq_rcos[symmetric], rule cgenideal_ideal, rule acarr)
245       apply (rule is_ideal)
246       done
248     --{* Showing @{term "J"} not smaller than @{term "I"} *}
249     have IinJ: "I \<subseteq> J"
250     proof (rule, simp add: J_def r_coset_def set_add_defs)
251       fix x
252       assume xI: "x \<in> I"
253       have Zcarr: "\<zero> \<in> carrier R" by fast
254       from xI[THEN a_Hcarr] acarr
255       have "x = \<zero> \<otimes> a \<oplus> x" by algebra
256       with Zcarr and xI show "\<exists>xa\<in>carrier R. \<exists>k\<in>I. x = xa \<otimes> a \<oplus> k" by fast
257     qed
259     --{* Showing @{term "J \<noteq> I"} *}
260     have anI: "a \<notin> I"
261     proof (rule ccontr, simp)
262       assume "a \<in> I"
263       then have "I +> a = I" by (rule a_rcos_const)
264       with IanI show False by simp
265     qed
267     have aJ: "a \<in> J"
268     proof (simp add: J_def r_coset_def set_add_defs)
269       from acarr
270       have "a = \<one> \<otimes> a \<oplus> \<zero>" by algebra
272       show "\<exists>x\<in>carrier R. \<exists>k\<in>I. a = x \<otimes> a \<oplus> k" by fast
273     qed
275     from aJ and anI have JnI: "J \<noteq> I" by fast
277     --{* Deducing @{term "J = carrier R"} because @{term "I"} is maximal *}
278     from idealJ and IinJ have "J = I \<or> J = carrier R"
279     proof (rule I_maximal, unfold J_def)
280       have "carrier R #> a \<subseteq> carrier R"
281         using subset_refl acarr by (rule r_coset_subset_G)
282       then show "carrier R #> a <+> I \<subseteq> carrier R"
283         using a_subset by (rule set_add_closed)
284     qed
286     with JnI have Jcarr: "J = carrier R" by simp
288     --{* Calculating an inverse for @{term "a"} *}
289     from one_closed[folded Jcarr]
290     have "\<exists>r\<in>carrier R. \<exists>i\<in>I. \<one> = r \<otimes> a \<oplus> i"
291       by (simp add: J_def r_coset_def set_add_defs)
292     then obtain r i where rcarr: "r \<in> carrier R"
293       and iI: "i \<in> I" and one: "\<one> = r \<otimes> a \<oplus> i" by fast
294     from one and rcarr and acarr and iI[THEN a_Hcarr]
295     have rai1: "a \<otimes> r = \<ominus>i \<oplus> \<one>" by algebra
297     --{* Lifting to cosets *}
298     from iI have "\<ominus>i \<oplus> \<one> \<in> I +> \<one>"
299       by (intro a_rcosI, simp, intro a_subset, simp)
300     with rai1 have "a \<otimes> r \<in> I +> \<one>" by simp
301     then have "I +> \<one> = I +> a \<otimes> r"
302       by (rule a_repr_independence, simp) (rule a_subgroup)
304     from rcarr and this[symmetric]
305     show "\<exists>r\<in>carrier R. I +> a \<otimes> r = I +> \<one>" by fast
306   qed
307 qed
309 end