src/CTT/Arith.thy
author wenzelm
Fri Jun 02 18:24:48 2006 +0200 (2006-06-02)
changeset 19762 957bcf55c98f
parent 19761 5cd82054c2c6
child 21210 c17fd2df4e9e
permissions -rw-r--r--
tuned;
wenzelm@17441
     1
(*  Title:      CTT/Arith.thy
clasohm@0
     2
    ID:         $Id$
clasohm@1474
     3
    Author:     Lawrence C Paulson, Cambridge University Computer Laboratory
clasohm@0
     4
    Copyright   1991  University of Cambridge
clasohm@0
     5
*)
clasohm@0
     6
wenzelm@19761
     7
header {* Elementary arithmetic *}
wenzelm@17441
     8
wenzelm@17441
     9
theory Arith
wenzelm@17441
    10
imports Bool
wenzelm@17441
    11
begin
clasohm@0
    12
wenzelm@19761
    13
subsection {* Arithmetic operators and their definitions *}
wenzelm@17441
    14
wenzelm@19762
    15
definition
wenzelm@19762
    16
  add :: "[i,i]=>i"   (infixr "#+" 65)
wenzelm@19762
    17
  "a#+b == rec(a, b, %u v. succ(v))"
clasohm@0
    18
wenzelm@19762
    19
  diff :: "[i,i]=>i"   (infixr "-" 65)
wenzelm@19762
    20
  "a-b == rec(b, a, %u v. rec(v, 0, %x y. x))"
wenzelm@19762
    21
wenzelm@19762
    22
  absdiff :: "[i,i]=>i"   (infixr "|-|" 65)
wenzelm@19762
    23
  "a|-|b == (a-b) #+ (b-a)"
wenzelm@19762
    24
wenzelm@19762
    25
  mult :: "[i,i]=>i"   (infixr "#*" 70)
wenzelm@19762
    26
  "a#*b == rec(a, 0, %u v. b #+ v)"
paulson@10467
    27
wenzelm@19762
    28
  mod :: "[i,i]=>i"   (infixr "mod" 70)
wenzelm@19762
    29
  "a mod b == rec(a, 0, %u v. rec(succ(v) |-| b, 0, %x y. succ(v)))"
wenzelm@19762
    30
wenzelm@19762
    31
  div :: "[i,i]=>i"   (infixr "div" 70)
wenzelm@19762
    32
  "a div b == rec(a, 0, %u v. rec(succ(u) mod b, succ(v), %x y. v))"
wenzelm@19762
    33
paulson@10467
    34
wenzelm@19762
    35
const_syntax (xsymbols)
wenzelm@19762
    36
  mult  (infixr "#\<times>" 70)
wenzelm@19762
    37
wenzelm@19762
    38
const_syntax (HTML output)
wenzelm@19762
    39
  mult (infixr "#\<times>" 70)
wenzelm@19762
    40
wenzelm@17441
    41
wenzelm@19761
    42
lemmas arith_defs = add_def diff_def absdiff_def mult_def mod_def div_def
wenzelm@19761
    43
wenzelm@19761
    44
wenzelm@19761
    45
subsection {* Proofs about elementary arithmetic: addition, multiplication, etc. *}
wenzelm@19761
    46
wenzelm@19761
    47
(** Addition *)
wenzelm@19761
    48
wenzelm@19761
    49
(*typing of add: short and long versions*)
wenzelm@19761
    50
wenzelm@19761
    51
lemma add_typing: "[| a:N;  b:N |] ==> a #+ b : N"
wenzelm@19761
    52
apply (unfold arith_defs)
wenzelm@19761
    53
apply (tactic "typechk_tac []")
wenzelm@19761
    54
done
wenzelm@19761
    55
wenzelm@19761
    56
lemma add_typingL: "[| a=c:N;  b=d:N |] ==> a #+ b = c #+ d : N"
wenzelm@19761
    57
apply (unfold arith_defs)
wenzelm@19761
    58
apply (tactic "equal_tac []")
wenzelm@19761
    59
done
wenzelm@19761
    60
wenzelm@19761
    61
wenzelm@19761
    62
(*computation for add: 0 and successor cases*)
wenzelm@19761
    63
wenzelm@19761
    64
lemma addC0: "b:N ==> 0 #+ b = b : N"
wenzelm@19761
    65
apply (unfold arith_defs)
wenzelm@19761
    66
apply (tactic "rew_tac []")
wenzelm@19761
    67
done
wenzelm@19761
    68
wenzelm@19761
    69
lemma addC_succ: "[| a:N;  b:N |] ==> succ(a) #+ b = succ(a #+ b) : N"
wenzelm@19761
    70
apply (unfold arith_defs)
wenzelm@19761
    71
apply (tactic "rew_tac []")
wenzelm@19761
    72
done
wenzelm@19761
    73
wenzelm@19761
    74
wenzelm@19761
    75
(** Multiplication *)
wenzelm@19761
    76
wenzelm@19761
    77
(*typing of mult: short and long versions*)
wenzelm@19761
    78
wenzelm@19761
    79
lemma mult_typing: "[| a:N;  b:N |] ==> a #* b : N"
wenzelm@19761
    80
apply (unfold arith_defs)
wenzelm@19761
    81
apply (tactic {* typechk_tac [thm "add_typing"] *})
wenzelm@19761
    82
done
wenzelm@19761
    83
wenzelm@19761
    84
lemma mult_typingL: "[| a=c:N;  b=d:N |] ==> a #* b = c #* d : N"
wenzelm@19761
    85
apply (unfold arith_defs)
wenzelm@19761
    86
apply (tactic {* equal_tac [thm "add_typingL"] *})
wenzelm@19761
    87
done
wenzelm@19761
    88
wenzelm@19761
    89
(*computation for mult: 0 and successor cases*)
wenzelm@19761
    90
wenzelm@19761
    91
lemma multC0: "b:N ==> 0 #* b = 0 : N"
wenzelm@19761
    92
apply (unfold arith_defs)
wenzelm@19761
    93
apply (tactic "rew_tac []")
wenzelm@19761
    94
done
wenzelm@19761
    95
wenzelm@19761
    96
lemma multC_succ: "[| a:N;  b:N |] ==> succ(a) #* b = b #+ (a #* b) : N"
wenzelm@19761
    97
apply (unfold arith_defs)
wenzelm@19761
    98
apply (tactic "rew_tac []")
wenzelm@19761
    99
done
wenzelm@19761
   100
wenzelm@19761
   101
wenzelm@19761
   102
(** Difference *)
wenzelm@19761
   103
wenzelm@19761
   104
(*typing of difference*)
wenzelm@19761
   105
wenzelm@19761
   106
lemma diff_typing: "[| a:N;  b:N |] ==> a - b : N"
wenzelm@19761
   107
apply (unfold arith_defs)
wenzelm@19761
   108
apply (tactic "typechk_tac []")
wenzelm@19761
   109
done
wenzelm@19761
   110
wenzelm@19761
   111
lemma diff_typingL: "[| a=c:N;  b=d:N |] ==> a - b = c - d : N"
wenzelm@19761
   112
apply (unfold arith_defs)
wenzelm@19761
   113
apply (tactic "equal_tac []")
wenzelm@19761
   114
done
wenzelm@19761
   115
wenzelm@19761
   116
wenzelm@19761
   117
(*computation for difference: 0 and successor cases*)
wenzelm@19761
   118
wenzelm@19761
   119
lemma diffC0: "a:N ==> a - 0 = a : N"
wenzelm@19761
   120
apply (unfold arith_defs)
wenzelm@19761
   121
apply (tactic "rew_tac []")
wenzelm@19761
   122
done
wenzelm@19761
   123
wenzelm@19761
   124
(*Note: rec(a, 0, %z w.z) is pred(a). *)
wenzelm@19761
   125
wenzelm@19761
   126
lemma diff_0_eq_0: "b:N ==> 0 - b = 0 : N"
wenzelm@19761
   127
apply (unfold arith_defs)
wenzelm@19761
   128
apply (tactic {* NE_tac "b" 1 *})
wenzelm@19761
   129
apply (tactic "hyp_rew_tac []")
wenzelm@19761
   130
done
wenzelm@19761
   131
wenzelm@19761
   132
wenzelm@19761
   133
(*Essential to simplify FIRST!!  (Else we get a critical pair)
wenzelm@19761
   134
  succ(a) - succ(b) rewrites to   pred(succ(a) - b)  *)
wenzelm@19761
   135
lemma diff_succ_succ: "[| a:N;  b:N |] ==> succ(a) - succ(b) = a - b : N"
wenzelm@19761
   136
apply (unfold arith_defs)
wenzelm@19761
   137
apply (tactic "hyp_rew_tac []")
wenzelm@19761
   138
apply (tactic {* NE_tac "b" 1 *})
wenzelm@19761
   139
apply (tactic "hyp_rew_tac []")
wenzelm@19761
   140
done
wenzelm@19761
   141
wenzelm@19761
   142
wenzelm@19761
   143
subsection {* Simplification *}
wenzelm@19761
   144
wenzelm@19761
   145
lemmas arith_typing_rls = add_typing mult_typing diff_typing
wenzelm@19761
   146
  and arith_congr_rls = add_typingL mult_typingL diff_typingL
wenzelm@19761
   147
lemmas congr_rls = arith_congr_rls intrL2_rls elimL_rls
wenzelm@19761
   148
wenzelm@19761
   149
lemmas arithC_rls =
wenzelm@19761
   150
  addC0 addC_succ
wenzelm@19761
   151
  multC0 multC_succ
wenzelm@19761
   152
  diffC0 diff_0_eq_0 diff_succ_succ
wenzelm@19761
   153
wenzelm@19761
   154
ML {*
wenzelm@19761
   155
wenzelm@19761
   156
structure Arith_simp_data: TSIMP_DATA =
wenzelm@19761
   157
  struct
wenzelm@19761
   158
  val refl              = thm "refl_elem"
wenzelm@19761
   159
  val sym               = thm "sym_elem"
wenzelm@19761
   160
  val trans             = thm "trans_elem"
wenzelm@19761
   161
  val refl_red          = thm "refl_red"
wenzelm@19761
   162
  val trans_red         = thm "trans_red"
wenzelm@19761
   163
  val red_if_equal      = thm "red_if_equal"
wenzelm@19761
   164
  val default_rls       = thms "arithC_rls" @ thms "comp_rls"
wenzelm@19761
   165
  val routine_tac       = routine_tac (thms "arith_typing_rls" @ thms "routine_rls")
wenzelm@19761
   166
  end
wenzelm@19761
   167
wenzelm@19761
   168
structure Arith_simp = TSimpFun (Arith_simp_data)
wenzelm@19761
   169
wenzelm@19761
   170
local val congr_rls = thms "congr_rls" in
wenzelm@19761
   171
wenzelm@19761
   172
fun arith_rew_tac prems = make_rew_tac
wenzelm@19761
   173
    (Arith_simp.norm_tac(congr_rls, prems))
wenzelm@19761
   174
wenzelm@19761
   175
fun hyp_arith_rew_tac prems = make_rew_tac
wenzelm@19761
   176
    (Arith_simp.cond_norm_tac(prove_cond_tac, congr_rls, prems))
wenzelm@17441
   177
clasohm@0
   178
end
wenzelm@19761
   179
*}
wenzelm@19761
   180
wenzelm@19761
   181
wenzelm@19761
   182
subsection {* Addition *}
wenzelm@19761
   183
wenzelm@19761
   184
(*Associative law for addition*)
wenzelm@19761
   185
lemma add_assoc: "[| a:N;  b:N;  c:N |] ==> (a #+ b) #+ c = a #+ (b #+ c) : N"
wenzelm@19761
   186
apply (tactic {* NE_tac "a" 1 *})
wenzelm@19761
   187
apply (tactic "hyp_arith_rew_tac []")
wenzelm@19761
   188
done
wenzelm@19761
   189
wenzelm@19761
   190
wenzelm@19761
   191
(*Commutative law for addition.  Can be proved using three inductions.
wenzelm@19761
   192
  Must simplify after first induction!  Orientation of rewrites is delicate*)
wenzelm@19761
   193
lemma add_commute: "[| a:N;  b:N |] ==> a #+ b = b #+ a : N"
wenzelm@19761
   194
apply (tactic {* NE_tac "a" 1 *})
wenzelm@19761
   195
apply (tactic "hyp_arith_rew_tac []")
wenzelm@19761
   196
apply (tactic {* NE_tac "b" 2 *})
wenzelm@19761
   197
apply (rule sym_elem)
wenzelm@19761
   198
apply (tactic {* NE_tac "b" 1 *})
wenzelm@19761
   199
apply (tactic "hyp_arith_rew_tac []")
wenzelm@19761
   200
done
wenzelm@19761
   201
wenzelm@19761
   202
wenzelm@19761
   203
subsection {* Multiplication *}
wenzelm@19761
   204
wenzelm@19761
   205
(*right annihilation in product*)
wenzelm@19761
   206
lemma mult_0_right: "a:N ==> a #* 0 = 0 : N"
wenzelm@19761
   207
apply (tactic {* NE_tac "a" 1 *})
wenzelm@19761
   208
apply (tactic "hyp_arith_rew_tac []")
wenzelm@19761
   209
done
wenzelm@19761
   210
wenzelm@19761
   211
(*right successor law for multiplication*)
wenzelm@19761
   212
lemma mult_succ_right: "[| a:N;  b:N |] ==> a #* succ(b) = a #+ (a #* b) : N"
wenzelm@19761
   213
apply (tactic {* NE_tac "a" 1 *})
wenzelm@19761
   214
apply (tactic {* hyp_arith_rew_tac [thm "add_assoc" RS thm "sym_elem"] *})
wenzelm@19761
   215
apply (assumption | rule add_commute mult_typingL add_typingL intrL_rls refl_elem)+
wenzelm@19761
   216
done
wenzelm@19761
   217
wenzelm@19761
   218
(*Commutative law for multiplication*)
wenzelm@19761
   219
lemma mult_commute: "[| a:N;  b:N |] ==> a #* b = b #* a : N"
wenzelm@19761
   220
apply (tactic {* NE_tac "a" 1 *})
wenzelm@19761
   221
apply (tactic {* hyp_arith_rew_tac [thm "mult_0_right", thm "mult_succ_right"] *})
wenzelm@19761
   222
done
wenzelm@19761
   223
wenzelm@19761
   224
(*addition distributes over multiplication*)
wenzelm@19761
   225
lemma add_mult_distrib: "[| a:N;  b:N;  c:N |] ==> (a #+ b) #* c = (a #* c) #+ (b #* c) : N"
wenzelm@19761
   226
apply (tactic {* NE_tac "a" 1 *})
wenzelm@19761
   227
apply (tactic {* hyp_arith_rew_tac [thm "add_assoc" RS thm "sym_elem"] *})
wenzelm@19761
   228
done
wenzelm@19761
   229
wenzelm@19761
   230
(*Associative law for multiplication*)
wenzelm@19761
   231
lemma mult_assoc: "[| a:N;  b:N;  c:N |] ==> (a #* b) #* c = a #* (b #* c) : N"
wenzelm@19761
   232
apply (tactic {* NE_tac "a" 1 *})
wenzelm@19761
   233
apply (tactic {* hyp_arith_rew_tac [thm "add_mult_distrib"] *})
wenzelm@19761
   234
done
wenzelm@19761
   235
wenzelm@19761
   236
wenzelm@19761
   237
subsection {* Difference *}
wenzelm@19761
   238
wenzelm@19761
   239
text {*
wenzelm@19761
   240
Difference on natural numbers, without negative numbers
wenzelm@19761
   241
  a - b = 0  iff  a<=b    a - b = succ(c) iff a>b   *}
wenzelm@19761
   242
wenzelm@19761
   243
lemma diff_self_eq_0: "a:N ==> a - a = 0 : N"
wenzelm@19761
   244
apply (tactic {* NE_tac "a" 1 *})
wenzelm@19761
   245
apply (tactic "hyp_arith_rew_tac []")
wenzelm@19761
   246
done
wenzelm@19761
   247
wenzelm@19761
   248
wenzelm@19761
   249
lemma add_0_right: "[| c : N; 0 : N; c : N |] ==> c #+ 0 = c : N"
wenzelm@19761
   250
  by (rule addC0 [THEN [3] add_commute [THEN trans_elem]])
wenzelm@19761
   251
wenzelm@19761
   252
(*Addition is the inverse of subtraction: if b<=x then b#+(x-b) = x.
wenzelm@19761
   253
  An example of induction over a quantified formula (a product).
wenzelm@19761
   254
  Uses rewriting with a quantified, implicative inductive hypothesis.*)
wenzelm@19761
   255
lemma add_diff_inverse_lemma: "b:N ==> ?a : PROD x:N. Eq(N, b-x, 0) --> Eq(N, b #+ (x-b), x)"
wenzelm@19761
   256
apply (tactic {* NE_tac "b" 1 *})
wenzelm@19761
   257
(*strip one "universal quantifier" but not the "implication"*)
wenzelm@19761
   258
apply (rule_tac [3] intr_rls)
wenzelm@19761
   259
(*case analysis on x in
wenzelm@19761
   260
    (succ(u) <= x) --> (succ(u)#+(x-succ(u)) = x) *)
wenzelm@19761
   261
apply (tactic {* NE_tac "x" 4 *}, tactic "assume_tac 4")
wenzelm@19761
   262
(*Prepare for simplification of types -- the antecedent succ(u)<=x *)
wenzelm@19761
   263
apply (rule_tac [5] replace_type)
wenzelm@19761
   264
apply (rule_tac [4] replace_type)
wenzelm@19761
   265
apply (tactic "arith_rew_tac []")
wenzelm@19761
   266
(*Solves first 0 goal, simplifies others.  Two sugbgoals remain.
wenzelm@19761
   267
  Both follow by rewriting, (2) using quantified induction hyp*)
wenzelm@19761
   268
apply (tactic "intr_tac []") (*strips remaining PRODs*)
wenzelm@19761
   269
apply (tactic {* hyp_arith_rew_tac [thm "add_0_right"] *})
wenzelm@19761
   270
apply assumption
wenzelm@19761
   271
done
wenzelm@19761
   272
wenzelm@19761
   273
wenzelm@19761
   274
(*Version of above with premise   b-a=0   i.e.    a >= b.
wenzelm@19761
   275
  Using ProdE does not work -- for ?B(?a) is ambiguous.
wenzelm@19761
   276
  Instead, add_diff_inverse_lemma states the desired induction scheme
wenzelm@19761
   277
    the use of RS below instantiates Vars in ProdE automatically. *)
wenzelm@19761
   278
lemma add_diff_inverse: "[| a:N;  b:N;  b-a = 0 : N |] ==> b #+ (a-b) = a : N"
wenzelm@19761
   279
apply (rule EqE)
wenzelm@19761
   280
apply (rule add_diff_inverse_lemma [THEN ProdE, THEN ProdE])
wenzelm@19761
   281
apply (assumption | rule EqI)+
wenzelm@19761
   282
done
wenzelm@19761
   283
wenzelm@19761
   284
wenzelm@19761
   285
subsection {* Absolute difference *}
wenzelm@19761
   286
wenzelm@19761
   287
(*typing of absolute difference: short and long versions*)
wenzelm@19761
   288
wenzelm@19761
   289
lemma absdiff_typing: "[| a:N;  b:N |] ==> a |-| b : N"
wenzelm@19761
   290
apply (unfold arith_defs)
wenzelm@19761
   291
apply (tactic "typechk_tac []")
wenzelm@19761
   292
done
wenzelm@19761
   293
wenzelm@19761
   294
lemma absdiff_typingL: "[| a=c:N;  b=d:N |] ==> a |-| b = c |-| d : N"
wenzelm@19761
   295
apply (unfold arith_defs)
wenzelm@19761
   296
apply (tactic "equal_tac []")
wenzelm@19761
   297
done
wenzelm@19761
   298
wenzelm@19761
   299
lemma absdiff_self_eq_0: "a:N ==> a |-| a = 0 : N"
wenzelm@19761
   300
apply (unfold absdiff_def)
wenzelm@19761
   301
apply (tactic {* arith_rew_tac [thm "diff_self_eq_0"] *})
wenzelm@19761
   302
done
wenzelm@19761
   303
wenzelm@19761
   304
lemma absdiffC0: "a:N ==> 0 |-| a = a : N"
wenzelm@19761
   305
apply (unfold absdiff_def)
wenzelm@19761
   306
apply (tactic "hyp_arith_rew_tac []")
wenzelm@19761
   307
done
wenzelm@19761
   308
wenzelm@19761
   309
wenzelm@19761
   310
lemma absdiff_succ_succ: "[| a:N;  b:N |] ==> succ(a) |-| succ(b)  =  a |-| b : N"
wenzelm@19761
   311
apply (unfold absdiff_def)
wenzelm@19761
   312
apply (tactic "hyp_arith_rew_tac []")
wenzelm@19761
   313
done
wenzelm@19761
   314
wenzelm@19761
   315
(*Note how easy using commutative laws can be?  ...not always... *)
wenzelm@19761
   316
lemma absdiff_commute: "[| a:N;  b:N |] ==> a |-| b = b |-| a : N"
wenzelm@19761
   317
apply (unfold absdiff_def)
wenzelm@19761
   318
apply (rule add_commute)
wenzelm@19761
   319
apply (tactic {* typechk_tac [thm "diff_typing"] *})
wenzelm@19761
   320
done
wenzelm@19761
   321
wenzelm@19761
   322
(*If a+b=0 then a=0.   Surprisingly tedious*)
wenzelm@19761
   323
lemma add_eq0_lemma: "[| a:N;  b:N |] ==> ?c : PROD u: Eq(N,a#+b,0) .  Eq(N,a,0)"
wenzelm@19761
   324
apply (tactic {* NE_tac "a" 1 *})
wenzelm@19761
   325
apply (rule_tac [3] replace_type)
wenzelm@19761
   326
apply (tactic "arith_rew_tac []")
wenzelm@19761
   327
apply (tactic "intr_tac []") (*strips remaining PRODs*)
wenzelm@19761
   328
apply (rule_tac [2] zero_ne_succ [THEN FE])
wenzelm@19761
   329
apply (erule_tac [3] EqE [THEN sym_elem])
wenzelm@19761
   330
apply (tactic {* typechk_tac [thm "add_typing"] *})
wenzelm@19761
   331
done
wenzelm@19761
   332
wenzelm@19761
   333
(*Version of above with the premise  a+b=0.
wenzelm@19761
   334
  Again, resolution instantiates variables in ProdE *)
wenzelm@19761
   335
lemma add_eq0: "[| a:N;  b:N;  a #+ b = 0 : N |] ==> a = 0 : N"
wenzelm@19761
   336
apply (rule EqE)
wenzelm@19761
   337
apply (rule add_eq0_lemma [THEN ProdE])
wenzelm@19761
   338
apply (rule_tac [3] EqI)
wenzelm@19761
   339
apply (tactic "typechk_tac []")
wenzelm@19761
   340
done
wenzelm@19761
   341
wenzelm@19761
   342
(*Here is a lemma to infer a-b=0 and b-a=0 from a|-|b=0, below. *)
wenzelm@19761
   343
lemma absdiff_eq0_lem:
wenzelm@19761
   344
    "[| a:N;  b:N;  a |-| b = 0 : N |] ==>
wenzelm@19761
   345
     ?a : SUM v: Eq(N, a-b, 0) . Eq(N, b-a, 0)"
wenzelm@19761
   346
apply (unfold absdiff_def)
wenzelm@19761
   347
apply (tactic "intr_tac []")
wenzelm@19761
   348
apply (tactic eqintr_tac)
wenzelm@19761
   349
apply (rule_tac [2] add_eq0)
wenzelm@19761
   350
apply (rule add_eq0)
wenzelm@19761
   351
apply (rule_tac [6] add_commute [THEN trans_elem])
wenzelm@19761
   352
apply (tactic {* typechk_tac [thm "diff_typing"] *})
wenzelm@19761
   353
done
wenzelm@19761
   354
wenzelm@19761
   355
(*if  a |-| b = 0  then  a = b
wenzelm@19761
   356
  proof: a-b=0 and b-a=0, so b = a+(b-a) = a+0 = a*)
wenzelm@19761
   357
lemma absdiff_eq0: "[| a |-| b = 0 : N;  a:N;  b:N |] ==> a = b : N"
wenzelm@19761
   358
apply (rule EqE)
wenzelm@19761
   359
apply (rule absdiff_eq0_lem [THEN SumE])
wenzelm@19761
   360
apply (tactic "TRYALL assume_tac")
wenzelm@19761
   361
apply (tactic eqintr_tac)
wenzelm@19761
   362
apply (rule add_diff_inverse [THEN sym_elem, THEN trans_elem])
wenzelm@19761
   363
apply (rule_tac [3] EqE, tactic "assume_tac 3")
wenzelm@19761
   364
apply (tactic {* hyp_arith_rew_tac [thm "add_0_right"] *})
wenzelm@19761
   365
done
wenzelm@19761
   366
wenzelm@19761
   367
wenzelm@19761
   368
subsection {* Remainder and Quotient *}
wenzelm@19761
   369
wenzelm@19761
   370
(*typing of remainder: short and long versions*)
wenzelm@19761
   371
wenzelm@19761
   372
lemma mod_typing: "[| a:N;  b:N |] ==> a mod b : N"
wenzelm@19761
   373
apply (unfold mod_def)
wenzelm@19761
   374
apply (tactic {* typechk_tac [thm "absdiff_typing"] *})
wenzelm@19761
   375
done
wenzelm@19761
   376
wenzelm@19761
   377
lemma mod_typingL: "[| a=c:N;  b=d:N |] ==> a mod b = c mod d : N"
wenzelm@19761
   378
apply (unfold mod_def)
wenzelm@19761
   379
apply (tactic {* equal_tac [thm "absdiff_typingL"] *})
wenzelm@19761
   380
done
wenzelm@19761
   381
wenzelm@19761
   382
wenzelm@19761
   383
(*computation for  mod : 0 and successor cases*)
wenzelm@19761
   384
wenzelm@19761
   385
lemma modC0: "b:N ==> 0 mod b = 0 : N"
wenzelm@19761
   386
apply (unfold mod_def)
wenzelm@19761
   387
apply (tactic {* rew_tac [thm "absdiff_typing"] *})
wenzelm@19761
   388
done
wenzelm@19761
   389
wenzelm@19761
   390
lemma modC_succ:
wenzelm@19761
   391
"[| a:N; b:N |] ==> succ(a) mod b = rec(succ(a mod b) |-| b, 0, %x y. succ(a mod b)) : N"
wenzelm@19761
   392
apply (unfold mod_def)
wenzelm@19761
   393
apply (tactic {* rew_tac [thm "absdiff_typing"] *})
wenzelm@19761
   394
done
wenzelm@19761
   395
wenzelm@19761
   396
wenzelm@19761
   397
(*typing of quotient: short and long versions*)
wenzelm@19761
   398
wenzelm@19761
   399
lemma div_typing: "[| a:N;  b:N |] ==> a div b : N"
wenzelm@19761
   400
apply (unfold div_def)
wenzelm@19761
   401
apply (tactic {* typechk_tac [thm "absdiff_typing", thm "mod_typing"] *})
wenzelm@19761
   402
done
wenzelm@19761
   403
wenzelm@19761
   404
lemma div_typingL: "[| a=c:N;  b=d:N |] ==> a div b = c div d : N"
wenzelm@19761
   405
apply (unfold div_def)
wenzelm@19761
   406
apply (tactic {* equal_tac [thm "absdiff_typingL", thm "mod_typingL"] *})
wenzelm@19761
   407
done
wenzelm@19761
   408
wenzelm@19761
   409
lemmas div_typing_rls = mod_typing div_typing absdiff_typing
wenzelm@19761
   410
wenzelm@19761
   411
wenzelm@19761
   412
(*computation for quotient: 0 and successor cases*)
wenzelm@19761
   413
wenzelm@19761
   414
lemma divC0: "b:N ==> 0 div b = 0 : N"
wenzelm@19761
   415
apply (unfold div_def)
wenzelm@19761
   416
apply (tactic {* rew_tac [thm "mod_typing", thm "absdiff_typing"] *})
wenzelm@19761
   417
done
wenzelm@19761
   418
wenzelm@19761
   419
lemma divC_succ:
wenzelm@19761
   420
 "[| a:N;  b:N |] ==> succ(a) div b =
wenzelm@19761
   421
     rec(succ(a) mod b, succ(a div b), %x y. a div b) : N"
wenzelm@19761
   422
apply (unfold div_def)
wenzelm@19761
   423
apply (tactic {* rew_tac [thm "mod_typing"] *})
wenzelm@19761
   424
done
wenzelm@19761
   425
wenzelm@19761
   426
wenzelm@19761
   427
(*Version of above with same condition as the  mod  one*)
wenzelm@19761
   428
lemma divC_succ2: "[| a:N;  b:N |] ==>
wenzelm@19761
   429
     succ(a) div b =rec(succ(a mod b) |-| b, succ(a div b), %x y. a div b) : N"
wenzelm@19761
   430
apply (rule divC_succ [THEN trans_elem])
wenzelm@19761
   431
apply (tactic {* rew_tac (thms "div_typing_rls" @ [thm "modC_succ"]) *})
wenzelm@19761
   432
apply (tactic {* NE_tac "succ (a mod b) |-|b" 1 *})
wenzelm@19761
   433
apply (tactic {* rew_tac [thm "mod_typing", thm "div_typing", thm "absdiff_typing"] *})
wenzelm@19761
   434
done
wenzelm@19761
   435
wenzelm@19761
   436
(*for case analysis on whether a number is 0 or a successor*)
wenzelm@19761
   437
lemma iszero_decidable: "a:N ==> rec(a, inl(eq), %ka kb. inr(<ka, eq>)) :
wenzelm@19761
   438
                      Eq(N,a,0) + (SUM x:N. Eq(N,a, succ(x)))"
wenzelm@19761
   439
apply (tactic {* NE_tac "a" 1 *})
wenzelm@19761
   440
apply (rule_tac [3] PlusI_inr)
wenzelm@19761
   441
apply (rule_tac [2] PlusI_inl)
wenzelm@19761
   442
apply (tactic eqintr_tac)
wenzelm@19761
   443
apply (tactic "equal_tac []")
wenzelm@19761
   444
done
wenzelm@19761
   445
wenzelm@19761
   446
(*Main Result.  Holds when b is 0 since   a mod 0 = a     and    a div 0 = 0  *)
wenzelm@19761
   447
lemma mod_div_equality: "[| a:N;  b:N |] ==> a mod b  #+  (a div b) #* b = a : N"
wenzelm@19761
   448
apply (tactic {* NE_tac "a" 1 *})
wenzelm@19761
   449
apply (tactic {* arith_rew_tac (thms "div_typing_rls" @
wenzelm@19761
   450
  [thm "modC0", thm "modC_succ", thm "divC0", thm "divC_succ2"]) *})
wenzelm@19761
   451
apply (rule EqE)
wenzelm@19761
   452
(*case analysis on   succ(u mod b)|-|b  *)
wenzelm@19761
   453
apply (rule_tac a1 = "succ (u mod b) |-| b" in iszero_decidable [THEN PlusE])
wenzelm@19761
   454
apply (erule_tac [3] SumE)
wenzelm@19761
   455
apply (tactic {* hyp_arith_rew_tac (thms "div_typing_rls" @
wenzelm@19761
   456
  [thm "modC0", thm "modC_succ", thm "divC0", thm "divC_succ2"]) *})
wenzelm@19761
   457
(*Replace one occurence of  b  by succ(u mod b).  Clumsy!*)
wenzelm@19761
   458
apply (rule add_typingL [THEN trans_elem])
wenzelm@19761
   459
apply (erule EqE [THEN absdiff_eq0, THEN sym_elem])
wenzelm@19761
   460
apply (rule_tac [3] refl_elem)
wenzelm@19761
   461
apply (tactic {* hyp_arith_rew_tac (thms "div_typing_rls") *})
wenzelm@19761
   462
done
wenzelm@19761
   463
wenzelm@19761
   464
end