src/HOL/Groups.thy
changeset 57512 cc97b347b301
parent 56950 c49edf06f8e4
child 57514 bdc2c6b40bf2
equal deleted inserted replaced
57511:de51a86fc903 57512:cc97b347b301
   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
   323   assume "a + b = a + c" 
   331   assume "a + b = a + c" 
   324   then show "b = c" by (rule add_imp_eq)
   332   then show "b = c" by (rule add_imp_eq)
   325 next
   333 next
   326   fix a b c :: 'a
   334   fix a b c :: 'a
   327   assume "b + a = c + a"
   335   assume "b + a = c + a"
   328   then have "a + b = a + c" by (simp only: add_commute)
   336   then have "a + b = a + c" by (simp only: add.commute)
   329   then show "b = c" by (rule add_imp_eq)
   337   then show "b = c" by (rule add_imp_eq)
   330 qed
   338 qed
   331 
   339 
   332 end
   340 end
   333 
   341 
   347 
   355 
   348 lemma minus_unique:
   356 lemma minus_unique:
   349   assumes "a + b = 0" shows "- a = b"
   357   assumes "a + b = 0" shows "- a = b"
   350 proof -
   358 proof -
   351   have "- a = - a + (a + b)" using assms by simp
   359   have "- a = - a + (a + b)" using assms by simp
   352   also have "\<dots> = b" by (simp add: add_assoc [symmetric])
   360   also have "\<dots> = b" by (simp add: add.assoc [symmetric])
   353   finally show ?thesis .
   361   finally show ?thesis .
   354 qed
   362 qed
   355 
   363 
   356 lemma minus_zero [simp]: "- 0 = 0"
   364 lemma minus_zero [simp]: "- 0 = 0"
   357 proof -
   365 proof -
   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
   482 proof
   490 proof
   483   assume "a = - b" then show "a + b = 0" by simp
   491   assume "a = - b" then show "a + b = 0" by simp
   484 next
   492 next
   485   assume "a + b = 0"
   493   assume "a + b = 0"
   486   moreover have "a + (b + - b) = (a + b) + - b"
   494   moreover have "a + (b + - b) = (a + b) + - b"
   487     by (simp only: add_assoc)
   495     by (simp only: add.assoc)
   488   ultimately show "a = - b" by simp
   496   ultimately show "a = - b" by simp
   489 qed
   497 qed
   490 
   498 
   491 lemma add_eq_0_iff2:
   499 lemma add_eq_0_iff2:
   492   "a + b = 0 \<longleftrightarrow> a = - b"
   500   "a + b = 0 \<longleftrightarrow> a = - b"
   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