src/HOL/Algebra/QuotRing.thy
 changeset 20318 0e0ea63fe768 child 21502 7f3ea2b3bab6
equal 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`