src/HOL/Algebra/QuotRing.thy
 author wenzelm Sun Mar 21 15:57:40 2010 +0100 (2010-03-21) changeset 35847 19f1f7066917 parent 29242 e190bc2a5399 child 35848 5443079512ea permissions -rw-r--r--
eliminated old constdefs;
1 (*
2   Title:     HOL/Algebra/QuotRing.thy
3   Author:    Stephan Hohe
4 *)
6 theory QuotRing
7 imports RingHom
8 begin
10 section {* Quotient Rings *}
12 subsection {* Multiplication on Cosets *}
14 definition
15   rcoset_mult :: "[('a, _) ring_scheme, 'a set, 'a set, 'a set] \<Rightarrow> 'a set"
16     ("[mod _:] _ \<Otimes>\<index> _" [81,81,81] 80)
17   where "rcoset_mult R I A B \<equiv> \<Union>a\<in>A. \<Union>b\<in>B. I +>\<^bsub>R\<^esub> (a \<otimes>\<^bsub>R\<^esub> b)"
20 text {* @{const "rcoset_mult"} fulfils the properties required by
21   congruences *}
22 lemma (in ideal) rcoset_mult_add:
23   "\<lbrakk>x \<in> carrier R; y \<in> carrier R\<rbrakk> \<Longrightarrow> [mod I:] (I +> x) \<Otimes> (I +> y) = I +> (x \<otimes> y)"
24 apply rule
25 apply (rule, simp add: rcoset_mult_def, clarsimp)
26 defer 1
27 apply (rule, simp add: rcoset_mult_def)
28 defer 1
29 proof -
30   fix z x' y'
31   assume carr: "x \<in> carrier R" "y \<in> carrier R"
32      and x'rcos: "x' \<in> I +> x"
33      and y'rcos: "y' \<in> I +> y"
34      and zrcos: "z \<in> I +> x' \<otimes> y'"
36   from x'rcos
37       have "\<exists>h\<in>I. x' = h \<oplus> x" by (simp add: a_r_coset_def r_coset_def)
38   from this obtain hx
39       where hxI: "hx \<in> I"
40       and x': "x' = hx \<oplus> x"
41       by fast+
43   from y'rcos
44       have "\<exists>h\<in>I. y' = h \<oplus> y" by (simp add: a_r_coset_def r_coset_def)
45   from this
46       obtain hy
47       where hyI: "hy \<in> I"
48       and y': "y' = hy \<oplus> y"
49       by fast+
51   from zrcos
52       have "\<exists>h\<in>I. z = h \<oplus> (x' \<otimes> y')" by (simp add: a_r_coset_def r_coset_def)
53   from this
54       obtain hz
55       where hzI: "hz \<in> I"
56       and z: "z = hz \<oplus> (x' \<otimes> y')"
57       by fast+
59   note carr = carr hxI[THEN a_Hcarr] hyI[THEN a_Hcarr] hzI[THEN a_Hcarr]
61   from z have "z = hz \<oplus> (x' \<otimes> y')" .
62   also from x' y'
63       have "\<dots> = hz \<oplus> ((hx \<oplus> x) \<otimes> (hy \<oplus> y))" by simp
64   also from carr
65       have "\<dots> = (hz \<oplus> (hx \<otimes> (hy \<oplus> y)) \<oplus> x \<otimes> hy) \<oplus> x \<otimes> y" by algebra
66   finally
67       have z2: "z = (hz \<oplus> (hx \<otimes> (hy \<oplus> y)) \<oplus> x \<otimes> hy) \<oplus> x \<otimes> y" .
69   from hxI hyI hzI carr
70       have "hz \<oplus> (hx \<otimes> (hy \<oplus> y)) \<oplus> x \<otimes> hy \<in> I"  by (simp add: I_l_closed I_r_closed)
72   from this and z2
73       have "\<exists>h\<in>I. z = h \<oplus> x \<otimes> y" by fast
74   thus "z \<in> I +> x \<otimes> y" by (simp add: a_r_coset_def r_coset_def)
75 next
76   fix z
77   assume xcarr: "x \<in> carrier R"
78      and ycarr: "y \<in> carrier R"
79      and zrcos: "z \<in> I +> x \<otimes> y"
80   from xcarr
81       have xself: "x \<in> I +> x" by (intro a_rcos_self)
82   from ycarr
83       have yself: "y \<in> I +> y" by (intro a_rcos_self)
85   from xself and yself and zrcos
86       show "\<exists>a\<in>I +> x. \<exists>b\<in>I +> y. z \<in> I +> a \<otimes> b" by fast
87 qed
90 subsection {* Quotient Ring Definition *}
92 definition
93   FactRing :: "[('a,'b) ring_scheme, 'a set] \<Rightarrow> ('a set) ring"  (infixl "Quot" 65)
94   where "FactRing R I \<equiv>
95     \<lparr>carrier = a_rcosets\<^bsub>R\<^esub> I, mult = rcoset_mult R I, one = (I +>\<^bsub>R\<^esub> \<one>\<^bsub>R\<^esub>), zero = I, add = set_add R\<rparr>"
98 subsection {* Factorization over General Ideals *}
100 text {* The quotient is a ring *}
101 lemma (in ideal) quotient_is_ring:
102   shows "ring (R Quot I)"
103 apply (rule ringI)
104    --{* abelian group *}
105    apply (rule comm_group_abelian_groupI)
106    apply (simp add: FactRing_def)
107    apply (rule a_factorgroup_is_comm_group[unfolded A_FactGroup_def'])
108   --{* mult monoid *}
109   apply (rule monoidI)
110       apply (simp_all add: FactRing_def A_RCOSETS_def RCOSETS_def
111              a_r_coset_def[symmetric])
112       --{* mult closed *}
113       apply (clarify)
115      --{* mult @{text one_closed} *}
116      apply (force intro: one_closed)
117     --{* mult assoc *}
118     apply clarify
120    --{* mult one *}
121    apply clarify
123   apply clarify
125  --{* distr *}
126  apply clarify
127  apply (simp add: rcoset_mult_add a_rcos_sum l_distr)
128 apply clarify
129 apply (simp add: rcoset_mult_add a_rcos_sum r_distr)
130 done
133 text {* This is a ring homomorphism *}
135 lemma (in ideal) rcos_ring_hom:
136   "(op +> I) \<in> ring_hom R (R Quot I)"
137 apply (rule ring_hom_memI)
138    apply (simp add: FactRing_def a_rcosetsI[OF a_subset])
140  apply (simp add: FactRing_def a_rcos_sum)
141 apply (simp add: FactRing_def)
142 done
144 lemma (in ideal) rcos_ring_hom_ring:
145   "ring_hom_ring R (R Quot I) (op +> I)"
146 apply (rule ring_hom_ringI)
147      apply (rule is_ring, rule quotient_is_ring)
148    apply (simp add: FactRing_def a_rcosetsI[OF a_subset])
150  apply (simp add: FactRing_def a_rcos_sum)
151 apply (simp add: FactRing_def)
152 done
154 text {* The quotient of a cring is also commutative *}
155 lemma (in ideal) quotient_is_cring:
156   assumes "cring R"
157   shows "cring (R Quot I)"
158 proof -
159   interpret cring R by fact
160   show ?thesis apply (intro cring.intro comm_monoid.intro comm_monoid_axioms.intro)
161   apply (rule quotient_is_ring)
162  apply (rule ring.axioms[OF quotient_is_ring])
163 apply (simp add: FactRing_def A_RCOSETS_defs a_r_coset_def[symmetric])
164 apply clarify
166 done
167 qed
169 text {* Cosets as a ring homomorphism on crings *}
170 lemma (in ideal) rcos_ring_hom_cring:
171   assumes "cring R"
172   shows "ring_hom_cring R (R Quot I) (op +> I)"
173 proof -
174   interpret cring R by fact
175   show ?thesis apply (rule ring_hom_cringI)
176   apply (rule rcos_ring_hom_ring)
177  apply (rule is_cring)
178 apply (rule quotient_is_cring)
179 apply (rule is_cring)
180 done
181 qed
183 subsection {* Factorization over Prime Ideals *}
185 text {* The quotient ring generated by a prime ideal is a domain *}
186 lemma (in primeideal) quotient_is_domain:
187   shows "domain (R Quot I)"
188 apply (rule domain.intro)
189  apply (rule quotient_is_cring, rule is_cring)
190 apply (rule domain_axioms.intro)
191  apply (simp add: FactRing_def) defer 1
192  apply (simp add: FactRing_def A_RCOSETS_defs a_r_coset_def[symmetric], clarify)
193  apply (simp add: rcoset_mult_add) defer 1
194 proof (rule ccontr, clarsimp)
195   assume "I +> \<one> = I"
196   hence "\<one> \<in> I" by (simp only: a_coset_join1 one_closed a_subgroup)
197   hence "carrier R \<subseteq> I" by (subst one_imp_carrier, simp, fast)
198   from this and a_subset
199       have "I = carrier R" by fast
200   from this and I_notcarr
201       show "False" by fast
202 next
203   fix x y
204   assume carr: "x \<in> carrier R" "y \<in> carrier R"
205      and a: "I +> x \<otimes> y = I"
206      and b: "I +> y \<noteq> I"
208   have ynI: "y \<notin> I"
209   proof (rule ccontr, simp)
210     assume "y \<in> I"
211     hence "I +> y = I" by (rule a_rcos_const)
212     from this and b
213         show "False" by simp
214   qed
216   from carr
217       have "x \<otimes> y \<in> I +> x \<otimes> y" by (simp add: a_rcos_self)
218   from this
219       have xyI: "x \<otimes> y \<in> I" by (simp add: a)
221   from xyI and carr
222       have xI: "x \<in> I \<or> y \<in> I" by (simp add: I_prime)
223   from this and ynI
224       have "x \<in> I" by fast
225   thus "I +> x = I" by (rule a_rcos_const)
226 qed
228 text {* Generating right cosets of a prime ideal is a homomorphism
229         on commutative rings *}
230 lemma (in primeideal) rcos_ring_hom_cring:
231   shows "ring_hom_cring R (R Quot I) (op +> I)"
232 by (rule rcos_ring_hom_cring, rule is_cring)
235 subsection {* Factorization over Maximal Ideals *}
237 text {* In a commutative ring, the quotient ring over a maximal ideal
238         is a field.
239         The proof follows ``W. Adkins, S. Weintraub: Algebra --
240         An Approach via Module Theory'' *}
241 lemma (in maximalideal) quotient_is_field:
242   assumes "cring R"
243   shows "field (R Quot I)"
244 proof -
245   interpret cring R by fact
246   show ?thesis apply (intro cring.cring_fieldI2)
247   apply (rule quotient_is_cring, rule is_cring)
248  defer 1
249  apply (simp add: FactRing_def A_RCOSETS_defs a_r_coset_def[symmetric], clarsimp)
250  apply (simp add: rcoset_mult_add) defer 1
251 proof (rule ccontr, simp)
252   --{* Quotient is not empty *}
253   assume "\<zero>\<^bsub>R Quot I\<^esub> = \<one>\<^bsub>R Quot I\<^esub>"
254   hence II1: "I = I +> \<one>" by (simp add: FactRing_def)
255   from a_rcos_self[OF one_closed]
256   have "\<one> \<in> I" by (simp add: II1[symmetric])
257   hence "I = carrier R" by (rule one_imp_carrier)
258   from this and I_notcarr
259   show "False" by simp
260 next
261   --{* Existence of Inverse *}
262   fix a
263   assume IanI: "I +> a \<noteq> I"
264     and acarr: "a \<in> carrier R"
266   --{* Helper ideal @{text "J"} *}
267   def J \<equiv> "(carrier R #> a) <+> I :: 'a set"
268   have idealJ: "ideal J R"
269     apply (unfold J_def, rule add_ideals)
270      apply (simp only: cgenideal_eq_rcos[symmetric], rule cgenideal_ideal, rule acarr)
271     apply (rule is_ideal)
272     done
274   --{* Showing @{term "J"} not smaller than @{term "I"} *}
275   have IinJ: "I \<subseteq> J"
276   proof (rule, simp add: J_def r_coset_def set_add_defs)
277     fix x
278     assume xI: "x \<in> I"
279     have Zcarr: "\<zero> \<in> carrier R" by fast
280     from xI[THEN a_Hcarr] acarr
281     have "x = \<zero> \<otimes> a \<oplus> x" by algebra
283     from Zcarr and xI and this
284     show "\<exists>xa\<in>carrier R. \<exists>k\<in>I. x = xa \<otimes> a \<oplus> k" by fast
285   qed
287   --{* Showing @{term "J \<noteq> I"} *}
288   have anI: "a \<notin> I"
289   proof (rule ccontr, simp)
290     assume "a \<in> I"
291     hence "I +> a = I" by (rule a_rcos_const)
292     from this and IanI
293     show "False" by simp
294   qed
296   have aJ: "a \<in> J"
297   proof (simp add: J_def r_coset_def set_add_defs)
298     from acarr
299     have "a = \<one> \<otimes> a \<oplus> \<zero>" by algebra
300     from one_closed and additive_subgroup.zero_closed[OF is_additive_subgroup] and this
301     show "\<exists>x\<in>carrier R. \<exists>k\<in>I. a = x \<otimes> a \<oplus> k" by fast
302   qed
304   from aJ and anI
305   have JnI: "J \<noteq> I" by fast
307   --{* Deducing @{term "J = carrier R"} because @{term "I"} is maximal *}
308   from idealJ and IinJ
309   have "J = I \<or> J = carrier R"
310   proof (rule I_maximal, unfold J_def)
311     have "carrier R #> a \<subseteq> carrier R"
312       using subset_refl acarr
313       by (rule r_coset_subset_G)
314     from this and a_subset
315     show "carrier R #> a <+> I \<subseteq> carrier R" by (rule set_add_closed)
316   qed
318   from this and JnI
319   have Jcarr: "J = carrier R" by simp
321   --{* Calculating an inverse for @{term "a"} *}
322   from one_closed[folded Jcarr]
323   have "\<exists>r\<in>carrier R. \<exists>i\<in>I. \<one> = r \<otimes> a \<oplus> i"
324     by (simp add: J_def r_coset_def set_add_defs)
325   from this
326   obtain r i
327     where rcarr: "r \<in> carrier R"
328       and iI: "i \<in> I"
329       and one: "\<one> = r \<otimes> a \<oplus> i"
330     by fast
331   from one and rcarr and acarr and iI[THEN a_Hcarr]
332   have rai1: "a \<otimes> r = \<ominus>i \<oplus> \<one>" by algebra
334   --{* Lifting to cosets *}
335   from iI
336   have "\<ominus>i \<oplus> \<one> \<in> I +> \<one>"
337     by (intro a_rcosI, simp, intro a_subset, simp)
338   from this and rai1
339   have "a \<otimes> r \<in> I +> \<one>" by simp
340   from this have "I +> \<one> = I +> a \<otimes> r"
341     by (rule a_repr_independence, simp) (rule a_subgroup)
343   from rcarr and this[symmetric]
344   show "\<exists>r\<in>carrier R. I +> a \<otimes> r = I +> \<one>" by fast
345 qed
346 qed
348 end