156 sublocale add!: semigroup plus |
156 sublocale add!: semigroup plus |
157 by default (fact add_assoc) |
157 by default (fact add_assoc) |
158 |
158 |
159 end |
159 end |
160 |
160 |
|
161 hide_fact add_assoc |
|
162 |
161 class ab_semigroup_add = semigroup_add + |
163 class ab_semigroup_add = semigroup_add + |
162 assumes add_commute [algebra_simps, field_simps]: "a + b = b + a" |
164 assumes add_commute [algebra_simps, field_simps]: "a + b = b + a" |
163 begin |
165 begin |
164 |
166 |
165 sublocale add!: abel_semigroup plus |
167 sublocale add!: abel_semigroup plus |
166 by default (fact add_commute) |
168 by default (fact add_commute) |
167 |
169 |
168 lemmas add_left_commute [algebra_simps, field_simps] = add.left_commute |
170 declare add.left_commute [algebra_simps, field_simps] |
169 |
171 |
170 theorems add_ac = add_assoc add_commute add_left_commute |
172 theorems add_ac = add.assoc add.commute add.left_commute |
171 |
173 |
172 end |
174 end |
173 |
175 |
174 theorems add_ac = add_assoc add_commute add_left_commute |
176 hide_fact add_commute |
|
177 |
|
178 theorems add_ac = add.assoc add.commute add.left_commute |
175 |
179 |
176 class semigroup_mult = times + |
180 class semigroup_mult = times + |
177 assumes mult_assoc [algebra_simps, field_simps]: "(a * b) * c = a * (b * c)" |
181 assumes mult_assoc [algebra_simps, field_simps]: "(a * b) * c = a * (b * c)" |
178 begin |
182 begin |
179 |
183 |
180 sublocale mult!: semigroup times |
184 sublocale mult!: semigroup times |
181 by default (fact mult_assoc) |
185 by default (fact mult_assoc) |
182 |
186 |
183 end |
187 end |
184 |
188 |
|
189 hide_fact mult_assoc |
|
190 |
185 class ab_semigroup_mult = semigroup_mult + |
191 class ab_semigroup_mult = semigroup_mult + |
186 assumes mult_commute [algebra_simps, field_simps]: "a * b = b * a" |
192 assumes mult_commute [algebra_simps, field_simps]: "a * b = b * a" |
187 begin |
193 begin |
188 |
194 |
189 sublocale mult!: abel_semigroup times |
195 sublocale mult!: abel_semigroup times |
190 by default (fact mult_commute) |
196 by default (fact mult_commute) |
191 |
197 |
192 lemmas mult_left_commute [algebra_simps, field_simps] = mult.left_commute |
198 declare mult.left_commute [algebra_simps, field_simps] |
193 |
199 |
194 theorems mult_ac = mult_assoc mult_commute mult_left_commute |
200 theorems mult_ac = mult.assoc mult.commute mult.left_commute |
195 |
201 |
196 end |
202 end |
197 |
203 |
198 theorems mult_ac = mult_assoc mult_commute mult_left_commute |
204 hide_fact mult_commute |
|
205 |
|
206 theorems mult_ac = mult.assoc mult.commute mult.left_commute |
199 |
207 |
200 class monoid_add = zero + semigroup_add + |
208 class monoid_add = zero + semigroup_add + |
201 assumes add_0_left: "0 + a = a" |
209 assumes add_0_left: "0 + a = a" |
202 and add_0_right: "a + 0 = a" |
210 and add_0_right: "a + 0 = a" |
203 begin |
211 begin |
379 subclass cancel_semigroup_add |
387 subclass cancel_semigroup_add |
380 proof |
388 proof |
381 fix a b c :: 'a |
389 fix a b c :: 'a |
382 assume "a + b = a + c" |
390 assume "a + b = a + c" |
383 then have "- a + a + b = - a + a + c" |
391 then have "- a + a + b = - a + a + c" |
384 unfolding add_assoc by simp |
392 unfolding add.assoc by simp |
385 then show "b = c" by simp |
393 then show "b = c" by simp |
386 next |
394 next |
387 fix a b c :: 'a |
395 fix a b c :: 'a |
388 assume "b + a = c + a" |
396 assume "b + a = c + a" |
389 then have "b + a + - a = c + a + - a" by simp |
397 then have "b + a + - a = c + a + - a" by simp |
390 then show "b = c" unfolding add_assoc by simp |
398 then show "b = c" unfolding add.assoc by simp |
391 qed |
399 qed |
392 |
400 |
393 lemma minus_add_cancel [simp]: |
401 lemma minus_add_cancel [simp]: |
394 "- a + (a + b) = b" |
402 "- a + (a + b) = b" |
395 by (simp add: add_assoc [symmetric]) |
403 by (simp add: add.assoc [symmetric]) |
396 |
404 |
397 lemma add_minus_cancel [simp]: |
405 lemma add_minus_cancel [simp]: |
398 "a + (- a + b) = b" |
406 "a + (- a + b) = b" |
399 by (simp add: add_assoc [symmetric]) |
407 by (simp add: add.assoc [symmetric]) |
400 |
408 |
401 lemma diff_add_cancel [simp]: |
409 lemma diff_add_cancel [simp]: |
402 "a - b + b = a" |
410 "a - b + b = a" |
403 by (simp only: diff_conv_add_uminus add_assoc) simp |
411 by (simp only: diff_conv_add_uminus add.assoc) simp |
404 |
412 |
405 lemma add_diff_cancel [simp]: |
413 lemma add_diff_cancel [simp]: |
406 "a + b - b = a" |
414 "a + b - b = a" |
407 by (simp only: diff_conv_add_uminus add_assoc) simp |
415 by (simp only: diff_conv_add_uminus add.assoc) simp |
408 |
416 |
409 lemma minus_add: |
417 lemma minus_add: |
410 "- (a + b) = - b + - a" |
418 "- (a + b) = - b + - a" |
411 proof - |
419 proof - |
412 have "(a + b) + (- b + - a) = 0" |
420 have "(a + b) + (- b + - a) = 0" |
413 by (simp only: add_assoc add_minus_cancel) simp |
421 by (simp only: add.assoc add_minus_cancel) simp |
414 then show "- (a + b) = - b + - a" |
422 then show "- (a + b) = - b + - a" |
415 by (rule minus_unique) |
423 by (rule minus_unique) |
416 qed |
424 qed |
417 |
425 |
418 lemma right_minus_eq [simp]: |
426 lemma right_minus_eq [simp]: |
419 "a - b = 0 \<longleftrightarrow> a = b" |
427 "a - b = 0 \<longleftrightarrow> a = b" |
420 proof |
428 proof |
421 assume "a - b = 0" |
429 assume "a - b = 0" |
422 have "a = (a - b) + b" by (simp add: add_assoc) |
430 have "a = (a - b) + b" by (simp add: add.assoc) |
423 also have "\<dots> = b" using `a - b = 0` by simp |
431 also have "\<dots> = b" using `a - b = 0` by simp |
424 finally show "a = b" . |
432 finally show "a = b" . |
425 next |
433 next |
426 assume "a = b" thus "a - b = 0" by simp |
434 assume "a = b" thus "a - b = 0" by simp |
427 qed |
435 qed |
500 "a + b = 0 \<longleftrightarrow> b = - a" |
508 "a + b = 0 \<longleftrightarrow> b = - a" |
501 by (auto simp add: neg_eq_iff_add_eq_0 [symmetric]) |
509 by (auto simp add: neg_eq_iff_add_eq_0 [symmetric]) |
502 |
510 |
503 lemma minus_diff_eq [simp]: |
511 lemma minus_diff_eq [simp]: |
504 "- (a - b) = b - a" |
512 "- (a - b) = b - a" |
505 by (simp only: neg_eq_iff_add_eq_0 diff_conv_add_uminus add_assoc minus_add_cancel) simp |
513 by (simp only: neg_eq_iff_add_eq_0 diff_conv_add_uminus add.assoc minus_add_cancel) simp |
506 |
514 |
507 lemma add_diff_eq [algebra_simps, field_simps]: |
515 lemma add_diff_eq [algebra_simps, field_simps]: |
508 "a + (b - c) = (a + b) - c" |
516 "a + (b - c) = (a + b) - c" |
509 by (simp only: diff_conv_add_uminus add_assoc) |
517 by (simp only: diff_conv_add_uminus add.assoc) |
510 |
518 |
511 lemma diff_add_eq_diff_diff_swap: |
519 lemma diff_add_eq_diff_diff_swap: |
512 "a - (b + c) = a - c - b" |
520 "a - (b + c) = a - c - b" |
513 by (simp only: diff_conv_add_uminus add_assoc minus_add) |
521 by (simp only: diff_conv_add_uminus add.assoc minus_add) |
514 |
522 |
515 lemma diff_eq_eq [algebra_simps, field_simps]: |
523 lemma diff_eq_eq [algebra_simps, field_simps]: |
516 "a - b = c \<longleftrightarrow> a = c + b" |
524 "a - b = c \<longleftrightarrow> a = c + b" |
517 by auto |
525 by auto |
518 |
526 |
520 "a = c - b \<longleftrightarrow> a + b = c" |
528 "a = c - b \<longleftrightarrow> a + b = c" |
521 by auto |
529 by auto |
522 |
530 |
523 lemma diff_diff_eq2 [algebra_simps, field_simps]: |
531 lemma diff_diff_eq2 [algebra_simps, field_simps]: |
524 "a - (b - c) = (a + c) - b" |
532 "a - (b - c) = (a + c) - b" |
525 by (simp only: diff_conv_add_uminus add_assoc) simp |
533 by (simp only: diff_conv_add_uminus add.assoc) simp |
526 |
534 |
527 lemma diff_eq_diff_eq: |
535 lemma diff_eq_diff_eq: |
528 "a - b = c - d \<Longrightarrow> a = b \<longleftrightarrow> c = d" |
536 "a - b = c - d \<Longrightarrow> a = b \<longleftrightarrow> c = d" |
529 by (simp only: eq_iff_diff_eq_0 [of a b] eq_iff_diff_eq_0 [of c d]) |
537 by (simp only: eq_iff_diff_eq_0 [of a b] eq_iff_diff_eq_0 [of c d]) |
530 |
538 |
541 subclass cancel_comm_monoid_add |
549 subclass cancel_comm_monoid_add |
542 proof |
550 proof |
543 fix a b c :: 'a |
551 fix a b c :: 'a |
544 assume "a + b = a + c" |
552 assume "a + b = a + c" |
545 then have "- a + a + b = - a + a + c" |
553 then have "- a + a + b = - a + a + c" |
546 by (simp only: add_assoc) |
554 by (simp only: add.assoc) |
547 then show "b = c" by simp |
555 then show "b = c" by simp |
548 qed |
556 qed |
549 |
557 |
550 lemma uminus_add_conv_diff [simp]: |
558 lemma uminus_add_conv_diff [simp]: |
551 "- a + b = b - a" |
559 "- a + b = b - a" |
552 by (simp add: add_commute) |
560 by (simp add: add.commute) |
553 |
561 |
554 lemma minus_add_distrib [simp]: |
562 lemma minus_add_distrib [simp]: |
555 "- (a + b) = - a + - b" |
563 "- (a + b) = - a + - b" |
556 by (simp add: algebra_simps) |
564 by (simp add: algebra_simps) |
557 |
565 |
593 assumes add_left_mono: "a \<le> b \<Longrightarrow> c + a \<le> c + b" |
601 assumes add_left_mono: "a \<le> b \<Longrightarrow> c + a \<le> c + b" |
594 begin |
602 begin |
595 |
603 |
596 lemma add_right_mono: |
604 lemma add_right_mono: |
597 "a \<le> b \<Longrightarrow> a + c \<le> b + c" |
605 "a \<le> b \<Longrightarrow> a + c \<le> b + c" |
598 by (simp add: add_commute [of _ c] add_left_mono) |
606 by (simp add: add.commute [of _ c] add_left_mono) |
599 |
607 |
600 text {* non-strict, in both arguments *} |
608 text {* non-strict, in both arguments *} |
601 lemma add_mono: |
609 lemma add_mono: |
602 "a \<le> b \<Longrightarrow> c \<le> d \<Longrightarrow> a + c \<le> b + d" |
610 "a \<le> b \<Longrightarrow> c \<le> d \<Longrightarrow> a + c \<le> b + d" |
603 apply (erule add_right_mono [THEN order_trans]) |
611 apply (erule add_right_mono [THEN order_trans]) |
604 apply (simp add: add_commute add_left_mono) |
612 apply (simp add: add.commute add_left_mono) |
605 done |
613 done |
606 |
614 |
607 end |
615 end |
608 |
616 |
609 class ordered_cancel_ab_semigroup_add = |
617 class ordered_cancel_ab_semigroup_add = |
614 "a < b \<Longrightarrow> c + a < c + b" |
622 "a < b \<Longrightarrow> c + a < c + b" |
615 by (auto simp add: less_le add_left_mono) |
623 by (auto simp add: less_le add_left_mono) |
616 |
624 |
617 lemma add_strict_right_mono: |
625 lemma add_strict_right_mono: |
618 "a < b \<Longrightarrow> a + c < b + c" |
626 "a < b \<Longrightarrow> a + c < b + c" |
619 by (simp add: add_commute [of _ c] add_strict_left_mono) |
627 by (simp add: add.commute [of _ c] add_strict_left_mono) |
620 |
628 |
621 text{*Strict monotonicity in both arguments*} |
629 text{*Strict monotonicity in both arguments*} |
622 lemma add_strict_mono: |
630 lemma add_strict_mono: |
623 "a < b \<Longrightarrow> c < d \<Longrightarrow> a + c < b + d" |
631 "a < b \<Longrightarrow> c < d \<Longrightarrow> a + c < b + d" |
624 apply (erule add_strict_right_mono [THEN less_trans]) |
632 apply (erule add_strict_right_mono [THEN less_trans]) |
663 qed |
671 qed |
664 |
672 |
665 lemma add_less_imp_less_right: |
673 lemma add_less_imp_less_right: |
666 "a + c < b + c \<Longrightarrow> a < b" |
674 "a + c < b + c \<Longrightarrow> a < b" |
667 apply (rule add_less_imp_less_left [of c]) |
675 apply (rule add_less_imp_less_left [of c]) |
668 apply (simp add: add_commute) |
676 apply (simp add: add.commute) |
669 done |
677 done |
670 |
678 |
671 lemma add_less_cancel_left [simp]: |
679 lemma add_less_cancel_left [simp]: |
672 "c + a < c + b \<longleftrightarrow> a < b" |
680 "c + a < c + b \<longleftrightarrow> a < b" |
673 by (blast intro: add_less_imp_less_left add_strict_left_mono) |
681 by (blast intro: add_less_imp_less_left add_strict_left_mono) |
680 "c + a \<le> c + b \<longleftrightarrow> a \<le> b" |
688 "c + a \<le> c + b \<longleftrightarrow> a \<le> b" |
681 by (auto, drule add_le_imp_le_left, simp_all add: add_left_mono) |
689 by (auto, drule add_le_imp_le_left, simp_all add: add_left_mono) |
682 |
690 |
683 lemma add_le_cancel_right [simp]: |
691 lemma add_le_cancel_right [simp]: |
684 "a + c \<le> b + c \<longleftrightarrow> a \<le> b" |
692 "a + c \<le> b + c \<longleftrightarrow> a \<le> b" |
685 by (simp add: add_commute [of a c] add_commute [of b c]) |
693 by (simp add: add.commute [of a c] add.commute [of b c]) |
686 |
694 |
687 lemma add_le_imp_le_right: |
695 lemma add_le_imp_le_right: |
688 "a + c \<le> b + c \<Longrightarrow> a \<le> b" |
696 "a + c \<le> b + c \<Longrightarrow> a \<le> b" |
689 by simp |
697 by simp |
690 |
698 |
719 "a + (b - a) = b" |
727 "a + (b - a) = b" |
720 using `a \<le> b` by (auto simp add: le_iff_add) |
728 using `a \<le> b` by (auto simp add: le_iff_add) |
721 |
729 |
722 lemma add_diff_assoc: |
730 lemma add_diff_assoc: |
723 "c + (b - a) = c + b - a" |
731 "c + (b - a) = c + b - a" |
724 using `a \<le> b` by (auto simp add: le_iff_add add_left_commute [of c]) |
732 using `a \<le> b` by (auto simp add: le_iff_add add.left_commute [of c]) |
725 |
733 |
726 lemma add_diff_assoc2: |
734 lemma add_diff_assoc2: |
727 "b - a + c = b + c - a" |
735 "b - a + c = b + c - a" |
728 using `a \<le> b` by (auto simp add: le_iff_add add_assoc) |
736 using `a \<le> b` by (auto simp add: le_iff_add add.assoc) |
729 |
737 |
730 lemma diff_add_assoc: |
738 lemma diff_add_assoc: |
731 "c + b - a = c + (b - a)" |
739 "c + b - a = c + (b - a)" |
732 using `a \<le> b` by (simp add: add_commute add_diff_assoc) |
740 using `a \<le> b` by (simp add: add.commute add_diff_assoc) |
733 |
741 |
734 lemma diff_add_assoc2: |
742 lemma diff_add_assoc2: |
735 "b + c - a = b - a + c" |
743 "b + c - a = b - a + c" |
736 using `a \<le> b`by (simp add: add_commute add_diff_assoc) |
744 using `a \<le> b`by (simp add: add.commute add_diff_assoc) |
737 |
745 |
738 lemma diff_diff_right: |
746 lemma diff_diff_right: |
739 "c - (b - a) = c + a - b" |
747 "c - (b - a) = c + a - b" |
740 by (simp add: add_diff_inverse add_diff_cancel_left [of a c "b - a", symmetric] add_commute) |
748 by (simp add: add_diff_inverse add_diff_cancel_left [of a c "b - a", symmetric] add.commute) |
741 |
749 |
742 lemma diff_add: |
750 lemma diff_add: |
743 "b - a + a = b" |
751 "b - a + a = b" |
744 by (simp add: add_commute add_diff_inverse) |
752 by (simp add: add.commute add_diff_inverse) |
745 |
753 |
746 lemma le_add_diff: |
754 lemma le_add_diff: |
747 "c \<le> b + c - a" |
755 "c \<le> b + c - a" |
748 by (auto simp add: add_commute diff_add_assoc2 le_iff_add) |
756 by (auto simp add: add.commute diff_add_assoc2 le_iff_add) |
749 |
757 |
750 lemma le_imp_diff_is_add: |
758 lemma le_imp_diff_is_add: |
751 "a \<le> b \<Longrightarrow> b - a = c \<longleftrightarrow> b = c + a" |
759 "a \<le> b \<Longrightarrow> b - a = c \<longleftrightarrow> b = c + a" |
752 by (auto simp add: add_commute add_diff_inverse) |
760 by (auto simp add: add.commute add_diff_inverse) |
753 |
761 |
754 lemma le_diff_conv2: |
762 lemma le_diff_conv2: |
755 "c \<le> b - a \<longleftrightarrow> c + a \<le> b" (is "?P \<longleftrightarrow> ?Q") |
763 "c \<le> b - a \<longleftrightarrow> c + a \<le> b" (is "?P \<longleftrightarrow> ?Q") |
756 proof |
764 proof |
757 assume ?P |
765 assume ?P |
758 then have "c + a \<le> b - a + a" by (rule add_right_mono) |
766 then have "c + a \<le> b - a + a" by (rule add_right_mono) |
759 then show ?Q by (simp add: add_diff_inverse add_commute) |
767 then show ?Q by (simp add: add_diff_inverse add.commute) |
760 next |
768 next |
761 assume ?Q |
769 assume ?Q |
762 then have "a + c \<le> a + (b - a)" by (simp add: add_diff_inverse add_commute) |
770 then have "a + c \<le> a + (b - a)" by (simp add: add_diff_inverse add.commute) |
763 then show ?P by simp |
771 then show ?P by simp |
764 qed |
772 qed |
765 |
773 |
766 end |
774 end |
767 |
775 |
858 "0 \<le> a \<Longrightarrow> b \<le> c \<Longrightarrow> b \<le> a + c" |
866 "0 \<le> a \<Longrightarrow> b \<le> c \<Longrightarrow> b \<le> a + c" |
859 by (insert add_mono [of 0 a b c], simp) |
867 by (insert add_mono [of 0 a b c], simp) |
860 |
868 |
861 lemma add_increasing2: |
869 lemma add_increasing2: |
862 "0 \<le> c \<Longrightarrow> b \<le> a \<Longrightarrow> b \<le> a + c" |
870 "0 \<le> c \<Longrightarrow> b \<le> a \<Longrightarrow> b \<le> a + c" |
863 by (simp add: add_increasing add_commute [of a]) |
871 by (simp add: add_increasing add.commute [of a]) |
864 |
872 |
865 lemma add_strict_increasing: |
873 lemma add_strict_increasing: |
866 "0 < a \<Longrightarrow> b \<le> c \<Longrightarrow> b < a + c" |
874 "0 < a \<Longrightarrow> b \<le> c \<Longrightarrow> b < a + c" |
867 by (insert add_less_le_mono [of 0 a b c], simp) |
875 by (insert add_less_le_mono [of 0 a b c], simp) |
868 |
876 |
881 subclass ordered_ab_semigroup_add_imp_le |
889 subclass ordered_ab_semigroup_add_imp_le |
882 proof |
890 proof |
883 fix a b c :: 'a |
891 fix a b c :: 'a |
884 assume "c + a \<le> c + b" |
892 assume "c + a \<le> c + b" |
885 hence "(-c) + (c + a) \<le> (-c) + (c + b)" by (rule add_left_mono) |
893 hence "(-c) + (c + a) \<le> (-c) + (c + b)" by (rule add_left_mono) |
886 hence "((-c) + c) + a \<le> ((-c) + c) + b" by (simp only: add_assoc) |
894 hence "((-c) + c) + a \<le> ((-c) + c) + b" by (simp only: add.assoc) |
887 thus "a \<le> b" by simp |
895 thus "a \<le> b" by simp |
888 qed |
896 qed |
889 |
897 |
890 subclass ordered_comm_monoid_add .. |
898 subclass ordered_comm_monoid_add .. |
891 |
899 |