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