src/HOL/Algebra/Ring.thy
changeset 68517 6b5f15387353
parent 68445 c183a6a69f2d
child 68551 b680e74eb6f2
equal deleted inserted replaced
68515:0854edc4d415 68517:6b5f15387353
   101     and "\<And>x. x \<in> carrier R \<Longrightarrow> \<exists>y \<in> carrier R. y \<oplus> x = \<zero>"
   101     and "\<And>x. x \<in> carrier R \<Longrightarrow> \<exists>y \<in> carrier R. y \<oplus> x = \<zero>"
   102   using abelian_group.a_comm_group assms comm_groupE by fastforce+
   102   using abelian_group.a_comm_group assms comm_groupE by fastforce+
   103 
   103 
   104 lemma (in abelian_monoid) a_monoid:
   104 lemma (in abelian_monoid) a_monoid:
   105   "monoid (add_monoid G)"
   105   "monoid (add_monoid G)"
   106 by (rule comm_monoid.axioms, rule a_comm_monoid) 
   106 by (rule comm_monoid.axioms, rule a_comm_monoid)
   107 
   107 
   108 lemma (in abelian_group) a_group:
   108 lemma (in abelian_group) a_group:
   109   "group (add_monoid G)"
   109   "group (add_monoid G)"
   110   by (simp add: group_def a_monoid)
   110   by (simp add: group_def a_monoid)
   111     (simp add: comm_group.axioms group.axioms a_comm_group)
   111     (simp add: comm_group.axioms group.axioms a_comm_group)
   123   by (rule a_monoid) (auto simp add: add_pow_def)
   123   by (rule a_monoid) (auto simp add: add_pow_def)
   124 
   124 
   125 context abelian_monoid
   125 context abelian_monoid
   126 begin
   126 begin
   127 
   127 
   128 lemmas a_closed = add.m_closed 
   128 lemmas a_closed = add.m_closed
   129 lemmas zero_closed = add.one_closed
   129 lemmas zero_closed = add.one_closed
   130 lemmas a_assoc = add.m_assoc
   130 lemmas a_assoc = add.m_assoc
   131 lemmas l_zero = add.l_one
   131 lemmas l_zero = add.l_one
   132 lemmas r_zero = add.r_one
   132 lemmas r_zero = add.r_one
   133 lemmas minus_unique = add.inv_unique
   133 lemmas minus_unique = add.inv_unique
   158 lemmas finsum_addf = add.finprod_multf
   158 lemmas finsum_addf = add.finprod_multf
   159 lemmas finsum_cong' = add.finprod_cong'
   159 lemmas finsum_cong' = add.finprod_cong'
   160 lemmas finsum_0 = add.finprod_0
   160 lemmas finsum_0 = add.finprod_0
   161 lemmas finsum_Suc = add.finprod_Suc
   161 lemmas finsum_Suc = add.finprod_Suc
   162 lemmas finsum_Suc2 = add.finprod_Suc2
   162 lemmas finsum_Suc2 = add.finprod_Suc2
   163 lemmas finsum_add = add.finprod_mult
       
   164 lemmas finsum_infinite = add.finprod_infinite
   163 lemmas finsum_infinite = add.finprod_infinite
   165 
   164 
   166 lemmas finsum_cong = add.finprod_cong
   165 lemmas finsum_cong = add.finprod_cong
   167 text \<open>Usually, if this rule causes a failed congruence proof error,
   166 text \<open>Usually, if this rule causes a failed congruence proof error,
   168    the reason is that the premise \<open>g \<in> B \<rightarrow> carrier G\<close> cannot be shown.
   167    the reason is that the premise \<open>g \<in> B \<rightarrow> carrier G\<close> cannot be shown.
   226        and "finprod (add_monoid G) = finsum G"
   225        and "finprod (add_monoid G) = finsum G"
   227        and "pow     (add_monoid G) = (\<lambda>a k. add_pow G k a)"
   226        and "pow     (add_monoid G) = (\<lambda>a k. add_pow G k a)"
   228   by (rule a_comm_group) (auto simp: m_inv_def a_inv_def finsum_def add_pow_def)
   227   by (rule a_comm_group) (auto simp: m_inv_def a_inv_def finsum_def add_pow_def)
   229 
   228 
   230 lemmas (in abelian_group) minus_add = add.inv_mult
   229 lemmas (in abelian_group) minus_add = add.inv_mult
   231  
   230 
   232 text \<open>Derive an \<open>abelian_group\<close> from a \<open>comm_group\<close>\<close>
   231 text \<open>Derive an \<open>abelian_group\<close> from a \<open>comm_group\<close>\<close>
   233 
   232 
   234 lemma comm_group_abelian_groupI:
   233 lemma comm_group_abelian_groupI:
   235   fixes G (structure)
   234   fixes G (structure)
   236   assumes cg: "comm_group (add_monoid G)"
   235   assumes cg: "comm_group (add_monoid G)"
   314     fix x y z
   313     fix x y z
   315     assume R: "x \<in> carrier R" "y \<in> carrier R" "z \<in> carrier R"
   314     assume R: "x \<in> carrier R" "y \<in> carrier R" "z \<in> carrier R"
   316     note [simp] = comm_monoid.axioms [OF comm_monoid]
   315     note [simp] = comm_monoid.axioms [OF comm_monoid]
   317       abelian_group.axioms [OF abelian_group]
   316       abelian_group.axioms [OF abelian_group]
   318       abelian_monoid.a_closed
   317       abelian_monoid.a_closed
   319         
   318 
   320     from R have "z \<otimes> (x \<oplus> y) = (x \<oplus> y) \<otimes> z"
   319     from R have "z \<otimes> (x \<oplus> y) = (x \<oplus> y) \<otimes> z"
   321       by (simp add: comm_monoid.m_comm [OF comm_monoid.intro])
   320       by (simp add: comm_monoid.m_comm [OF comm_monoid.intro])
   322     also from R have "... = x \<otimes> z \<oplus> y \<otimes> z" by (simp add: l_distr)
   321     also from R have "... = x \<otimes> z \<oplus> y \<otimes> z" by (simp add: l_distr)
   323     also from R have "... = z \<otimes> x \<oplus> z \<otimes> y"
   322     also from R have "... = z \<otimes> x \<oplus> z \<otimes> y"
   324       by (simp add: comm_monoid.m_comm [OF comm_monoid.intro])
   323       by (simp add: comm_monoid.m_comm [OF comm_monoid.intro])
   349 
   348 
   350 lemma (in abelian_group) r_neg1:
   349 lemma (in abelian_group) r_neg1:
   351   "\<lbrakk> x \<in> carrier G; y \<in> carrier G \<rbrakk> \<Longrightarrow> (\<ominus> x) \<oplus> (x \<oplus> y) = y"
   350   "\<lbrakk> x \<in> carrier G; y \<in> carrier G \<rbrakk> \<Longrightarrow> (\<ominus> x) \<oplus> (x \<oplus> y) = y"
   352 proof -
   351 proof -
   353   assume G: "x \<in> carrier G" "y \<in> carrier G"
   352   assume G: "x \<in> carrier G" "y \<in> carrier G"
   354   then have "(\<ominus> x \<oplus> x) \<oplus> y = y" 
   353   then have "(\<ominus> x \<oplus> x) \<oplus> y = y"
   355     by (simp only: l_neg l_zero)
   354     by (simp only: l_neg l_zero)
   356   with G show ?thesis by (simp add: a_ac)
   355   with G show ?thesis by (simp add: a_ac)
   357 qed
   356 qed
   358 
   357 
   359 lemma (in abelian_group) r_neg2:
   358 lemma (in abelian_group) r_neg2:
   437 
   436 
   438 lemmas (in semiring) semiring_simprules
   437 lemmas (in semiring) semiring_simprules
   439   [algebra ring "zero R" "add R" "a_inv R" "a_minus R" "one R" "mult R"] =
   438   [algebra ring "zero R" "add R" "a_inv R" "a_minus R" "one R" "mult R"] =
   440   a_closed zero_closed  m_closed one_closed
   439   a_closed zero_closed  m_closed one_closed
   441   a_assoc l_zero  a_comm m_assoc l_one l_distr r_zero
   440   a_assoc l_zero  a_comm m_assoc l_one l_distr r_zero
   442   a_lcomm r_distr l_null r_null 
   441   a_lcomm r_distr l_null r_null
   443 
   442 
   444 lemmas (in ring) ring_simprules
   443 lemmas (in ring) ring_simprules
   445   [algebra ring "zero R" "add R" "a_inv R" "a_minus R" "one R" "mult R"] =
   444   [algebra ring "zero R" "add R" "a_inv R" "a_minus R" "one R" "mult R"] =
   446   a_closed zero_closed a_inv_closed minus_closed m_closed one_closed
   445   a_closed zero_closed a_inv_closed minus_closed m_closed one_closed
   447   a_assoc l_zero l_neg a_comm m_assoc l_one l_distr minus_eq
   446   a_assoc l_zero l_neg a_comm m_assoc l_one l_distr minus_eq
   547 
   546 
   548 lemma add_pow_int_ge: "(k :: int) \<ge> 0 \<Longrightarrow> [ k ] \<cdot>\<^bsub>R\<^esub> a = [ nat k ] \<cdot>\<^bsub>R\<^esub> a"
   547 lemma add_pow_int_ge: "(k :: int) \<ge> 0 \<Longrightarrow> [ k ] \<cdot>\<^bsub>R\<^esub> a = [ nat k ] \<cdot>\<^bsub>R\<^esub> a"
   549   by (simp add: add_pow_def int_pow_def nat_pow_def)
   548   by (simp add: add_pow_def int_pow_def nat_pow_def)
   550 
   549 
   551 lemma add_pow_int_lt: "(k :: int) < 0 \<Longrightarrow> [ k ] \<cdot>\<^bsub>R\<^esub> a = \<ominus>\<^bsub>R\<^esub> ([ nat (- k) ] \<cdot>\<^bsub>R\<^esub> a)"
   550 lemma add_pow_int_lt: "(k :: int) < 0 \<Longrightarrow> [ k ] \<cdot>\<^bsub>R\<^esub> a = \<ominus>\<^bsub>R\<^esub> ([ nat (- k) ] \<cdot>\<^bsub>R\<^esub> a)"
   552   by (simp add: int_pow_def nat_pow_def a_inv_def add_pow_def) 
   551   by (simp add: int_pow_def nat_pow_def a_inv_def add_pow_def)
   553 
   552 
   554 corollary (in semiring) add_pow_ldistr:
   553 corollary (in semiring) add_pow_ldistr:
   555   assumes "a \<in> carrier R" "b \<in> carrier R"
   554   assumes "a \<in> carrier R" "b \<in> carrier R"
   556   shows "([(k :: nat)] \<cdot> a) \<otimes> b = [k] \<cdot> (a \<otimes> b)"
   555   shows "([(k :: nat)] \<cdot> a) \<otimes> b = [k] \<cdot> (a \<otimes> b)"
   557 proof -
   556 proof -
   573   also have " ... = (\<Oplus> i \<in> {..< k}. (a \<otimes> b))"
   572   also have " ... = (\<Oplus> i \<in> {..< k}. (a \<otimes> b))"
   574     using finsum_rdistr[of "{..<k}" a "\<lambda>x. b"] assms by simp
   573     using finsum_rdistr[of "{..<k}" a "\<lambda>x. b"] assms by simp
   575   also have " ... = [k] \<cdot> (a \<otimes> b)"
   574   also have " ... = [k] \<cdot> (a \<otimes> b)"
   576     using add.finprod_const[of "a \<otimes> b" "{..<k}"] assms by simp
   575     using add.finprod_const[of "a \<otimes> b" "{..<k}"] assms by simp
   577   finally show ?thesis .
   576   finally show ?thesis .
   578 qed 
   577 qed
   579 
   578 
   580 (* For integers, we need the uniqueness of the additive inverse *)
   579 (* For integers, we need the uniqueness of the additive inverse *)
   581 lemma (in ring) add_pow_ldistr_int:
   580 lemma (in ring) add_pow_ldistr_int:
   582   assumes "a \<in> carrier R" "b \<in> carrier R"
   581   assumes "a \<in> carrier R" "b \<in> carrier R"
   583   shows "([(k :: int)] \<cdot> a) \<otimes> b = [k] \<cdot> (a \<otimes> b)"
   582   shows "([(k :: int)] \<cdot> a) \<otimes> b = [k] \<cdot> (a \<otimes> b)"
   585   case True thus ?thesis
   584   case True thus ?thesis
   586     using add_pow_int_ge[of k R] add_pow_ldistr[OF assms] by auto
   585     using add_pow_int_ge[of k R] add_pow_ldistr[OF assms] by auto
   587 next
   586 next
   588   case False thus ?thesis
   587   case False thus ?thesis
   589     using add_pow_int_lt[of k R a] add_pow_int_lt[of k R "a \<otimes> b"]
   588     using add_pow_int_lt[of k R a] add_pow_int_lt[of k R "a \<otimes> b"]
   590           add_pow_ldistr[OF assms, of "nat (- k)"] assms l_minus by auto 
   589           add_pow_ldistr[OF assms, of "nat (- k)"] assms l_minus by auto
   591 qed
   590 qed
   592 
   591 
   593 lemma (in ring) add_pow_rdistr_int:
   592 lemma (in ring) add_pow_rdistr_int:
   594   assumes "a \<in> carrier R" "b \<in> carrier R"
   593   assumes "a \<in> carrier R" "b \<in> carrier R"
   595   shows "a \<otimes> ([(k :: int)] \<cdot> b) = [k] \<cdot> (a \<otimes> b)"
   594   shows "a \<otimes> ([(k :: int)] \<cdot> b) = [k] \<cdot> (a \<otimes> b)"
   597   case True thus ?thesis
   596   case True thus ?thesis
   598     using add_pow_int_ge[of k R] add_pow_rdistr[OF assms] by auto
   597     using add_pow_int_ge[of k R] add_pow_rdistr[OF assms] by auto
   599 next
   598 next
   600   case False thus ?thesis
   599   case False thus ?thesis
   601     using add_pow_int_lt[of k R b] add_pow_int_lt[of k R "a \<otimes> b"]
   600     using add_pow_int_lt[of k R b] add_pow_int_lt[of k R "a \<otimes> b"]
   602           add_pow_rdistr[OF assms, of "nat (- k)"] assms r_minus by auto 
   601           add_pow_rdistr[OF assms, of "nat (- k)"] assms r_minus by auto
   603 qed
   602 qed
   604 
   603 
   605 
   604 
   606 subsection \<open>Integral Domains\<close>
   605 subsection \<open>Integral Domains\<close>
   607 
   606 
   626   shows "(a \<otimes> b = a \<otimes> c) = (b = c)"
   625   shows "(a \<otimes> b = a \<otimes> c) = (b = c)"
   627 proof
   626 proof
   628   assume eq: "a \<otimes> b = a \<otimes> c"
   627   assume eq: "a \<otimes> b = a \<otimes> c"
   629   with R have "a \<otimes> (b \<ominus> c) = \<zero>" by algebra
   628   with R have "a \<otimes> (b \<ominus> c) = \<zero>" by algebra
   630   with R have "a = \<zero> \<or> (b \<ominus> c) = \<zero>" by (simp add: integral_iff)
   629   with R have "a = \<zero> \<or> (b \<ominus> c) = \<zero>" by (simp add: integral_iff)
   631   with prem and R have "b \<ominus> c = \<zero>" by auto 
   630   with prem and R have "b \<ominus> c = \<zero>" by auto
   632   with R have "b = b \<ominus> (b \<ominus> c)" by algebra
   631   with R have "b = b \<ominus> (b \<ominus> c)" by algebra
   633   also from R have "b \<ominus> (b \<ominus> c) = c" by algebra
   632   also from R have "b \<ominus> (b \<ominus> c) = c" by algebra
   634   finally show "b = c" .
   633   finally show "b = c" .
   635 next
   634 next
   636   assume "b = c" then show "a \<otimes> b = a \<otimes> c" by simp
   635   assume "b = c" then show "a \<otimes> b = a \<otimes> c" by simp