src/HOL/Algebra/QuotRing.thy
changeset 20318 0e0ea63fe768
child 21502 7f3ea2b3bab6
equal deleted inserted replaced
20317:6e070b33e72b 20318:0e0ea63fe768
       
     1 (*
       
     2   Title:     HOL/Algebra/QuotRing.thy
       
     3   Id:        $Id$
       
     4   Author:    Stephan Hohe
       
     5 *)
       
     6 
       
     7 theory QuotRing
       
     8 imports RingHom
       
     9 begin
       
    10 
       
    11 
       
    12 section {* Quotient Rings *}
       
    13 
       
    14 subsection {* Multiplication on Cosets *}
       
    15 
       
    16 constdefs (structure R)
       
    17   rcoset_mult :: "[('a, _) ring_scheme, 'a set, 'a set, 'a set] \<Rightarrow> 'a set"   ("[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 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   includes cring
       
   159   shows "cring (R Quot I)"
       
   160 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
       
   165 apply (simp add: rcoset_mult_add m_comm)
       
   166 done
       
   167 
       
   168 text {* Cosets as a ring homomorphism on crings *}
       
   169 lemma (in ideal) rcos_ring_hom_cring:
       
   170   includes cring
       
   171   shows "ring_hom_cring R (R Quot I) (op +> I)"
       
   172 apply (rule ring_hom_cringI)
       
   173   apply (rule rcos_ring_hom_ring)
       
   174  apply assumption
       
   175 apply (rule quotient_is_cring, assumption)
       
   176 done
       
   177 
       
   178 
       
   179 subsection {* Factorization over Prime Ideals *}
       
   180 
       
   181 text {* The quotient ring generated by a prime ideal is a domain *}
       
   182 lemma (in primeideal) quotient_is_domain:
       
   183   shows "domain (R Quot I)"
       
   184 apply (rule domain.intro)
       
   185  apply (rule quotient_is_cring, rule is_cring)
       
   186 apply (rule domain_axioms.intro)
       
   187  apply (simp add: FactRing_def) defer 1
       
   188  apply (simp add: FactRing_def A_RCOSETS_defs a_r_coset_def[symmetric], clarify)
       
   189  apply (simp add: rcoset_mult_add) defer 1
       
   190 proof (rule ccontr, clarsimp)
       
   191   assume "I +> \<one> = I"
       
   192   hence "\<one> \<in> I" by (simp only: a_coset_join1 one_closed a_subgroup)
       
   193   hence "carrier R \<subseteq> I" by (subst one_imp_carrier, simp, fast)
       
   194   from this and a_subset
       
   195       have "I = carrier R" by fast
       
   196   from this and I_notcarr
       
   197       show "False" by fast
       
   198 next
       
   199   fix x y
       
   200   assume carr: "x \<in> carrier R" "y \<in> carrier R"
       
   201      and a: "I +> x \<otimes> y = I"
       
   202      and b: "I +> y \<noteq> I"
       
   203 
       
   204   have ynI: "y \<notin> I"
       
   205   proof (rule ccontr, simp)
       
   206     assume "y \<in> I"
       
   207     hence "I +> y = I" by (rule a_rcos_const)
       
   208     from this and b
       
   209         show "False" by simp
       
   210   qed
       
   211 
       
   212   from carr
       
   213       have "x \<otimes> y \<in> I +> x \<otimes> y" by (simp add: a_rcos_self)
       
   214   from this
       
   215       have xyI: "x \<otimes> y \<in> I" by (simp add: a)
       
   216 
       
   217   from xyI and carr
       
   218       have xI: "x \<in> I \<or> y \<in> I" by (simp add: I_prime)
       
   219   from this and ynI
       
   220       have "x \<in> I" by fast
       
   221   thus "I +> x = I" by (rule a_rcos_const)
       
   222 qed
       
   223 
       
   224 text {* Generating right cosets of a prime ideal is a homomorphism
       
   225         on commutative rings *}
       
   226 lemma (in primeideal) rcos_ring_hom_cring:
       
   227   shows "ring_hom_cring R (R Quot I) (op +> I)"
       
   228 by (rule rcos_ring_hom_cring, rule is_cring)
       
   229 
       
   230 
       
   231 subsection {* Factorization over Maximal Ideals *}
       
   232 
       
   233 text {* In a commutative ring, the quotient ring over a maximal ideal
       
   234         is a field.
       
   235         The proof follows ``W. Adkins, S. Weintraub: Algebra --
       
   236         An Approach via Module Theory'' *}
       
   237 lemma (in maximalideal) quotient_is_field:
       
   238   includes cring
       
   239   shows "field (R Quot I)"
       
   240 apply (intro cring.cring_fieldI2)
       
   241   apply (rule quotient_is_cring, rule is_cring)
       
   242  defer 1
       
   243  apply (simp add: FactRing_def A_RCOSETS_defs a_r_coset_def[symmetric], clarsimp)
       
   244  apply (simp add: rcoset_mult_add) defer 1
       
   245 proof (rule ccontr, simp)
       
   246   --{* Quotient is not empty *}
       
   247   assume "\<zero>\<^bsub>R Quot I\<^esub> = \<one>\<^bsub>R Quot I\<^esub>"
       
   248   hence II1: "I = I +> \<one>" by (simp add: FactRing_def)
       
   249   from a_rcos_self[OF one_closed]
       
   250       have "\<one> \<in> I" by (simp add: II1[symmetric])
       
   251   hence "I = carrier R" by (rule one_imp_carrier)
       
   252   from this and I_notcarr
       
   253       show "False" by simp
       
   254 next
       
   255   --{* Existence of Inverse *}
       
   256   fix a
       
   257   assume IanI: "I +> a \<noteq> I"
       
   258      and acarr: "a \<in> carrier R"
       
   259 
       
   260   --{* Helper ideal @{text "J"} *}
       
   261   def J \<equiv> "(carrier R #> a) <+> I :: 'a set"
       
   262   have idealJ: "ideal J R"
       
   263       apply (unfold J_def, rule add_ideals)
       
   264       apply (simp only: cgenideal_eq_rcos[symmetric], rule cgenideal_ideal, rule acarr)
       
   265       apply (rule is_ideal)
       
   266       done
       
   267 
       
   268   --{* Showing @{term "J"} not smaller than @{term "I"} *}
       
   269   have IinJ: "I \<subseteq> J"
       
   270   proof (rule, simp add: J_def r_coset_def set_add_defs)
       
   271     fix x
       
   272     assume xI: "x \<in> I"
       
   273     have Zcarr: "\<zero> \<in> carrier R" by fast
       
   274     from xI[THEN a_Hcarr] acarr
       
   275     have "x = \<zero> \<otimes> a \<oplus> x" by algebra
       
   276 
       
   277     from Zcarr and xI and this
       
   278         show "\<exists>xa\<in>carrier R. \<exists>k\<in>I. x = xa \<otimes> a \<oplus> k" by fast
       
   279   qed
       
   280 
       
   281   --{* Showing @{term "J \<noteq> I"} *}
       
   282   have anI: "a \<notin> I"
       
   283   proof (rule ccontr, simp)
       
   284     assume "a \<in> I"
       
   285     hence "I +> a = I" by (rule a_rcos_const)
       
   286     from this and IanI
       
   287         show "False" by simp
       
   288   qed
       
   289 
       
   290   have aJ: "a \<in> J"
       
   291   proof (simp add: J_def r_coset_def set_add_defs)
       
   292     from acarr
       
   293         have "a = \<one> \<otimes> a \<oplus> \<zero>" by algebra
       
   294     from one_closed and additive_subgroup.zero_closed[OF is_additive_subgroup] and this
       
   295         show "\<exists>x\<in>carrier R. \<exists>k\<in>I. a = x \<otimes> a \<oplus> k" by fast
       
   296   qed
       
   297 
       
   298   from aJ and anI
       
   299       have JnI: "J \<noteq> I" by fast
       
   300 
       
   301   --{* Deducing @{term "J = carrier R"} because @{term "I"} is maximal *}
       
   302   from idealJ and IinJ
       
   303       have "J = I \<or> J = carrier R"
       
   304   proof (rule I_maximal, unfold J_def)
       
   305     have "carrier R #> a \<subseteq> carrier R"
       
   306 	  by (rule r_coset_subset_G) fast
       
   307     from this and a_subset
       
   308         show "carrier R #> a <+> I \<subseteq> carrier R" by (rule set_add_closed)
       
   309   qed
       
   310 
       
   311   from this and JnI
       
   312       have Jcarr: "J = carrier R" by simp
       
   313 
       
   314   --{* Calculating an inverse for @{term "a"} *}
       
   315   from one_closed[folded Jcarr]
       
   316       have "\<exists>r\<in>carrier R. \<exists>i\<in>I. \<one> = r \<otimes> a \<oplus> i"
       
   317       by (simp add: J_def r_coset_def set_add_defs)
       
   318   from this
       
   319      obtain r i
       
   320        where rcarr: "r \<in> carrier R"
       
   321        and iI: "i \<in> I"
       
   322        and one: "\<one> = r \<otimes> a \<oplus> i"
       
   323      by fast
       
   324   from one and rcarr and acarr and iI[THEN a_Hcarr]
       
   325       have rai1: "a \<otimes> r = \<ominus>i \<oplus> \<one>" by algebra
       
   326 
       
   327   --{* Lifting to cosets *}
       
   328   from iI
       
   329       have "\<ominus>i \<oplus> \<one> \<in> I +> \<one>"
       
   330       by (intro a_rcosI, simp, intro a_subset, simp)
       
   331   from this and rai1
       
   332       have "a \<otimes> r \<in> I +> \<one>" by simp
       
   333   from this have "I +> \<one> = I +> a \<otimes> r"
       
   334       by (rule a_repr_independence, simp) (rule a_subgroup)
       
   335 
       
   336   from rcarr and this[symmetric]
       
   337       show "\<exists>r\<in>carrier R. I +> a \<otimes> r = I +> \<one>" by fast
       
   338 qed
       
   339 
       
   340 end