equal
deleted
inserted
replaced
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 |