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