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