src/HOL/Algebra/QuotRing.thy
author wenzelm
Sun Mar 21 17:12:31 2010 +0100 (2010-03-21)
changeset 35849 b5522b51cb1e
parent 35848 5443079512ea
child 45005 0d2d59525912
permissions -rw-r--r--
standard headers;
     1 (*  Title:      HOL/Algebra/QuotRing.thy
     2     Author:     Stephan Hohe
     3 *)
     4 
     5 theory QuotRing
     6 imports RingHom
     7 begin
     8 
     9 section {* Quotient Rings *}
    10 
    11 subsection {* Multiplication on Cosets *}
    12 
    13 definition
    14   rcoset_mult :: "[('a, _) ring_scheme, 'a set, 'a set, 'a set] \<Rightarrow> 'a set"
    15     ("[mod _:] _ \<Otimes>\<index> _" [81,81,81] 80)
    16   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))"
    17 
    18 
    19 text {* @{const "rcoset_mult"} fulfils the properties required by
    20   congruences *}
    21 lemma (in ideal) rcoset_mult_add:
    22   "\<lbrakk>x \<in> carrier R; y \<in> carrier R\<rbrakk> \<Longrightarrow> [mod I:] (I +> x) \<Otimes> (I +> y) = I +> (x \<otimes> y)"
    23 apply rule
    24 apply (rule, simp add: rcoset_mult_def, clarsimp)
    25 defer 1
    26 apply (rule, simp add: rcoset_mult_def)
    27 defer 1
    28 proof -
    29   fix z x' y'
    30   assume carr: "x \<in> carrier R" "y \<in> carrier R"
    31      and x'rcos: "x' \<in> I +> x"
    32      and y'rcos: "y' \<in> I +> y"
    33      and zrcos: "z \<in> I +> x' \<otimes> y'"
    34 
    35   from x'rcos 
    36       have "\<exists>h\<in>I. x' = h \<oplus> x" by (simp add: a_r_coset_def r_coset_def)
    37   from this obtain hx
    38       where hxI: "hx \<in> I"
    39       and x': "x' = hx \<oplus> x"
    40       by fast+
    41   
    42   from y'rcos
    43       have "\<exists>h\<in>I. y' = h \<oplus> y" by (simp add: a_r_coset_def r_coset_def)
    44   from this
    45       obtain hy
    46       where hyI: "hy \<in> I"
    47       and y': "y' = hy \<oplus> y"
    48       by fast+
    49 
    50   from zrcos
    51       have "\<exists>h\<in>I. z = h \<oplus> (x' \<otimes> y')" by (simp add: a_r_coset_def r_coset_def)
    52   from this
    53       obtain hz
    54       where hzI: "hz \<in> I"
    55       and z: "z = hz \<oplus> (x' \<otimes> y')"
    56       by fast+
    57 
    58   note carr = carr hxI[THEN a_Hcarr] hyI[THEN a_Hcarr] hzI[THEN a_Hcarr]
    59 
    60   from z have "z = hz \<oplus> (x' \<otimes> y')" .
    61   also from x' y'
    62       have "\<dots> = hz \<oplus> ((hx \<oplus> x) \<otimes> (hy \<oplus> y))" by simp
    63   also from carr
    64       have "\<dots> = (hz \<oplus> (hx \<otimes> (hy \<oplus> y)) \<oplus> x \<otimes> hy) \<oplus> x \<otimes> y" by algebra
    65   finally
    66       have z2: "z = (hz \<oplus> (hx \<otimes> (hy \<oplus> y)) \<oplus> x \<otimes> hy) \<oplus> x \<otimes> y" .
    67 
    68   from hxI hyI hzI carr
    69       have "hz \<oplus> (hx \<otimes> (hy \<oplus> y)) \<oplus> x \<otimes> hy \<in> I"  by (simp add: I_l_closed I_r_closed)
    70 
    71   from this and z2
    72       have "\<exists>h\<in>I. z = h \<oplus> x \<otimes> y" by fast
    73   thus "z \<in> I +> x \<otimes> y" by (simp add: a_r_coset_def r_coset_def)
    74 next
    75   fix z
    76   assume xcarr: "x \<in> carrier R"
    77      and ycarr: "y \<in> carrier R"
    78      and zrcos: "z \<in> I +> x \<otimes> y"
    79   from xcarr
    80       have xself: "x \<in> I +> x" by (intro a_rcos_self)
    81   from ycarr
    82       have yself: "y \<in> I +> y" by (intro a_rcos_self)
    83 
    84   from xself and yself and zrcos
    85       show "\<exists>a\<in>I +> x. \<exists>b\<in>I +> y. z \<in> I +> a \<otimes> b" by fast
    86 qed
    87 
    88 
    89 subsection {* Quotient Ring Definition *}
    90 
    91 definition
    92   FactRing :: "[('a,'b) ring_scheme, 'a set] \<Rightarrow> ('a set) ring"  (infixl "Quot" 65)
    93   where "FactRing R I =
    94     \<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>"
    95 
    96 
    97 subsection {* Factorization over General Ideals *}
    98 
    99 text {* The quotient is a ring *}
   100 lemma (in ideal) quotient_is_ring:
   101   shows "ring (R Quot I)"
   102 apply (rule ringI)
   103    --{* abelian group *}
   104    apply (rule comm_group_abelian_groupI)
   105    apply (simp add: FactRing_def)
   106    apply (rule a_factorgroup_is_comm_group[unfolded A_FactGroup_def'])
   107   --{* mult monoid *}
   108   apply (rule monoidI)
   109       apply (simp_all add: FactRing_def A_RCOSETS_def RCOSETS_def
   110              a_r_coset_def[symmetric])
   111       --{* mult closed *}
   112       apply (clarify)
   113       apply (simp add: rcoset_mult_add, fast)
   114      --{* mult @{text one_closed} *}
   115      apply (force intro: one_closed)
   116     --{* mult assoc *}
   117     apply clarify
   118     apply (simp add: rcoset_mult_add m_assoc)
   119    --{* mult one *}
   120    apply clarify
   121    apply (simp add: rcoset_mult_add l_one)
   122   apply clarify
   123   apply (simp add: rcoset_mult_add r_one)
   124  --{* distr *}
   125  apply clarify
   126  apply (simp add: rcoset_mult_add a_rcos_sum l_distr)
   127 apply clarify
   128 apply (simp add: rcoset_mult_add a_rcos_sum r_distr)
   129 done
   130 
   131 
   132 text {* This is a ring homomorphism *}
   133 
   134 lemma (in ideal) rcos_ring_hom:
   135   "(op +> I) \<in> ring_hom R (R Quot I)"
   136 apply (rule ring_hom_memI)
   137    apply (simp add: FactRing_def a_rcosetsI[OF a_subset])
   138   apply (simp add: FactRing_def rcoset_mult_add)
   139  apply (simp add: FactRing_def a_rcos_sum)
   140 apply (simp add: FactRing_def)
   141 done
   142 
   143 lemma (in ideal) rcos_ring_hom_ring:
   144   "ring_hom_ring R (R Quot I) (op +> I)"
   145 apply (rule ring_hom_ringI)
   146      apply (rule is_ring, rule quotient_is_ring)
   147    apply (simp add: FactRing_def a_rcosetsI[OF a_subset])
   148   apply (simp add: FactRing_def rcoset_mult_add)
   149  apply (simp add: FactRing_def a_rcos_sum)
   150 apply (simp add: FactRing_def)
   151 done
   152 
   153 text {* The quotient of a cring is also commutative *}
   154 lemma (in ideal) quotient_is_cring:
   155   assumes "cring R"
   156   shows "cring (R Quot I)"
   157 proof -
   158   interpret cring R by fact
   159   show ?thesis apply (intro cring.intro comm_monoid.intro comm_monoid_axioms.intro)
   160   apply (rule quotient_is_ring)
   161  apply (rule ring.axioms[OF quotient_is_ring])
   162 apply (simp add: FactRing_def A_RCOSETS_defs a_r_coset_def[symmetric])
   163 apply clarify
   164 apply (simp add: rcoset_mult_add m_comm)
   165 done
   166 qed
   167 
   168 text {* Cosets as a ring homomorphism on crings *}
   169 lemma (in ideal) rcos_ring_hom_cring:
   170   assumes "cring R"
   171   shows "ring_hom_cring R (R Quot I) (op +> I)"
   172 proof -
   173   interpret cring R by fact
   174   show ?thesis apply (rule ring_hom_cringI)
   175   apply (rule rcos_ring_hom_ring)
   176  apply (rule is_cring)
   177 apply (rule quotient_is_cring)
   178 apply (rule is_cring)
   179 done
   180 qed
   181 
   182 
   183 subsection {* Factorization over Prime Ideals *}
   184 
   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"
   207 
   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
   215 
   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)
   220 
   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
   227 
   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)
   233 
   234 
   235 subsection {* Factorization over Maximal Ideals *}
   236 
   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"
   265 
   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
   273 
   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
   282 
   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
   286 
   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
   295 
   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
   303 
   304   from aJ and anI
   305   have JnI: "J \<noteq> I" by fast
   306 
   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
   317 
   318   from this and JnI
   319   have Jcarr: "J = carrier R" by simp
   320 
   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
   333 
   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)
   342 
   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
   347 
   348 end