Quelle  Nonpos_Ints.thy

(*  Title:    HOL/Library/Nonpos_Ints.thy
  Author: Manuel Eberl, TU München
*)

section ‹Non-negative, non-positive integers and reals›

theory Nonpos_Ints
imports Complex_Main
begin

subsection‹Non-positive integers›
text ‹
  The set of non-positive integers on a ring. (in analogy to the set of non-negative
  integers 🍋‹ℕ›) This is useful e.g. for the Gamma function.
 ›

definition nonpos_Ints (‹ℤ🪙≤🪙0›) where "ℤ🪙≤🪙0 = {of_int n |n. n ≤ 0}"

lemma zero_in_nonpos_Ints [simp,intro]: "0 ∈ ℤ🪙≤🪙0"
  unfolding nonpos_Ints_def by (auto intro!: exI[of _ "0::int"])

lemma neg_one_in_nonpos_Ints [simp,intro]: "-1 ∈ ℤ🪙≤🪙0"
  unfolding nonpos_Ints_def by (auto intro!: exI[of _ "-1::int"])

lemma neg_numeral_in_nonpos_Ints [simp,intro]: "-numeral n ∈ ℤ🪙≤🪙0"
  unfolding nonpos_Ints_def by (auto intro!: exI[of _ "-numeral n::int"])

lemma one_notin_nonpos_Ints [simp]: "(1 :: 'a :: ring_char_0) ∉ ℤ🪙≤🪙0"
  by (auto simp: nonpos_Ints_def)

lemma numeral_notin_nonpos_Ints [simp]: "(numeral n :: 'a :: ring_char_0) ∉ ℤ🪙≤🪙0"
  by (auto simp: nonpos_Ints_def)

lemma minus_of_nat_in_nonpos_Ints [simp, intro]: "- of_nat n ∈ ℤ🪙≤🪙0"
proof -
  have "- of_nat n = of_int (-int n)" by simp
  also have "-int n ≤ 0" by simp
  hence "of_int (-int n) ∈ ℤ🪙≤🪙0" unfolding nonpos_Ints_def by blast
  finally show ?thesis .
qed

lemma of_nat_in_nonpos_Ints_iff: "(of_nat n :: 'a :: {ring_1,ring_char_0}) ∈ ℤ🪙≤??0 ⟷ n = 0"
proof
  assume "(of_nat n :: 'a) ∈ ℤ🪙≤🪙0"
  then obtain m where "of_nat n = (of_int m :: 'a)" "m ≤ 0" by (auto simp: nonpos_Ints_def)
  hence "(of_int m :: 'a) = of_nat n" by simp
  also have "... = of_int (int n)" by simp
  finally have "m = int n" by (subst (asm) of_int_eq_iff)
  with ‹m ≤ 0› show "n = 0" by auto
qed simp

lemma nonpos_Ints_of_int: "n ≤ 0 ==> of_int n ∈ ℤ🪙≤🪙0"
  unfolding nonpos_Ints_def by blast

lemma nonpos_IntsI: 
  "x ∈ ℤ ==> x ≤ 0 ==> (x :: 'a :: linordered_idom) ∈ ℤ🪙≤🪙0"
  unfolding nonpos_Ints_def Ints_def by auto

lemma nonpos_Ints_subset_Ints: "ℤ🪙≤🪙0 ⊆ ℤ"
  unfolding nonpos_Ints_def Ints_def by blast

lemma nonpos_Ints_nonpos [dest]: "x ∈ ℤ🪙≤🪙0 ==> x ≤ (0 :: 'a :: linordered_idom)"
  unfolding nonpos_Ints_def by auto

lemma nonpos_Ints_Int [dest]: "x ∈ ℤ🪙≤🪙0 ==> x ∈ ℤ"
  unfolding nonpos_Ints_def Ints_def by blast

lemma nonpos_Ints_cases:
  assumes "x ∈ ℤ🪙≤🪙0"
  obtains n where "x = of_int n" "n ≤ 0"
  using assms unfolding nonpos_Ints_def by (auto elim!: Ints_cases)

lemma nonpos_Ints_cases':
  assumes "x ∈ ℤ🪙≤🪙0"
  obtains n where "x = -of_nat n"
proof -
  from assms obtain m where "x = of_int m" and m: "m ≤ 0" by (auto elim!: nonpos_Ints_cases)
  hence "x = - of_int (-m)" by auto
  also from m have "(of_int (-m) :: 'a) = of_nat (nat (-m))" by simp_all
  finally show ?thesis by (rule that)
qed

lemma of_real_in_nonpos_Ints_iff: "(of_real x :: 'a :: real_algebra_1) ∈ ℤ🪙≤🪙0 ⟷ x ∈ ℤ🪙≤🪙0"
proof
  assume "of_real x ∈ (ℤ🪙≤🪙0 :: 'a set)"
  then obtain n where "(of_real x :: 'a) = of_int n" "n ≤ 0" by (erule nonpos_Ints_cases)
  note ‹of_real x = of_int n›
  also have "of_int n = of_real (of_int n)" by (rule of_real_of_int_eq [symmetric])
  finally have "x = of_int n" by (subst (asm) of_real_eq_iff)
  with ‹n ≤ 0› show "x ∈ ℤ🪙≤🪙0" by (simp add: nonpos_Ints_of_int)
qed (auto elim!: nonpos_Ints_cases intro!: nonpos_Ints_of_int)

lemma nonpos_Ints_altdef: "ℤ🪙≤🪙0 = {n ∈ ℤ. (n :: 'a :: linordered_idom) ≤ 0}"
  by (auto intro!: nonpos_IntsI elim!: nonpos_Ints_cases)

lemma uminus_in_Nats_iff: "-x ∈ ℕ ⟷ x ∈ ℤ🪙≤🪙0"
proof
  assume "-x ∈ ℕ"
  then obtain n where "n ≥ 0" "-x = of_int n" by (auto simp: Nats_altdef1)
  hence "-n ≤ 0" "x = of_int (-n)" by (simp_all add: eq_commute minus_equation_iff[of x])
  thus "x ∈ ℤ🪙≤🪙0" unfolding nonpos_Ints_def by blast
next
  assume "x ∈ ℤ🪙≤🪙0"
  then obtain n where "n ≤ 0" "x = of_int n" by (auto simp: nonpos_Ints_def)
  hence "-n ≥ 0" "-x = of_int (-n)" by (simp_all add: eq_commute minus_equation_iff[of x])
  thus "-x ∈ ℕ" unfolding Nats_altdef1 by blast
qed

lemma uminus_in_nonpos_Ints_iff: "-x ∈ ℤ🪙≤🪙0 ⟷ x ∈ ℕ"
  using uminus_in_Nats_iff[of "-x"] by simp

lemma nonpos_Ints_mult: "x ∈ ℤ🪙≤🪙0 ==> y ∈ ℤ🪙≤🪙0 ==> x * y ∈ ℕ"
  using Nats_mult[of "-x" "-y"] by (simp add: uminus_in_Nats_iff)

lemma Nats_mult_nonpos_Ints: "x ∈ ℕ ==> y ∈ ℤ🪙≤🪙0 ==> x * y ∈ ℤ🪙≤🪙0"
  using Nats_mult[of x "-y"] by (simp add: uminus_in_Nats_iff)

lemma nonpos_Ints_mult_Nats:
  "x ∈ ℤ🪙≤🪙0 ==> y ∈ ℕ ==> x * y ∈ ℤ🪙≤🪙0"
  using Nats_mult[of "-x" y] by (simp add: uminus_in_Nats_iff)

lemma nonpos_Ints_add:
  "x ∈ ℤ🪙≤🪙0 ==> y ∈ ℤ🪙≤🪙0 ==> x + y ∈ ℤ🪙≤🪙0"
  using Nats_add[of "-x" "-y"] uminus_in_Nats_iff[of "y+x", simplified minus_add] 
  by (simp add: uminus_in_Nats_iff add.commute)

lemma nonpos_Ints_diff_Nats:
  "x ∈ ℤ🪙≤🪙0 ==> y ∈ ℕ ==> x - y ∈ ℤ🪙≤🪙0"
  using Nats_add[of "-x" "y"] uminus_in_Nats_iff[of "x-y", simplified minus_add] 
  by (simp add: uminus_in_Nats_iff add.commute)

lemma Nats_diff_nonpos_Ints:
  "x ∈ ℕ ==> y ∈ ℤ🪙≤🪙0 ==> x - y ∈ ℕ"
  using Nats_add[of "x" "-y"] by (simp add: uminus_in_Nats_iff add.commute)

lemma plus_of_nat_eq_0_imp: "z + of_nat n = 0 ==> z ∈ ℤ🪙≤🪙0"
proof -
  assume "z + of_nat n = 0"
  hence A: "z = - of_nat n" by (simp add: eq_neg_iff_add_eq_0)
  show "z ∈ ℤ🪙≤🪙0" by (subst A) simp
qed


subsection‹Non-negative reals›

definition nonneg_Reals :: "'a::real_algebra_1 set"  (‹ℝ🪙≥🪙0›)
  where "ℝ🪙≥🪙0 = {of_real r | r. r ≥ 0}"

lemma nonneg_Reals_of_real_iff [simp]: "of_real r ∈ ℝ🪙≥🪙0 ⟷ r ≥ 0"
  by (force simp add: nonneg_Reals_def)

lemma nonneg_Reals_subset_Reals: "ℝ🪙≥🪙0 ⊆ ℝ"
  unfolding nonneg_Reals_def Reals_def by blast

lemma nonneg_Reals_Real [dest]: "x ∈ ℝ🪙≥🪙0 ==> x ∈ ℝ"
  unfolding nonneg_Reals_def Reals_def by blast

lemma nonneg_Reals_of_nat_I [simp]: "of_nat n ∈ ℝ🪙≥🪙0"
  by (metis nonneg_Reals_of_real_iff of_nat_0_le_iff of_real_of_nat_eq)

lemma nonneg_Reals_cases:
  assumes "x ∈ ℝ🪙≥🪙0"
  obtains r where "x = of_real r" "r ≥ 0"
  using assms unfolding nonneg_Reals_def by (auto elim!: Reals_cases)

lemma nonneg_Reals_zero_I [simp]: "0 ∈ ℝ🪙≥🪙0"
  unfolding nonneg_Reals_def by auto

lemma nonneg_Reals_one_I [simp]: "1 ∈ ℝ🪙≥🪙0"
  by (metis (mono_tags, lifting) nonneg_Reals_of_nat_I of_nat_1)

lemma nonneg_Reals_minus_one_I [simp]: "-1 ∉ ℝ🪙≥🪙0"
  by (metis nonneg_Reals_of_real_iff le_minus_one_simps(3) of_real_1 of_real_def real_vector.scale_minus_left)

lemma nonneg_Reals_numeral_I [simp]: "numeral w ∈ ℝ🪙≥🪙0"
  by (metis (no_types) nonneg_Reals_of_nat_I of_nat_numeral)

lemma nonneg_Reals_minus_numeral_I [simp]: "- numeral w ∉ ℝ🪙≥🪙0"
  using nonneg_Reals_of_real_iff not_zero_le_neg_numeral by fastforce

lemma nonneg_Reals_add_I [simp]: "[a ∈ ℝ🪙≥🪙0; b ∈ ℝ🪙≥🪙0] ==> a + b ∈ ℝ🪙≥🪙0"
apply (simp add: nonneg_Reals_def)
apply clarify
apply (rename_tac r s)
apply (rule_tac x="r+s" in exI, auto)
done

lemma nonneg_Reals_mult_I [simp]: "[a ∈ ℝ🪙≥🪙0; b ∈ ℝ🪙≥🪙0] ==> a * b ∈ ℝ🪙≥🪙0"
  unfolding nonneg_Reals_def  by (auto simp: of_real_def)

lemma nonneg_Reals_inverse_I [simp]:
  fixes a :: "'a::real_div_algebra"
  shows "a ∈ ℝ🪙≥🪙0 ==> inverse a ∈ ℝ🪙≥🪙0"
  by (simp add: nonneg_Reals_def image_iff) (metis inverse_nonnegative_iff_nonnegative of_real_inverse)

lemma nonneg_Reals_divide_I [simp]:
  fixes a :: "'a::real_div_algebra"
  shows "[a ∈ ℝ🪙≥🪙0; b ∈ ℝ🪙≥🪙0] ==> a / b ∈ ℝ🪙≥🪙0"
  by (simp add: divide_inverse)

lemma nonneg_Reals_pow_I [simp]: "a ∈ ℝ🪙≥🪙0 ==> a^n ∈ ℝ🪙≥🪙0"
  by (induction n) auto

lemma complex_nonneg_Reals_iff: "z ∈ ℝ🪙≥🪙0 ⟷ Re z ≥ 0 ∧ Im z = 0"
  by (auto simp: nonneg_Reals_def) (metis complex_of_real_def complex_surj)

lemma ii_not_nonneg_Reals [iff]: "i ∉ ℝ🪙≥🪙0"
  by (simp add: complex_nonneg_Reals_iff)


subsection‹Non-positive reals›

definition nonpos_Reals :: "'a::real_algebra_1 set"  (‹ℝ🪙≤🪙0›)
  where "ℝ🪙≤🪙0 = {of_real r | r. r ≤ 0}"

lemma nonpos_Reals_of_real_iff [simp]: "of_real r ∈ ℝ🪙≤🪙0 ⟷ r ≤ 0"
  by (force simp add: nonpos_Reals_def)

lemma nonpos_Reals_subset_Reals: "ℝ🪙≤🪙0 ⊆ ℝ"
  unfolding nonpos_Reals_def Reals_def by blast

lemma nonpos_Ints_subset_nonpos_Reals: "ℤ🪙≤🪙0 ⊆ ℝ🪙≤🪙0"
  by (metis nonpos_Ints_cases nonpos_Ints_nonpos nonpos_Ints_of_int 
    nonpos_Reals_of_real_iff of_real_of_int_eq subsetI)

lemma nonpos_Reals_of_nat_iff [simp]: "of_nat n ∈ ℝ🪙≤🪙0 ⟷ n=0"
  by (metis nonpos_Reals_of_real_iff of_nat_le_0_iff of_real_of_nat_eq)

lemma nonpos_Reals_Real [dest]: "x ∈ ℝ🪙≤🪙0 ==> x ∈ ℝ"
  unfolding nonpos_Reals_def Reals_def by blast

lemma nonpos_Reals_cases:
  assumes "x ∈ ℝ🪙≤🪙0"
  obtains r where "x = of_real r" "r ≤ 0"
  using assms unfolding nonpos_Reals_def by (auto elim!: Reals_cases)

lemma uminus_nonneg_Reals_iff [simp]: "-x ∈ ℝ🪙≥🪙0 ⟷ x ∈ ℝ🪙≤🪙0"
  apply (auto simp: nonpos_Reals_def nonneg_Reals_def)
  apply (metis nonpos_Reals_of_real_iff minus_minus neg_le_0_iff_le of_real_minus)
  done

lemma uminus_nonpos_Reals_iff [simp]: "-x ∈ ℝ🪙≤🪙0 ⟷ x ∈ ℝ🪙≥🪙0"
  by (metis (no_types) minus_minus uminus_nonneg_Reals_iff)

lemma nonpos_Reals_zero_I [simp]: "0 ∈ ℝ🪙≤🪙0"
  unfolding nonpos_Reals_def by force

lemma nonpos_Reals_one_I [simp]: "1 ∉ ℝ🪙≤🪙0"
  using nonneg_Reals_minus_one_I uminus_nonneg_Reals_iff by blast

lemma nonpos_Reals_numeral_I [simp]: "numeral w ∉ ℝ🪙≤🪙0"
  using nonneg_Reals_minus_numeral_I uminus_nonneg_Reals_iff by blast

lemma nonpos_Reals_add_I [simp]: "[a ∈ ℝ🪙≤🪙0; b ∈ ℝ🪙≤🪙0] ==> a + b ∈ ℝ🪙≤🪙0"
  by (metis nonneg_Reals_add_I add_uminus_conv_diff minus_diff_eq minus_minus uminus_nonpos_Reals_iff)

lemma nonpos_Reals_mult_I1: "[a ∈ ℝ🪙≥🪙0; b ∈ ℝ🪙≤🪙0] ==> a * b ∈ ℝ🪙≤🪙0"
  by (metis nonneg_Reals_mult_I mult_minus_right uminus_nonneg_Reals_iff)

lemma nonpos_Reals_mult_I2: "[a ∈ ℝ🪙≤🪙0; b ∈ ℝ🪙≥🪙0] ==> a * b ∈ ℝ🪙≤🪙0"
  by (metis nonneg_Reals_mult_I mult_minus_left uminus_nonneg_Reals_iff)

lemma nonpos_Reals_mult_of_nat_iff:
  fixes a:: "'a :: real_div_algebra" shows "a * of_nat n ∈ ℝ🪙≤🪙0 ⟷ a ∈ ℝ🪙≤🪙0 ∨ n=0"
  apply (auto intro: nonpos_Reals_mult_I2)
  apply (auto simp: nonpos_Reals_def)
  apply (rule_tac x="r/n" in exI)
  apply (auto simp: field_split_simps)
  done

lemma nonpos_Reals_inverse_I:
    fixes a :: "'a::real_div_algebra"
    shows "a ∈ ℝ🪙≤🪙0 ==> inverse a ∈ ℝ🪙≤🪙0"
  using nonneg_Reals_inverse_I uminus_nonneg_Reals_iff by fastforce

lemma nonpos_Reals_divide_I1:
    fixes a :: "'a::real_div_algebra"
    shows "[a ∈ ℝ🪙≥🪙0; b ∈ ℝ🪙≤🪙0] ==> a / b ∈ ℝ🪙≤🪙0"
  by (simp add: nonpos_Reals_inverse_I nonpos_Reals_mult_I1 divide_inverse)

lemma nonpos_Reals_divide_I2:
    fixes a :: "'a::real_div_algebra"
    shows "[a ∈ ℝ🪙≤🪙0; b ∈ ℝ🪙≥🪙0] ==> a / b ∈ ℝ🪙≤🪙0"
  by (metis nonneg_Reals_divide_I minus_divide_left uminus_nonneg_Reals_iff)

lemma nonpos_Reals_divide_of_nat_iff:
  fixes a:: "'a :: real_div_algebra" shows "a / of_nat n ∈ ℝ🪙≤🪙0 ⟷ a ∈ ℝ🪙≤🪙0 ∨ n=0"
  apply (auto intro: nonpos_Reals_divide_I2)
  apply (auto simp: nonpos_Reals_def)
  apply (rule_tac x="r*n" in exI)
  apply (auto simp: field_split_simps mult_le_0_iff)
  done

lemma nonpos_Reals_inverse_iff [simp]:
  fixes a :: "'a::real_div_algebra"
  shows "inverse a ∈ ℝ🪙≤🪙0 ⟷ a ∈ ℝ🪙≤🪙0"
  using nonpos_Reals_inverse_I by fastforce

lemma nonpos_Reals_pow_I: "[a ∈ ℝ🪙≤🪙0; odd n] ==> a^n ∈ ℝ🪙≤🪙0"
  by (metis nonneg_Reals_pow_I power_minus_odd uminus_nonneg_Reals_iff)

lemma complex_nonpos_Reals_iff: "z ∈ ℝ🪙≤🪙0 ⟷ Re z ≤ 0 ∧ Im z = 0"
   using complex_is_Real_iff by (force simp add: nonpos_Reals_def)

lemma ii_not_nonpos_Reals [iff]: "i ∉ ℝ🪙≤🪙0"
  by (simp add: complex_nonpos_Reals_iff)

lemma plus_one_in_nonpos_Ints_imp: "z + 1 ∈ ℤ🪙≤🪙0 ==> z ∈ ℤ🪙≤🪙0"
  using nonpos_Ints_diff_Nats[of "z+1" "1"] by simp_all

lemma of_int_in_nonpos_Ints_iff:
  "(of_int n :: 'a :: ring_char_0) ∈ ℤ🪙≤🪙0 ⟷ n ≤ 0"
  by (auto simp: nonpos_Ints_def)

lemma one_plus_of_int_in_nonpos_Ints_iff:
  "(1 + of_int n :: 'a :: ring_char_0) ∈ ℤ🪙≤🪙0 ⟷ n ≤ -1"
proof -
  have "1 + of_int n = (of_int (n + 1) :: 'a)" by simp
  also have "… ∈ ℤ🪙≤🪙0 ⟷ n + 1 ≤ 0" by (subst of_int_in_nonpos_Ints_iff) simp_all
  also have "… ⟷ n ≤ -1" by presburger
  finally show ?thesis .
qed

lemma one_minus_of_nat_in_nonpos_Ints_iff:
  "(1 - of_nat n :: 'a :: ring_char_0) ∈ ℤ🪙≤🪙0 ⟷ n > 0"
proof -
  have "(1 - of_nat n :: 'a) = of_int (1 - int n)" by simp
  also have "… ∈ ℤ🪙≤🪙0 ⟷ n > 0" by (subst of_int_in_nonpos_Ints_iff) presburger
  finally show ?thesis .
qed

lemma fraction_not_in_Nats:
  assumes "¬n dvd m" "n ≠ 0"
  shows   "of_int m / of_int n ∉ (ℕ :: 'a :: {division_ring,ring_char_0} set)"
proof
  assume "of_int m / of_int n ∈ (ℕ :: 'a set)"
  also note Nats_subset_Ints
  finally have "of_int m / of_int n ∈ (ℤ :: 'a set)" .
  moreover have "of_int m / of_int n ∉ (ℤ :: 'a set)"
    using assms by (intro fraction_not_in_Ints)
  ultimately show False by contradiction
qed

lemma not_in_Ints_imp_not_in_nonpos_Ints: "z ∉ ℤ ==> z ∉ ℤ🪙≤🪙0"
  by (auto simp: Ints_def nonpos_Ints_def)

lemma double_in_nonpos_Ints_imp:
  assumes "2 * (z :: 'a :: field_char_0) ∈ ℤ🪙≤🪙0"
  shows   "z ∈ ℤ🪙≤🪙0 ∨ z + 1/2 ∈ ℤ🪙≤🪙0"
proof-
  from assms obtain k where k: "2 * z = - of_nat k" by (elim nonpos_Ints_cases')
  thus ?thesis by (cases "even k") (auto elim!: evenE oddE simp: field_simps)
qed

lemma fraction_numeral_Ints_iff [simp]:
  "numeral a / numeral b ∈ (ℤ :: 'a :: {division_ring, ring_char_0} set)
   ⟷ (numeral b :: int) dvd numeral a"  (is "?L=?R")
proof
  show "?L ==> ?R"
    by (metis fraction_not_in_Ints of_int_numeral zero_neq_numeral)
  assume ?R
  then obtain k::int where "numeral a = numeral b * (of_int k :: 'a)"
    unfolding dvd_def by (metis of_int_mult of_int_numeral)
  then show ?L
    by (metis Ints_of_int divide_eq_eq mult.commute of_int_mult of_int_numeral)
qed

lemma fraction_numeral_Ints_iff1 [simp]:
  "1 / numeral b ∈ (ℤ :: 'a :: {division_ring, ring_char_0} set)
   ⟷ b = Num.One"  (is "?L=?R")
  using fraction_numeral_Ints_iff [of Num.One, where 'a='a] by simp

lemma fraction_numeral_Nats_iff [simp]:
  "numeral a / numeral b ∈ (ℕ :: 'a :: {division_ring, ring_char_0} set)
   ⟷ (numeral b :: int) dvd numeral a"  (is "?L=?R")
proof
  show "?L ==> ?R"
    using Nats_subset_Ints fraction_numeral_Ints_iff by blast
  assume ?R
  then obtain k::nat where "numeral a = numeral b * (of_nat k :: 'a)"
    unfolding dvd_def
    by (metis dvd_def int_dvd_int_iff of_nat_mult of_nat_numeral)
  then show ?L
    by (metis mult_of_nat_commute nonzero_divide_eq_eq of_nat_in_Nats
        zero_neq_numeral)
qed

lemma fraction_numeral_Nats_iff1 [simp]:
  "1 / numeral b ∈ (ℕ :: 'a :: {division_ring, ring_char_0} set)
   ⟷ b = Num.One"  (is "?L=?R")
  using fraction_numeral_Nats_iff [of Num.One, where 'a='a] by simp

end