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