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