1(* Title: ZF/ArithSimp.thy 2 Author: Lawrence C Paulson, Cambridge University Computer Laboratory 3 Copyright 2000 University of Cambridge 4*) 5 6section\<open>Arithmetic with simplification\<close> 7 8theory ArithSimp 9imports Arith 10begin 11 12ML_file \<open>~~/src/Provers/Arith/cancel_numerals.ML\<close> 13ML_file \<open>~~/src/Provers/Arith/combine_numerals.ML\<close> 14ML_file \<open>arith_data.ML\<close> 15 16 17subsection\<open>Difference\<close> 18 19lemma diff_self_eq_0 [simp]: "m #- m = 0" 20apply (subgoal_tac "natify (m) #- natify (m) = 0") 21apply (rule_tac [2] natify_in_nat [THEN nat_induct], auto) 22done 23 24(**Addition is the inverse of subtraction**) 25 26(*We need m:nat even if we replace the RHS by natify(m), for consider e.g. 27 n=2, m=omega; then n + (m-n) = 2 + (0-2) = 2 \<noteq> 0 = natify(m).*) 28lemma add_diff_inverse: "[| n \<le> m; m:nat |] ==> n #+ (m#-n) = m" 29apply (frule lt_nat_in_nat, erule nat_succI) 30apply (erule rev_mp) 31apply (rule_tac m = m and n = n in diff_induct, auto) 32done 33 34lemma add_diff_inverse2: "[| n \<le> m; m:nat |] ==> (m#-n) #+ n = m" 35apply (frule lt_nat_in_nat, erule nat_succI) 36apply (simp (no_asm_simp) add: add_commute add_diff_inverse) 37done 38 39(*Proof is IDENTICAL to that of add_diff_inverse*) 40lemma diff_succ: "[| n \<le> m; m:nat |] ==> succ(m) #- n = succ(m#-n)" 41apply (frule lt_nat_in_nat, erule nat_succI) 42apply (erule rev_mp) 43apply (rule_tac m = m and n = n in diff_induct) 44apply (simp_all (no_asm_simp)) 45done 46 47lemma zero_less_diff [simp]: 48 "[| m: nat; n: nat |] ==> 0 < (n #- m) \<longleftrightarrow> m<n" 49apply (rule_tac m = m and n = n in diff_induct) 50apply (simp_all (no_asm_simp)) 51done 52 53 54(** Difference distributes over multiplication **) 55 56lemma diff_mult_distrib: "(m #- n) #* k = (m #* k) #- (n #* k)" 57apply (subgoal_tac " (natify (m) #- natify (n)) #* natify (k) = (natify (m) #* natify (k)) #- (natify (n) #* natify (k))") 58apply (rule_tac [2] m = "natify (m) " and n = "natify (n) " in diff_induct) 59apply (simp_all add: diff_cancel) 60done 61 62lemma diff_mult_distrib2: "k #* (m #- n) = (k #* m) #- (k #* n)" 63apply (simp (no_asm) add: mult_commute [of k] diff_mult_distrib) 64done 65 66 67subsection\<open>Remainder\<close> 68 69(*We need m:nat even with natify*) 70lemma div_termination: "[| 0<n; n \<le> m; m:nat |] ==> m #- n < m" 71apply (frule lt_nat_in_nat, erule nat_succI) 72apply (erule rev_mp) 73apply (erule rev_mp) 74apply (rule_tac m = m and n = n in diff_induct) 75apply (simp_all (no_asm_simp) add: diff_le_self) 76done 77 78(*for mod and div*) 79lemmas div_rls = 80 nat_typechecks Ord_transrec_type apply_funtype 81 div_termination [THEN ltD] 82 nat_into_Ord not_lt_iff_le [THEN iffD1] 83 84lemma raw_mod_type: "[| m:nat; n:nat |] ==> raw_mod (m, n) \<in> nat" 85apply (unfold raw_mod_def) 86apply (rule Ord_transrec_type) 87apply (auto simp add: nat_into_Ord [THEN Ord_0_lt_iff]) 88apply (blast intro: div_rls) 89done 90 91lemma mod_type [TC,iff]: "m mod n \<in> nat" 92apply (unfold mod_def) 93apply (simp (no_asm) add: mod_def raw_mod_type) 94done 95 96 97(** Aribtrary definitions for division by zero. Useful to simplify 98 certain equations **) 99 100lemma DIVISION_BY_ZERO_DIV: "a div 0 = 0" 101apply (unfold div_def) 102apply (rule raw_div_def [THEN def_transrec, THEN trans]) 103apply (simp (no_asm_simp)) 104done (*NOT for adding to default simpset*) 105 106lemma DIVISION_BY_ZERO_MOD: "a mod 0 = natify(a)" 107apply (unfold mod_def) 108apply (rule raw_mod_def [THEN def_transrec, THEN trans]) 109apply (simp (no_asm_simp)) 110done (*NOT for adding to default simpset*) 111 112lemma raw_mod_less: "m<n ==> raw_mod (m,n) = m" 113apply (rule raw_mod_def [THEN def_transrec, THEN trans]) 114apply (simp (no_asm_simp) add: div_termination [THEN ltD]) 115done 116 117lemma mod_less [simp]: "[| m<n; n \<in> nat |] ==> m mod n = m" 118apply (frule lt_nat_in_nat, assumption) 119apply (simp (no_asm_simp) add: mod_def raw_mod_less) 120done 121 122lemma raw_mod_geq: 123 "[| 0<n; n \<le> m; m:nat |] ==> raw_mod (m, n) = raw_mod (m#-n, n)" 124apply (frule lt_nat_in_nat, erule nat_succI) 125apply (rule raw_mod_def [THEN def_transrec, THEN trans]) 126apply (simp (no_asm_simp) add: div_termination [THEN ltD] not_lt_iff_le [THEN iffD2], blast) 127done 128 129 130lemma mod_geq: "[| n \<le> m; m:nat |] ==> m mod n = (m#-n) mod n" 131apply (frule lt_nat_in_nat, erule nat_succI) 132apply (case_tac "n=0") 133 apply (simp add: DIVISION_BY_ZERO_MOD) 134apply (simp add: mod_def raw_mod_geq nat_into_Ord [THEN Ord_0_lt_iff]) 135done 136 137 138subsection\<open>Division\<close> 139 140lemma raw_div_type: "[| m:nat; n:nat |] ==> raw_div (m, n) \<in> nat" 141apply (unfold raw_div_def) 142apply (rule Ord_transrec_type) 143apply (auto simp add: nat_into_Ord [THEN Ord_0_lt_iff]) 144apply (blast intro: div_rls) 145done 146 147lemma div_type [TC,iff]: "m div n \<in> nat" 148apply (unfold div_def) 149apply (simp (no_asm) add: div_def raw_div_type) 150done 151 152lemma raw_div_less: "m<n ==> raw_div (m,n) = 0" 153apply (rule raw_div_def [THEN def_transrec, THEN trans]) 154apply (simp (no_asm_simp) add: div_termination [THEN ltD]) 155done 156 157lemma div_less [simp]: "[| m<n; n \<in> nat |] ==> m div n = 0" 158apply (frule lt_nat_in_nat, assumption) 159apply (simp (no_asm_simp) add: div_def raw_div_less) 160done 161 162lemma raw_div_geq: "[| 0<n; n \<le> m; m:nat |] ==> raw_div(m,n) = succ(raw_div(m#-n, n))" 163apply (subgoal_tac "n \<noteq> 0") 164prefer 2 apply blast 165apply (frule lt_nat_in_nat, erule nat_succI) 166apply (rule raw_div_def [THEN def_transrec, THEN trans]) 167apply (simp (no_asm_simp) add: div_termination [THEN ltD] not_lt_iff_le [THEN iffD2] ) 168done 169 170lemma div_geq [simp]: 171 "[| 0<n; n \<le> m; m:nat |] ==> m div n = succ ((m#-n) div n)" 172apply (frule lt_nat_in_nat, erule nat_succI) 173apply (simp (no_asm_simp) add: div_def raw_div_geq) 174done 175 176declare div_less [simp] div_geq [simp] 177 178 179(*A key result*) 180lemma mod_div_lemma: "[| m: nat; n: nat |] ==> (m div n)#*n #+ m mod n = m" 181apply (case_tac "n=0") 182 apply (simp add: DIVISION_BY_ZERO_MOD) 183apply (simp add: nat_into_Ord [THEN Ord_0_lt_iff]) 184apply (erule complete_induct) 185apply (case_tac "x<n") 186txt\<open>case x<n\<close> 187apply (simp (no_asm_simp)) 188txt\<open>case \<^term>\<open>n \<le> x\<close>\<close> 189apply (simp add: not_lt_iff_le add_assoc mod_geq div_termination [THEN ltD] add_diff_inverse) 190done 191 192lemma mod_div_equality_natify: "(m div n)#*n #+ m mod n = natify(m)" 193apply (subgoal_tac " (natify (m) div natify (n))#*natify (n) #+ natify (m) mod natify (n) = natify (m) ") 194apply force 195apply (subst mod_div_lemma, auto) 196done 197 198lemma mod_div_equality: "m: nat ==> (m div n)#*n #+ m mod n = m" 199apply (simp (no_asm_simp) add: mod_div_equality_natify) 200done 201 202 203subsection\<open>Further Facts about Remainder\<close> 204 205text\<open>(mainly for mutilated chess board)\<close> 206 207lemma mod_succ_lemma: 208 "[| 0<n; m:nat; n:nat |] 209 ==> succ(m) mod n = (if succ(m mod n) = n then 0 else succ(m mod n))" 210apply (erule complete_induct) 211apply (case_tac "succ (x) <n") 212txt\<open>case succ(x) < n\<close> 213 apply (simp (no_asm_simp) add: nat_le_refl [THEN lt_trans] succ_neq_self) 214 apply (simp add: ltD [THEN mem_imp_not_eq]) 215txt\<open>case \<^term>\<open>n \<le> succ(x)\<close>\<close> 216apply (simp add: mod_geq not_lt_iff_le) 217apply (erule leE) 218 apply (simp (no_asm_simp) add: mod_geq div_termination [THEN ltD] diff_succ) 219txt\<open>equality case\<close> 220apply (simp add: diff_self_eq_0) 221done 222 223lemma mod_succ: 224 "n:nat ==> succ(m) mod n = (if succ(m mod n) = n then 0 else succ(m mod n))" 225apply (case_tac "n=0") 226 apply (simp (no_asm_simp) add: natify_succ DIVISION_BY_ZERO_MOD) 227apply (subgoal_tac "natify (succ (m)) mod n = (if succ (natify (m) mod n) = n then 0 else succ (natify (m) mod n))") 228 prefer 2 229 apply (subst natify_succ) 230 apply (rule mod_succ_lemma) 231 apply (auto simp del: natify_succ simp add: nat_into_Ord [THEN Ord_0_lt_iff]) 232done 233 234lemma mod_less_divisor: "[| 0<n; n:nat |] ==> m mod n < n" 235apply (subgoal_tac "natify (m) mod n < n") 236apply (rule_tac [2] i = "natify (m) " in complete_induct) 237apply (case_tac [3] "x<n", auto) 238txt\<open>case \<^term>\<open>n \<le> x\<close>\<close> 239apply (simp add: mod_geq not_lt_iff_le div_termination [THEN ltD]) 240done 241 242lemma mod_1_eq [simp]: "m mod 1 = 0" 243by (cut_tac n = 1 in mod_less_divisor, auto) 244 245lemma mod2_cases: "b<2 ==> k mod 2 = b | k mod 2 = (if b=1 then 0 else 1)" 246apply (subgoal_tac "k mod 2: 2") 247 prefer 2 apply (simp add: mod_less_divisor [THEN ltD]) 248apply (drule ltD, auto) 249done 250 251lemma mod2_succ_succ [simp]: "succ(succ(m)) mod 2 = m mod 2" 252apply (subgoal_tac "m mod 2: 2") 253 prefer 2 apply (simp add: mod_less_divisor [THEN ltD]) 254apply (auto simp add: mod_succ) 255done 256 257lemma mod2_add_more [simp]: "(m#+m#+n) mod 2 = n mod 2" 258apply (subgoal_tac " (natify (m) #+natify (m) #+n) mod 2 = n mod 2") 259apply (rule_tac [2] n = "natify (m) " in nat_induct) 260apply auto 261done 262 263lemma mod2_add_self [simp]: "(m#+m) mod 2 = 0" 264by (cut_tac n = 0 in mod2_add_more, auto) 265 266 267subsection\<open>Additional theorems about \<open>\<le>\<close>\<close> 268 269lemma add_le_self: "m:nat ==> m \<le> (m #+ n)" 270apply (simp (no_asm_simp)) 271done 272 273lemma add_le_self2: "m:nat ==> m \<le> (n #+ m)" 274apply (simp (no_asm_simp)) 275done 276 277(*** Monotonicity of Multiplication ***) 278 279lemma mult_le_mono1: "[| i \<le> j; j:nat |] ==> (i#*k) \<le> (j#*k)" 280apply (subgoal_tac "natify (i) #*natify (k) \<le> j#*natify (k) ") 281apply (frule_tac [2] lt_nat_in_nat) 282apply (rule_tac [3] n = "natify (k) " in nat_induct) 283apply (simp_all add: add_le_mono) 284done 285 286(* @{text"\<le>"} monotonicity, BOTH arguments*) 287lemma mult_le_mono: "[| i \<le> j; k \<le> l; j:nat; l:nat |] ==> i#*k \<le> j#*l" 288apply (rule mult_le_mono1 [THEN le_trans], assumption+) 289apply (subst mult_commute, subst mult_commute, rule mult_le_mono1, assumption+) 290done 291 292(*strict, in 1st argument; proof is by induction on k>0. 293 I can't see how to relax the typing conditions.*) 294lemma mult_lt_mono2: "[| i<j; 0<k; j:nat; k:nat |] ==> k#*i < k#*j" 295apply (erule zero_lt_natE) 296apply (frule_tac [2] lt_nat_in_nat) 297apply (simp_all (no_asm_simp)) 298apply (induct_tac "x") 299apply (simp_all (no_asm_simp) add: add_lt_mono) 300done 301 302lemma mult_lt_mono1: "[| i<j; 0<k; j:nat; k:nat |] ==> i#*k < j#*k" 303apply (simp (no_asm_simp) add: mult_lt_mono2 mult_commute [of _ k]) 304done 305 306lemma add_eq_0_iff [iff]: "m#+n = 0 \<longleftrightarrow> natify(m)=0 & natify(n)=0" 307apply (subgoal_tac "natify (m) #+ natify (n) = 0 \<longleftrightarrow> natify (m) =0 & natify (n) =0") 308apply (rule_tac [2] n = "natify (m) " in natE) 309 apply (rule_tac [4] n = "natify (n) " in natE) 310apply auto 311done 312 313lemma zero_lt_mult_iff [iff]: "0 < m#*n \<longleftrightarrow> 0 < natify(m) & 0 < natify(n)" 314apply (subgoal_tac "0 < natify (m) #*natify (n) \<longleftrightarrow> 0 < natify (m) & 0 < natify (n) ") 315apply (rule_tac [2] n = "natify (m) " in natE) 316 apply (rule_tac [4] n = "natify (n) " in natE) 317 apply (rule_tac [3] n = "natify (n) " in natE) 318apply auto 319done 320 321lemma mult_eq_1_iff [iff]: "m#*n = 1 \<longleftrightarrow> natify(m)=1 & natify(n)=1" 322apply (subgoal_tac "natify (m) #* natify (n) = 1 \<longleftrightarrow> natify (m) =1 & natify (n) =1") 323apply (rule_tac [2] n = "natify (m) " in natE) 324 apply (rule_tac [4] n = "natify (n) " in natE) 325apply auto 326done 327 328 329lemma mult_is_zero: "[|m: nat; n: nat|] ==> (m #* n = 0) \<longleftrightarrow> (m = 0 | n = 0)" 330apply auto 331apply (erule natE) 332apply (erule_tac [2] natE, auto) 333done 334 335lemma mult_is_zero_natify [iff]: 336 "(m #* n = 0) \<longleftrightarrow> (natify(m) = 0 | natify(n) = 0)" 337apply (cut_tac m = "natify (m) " and n = "natify (n) " in mult_is_zero) 338apply auto 339done 340 341 342subsection\<open>Cancellation Laws for Common Factors in Comparisons\<close> 343 344lemma mult_less_cancel_lemma: 345 "[| k: nat; m: nat; n: nat |] ==> (m#*k < n#*k) \<longleftrightarrow> (0<k & m<n)" 346apply (safe intro!: mult_lt_mono1) 347apply (erule natE, auto) 348apply (rule not_le_iff_lt [THEN iffD1]) 349apply (drule_tac [3] not_le_iff_lt [THEN [2] rev_iffD2]) 350prefer 5 apply (blast intro: mult_le_mono1, auto) 351done 352 353lemma mult_less_cancel2 [simp]: 354 "(m#*k < n#*k) \<longleftrightarrow> (0 < natify(k) & natify(m) < natify(n))" 355apply (rule iff_trans) 356apply (rule_tac [2] mult_less_cancel_lemma, auto) 357done 358 359lemma mult_less_cancel1 [simp]: 360 "(k#*m < k#*n) \<longleftrightarrow> (0 < natify(k) & natify(m) < natify(n))" 361apply (simp (no_asm) add: mult_less_cancel2 mult_commute [of k]) 362done 363 364lemma mult_le_cancel2 [simp]: "(m#*k \<le> n#*k) \<longleftrightarrow> (0 < natify(k) \<longrightarrow> natify(m) \<le> natify(n))" 365apply (simp (no_asm_simp) add: not_lt_iff_le [THEN iff_sym]) 366apply auto 367done 368 369lemma mult_le_cancel1 [simp]: "(k#*m \<le> k#*n) \<longleftrightarrow> (0 < natify(k) \<longrightarrow> natify(m) \<le> natify(n))" 370apply (simp (no_asm_simp) add: not_lt_iff_le [THEN iff_sym]) 371apply auto 372done 373 374lemma mult_le_cancel_le1: "k \<in> nat ==> k #* m \<le> k \<longleftrightarrow> (0 < k \<longrightarrow> natify(m) \<le> 1)" 375by (cut_tac k = k and m = m and n = 1 in mult_le_cancel1, auto) 376 377lemma Ord_eq_iff_le: "[| Ord(m); Ord(n) |] ==> m=n \<longleftrightarrow> (m \<le> n & n \<le> m)" 378by (blast intro: le_anti_sym) 379 380lemma mult_cancel2_lemma: 381 "[| k: nat; m: nat; n: nat |] ==> (m#*k = n#*k) \<longleftrightarrow> (m=n | k=0)" 382apply (simp (no_asm_simp) add: Ord_eq_iff_le [of "m#*k"] Ord_eq_iff_le [of m]) 383apply (auto simp add: Ord_0_lt_iff) 384done 385 386lemma mult_cancel2 [simp]: 387 "(m#*k = n#*k) \<longleftrightarrow> (natify(m) = natify(n) | natify(k) = 0)" 388apply (rule iff_trans) 389apply (rule_tac [2] mult_cancel2_lemma, auto) 390done 391 392lemma mult_cancel1 [simp]: 393 "(k#*m = k#*n) \<longleftrightarrow> (natify(m) = natify(n) | natify(k) = 0)" 394apply (simp (no_asm) add: mult_cancel2 mult_commute [of k]) 395done 396 397 398(** Cancellation law for division **) 399 400lemma div_cancel_raw: 401 "[| 0<n; 0<k; k:nat; m:nat; n:nat |] ==> (k#*m) div (k#*n) = m div n" 402apply (erule_tac i = m in complete_induct) 403apply (case_tac "x<n") 404 apply (simp add: div_less zero_lt_mult_iff mult_lt_mono2) 405apply (simp add: not_lt_iff_le zero_lt_mult_iff le_refl [THEN mult_le_mono] 406 div_geq diff_mult_distrib2 [symmetric] div_termination [THEN ltD]) 407done 408 409lemma div_cancel: 410 "[| 0 < natify(n); 0 < natify(k) |] ==> (k#*m) div (k#*n) = m div n" 411apply (cut_tac k = "natify (k) " and m = "natify (m)" and n = "natify (n)" 412 in div_cancel_raw) 413apply auto 414done 415 416 417subsection\<open>More Lemmas about Remainder\<close> 418 419lemma mult_mod_distrib_raw: 420 "[| k:nat; m:nat; n:nat |] ==> (k#*m) mod (k#*n) = k #* (m mod n)" 421apply (case_tac "k=0") 422 apply (simp add: DIVISION_BY_ZERO_MOD) 423apply (case_tac "n=0") 424 apply (simp add: DIVISION_BY_ZERO_MOD) 425apply (simp add: nat_into_Ord [THEN Ord_0_lt_iff]) 426apply (erule_tac i = m in complete_induct) 427apply (case_tac "x<n") 428 apply (simp (no_asm_simp) add: mod_less zero_lt_mult_iff mult_lt_mono2) 429apply (simp add: not_lt_iff_le zero_lt_mult_iff le_refl [THEN mult_le_mono] 430 mod_geq diff_mult_distrib2 [symmetric] div_termination [THEN ltD]) 431done 432 433lemma mod_mult_distrib2: "k #* (m mod n) = (k#*m) mod (k#*n)" 434apply (cut_tac k = "natify (k) " and m = "natify (m)" and n = "natify (n)" 435 in mult_mod_distrib_raw) 436apply auto 437done 438 439lemma mult_mod_distrib: "(m mod n) #* k = (m#*k) mod (n#*k)" 440apply (simp (no_asm) add: mult_commute mod_mult_distrib2) 441done 442 443lemma mod_add_self2_raw: "n \<in> nat ==> (m #+ n) mod n = m mod n" 444apply (subgoal_tac " (n #+ m) mod n = (n #+ m #- n) mod n") 445apply (simp add: add_commute) 446apply (subst mod_geq [symmetric], auto) 447done 448 449lemma mod_add_self2 [simp]: "(m #+ n) mod n = m mod n" 450apply (cut_tac n = "natify (n) " in mod_add_self2_raw) 451apply auto 452done 453 454lemma mod_add_self1 [simp]: "(n#+m) mod n = m mod n" 455apply (simp (no_asm_simp) add: add_commute mod_add_self2) 456done 457 458lemma mod_mult_self1_raw: "k \<in> nat ==> (m #+ k#*n) mod n = m mod n" 459apply (erule nat_induct) 460apply (simp_all (no_asm_simp) add: add_left_commute [of _ n]) 461done 462 463lemma mod_mult_self1 [simp]: "(m #+ k#*n) mod n = m mod n" 464apply (cut_tac k = "natify (k) " in mod_mult_self1_raw) 465apply auto 466done 467 468lemma mod_mult_self2 [simp]: "(m #+ n#*k) mod n = m mod n" 469apply (simp (no_asm) add: mult_commute mod_mult_self1) 470done 471 472(*Lemma for gcd*) 473lemma mult_eq_self_implies_10: "m = m#*n ==> natify(n)=1 | m=0" 474apply (subgoal_tac "m: nat") 475 prefer 2 476 apply (erule ssubst) 477 apply simp 478apply (rule disjCI) 479apply (drule sym) 480apply (rule Ord_linear_lt [of "natify(n)" 1]) 481apply simp_all 482 apply (subgoal_tac "m #* n = 0", simp) 483 apply (subst mult_natify2 [symmetric]) 484 apply (simp del: mult_natify2) 485apply (drule nat_into_Ord [THEN Ord_0_lt, THEN [2] mult_lt_mono2], auto) 486done 487 488lemma less_imp_succ_add [rule_format]: 489 "[| m<n; n: nat |] ==> \<exists>k\<in>nat. n = succ(m#+k)" 490apply (frule lt_nat_in_nat, assumption) 491apply (erule rev_mp) 492apply (induct_tac "n") 493apply (simp_all (no_asm) add: le_iff) 494apply (blast elim!: leE intro!: add_0_right [symmetric] add_succ_right [symmetric]) 495done 496 497lemma less_iff_succ_add: 498 "[| m: nat; n: nat |] ==> (m<n) \<longleftrightarrow> (\<exists>k\<in>nat. n = succ(m#+k))" 499by (auto intro: less_imp_succ_add) 500 501lemma add_lt_elim2: 502 "\<lbrakk>a #+ d = b #+ c; a < b; b \<in> nat; c \<in> nat; d \<in> nat\<rbrakk> \<Longrightarrow> c < d" 503by (drule less_imp_succ_add, auto) 504 505lemma add_le_elim2: 506 "\<lbrakk>a #+ d = b #+ c; a \<le> b; b \<in> nat; c \<in> nat; d \<in> nat\<rbrakk> \<Longrightarrow> c \<le> d" 507by (drule less_imp_succ_add, auto) 508 509 510subsubsection\<open>More Lemmas About Difference\<close> 511 512lemma diff_is_0_lemma: 513 "[| m: nat; n: nat |] ==> m #- n = 0 \<longleftrightarrow> m \<le> n" 514apply (rule_tac m = m and n = n in diff_induct, simp_all) 515done 516 517lemma diff_is_0_iff: "m #- n = 0 \<longleftrightarrow> natify(m) \<le> natify(n)" 518by (simp add: diff_is_0_lemma [symmetric]) 519 520lemma nat_lt_imp_diff_eq_0: 521 "[| a:nat; b:nat; a<b |] ==> a #- b = 0" 522by (simp add: diff_is_0_iff le_iff) 523 524lemma raw_nat_diff_split: 525 "[| a:nat; b:nat |] ==> 526 (P(a #- b)) \<longleftrightarrow> ((a < b \<longrightarrow>P(0)) & (\<forall>d\<in>nat. a = b #+ d \<longrightarrow> P(d)))" 527apply (case_tac "a < b") 528 apply (force simp add: nat_lt_imp_diff_eq_0) 529apply (rule iffI, force, simp) 530apply (drule_tac x="a#-b" in bspec) 531apply (simp_all add: Ordinal.not_lt_iff_le add_diff_inverse) 532done 533 534lemma nat_diff_split: 535 "(P(a #- b)) \<longleftrightarrow> 536 (natify(a) < natify(b) \<longrightarrow>P(0)) & (\<forall>d\<in>nat. natify(a) = b #+ d \<longrightarrow> P(d))" 537apply (cut_tac P=P and a="natify(a)" and b="natify(b)" in raw_nat_diff_split) 538apply simp_all 539done 540 541text\<open>Difference and less-than\<close> 542 543lemma diff_lt_imp_lt: "[|(k#-i) < (k#-j); i\<in>nat; j\<in>nat; k\<in>nat|] ==> j<i" 544apply (erule rev_mp) 545apply (simp split: nat_diff_split, auto) 546 apply (blast intro: add_le_self lt_trans1) 547apply (rule not_le_iff_lt [THEN iffD1], auto) 548apply (subgoal_tac "i #+ da < j #+ d", force) 549apply (blast intro: add_le_lt_mono) 550done 551 552lemma lt_imp_diff_lt: "[|j<i; i\<le>k; k\<in>nat|] ==> (k#-i) < (k#-j)" 553apply (frule le_in_nat, assumption) 554apply (frule lt_nat_in_nat, assumption) 555apply (simp split: nat_diff_split, auto) 556 apply (blast intro: lt_asym lt_trans2) 557 apply (blast intro: lt_irrefl lt_trans2) 558apply (rule not_le_iff_lt [THEN iffD1], auto) 559apply (subgoal_tac "j #+ d < i #+ da", force) 560apply (blast intro: add_lt_le_mono) 561done 562 563 564lemma diff_lt_iff_lt: "[|i\<le>k; j\<in>nat; k\<in>nat|] ==> (k#-i) < (k#-j) \<longleftrightarrow> j<i" 565apply (frule le_in_nat, assumption) 566apply (blast intro: lt_imp_diff_lt diff_lt_imp_lt) 567done 568 569end 570