# Theory ArithSimp

Up to index of Isabelle/ZF

theory ArithSimp
imports Arith
`(*  Title:      ZF/ArithSimp.thy    Author:     Lawrence C Paulson, Cambridge University Computer Laboratory    Copyright   2000  University of Cambridge*)header{*Arithmetic with simplification*}theory ArithSimpimports ArithbeginML_file "~~/src/Provers/Arith/cancel_numerals.ML"ML_file "~~/src/Provers/Arith/combine_numerals.ML"ML_file "arith_data.ML"subsection{*Difference*}lemma diff_self_eq_0 [simp]: "m #- m = 0"apply (subgoal_tac "natify (m) #- natify (m) = 0")apply (rule_tac [2] natify_in_nat [THEN nat_induct], auto)done(**Addition is the inverse of subtraction**)(*We need m:nat even if we replace the RHS by natify(m), for consider e.g.  n=2, m=omega; then n + (m-n) = 2 + (0-2) = 2 ≠ 0 = natify(m).*)lemma add_diff_inverse: "[| n ≤ m;  m:nat |] ==> n #+ (m#-n) = m"apply (frule lt_nat_in_nat, erule nat_succI)apply (erule rev_mp)apply (rule_tac m = m and n = n in diff_induct, auto)donelemma add_diff_inverse2: "[| n ≤ m;  m:nat |] ==> (m#-n) #+ n = m"apply (frule lt_nat_in_nat, erule nat_succI)apply (simp (no_asm_simp) add: add_commute add_diff_inverse)done(*Proof is IDENTICAL to that of add_diff_inverse*)lemma diff_succ: "[| n ≤ m;  m:nat |] ==> succ(m) #- n = succ(m#-n)"apply (frule lt_nat_in_nat, erule nat_succI)apply (erule rev_mp)apply (rule_tac m = m and n = n in diff_induct)apply (simp_all (no_asm_simp))donelemma zero_less_diff [simp]:     "[| m: nat; n: nat |] ==> 0 < (n #- m)   <->   m<n"apply (rule_tac m = m and n = n in diff_induct)apply (simp_all (no_asm_simp))done(** Difference distributes over multiplication **)lemma diff_mult_distrib: "(m #- n) #* k = (m #* k) #- (n #* k)"apply (subgoal_tac " (natify (m) #- natify (n)) #* natify (k) = (natify (m) #* natify (k)) #- (natify (n) #* natify (k))")apply (rule_tac [2] m = "natify (m) " and n = "natify (n) " in diff_induct)apply (simp_all add: diff_cancel)donelemma diff_mult_distrib2: "k #* (m #- n) = (k #* m) #- (k #* n)"apply (simp (no_asm) add: mult_commute [of k] diff_mult_distrib)donesubsection{*Remainder*}(*We need m:nat even with natify*)lemma div_termination: "[| 0<n;  n ≤ m;  m:nat |] ==> m #- n < m"apply (frule lt_nat_in_nat, erule nat_succI)apply (erule rev_mp)apply (erule rev_mp)apply (rule_tac m = m and n = n in diff_induct)apply (simp_all (no_asm_simp) add: diff_le_self)done(*for mod and div*)lemmas div_rls =    nat_typechecks Ord_transrec_type apply_funtype    div_termination [THEN ltD]    nat_into_Ord not_lt_iff_le [THEN iffD1]lemma raw_mod_type: "[| m:nat;  n:nat |] ==> raw_mod (m, n) ∈ nat"apply (unfold raw_mod_def)apply (rule Ord_transrec_type)apply (auto simp add: nat_into_Ord [THEN Ord_0_lt_iff])apply (blast intro: div_rls)donelemma mod_type [TC,iff]: "m mod n ∈ nat"apply (unfold mod_def)apply (simp (no_asm) add: mod_def raw_mod_type)done(** Aribtrary definitions for division by zero.  Useful to simplify    certain equations **)lemma DIVISION_BY_ZERO_DIV: "a div 0 = 0"apply (unfold div_def)apply (rule raw_div_def [THEN def_transrec, THEN trans])apply (simp (no_asm_simp))done  (*NOT for adding to default simpset*)lemma DIVISION_BY_ZERO_MOD: "a mod 0 = natify(a)"apply (unfold mod_def)apply (rule raw_mod_def [THEN def_transrec, THEN trans])apply (simp (no_asm_simp))done  (*NOT for adding to default simpset*)lemma raw_mod_less: "m<n ==> raw_mod (m,n) = m"apply (rule raw_mod_def [THEN def_transrec, THEN trans])apply (simp (no_asm_simp) add: div_termination [THEN ltD])donelemma mod_less [simp]: "[| m<n; n ∈ nat |] ==> m mod n = m"apply (frule lt_nat_in_nat, assumption)apply (simp (no_asm_simp) add: mod_def raw_mod_less)donelemma raw_mod_geq:     "[| 0<n; n ≤ m;  m:nat |] ==> raw_mod (m, n) = raw_mod (m#-n, n)"apply (frule lt_nat_in_nat, erule nat_succI)apply (rule raw_mod_def [THEN def_transrec, THEN trans])apply (simp (no_asm_simp) add: div_termination [THEN ltD] not_lt_iff_le [THEN iffD2], blast)donelemma mod_geq: "[| n ≤ m;  m:nat |] ==> m mod n = (m#-n) mod n"apply (frule lt_nat_in_nat, erule nat_succI)apply (case_tac "n=0") apply (simp add: DIVISION_BY_ZERO_MOD)apply (simp add: mod_def raw_mod_geq nat_into_Ord [THEN Ord_0_lt_iff])donesubsection{*Division*}lemma raw_div_type: "[| m:nat;  n:nat |] ==> raw_div (m, n) ∈ nat"apply (unfold raw_div_def)apply (rule Ord_transrec_type)apply (auto simp add: nat_into_Ord [THEN Ord_0_lt_iff])apply (blast intro: div_rls)donelemma div_type [TC,iff]: "m div n ∈ nat"apply (unfold div_def)apply (simp (no_asm) add: div_def raw_div_type)donelemma raw_div_less: "m<n ==> raw_div (m,n) = 0"apply (rule raw_div_def [THEN def_transrec, THEN trans])apply (simp (no_asm_simp) add: div_termination [THEN ltD])donelemma div_less [simp]: "[| m<n; n ∈ nat |] ==> m div n = 0"apply (frule lt_nat_in_nat, assumption)apply (simp (no_asm_simp) add: div_def raw_div_less)donelemma raw_div_geq: "[| 0<n;  n ≤ m;  m:nat |] ==> raw_div(m,n) = succ(raw_div(m#-n, n))"apply (subgoal_tac "n ≠ 0")prefer 2 apply blastapply (frule lt_nat_in_nat, erule nat_succI)apply (rule raw_div_def [THEN def_transrec, THEN trans])apply (simp (no_asm_simp) add: div_termination [THEN ltD] not_lt_iff_le [THEN iffD2] )donelemma div_geq [simp]:     "[| 0<n;  n ≤ m;  m:nat |] ==> m div n = succ ((m#-n) div n)"apply (frule lt_nat_in_nat, erule nat_succI)apply (simp (no_asm_simp) add: div_def raw_div_geq)donedeclare div_less [simp] div_geq [simp](*A key result*)lemma mod_div_lemma: "[| m: nat;  n: nat |] ==> (m div n)#*n #+ m mod n = m"apply (case_tac "n=0") apply (simp add: DIVISION_BY_ZERO_MOD)apply (simp add: nat_into_Ord [THEN Ord_0_lt_iff])apply (erule complete_induct)apply (case_tac "x<n")txt{*case x<n*}apply (simp (no_asm_simp))txt{*case @{term"n ≤ x"}*}apply (simp add: not_lt_iff_le add_assoc mod_geq div_termination [THEN ltD] add_diff_inverse)donelemma mod_div_equality_natify: "(m div n)#*n #+ m mod n = natify(m)"apply (subgoal_tac " (natify (m) div natify (n))#*natify (n) #+ natify (m) mod natify (n) = natify (m) ")apply forceapply (subst mod_div_lemma, auto)donelemma mod_div_equality: "m: nat ==> (m div n)#*n #+ m mod n = m"apply (simp (no_asm_simp) add: mod_div_equality_natify)donesubsection{*Further Facts about Remainder*}text{*(mainly for mutilated chess board)*}lemma mod_succ_lemma:     "[| 0<n;  m:nat;  n:nat |]      ==> succ(m) mod n = (if succ(m mod n) = n then 0 else succ(m mod n))"apply (erule complete_induct)apply (case_tac "succ (x) <n")txt{* case succ(x) < n *} apply (simp (no_asm_simp) add: nat_le_refl [THEN lt_trans] succ_neq_self) apply (simp add: ltD [THEN mem_imp_not_eq])txt{* case @{term"n ≤ succ(x)"} *}apply (simp add: mod_geq not_lt_iff_le)apply (erule leE) apply (simp (no_asm_simp) add: mod_geq div_termination [THEN ltD] diff_succ)txt{*equality case*}apply (simp add: diff_self_eq_0)donelemma mod_succ:  "n:nat ==> succ(m) mod n = (if succ(m mod n) = n then 0 else succ(m mod n))"apply (case_tac "n=0") apply (simp (no_asm_simp) add: natify_succ DIVISION_BY_ZERO_MOD)apply (subgoal_tac "natify (succ (m)) mod n = (if succ (natify (m) mod n) = n then 0 else succ (natify (m) mod n))") prefer 2 apply (subst natify_succ) apply (rule mod_succ_lemma)  apply (auto simp del: natify_succ simp add: nat_into_Ord [THEN Ord_0_lt_iff])donelemma mod_less_divisor: "[| 0<n;  n:nat |] ==> m mod n < n"apply (subgoal_tac "natify (m) mod n < n")apply (rule_tac [2] i = "natify (m) " in complete_induct)apply (case_tac [3] "x<n", auto)txt{* case @{term"n ≤ x"}*}apply (simp add: mod_geq not_lt_iff_le div_termination [THEN ltD])donelemma mod_1_eq [simp]: "m mod 1 = 0"by (cut_tac n = 1 in mod_less_divisor, auto)lemma mod2_cases: "b<2 ==> k mod 2 = b | k mod 2 = (if b=1 then 0 else 1)"apply (subgoal_tac "k mod 2: 2") prefer 2 apply (simp add: mod_less_divisor [THEN ltD])apply (drule ltD, auto)donelemma mod2_succ_succ [simp]: "succ(succ(m)) mod 2 = m mod 2"apply (subgoal_tac "m mod 2: 2") prefer 2 apply (simp add: mod_less_divisor [THEN ltD])apply (auto simp add: mod_succ)donelemma mod2_add_more [simp]: "(m#+m#+n) mod 2 = n mod 2"apply (subgoal_tac " (natify (m) #+natify (m) #+n) mod 2 = n mod 2")apply (rule_tac [2] n = "natify (m) " in nat_induct)apply autodonelemma mod2_add_self [simp]: "(m#+m) mod 2 = 0"by (cut_tac n = 0 in mod2_add_more, auto)subsection{*Additional theorems about @{text "≤"}*}lemma add_le_self: "m:nat ==> m ≤ (m #+ n)"apply (simp (no_asm_simp))donelemma add_le_self2: "m:nat ==> m ≤ (n #+ m)"apply (simp (no_asm_simp))done(*** Monotonicity of Multiplication ***)lemma mult_le_mono1: "[| i ≤ j; j:nat |] ==> (i#*k) ≤ (j#*k)"apply (subgoal_tac "natify (i) #*natify (k) ≤ j#*natify (k) ")apply (frule_tac [2] lt_nat_in_nat)apply (rule_tac [3] n = "natify (k) " in nat_induct)apply (simp_all add: add_le_mono)done(* @{text"≤"} monotonicity, BOTH arguments*)lemma mult_le_mono: "[| i ≤ j; k ≤ l; j:nat; l:nat |] ==> i#*k ≤ j#*l"apply (rule mult_le_mono1 [THEN le_trans], assumption+)apply (subst mult_commute, subst mult_commute, rule mult_le_mono1, assumption+)done(*strict, in 1st argument; proof is by induction on k>0.  I can't see how to relax the typing conditions.*)lemma mult_lt_mono2: "[| i<j; 0<k; j:nat; k:nat |] ==> k#*i < k#*j"apply (erule zero_lt_natE)apply (frule_tac [2] lt_nat_in_nat)apply (simp_all (no_asm_simp))apply (induct_tac "x")apply (simp_all (no_asm_simp) add: add_lt_mono)donelemma mult_lt_mono1: "[| i<j; 0<k; j:nat; k:nat |] ==> i#*k < j#*k"apply (simp (no_asm_simp) add: mult_lt_mono2 mult_commute [of _ k])donelemma add_eq_0_iff [iff]: "m#+n = 0 <-> natify(m)=0 & natify(n)=0"apply (subgoal_tac "natify (m) #+ natify (n) = 0 <-> natify (m) =0 & natify (n) =0")apply (rule_tac [2] n = "natify (m) " in natE) apply (rule_tac [4] n = "natify (n) " in natE)apply autodonelemma zero_lt_mult_iff [iff]: "0 < m#*n <-> 0 < natify(m) & 0 < natify(n)"apply (subgoal_tac "0 < natify (m) #*natify (n) <-> 0 < natify (m) & 0 < natify (n) ")apply (rule_tac [2] n = "natify (m) " in natE) apply (rule_tac [4] n = "natify (n) " in natE)  apply (rule_tac [3] n = "natify (n) " in natE)apply autodonelemma mult_eq_1_iff [iff]: "m#*n = 1 <-> natify(m)=1 & natify(n)=1"apply (subgoal_tac "natify (m) #* natify (n) = 1 <-> natify (m) =1 & natify (n) =1")apply (rule_tac [2] n = "natify (m) " in natE) apply (rule_tac [4] n = "natify (n) " in natE)apply autodonelemma mult_is_zero: "[|m: nat; n: nat|] ==> (m #* n = 0) <-> (m = 0 | n = 0)"apply autoapply (erule natE)apply (erule_tac [2] natE, auto)donelemma mult_is_zero_natify [iff]:     "(m #* n = 0) <-> (natify(m) = 0 | natify(n) = 0)"apply (cut_tac m = "natify (m) " and n = "natify (n) " in mult_is_zero)apply autodonesubsection{*Cancellation Laws for Common Factors in Comparisons*}lemma mult_less_cancel_lemma:     "[| k: nat; m: nat; n: nat |] ==> (m#*k < n#*k) <-> (0<k & m<n)"apply (safe intro!: mult_lt_mono1)apply (erule natE, auto)apply (rule not_le_iff_lt [THEN iffD1])apply (drule_tac [3] not_le_iff_lt [THEN [2] rev_iffD2])prefer 5 apply (blast intro: mult_le_mono1, auto)donelemma mult_less_cancel2 [simp]:     "(m#*k < n#*k) <-> (0 < natify(k) & natify(m) < natify(n))"apply (rule iff_trans)apply (rule_tac [2] mult_less_cancel_lemma, auto)donelemma mult_less_cancel1 [simp]:     "(k#*m < k#*n) <-> (0 < natify(k) & natify(m) < natify(n))"apply (simp (no_asm) add: mult_less_cancel2 mult_commute [of k])donelemma mult_le_cancel2 [simp]: "(m#*k ≤ n#*k) <-> (0 < natify(k) --> natify(m) ≤ natify(n))"apply (simp (no_asm_simp) add: not_lt_iff_le [THEN iff_sym])apply autodonelemma mult_le_cancel1 [simp]: "(k#*m ≤ k#*n) <-> (0 < natify(k) --> natify(m) ≤ natify(n))"apply (simp (no_asm_simp) add: not_lt_iff_le [THEN iff_sym])apply autodonelemma mult_le_cancel_le1: "k ∈ nat ==> k #* m ≤ k <-> (0 < k --> natify(m) ≤ 1)"by (cut_tac k = k and m = m and n = 1 in mult_le_cancel1, auto)lemma Ord_eq_iff_le: "[| Ord(m); Ord(n) |] ==> m=n <-> (m ≤ n & n ≤ m)"by (blast intro: le_anti_sym)lemma mult_cancel2_lemma:     "[| k: nat; m: nat; n: nat |] ==> (m#*k = n#*k) <-> (m=n | k=0)"apply (simp (no_asm_simp) add: Ord_eq_iff_le [of "m#*k"] Ord_eq_iff_le [of m])apply (auto simp add: Ord_0_lt_iff)donelemma mult_cancel2 [simp]:     "(m#*k = n#*k) <-> (natify(m) = natify(n) | natify(k) = 0)"apply (rule iff_trans)apply (rule_tac [2] mult_cancel2_lemma, auto)donelemma mult_cancel1 [simp]:     "(k#*m = k#*n) <-> (natify(m) = natify(n) | natify(k) = 0)"apply (simp (no_asm) add: mult_cancel2 mult_commute [of k])done(** Cancellation law for division **)lemma div_cancel_raw:     "[| 0<n; 0<k; k:nat; m:nat; n:nat |] ==> (k#*m) div (k#*n) = m div n"apply (erule_tac i = m in complete_induct)apply (case_tac "x<n") apply (simp add: div_less zero_lt_mult_iff mult_lt_mono2)apply (simp add: not_lt_iff_le zero_lt_mult_iff le_refl [THEN mult_le_mono]          div_geq diff_mult_distrib2 [symmetric] div_termination [THEN ltD])donelemma div_cancel:     "[| 0 < natify(n);  0 < natify(k) |] ==> (k#*m) div (k#*n) = m div n"apply (cut_tac k = "natify (k) " and m = "natify (m)" and n = "natify (n)"       in div_cancel_raw)apply autodonesubsection{*More Lemmas about Remainder*}lemma mult_mod_distrib_raw:     "[| k:nat; m:nat; n:nat |] ==> (k#*m) mod (k#*n) = k #* (m mod n)"apply (case_tac "k=0") apply (simp add: DIVISION_BY_ZERO_MOD)apply (case_tac "n=0") apply (simp add: DIVISION_BY_ZERO_MOD)apply (simp add: nat_into_Ord [THEN Ord_0_lt_iff])apply (erule_tac i = m in complete_induct)apply (case_tac "x<n") apply (simp (no_asm_simp) add: mod_less zero_lt_mult_iff mult_lt_mono2)apply (simp add: not_lt_iff_le zero_lt_mult_iff le_refl [THEN mult_le_mono]         mod_geq diff_mult_distrib2 [symmetric] div_termination [THEN ltD])donelemma mod_mult_distrib2: "k #* (m mod n) = (k#*m) mod (k#*n)"apply (cut_tac k = "natify (k) " and m = "natify (m)" and n = "natify (n)"       in mult_mod_distrib_raw)apply autodonelemma mult_mod_distrib: "(m mod n) #* k = (m#*k) mod (n#*k)"apply (simp (no_asm) add: mult_commute mod_mult_distrib2)donelemma mod_add_self2_raw: "n ∈ nat ==> (m #+ n) mod n = m mod n"apply (subgoal_tac " (n #+ m) mod n = (n #+ m #- n) mod n")apply (simp add: add_commute)apply (subst mod_geq [symmetric], auto)donelemma mod_add_self2 [simp]: "(m #+ n) mod n = m mod n"apply (cut_tac n = "natify (n) " in mod_add_self2_raw)apply autodonelemma mod_add_self1 [simp]: "(n#+m) mod n = m mod n"apply (simp (no_asm_simp) add: add_commute mod_add_self2)donelemma mod_mult_self1_raw: "k ∈ nat ==> (m #+ k#*n) mod n = m mod n"apply (erule nat_induct)apply (simp_all (no_asm_simp) add: add_left_commute [of _ n])donelemma mod_mult_self1 [simp]: "(m #+ k#*n) mod n = m mod n"apply (cut_tac k = "natify (k) " in mod_mult_self1_raw)apply autodonelemma mod_mult_self2 [simp]: "(m #+ n#*k) mod n = m mod n"apply (simp (no_asm) add: mult_commute mod_mult_self1)done(*Lemma for gcd*)lemma mult_eq_self_implies_10: "m = m#*n ==> natify(n)=1 | m=0"apply (subgoal_tac "m: nat") prefer 2 apply (erule ssubst) apply simpapply (rule disjCI)apply (drule sym)apply (rule Ord_linear_lt [of "natify(n)" 1])apply simp_all apply (subgoal_tac "m #* n = 0", simp) apply (subst mult_natify2 [symmetric]) apply (simp del: mult_natify2)apply (drule nat_into_Ord [THEN Ord_0_lt, THEN [2] mult_lt_mono2], auto)donelemma less_imp_succ_add [rule_format]:     "[| m<n; n: nat |] ==> ∃k∈nat. n = succ(m#+k)"apply (frule lt_nat_in_nat, assumption)apply (erule rev_mp)apply (induct_tac "n")apply (simp_all (no_asm) add: le_iff)apply (blast elim!: leE intro!: add_0_right [symmetric] add_succ_right [symmetric])donelemma less_iff_succ_add:     "[| m: nat; n: nat |] ==> (m<n) <-> (∃k∈nat. n = succ(m#+k))"by (auto intro: less_imp_succ_add)lemma add_lt_elim2:     "[|a #+ d = b #+ c; a < b; b ∈ nat; c ∈ nat; d ∈ nat|] ==> c < d"by (drule less_imp_succ_add, auto)lemma add_le_elim2:     "[|a #+ d = b #+ c; a ≤ b; b ∈ nat; c ∈ nat; d ∈ nat|] ==> c ≤ d"by (drule less_imp_succ_add, auto)subsubsection{*More Lemmas About Difference*}lemma diff_is_0_lemma:     "[| m: nat; n: nat |] ==> m #- n = 0 <-> m ≤ n"apply (rule_tac m = m and n = n in diff_induct, simp_all)donelemma diff_is_0_iff: "m #- n = 0 <-> natify(m) ≤ natify(n)"by (simp add: diff_is_0_lemma [symmetric])lemma nat_lt_imp_diff_eq_0:     "[| a:nat; b:nat; a<b |] ==> a #- b = 0"by (simp add: diff_is_0_iff le_iff)lemma raw_nat_diff_split:     "[| a:nat; b:nat |] ==>      (P(a #- b)) <-> ((a < b -->P(0)) & (∀d∈nat. a = b #+ d --> P(d)))"apply (case_tac "a < b") apply (force simp add: nat_lt_imp_diff_eq_0)apply (rule iffI, force, simp)apply (drule_tac x="a#-b" in bspec)apply (simp_all add: Ordinal.not_lt_iff_le add_diff_inverse)donelemma nat_diff_split:   "(P(a #- b)) <->    (natify(a) < natify(b) -->P(0)) & (∀d∈nat. natify(a) = b #+ d --> P(d))"apply (cut_tac P=P and a="natify(a)" and b="natify(b)" in raw_nat_diff_split)apply simp_alldonetext{*Difference and less-than*}lemma diff_lt_imp_lt: "[|(k#-i) < (k#-j); i∈nat; j∈nat; k∈nat|] ==> j<i"apply (erule rev_mp)apply (simp split add: nat_diff_split, auto) apply (blast intro: add_le_self lt_trans1)apply (rule not_le_iff_lt [THEN iffD1], auto)apply (subgoal_tac "i #+ da < j #+ d", force)apply (blast intro: add_le_lt_mono)donelemma lt_imp_diff_lt: "[|j<i; i≤k; k∈nat|] ==> (k#-i) < (k#-j)"apply (frule le_in_nat, assumption)apply (frule lt_nat_in_nat, assumption)apply (simp split add: nat_diff_split, auto)  apply (blast intro: lt_asym lt_trans2) apply (blast intro: lt_irrefl lt_trans2)apply (rule not_le_iff_lt [THEN iffD1], auto)apply (subgoal_tac "j #+ d < i #+ da", force)apply (blast intro: add_lt_le_mono)donelemma diff_lt_iff_lt: "[|i≤k; j∈nat; k∈nat|] ==> (k#-i) < (k#-j) <-> j<i"apply (frule le_in_nat, assumption)apply (blast intro: lt_imp_diff_lt diff_lt_imp_lt)doneend`