src/HOL/Rings.thy
changeset 71699 8e5c20e4e11a
parent 71697 34ff9ca387c0
child 73535 0f33c7031ec9
equal deleted inserted replaced
71698:b69dc6bcbea3 71699:8e5c20e4e11a
  2253 text \<open>
  2253 text \<open>
  2254   These ``disjunction'' versions produce two cases when the comparison is
  2254   These ``disjunction'' versions produce two cases when the comparison is
  2255   an assumption, but effectively four when the comparison is a goal.
  2255   an assumption, but effectively four when the comparison is a goal.
  2256 \<close>
  2256 \<close>
  2257 
  2257 
  2258 lemma mult_less_cancel_right_disj: "a * c < b * c \<longleftrightarrow> 0 < c \<and> a < b \<or> c < 0 \<and>  b < a"
  2258 lemma mult_less_cancel_right_disj: "a * c < b * c \<longleftrightarrow> 0 < c \<and> a < b \<or> c < 0 \<and> b < a"
  2259   apply (cases "c = 0")
  2259 proof (cases "c = 0")
  2260    apply (auto simp add: neq_iff mult_strict_right_mono mult_strict_right_mono_neg)
  2260   case False
  2261      apply (auto simp add: not_less not_le [symmetric, of "a*c"] not_le [symmetric, of a])
  2261   show ?thesis (is "?lhs \<longleftrightarrow> ?rhs")
  2262      apply (erule_tac [!] notE)
  2262   proof
  2263      apply (auto simp add: less_imp_le mult_right_mono mult_right_mono_neg)
  2263     assume ?lhs
  2264   done
  2264     then have "c < 0 \<Longrightarrow> b < a" "c > 0 \<Longrightarrow> b > a"
  2265 
  2265       by (auto simp flip: not_le intro: mult_right_mono mult_right_mono_neg)
  2266 lemma mult_less_cancel_left_disj: "c * a < c * b \<longleftrightarrow> 0 < c \<and> a < b \<or> c < 0 \<and>  b < a"
  2266     with False show ?rhs 
  2267   apply (cases "c = 0")
  2267       by (auto simp add: neq_iff)
  2268    apply (auto simp add: neq_iff mult_strict_left_mono mult_strict_left_mono_neg)
  2268   next
  2269      apply (auto simp add: not_less not_le [symmetric, of "c * a"] not_le [symmetric, of a])
  2269     assume ?rhs
  2270      apply (erule_tac [!] notE)
  2270     with False show ?lhs 
  2271      apply (auto simp add: less_imp_le mult_left_mono mult_left_mono_neg)
  2271       by (auto simp add: mult_strict_right_mono mult_strict_right_mono_neg)
  2272   done
  2272   qed
       
  2273 qed auto
       
  2274 
       
  2275 lemma mult_less_cancel_left_disj: "c * a < c * b \<longleftrightarrow> 0 < c \<and> a < b \<or> c < 0 \<and> b < a"
       
  2276 proof (cases "c = 0")
       
  2277   case False
       
  2278   show ?thesis (is "?lhs \<longleftrightarrow> ?rhs")
       
  2279   proof
       
  2280     assume ?lhs
       
  2281     then have "c < 0 \<Longrightarrow> b < a" "c > 0 \<Longrightarrow> b > a"
       
  2282       by (auto simp flip: not_le intro: mult_left_mono mult_left_mono_neg)
       
  2283     with False show ?rhs 
       
  2284       by (auto simp add: neq_iff)
       
  2285   next
       
  2286     assume ?rhs
       
  2287     with False show ?lhs 
       
  2288       by (auto simp add: mult_strict_left_mono mult_strict_left_mono_neg)
       
  2289   qed
       
  2290 qed auto
  2273 
  2291 
  2274 text \<open>
  2292 text \<open>
  2275   The ``conjunction of implication'' lemmas produce two cases when the
  2293   The ``conjunction of implication'' lemmas produce two cases when the
  2276   comparison is a goal, but give four when the comparison is an assumption.
  2294   comparison is a goal, but give four when the comparison is an assumption.
  2277 \<close>
  2295 \<close>
  2366   by (frule le_add_diff_inverse2) (simp add: add.commute)
  2384   by (frule le_add_diff_inverse2) (simp add: add.commute)
  2367 
  2385 
  2368 lemma add_diff_inverse: "\<not> a < b \<Longrightarrow> b + (a - b) = a"
  2386 lemma add_diff_inverse: "\<not> a < b \<Longrightarrow> b + (a - b) = a"
  2369   by simp
  2387   by simp
  2370 
  2388 
  2371 lemma add_le_imp_le_diff: "i + k \<le> n \<Longrightarrow> i \<le> n - k"
  2389 lemma add_le_imp_le_diff: 
  2372   apply (subst add_le_cancel_right [where c=k, symmetric])
  2390   assumes "i + k \<le> n" shows "i \<le> n - k"
  2373   apply (frule le_add_diff_inverse2)
  2391 proof -
  2374   apply (simp only: add.assoc [symmetric])
  2392   have "n - (i + k) + i + k = n"
  2375   using add_implies_diff
  2393     by (simp add: assms add.assoc)
  2376   apply fastforce
  2394   with assms add_implies_diff have "i + k \<le> n - k + k"
  2377   done
  2395     by fastforce
       
  2396   then show ?thesis
       
  2397     by simp
       
  2398 qed
  2378 
  2399 
  2379 lemma add_le_add_imp_diff_le:
  2400 lemma add_le_add_imp_diff_le:
  2380   assumes 1: "i + k \<le> n"
  2401   assumes 1: "i + k \<le> n"
  2381     and 2: "n \<le> j + k"
  2402     and 2: "n \<le> j + k"
  2382   shows "i + k \<le> n \<Longrightarrow> n \<le> j + k \<Longrightarrow> n - k \<le> j"
  2403   shows "i + k \<le> n \<Longrightarrow> n \<le> j + k \<Longrightarrow> n - k \<le> j"
  2383 proof -
  2404 proof -
  2384   have "n - (i + k) + (i + k) = n"
  2405   have "n - (i + k) + i + k = n"
  2385     using 1 by simp
  2406     using 1 by (simp add: add.assoc)
  2386   moreover have "n - k = n - k - i + i"
  2407   moreover have "n - k = n - k - i + i"
  2387     using 1 by (simp add: add_le_imp_le_diff)
  2408     using 1 by (simp add: add_le_imp_le_diff)
  2388   ultimately show ?thesis
  2409   ultimately show ?thesis
  2389     using 2
  2410     using 2 add_le_imp_le_diff [of "n-k" k "j + k"]
  2390     apply (simp add: add.assoc [symmetric])
  2411     by (simp add: add.commute diff_diff_add)
  2391     apply (rule add_le_imp_le_diff [of _ k "j + k", simplified add_diff_cancel_right'])
       
  2392     apply (simp add: add.commute diff_diff_add)
       
  2393     done
       
  2394 qed
  2412 qed
  2395 
  2413 
  2396 lemma less_1_mult: "1 < m \<Longrightarrow> 1 < n \<Longrightarrow> 1 < m * n"
  2414 lemma less_1_mult: "1 < m \<Longrightarrow> 1 < n \<Longrightarrow> 1 < m * n"
  2397   using mult_strict_mono [of 1 m 1 n] by (simp add: less_trans [OF zero_less_one])
  2415   using mult_strict_mono [of 1 m 1 n] by (simp add: less_trans [OF zero_less_one])
  2398 
  2416