src/HOL/Nat.thy
changeset 25111 d52a58b51f1f
parent 25076 a50b36401c61
child 25134 3d4953e88449
equal deleted inserted replaced
25110:7253d331e9fc 25111:d52a58b51f1f
   495   by (cases n) simp_all
   495   by (cases n) simp_all
   496 
   496 
   497 lemma gr_implies_not0: fixes n :: nat shows "m<n ==> n \<noteq> 0"
   497 lemma gr_implies_not0: fixes n :: nat shows "m<n ==> n \<noteq> 0"
   498   by (cases n) simp_all
   498   by (cases n) simp_all
   499 
   499 
   500 lemma neq0_conv [iff]: fixes n :: nat shows "(n \<noteq> 0) = (0 < n)"
   500 lemma neq0_conv: fixes n :: nat shows "(n \<noteq> 0) = (0 < n)"
   501   by (cases n) simp_all
   501   by (cases n) simp_all
   502 
   502 
   503 text {* This theorem is useful with @{text blast} *}
   503 text {* This theorem is useful with @{text blast} *}
   504 lemma gr0I: "((n::nat) = 0 ==> False) ==> 0 < n"
   504 lemma gr0I: "((n::nat) = 0 ==> False) ==> 0 < n"
   505   by (rule iffD1, rule neq0_conv, iprover)
   505   by (rule iffD1, rule neq0_conv, iprover)
   508   by (fast intro: not0_implies_Suc)
   508   by (fast intro: not0_implies_Suc)
   509 
   509 
   510 lemma not_gr0 [iff,noatp]: "!!n::nat. (~ (0 < n)) = (n = 0)"
   510 lemma not_gr0 [iff,noatp]: "!!n::nat. (~ (0 < n)) = (n = 0)"
   511   apply (rule iffI)
   511   apply (rule iffI)
   512   apply (rule ccontr)
   512   apply (rule ccontr)
   513   apply simp_all
   513   apply (simp_all add: neq0_conv)
   514   done
   514   done
   515 
   515 
   516 lemma Suc_le_D: "(Suc n \<le> m') ==> (? m. m' = Suc m)"
   516 lemma Suc_le_D: "(Suc n \<le> m') ==> (? m. m' = Suc m)"
   517   by (induct m') simp_all
   517   by (induct m') simp_all
   518 
   518 
   602   Could be (and is, below) generalized in various ways
   602   Could be (and is, below) generalized in various ways
   603   However, none of the generalizations are currently in the simpset,
   603   However, none of the generalizations are currently in the simpset,
   604   and I dread to think what happens if I put them in
   604   and I dread to think what happens if I put them in
   605 *}
   605 *}
   606 lemma Suc_pred [simp]: "0 < n ==> Suc (n - Suc 0) = n"
   606 lemma Suc_pred [simp]: "0 < n ==> Suc (n - Suc 0) = n"
   607   by (simp split add: nat.split)
   607   by (simp add: neq0_conv split add: nat.split)
   608 
   608 
   609 declare diff_Suc [simp del, code del]
   609 declare diff_Suc [simp del, code del]
   610 
   610 
   611 
   611 
   612 subsection {* Addition *}
   612 subsection {* Addition *}
  1082 
  1082 
  1083 lemma mult_le_cancel2 [simp]: "((m::nat) * k \<le> n * k) = (0 < k --> m \<le> n)"
  1083 lemma mult_le_cancel2 [simp]: "((m::nat) * k \<le> n * k) = (0 < k --> m \<le> n)"
  1084 by (simp add: linorder_not_less [symmetric], auto)
  1084 by (simp add: linorder_not_less [symmetric], auto)
  1085 
  1085 
  1086 lemma mult_cancel2 [simp]: "(m * k = n * k) = (m = n | (k = (0::nat)))"
  1086 lemma mult_cancel2 [simp]: "(m * k = n * k) = (m = n | (k = (0::nat)))"
  1087   apply (cut_tac less_linear, safe, auto)
  1087   apply (cut_tac less_linear, safe, auto simp add: neq0_conv)
  1088   apply (drule mult_less_mono1, assumption, simp)+
  1088   apply (drule mult_less_mono1, assumption, simp)+
  1089   done
  1089   done
  1090 
  1090 
  1091 lemma mult_cancel1 [simp]: "(k * m = k * n) = (m = n | (k = (0::nat)))"
  1091 lemma mult_cancel1 [simp]: "(k * m = k * n) = (m = n | (k = (0::nat)))"
  1092 by (simp add: mult_commute [of k])
  1092 by (simp add: mult_commute [of k])
  1103 text {* Lemma for @{text gcd} *}
  1103 text {* Lemma for @{text gcd} *}
  1104 lemma mult_eq_self_implies_10: "(m::nat) = m * n ==> n = 1 | m = 0"
  1104 lemma mult_eq_self_implies_10: "(m::nat) = m * n ==> n = 1 | m = 0"
  1105   apply (drule sym)
  1105   apply (drule sym)
  1106   apply (rule disjCI)
  1106   apply (rule disjCI)
  1107   apply (rule nat_less_cases, erule_tac [2] _)
  1107   apply (rule nat_less_cases, erule_tac [2] _)
  1108   apply (fastsimp elim!: less_SucE)
  1108   apply (fastsimp simp add: neq0_conv elim!: less_SucE)
  1109   apply (fastsimp dest: mult_less_mono2)
  1109   apply (fastsimp simp add: neq0_conv dest: mult_less_mono2)
  1110   done
  1110   done
  1111 
  1111 
  1112 
  1112 
  1113 subsection {* size of a datatype value *}
  1113 subsection {* size of a datatype value *}
  1114 
  1114