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