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