src/HOL/Rings.thy
changeset 69593 3dda49e08b9d
parent 68253 a8660a39e304
child 69605 a96320074298
equal deleted inserted replaced
69592:a80d8ec6c998 69593:3dda49e08b9d
   646 text \<open>Syntactic division operator\<close>
   646 text \<open>Syntactic division operator\<close>
   647 
   647 
   648 class divide =
   648 class divide =
   649   fixes divide :: "'a \<Rightarrow> 'a \<Rightarrow> 'a"  (infixl "div" 70)
   649   fixes divide :: "'a \<Rightarrow> 'a \<Rightarrow> 'a"  (infixl "div" 70)
   650 
   650 
   651 setup \<open>Sign.add_const_constraint (@{const_name "divide"}, SOME @{typ "'a \<Rightarrow> 'a \<Rightarrow> 'a"})\<close>
   651 setup \<open>Sign.add_const_constraint (\<^const_name>\<open>divide\<close>, SOME \<^typ>\<open>'a \<Rightarrow> 'a \<Rightarrow> 'a\<close>)\<close>
   652 
   652 
   653 context semiring
   653 context semiring
   654 begin
   654 begin
   655 
   655 
   656 lemma [field_simps]:
   656 lemma [field_simps]:
   668     and right_diff_distrib_NO_MATCH: "NO_MATCH (x div y) a \<Longrightarrow> a * (b - c) = a * b - a * c"
   668     and right_diff_distrib_NO_MATCH: "NO_MATCH (x div y) a \<Longrightarrow> a * (b - c) = a * b - a * c"
   669   by (rule left_diff_distrib right_diff_distrib)+
   669   by (rule left_diff_distrib right_diff_distrib)+
   670 
   670 
   671 end
   671 end
   672 
   672 
   673 setup \<open>Sign.add_const_constraint (@{const_name "divide"}, SOME @{typ "'a::divide \<Rightarrow> 'a \<Rightarrow> 'a"})\<close>
   673 setup \<open>Sign.add_const_constraint (\<^const_name>\<open>divide\<close>, SOME \<^typ>\<open>'a::divide \<Rightarrow> 'a \<Rightarrow> 'a\<close>)\<close>
   674 
   674 
   675 text \<open>Algebraic classes with division\<close>
   675 text \<open>Algebraic classes with division\<close>
   676   
   676   
   677 class semidom_divide = semidom + divide +
   677 class semidom_divide = semidom + divide +
   678   assumes nonzero_mult_div_cancel_right [simp]: "b \<noteq> 0 \<Longrightarrow> (a * b) div b = a"
   678   assumes nonzero_mult_div_cancel_right [simp]: "b \<noteq> 0 \<Longrightarrow> (a * b) div b = a"
   778 
   778 
   779 class algebraic_semidom = semidom_divide
   779 class algebraic_semidom = semidom_divide
   780 begin
   780 begin
   781 
   781 
   782 text \<open>
   782 text \<open>
   783   Class @{class algebraic_semidom} enriches a integral domain
   783   Class \<^class>\<open>algebraic_semidom\<close> enriches a integral domain
   784   by notions from algebra, like units in a ring.
   784   by notions from algebra, like units in a ring.
   785   It is a separate class to avoid spoiling fields with notions
   785   It is a separate class to avoid spoiling fields with notions
   786   which are degenerated there.
   786   which are degenerated there.
   787 \<close>
   787 \<close>
   788 
   788 
  1290   assumes unit_factor_mult_normalize [simp]: "unit_factor a * normalize a = a"
  1290   assumes unit_factor_mult_normalize [simp]: "unit_factor a * normalize a = a"
  1291     and normalize_0 [simp]: "normalize 0 = 0"
  1291     and normalize_0 [simp]: "normalize 0 = 0"
  1292 begin
  1292 begin
  1293 
  1293 
  1294 text \<open>
  1294 text \<open>
  1295   Class @{class normalization_semidom} cultivates the idea that each integral
  1295   Class \<^class>\<open>normalization_semidom\<close> cultivates the idea that each integral
  1296   domain can be split into equivalence classes whose representants are
  1296   domain can be split into equivalence classes whose representants are
  1297   associated, i.e. divide each other. @{const normalize} specifies a canonical
  1297   associated, i.e. divide each other. \<^const>\<open>normalize\<close> specifies a canonical
  1298   representant for each equivalence class. The rationale behind this is that
  1298   representant for each equivalence class. The rationale behind this is that
  1299   it is easier to reason about equality than equivalences, hence we prefer to
  1299   it is easier to reason about equality than equivalences, hence we prefer to
  1300   think about equality of normalized values rather than associated elements.
  1300   think about equality of normalized values rather than associated elements.
  1301 \<close>
  1301 \<close>
  1302 
  1302 
  1550   "coprime a (normalize b) \<longleftrightarrow> coprime a b"
  1550   "coprime a (normalize b) \<longleftrightarrow> coprime a b"
  1551   using coprime_normalize_left_iff [of b a] by (simp add: ac_simps)
  1551   using coprime_normalize_left_iff [of b a] by (simp add: ac_simps)
  1552 
  1552 
  1553 text \<open>
  1553 text \<open>
  1554   We avoid an explicit definition of associated elements but prefer explicit
  1554   We avoid an explicit definition of associated elements but prefer explicit
  1555   normalisation instead. In theory we could define an abbreviation like @{prop
  1555   normalisation instead. In theory we could define an abbreviation like \<^prop>\<open>associated a b \<longleftrightarrow> normalize a = normalize b\<close> but this is counterproductive
  1556   "associated a b \<longleftrightarrow> normalize a = normalize b"} but this is counterproductive
       
  1557   without suggestive infix syntax, which we do not want to sacrifice for this
  1556   without suggestive infix syntax, which we do not want to sacrifice for this
  1558   purpose here.
  1557   purpose here.
  1559 \<close>
  1558 \<close>
  1560 
  1559 
  1561 lemma associatedI:
  1560 lemma associatedI:
  1768 ML_file "~~/src/Provers/Arith/cancel_div_mod.ML"
  1767 ML_file "~~/src/Provers/Arith/cancel_div_mod.ML"
  1769 
  1768 
  1770 ML \<open>
  1769 ML \<open>
  1771 structure Cancel_Div_Mod_Ring = Cancel_Div_Mod
  1770 structure Cancel_Div_Mod_Ring = Cancel_Div_Mod
  1772 (
  1771 (
  1773   val div_name = @{const_name divide};
  1772   val div_name = \<^const_name>\<open>divide\<close>;
  1774   val mod_name = @{const_name modulo};
  1773   val mod_name = \<^const_name>\<open>modulo\<close>;
  1775   val mk_binop = HOLogic.mk_binop;
  1774   val mk_binop = HOLogic.mk_binop;
  1776   val mk_sum = Arith_Data.mk_sum;
  1775   val mk_sum = Arith_Data.mk_sum;
  1777   val dest_sum = Arith_Data.dest_sum;
  1776   val dest_sum = Arith_Data.dest_sum;
  1778 
  1777 
  1779   val div_mod_eqs = map mk_meta_eq @{thms cancel_div_mod_rules};
  1778   val div_mod_eqs = map mk_meta_eq @{thms cancel_div_mod_rules};
  2177 
  2176 
  2178 lemma mult_le_0_iff: "a * b \<le> 0 \<longleftrightarrow> 0 \<le> a \<and> b \<le> 0 \<or> a \<le> 0 \<and> 0 \<le> b"
  2177 lemma mult_le_0_iff: "a * b \<le> 0 \<longleftrightarrow> 0 \<le> a \<and> b \<le> 0 \<or> a \<le> 0 \<and> 0 \<le> b"
  2179   using zero_le_mult_iff [of "- a" b] by auto
  2178   using zero_le_mult_iff [of "- a" b] by auto
  2180 
  2179 
  2181 text \<open>
  2180 text \<open>
  2182   Cancellation laws for @{term "c * a < c * b"} and @{term "a * c < b * c"},
  2181   Cancellation laws for \<^term>\<open>c * a < c * b\<close> and \<^term>\<open>a * c < b * c\<close>,
  2183   also with the relations \<open>\<le>\<close> and equality.
  2182   also with the relations \<open>\<le>\<close> and equality.
  2184 \<close>
  2183 \<close>
  2185 
  2184 
  2186 text \<open>
  2185 text \<open>
  2187   These ``disjunction'' versions produce two cases when the comparison is
  2186   These ``disjunction'' versions produce two cases when the comparison is