src/ZF/Arith.thy
author wenzelm
Thu Sep 02 00:48:07 2010 +0200 (2010-09-02)
changeset 38980 af73cf0dc31f
parent 35762 af3ff2ba4c54
child 45608 13b101cee425
permissions -rw-r--r--
turned show_question_marks into proper configuration option;
show_question_marks only affects regular type/term pretty printing, not raw Term.string_of_vname;
tuned;
     1 (*  Title:      ZF/Arith.thy
     2     Author:     Lawrence C Paulson, Cambridge University Computer Laboratory
     3     Copyright   1992  University of Cambridge
     4 *)
     5 
     6 (*"Difference" is subtraction of natural numbers.
     7   There are no negative numbers; we have
     8      m #- n = 0  iff  m<=n   and     m #- n = succ(k) iff m>n.
     9   Also, rec(m, 0, %z w.z) is pred(m).   
    10 *)
    11 
    12 header{*Arithmetic Operators and Their Definitions*} 
    13 
    14 theory Arith imports Univ begin
    15 
    16 text{*Proofs about elementary arithmetic: addition, multiplication, etc.*}
    17 
    18 definition
    19   pred   :: "i=>i"    (*inverse of succ*)  where
    20     "pred(y) == nat_case(0, %x. x, y)"
    21 
    22 definition
    23   natify :: "i=>i"    (*coerces non-nats to nats*)  where
    24     "natify == Vrecursor(%f a. if a = succ(pred(a)) then succ(f`pred(a))
    25                                                     else 0)"
    26 
    27 consts
    28   raw_add  :: "[i,i]=>i"
    29   raw_diff  :: "[i,i]=>i"
    30   raw_mult  :: "[i,i]=>i"
    31 
    32 primrec
    33   "raw_add (0, n) = n"
    34   "raw_add (succ(m), n) = succ(raw_add(m, n))"
    35 
    36 primrec
    37   raw_diff_0:     "raw_diff(m, 0) = m"
    38   raw_diff_succ:  "raw_diff(m, succ(n)) =
    39                      nat_case(0, %x. x, raw_diff(m, n))"
    40 
    41 primrec
    42   "raw_mult(0, n) = 0"
    43   "raw_mult(succ(m), n) = raw_add (n, raw_mult(m, n))"
    44 
    45 definition
    46   add :: "[i,i]=>i"                    (infixl "#+" 65)  where
    47     "m #+ n == raw_add (natify(m), natify(n))"
    48 
    49 definition
    50   diff :: "[i,i]=>i"                    (infixl "#-" 65)  where
    51     "m #- n == raw_diff (natify(m), natify(n))"
    52 
    53 definition
    54   mult :: "[i,i]=>i"                    (infixl "#*" 70)  where
    55     "m #* n == raw_mult (natify(m), natify(n))"
    56 
    57 definition
    58   raw_div  :: "[i,i]=>i"  where
    59     "raw_div (m, n) ==
    60        transrec(m, %j f. if j<n | n=0 then 0 else succ(f`(j#-n)))"
    61 
    62 definition
    63   raw_mod  :: "[i,i]=>i"  where
    64     "raw_mod (m, n) ==
    65        transrec(m, %j f. if j<n | n=0 then j else f`(j#-n))"
    66 
    67 definition
    68   div  :: "[i,i]=>i"                    (infixl "div" 70)  where
    69     "m div n == raw_div (natify(m), natify(n))"
    70 
    71 definition
    72   mod  :: "[i,i]=>i"                    (infixl "mod" 70)  where
    73     "m mod n == raw_mod (natify(m), natify(n))"
    74 
    75 notation (xsymbols)
    76   mult  (infixr "#\<times>" 70)
    77 
    78 notation (HTML output)
    79   mult  (infixr "#\<times>" 70)
    80 
    81 declare rec_type [simp]
    82         nat_0_le [simp]
    83 
    84 
    85 lemma zero_lt_lemma: "[| 0<k; k \<in> nat |] ==> \<exists>j\<in>nat. k = succ(j)"
    86 apply (erule rev_mp)
    87 apply (induct_tac "k", auto)
    88 done
    89 
    90 (* [| 0 < k; k \<in> nat; !!j. [| j \<in> nat; k = succ(j) |] ==> Q |] ==> Q *)
    91 lemmas zero_lt_natE = zero_lt_lemma [THEN bexE, standard]
    92 
    93 
    94 subsection{*@{text natify}, the Coercion to @{term nat}*}
    95 
    96 lemma pred_succ_eq [simp]: "pred(succ(y)) = y"
    97 by (unfold pred_def, auto)
    98 
    99 lemma natify_succ: "natify(succ(x)) = succ(natify(x))"
   100 by (rule natify_def [THEN def_Vrecursor, THEN trans], auto)
   101 
   102 lemma natify_0 [simp]: "natify(0) = 0"
   103 by (rule natify_def [THEN def_Vrecursor, THEN trans], auto)
   104 
   105 lemma natify_non_succ: "\<forall>z. x ~= succ(z) ==> natify(x) = 0"
   106 by (rule natify_def [THEN def_Vrecursor, THEN trans], auto)
   107 
   108 lemma natify_in_nat [iff,TC]: "natify(x) \<in> nat"
   109 apply (rule_tac a=x in eps_induct)
   110 apply (case_tac "\<exists>z. x = succ(z)")
   111 apply (auto simp add: natify_succ natify_non_succ)
   112 done
   113 
   114 lemma natify_ident [simp]: "n \<in> nat ==> natify(n) = n"
   115 apply (induct_tac "n")
   116 apply (auto simp add: natify_succ)
   117 done
   118 
   119 lemma natify_eqE: "[|natify(x) = y;  x \<in> nat|] ==> x=y"
   120 by auto
   121 
   122 
   123 (*** Collapsing rules: to remove natify from arithmetic expressions ***)
   124 
   125 lemma natify_idem [simp]: "natify(natify(x)) = natify(x)"
   126 by simp
   127 
   128 (** Addition **)
   129 
   130 lemma add_natify1 [simp]: "natify(m) #+ n = m #+ n"
   131 by (simp add: add_def)
   132 
   133 lemma add_natify2 [simp]: "m #+ natify(n) = m #+ n"
   134 by (simp add: add_def)
   135 
   136 (** Multiplication **)
   137 
   138 lemma mult_natify1 [simp]: "natify(m) #* n = m #* n"
   139 by (simp add: mult_def)
   140 
   141 lemma mult_natify2 [simp]: "m #* natify(n) = m #* n"
   142 by (simp add: mult_def)
   143 
   144 (** Difference **)
   145 
   146 lemma diff_natify1 [simp]: "natify(m) #- n = m #- n"
   147 by (simp add: diff_def)
   148 
   149 lemma diff_natify2 [simp]: "m #- natify(n) = m #- n"
   150 by (simp add: diff_def)
   151 
   152 (** Remainder **)
   153 
   154 lemma mod_natify1 [simp]: "natify(m) mod n = m mod n"
   155 by (simp add: mod_def)
   156 
   157 lemma mod_natify2 [simp]: "m mod natify(n) = m mod n"
   158 by (simp add: mod_def)
   159 
   160 
   161 (** Quotient **)
   162 
   163 lemma div_natify1 [simp]: "natify(m) div n = m div n"
   164 by (simp add: div_def)
   165 
   166 lemma div_natify2 [simp]: "m div natify(n) = m div n"
   167 by (simp add: div_def)
   168 
   169 
   170 subsection{*Typing rules*}
   171 
   172 (** Addition **)
   173 
   174 lemma raw_add_type: "[| m\<in>nat;  n\<in>nat |] ==> raw_add (m, n) \<in> nat"
   175 by (induct_tac "m", auto)
   176 
   177 lemma add_type [iff,TC]: "m #+ n \<in> nat"
   178 by (simp add: add_def raw_add_type)
   179 
   180 (** Multiplication **)
   181 
   182 lemma raw_mult_type: "[| m\<in>nat;  n\<in>nat |] ==> raw_mult (m, n) \<in> nat"
   183 apply (induct_tac "m")
   184 apply (simp_all add: raw_add_type)
   185 done
   186 
   187 lemma mult_type [iff,TC]: "m #* n \<in> nat"
   188 by (simp add: mult_def raw_mult_type)
   189 
   190 
   191 (** Difference **)
   192 
   193 lemma raw_diff_type: "[| m\<in>nat;  n\<in>nat |] ==> raw_diff (m, n) \<in> nat"
   194 by (induct_tac "n", auto)
   195 
   196 lemma diff_type [iff,TC]: "m #- n \<in> nat"
   197 by (simp add: diff_def raw_diff_type)
   198 
   199 lemma diff_0_eq_0 [simp]: "0 #- n = 0"
   200 apply (unfold diff_def)
   201 apply (rule natify_in_nat [THEN nat_induct], auto)
   202 done
   203 
   204 (*Must simplify BEFORE the induction: else we get a critical pair*)
   205 lemma diff_succ_succ [simp]: "succ(m) #- succ(n) = m #- n"
   206 apply (simp add: natify_succ diff_def)
   207 apply (rule_tac x1 = n in natify_in_nat [THEN nat_induct], auto)
   208 done
   209 
   210 (*This defining property is no longer wanted*)
   211 declare raw_diff_succ [simp del]
   212 
   213 (*Natify has weakened this law, compared with the older approach*)
   214 lemma diff_0 [simp]: "m #- 0 = natify(m)"
   215 by (simp add: diff_def)
   216 
   217 lemma diff_le_self: "m\<in>nat ==> (m #- n) le m"
   218 apply (subgoal_tac " (m #- natify (n)) le m")
   219 apply (rule_tac [2] m = m and n = "natify (n) " in diff_induct)
   220 apply (erule_tac [6] leE)
   221 apply (simp_all add: le_iff)
   222 done
   223 
   224 
   225 subsection{*Addition*}
   226 
   227 (*Natify has weakened this law, compared with the older approach*)
   228 lemma add_0_natify [simp]: "0 #+ m = natify(m)"
   229 by (simp add: add_def)
   230 
   231 lemma add_succ [simp]: "succ(m) #+ n = succ(m #+ n)"
   232 by (simp add: natify_succ add_def)
   233 
   234 lemma add_0: "m \<in> nat ==> 0 #+ m = m"
   235 by simp
   236 
   237 (*Associative law for addition*)
   238 lemma add_assoc: "(m #+ n) #+ k = m #+ (n #+ k)"
   239 apply (subgoal_tac "(natify(m) #+ natify(n)) #+ natify(k) =
   240                     natify(m) #+ (natify(n) #+ natify(k))")
   241 apply (rule_tac [2] n = "natify(m)" in nat_induct)
   242 apply auto
   243 done
   244 
   245 (*The following two lemmas are used for add_commute and sometimes
   246   elsewhere, since they are safe for rewriting.*)
   247 lemma add_0_right_natify [simp]: "m #+ 0 = natify(m)"
   248 apply (subgoal_tac "natify(m) #+ 0 = natify(m)")
   249 apply (rule_tac [2] n = "natify(m)" in nat_induct)
   250 apply auto
   251 done
   252 
   253 lemma add_succ_right [simp]: "m #+ succ(n) = succ(m #+ n)"
   254 apply (unfold add_def)
   255 apply (rule_tac n = "natify(m) " in nat_induct)
   256 apply (auto simp add: natify_succ)
   257 done
   258 
   259 lemma add_0_right: "m \<in> nat ==> m #+ 0 = m"
   260 by auto
   261 
   262 (*Commutative law for addition*)
   263 lemma add_commute: "m #+ n = n #+ m"
   264 apply (subgoal_tac "natify(m) #+ natify(n) = natify(n) #+ natify(m) ")
   265 apply (rule_tac [2] n = "natify(m) " in nat_induct)
   266 apply auto
   267 done
   268 
   269 (*for a/c rewriting*)
   270 lemma add_left_commute: "m#+(n#+k)=n#+(m#+k)"
   271 apply (rule add_commute [THEN trans])
   272 apply (rule add_assoc [THEN trans])
   273 apply (rule add_commute [THEN subst_context])
   274 done
   275 
   276 (*Addition is an AC-operator*)
   277 lemmas add_ac = add_assoc add_commute add_left_commute
   278 
   279 (*Cancellation law on the left*)
   280 lemma raw_add_left_cancel:
   281      "[| raw_add(k, m) = raw_add(k, n);  k\<in>nat |] ==> m=n"
   282 apply (erule rev_mp)
   283 apply (induct_tac "k", auto)
   284 done
   285 
   286 lemma add_left_cancel_natify: "k #+ m = k #+ n ==> natify(m) = natify(n)"
   287 apply (unfold add_def)
   288 apply (drule raw_add_left_cancel, auto)
   289 done
   290 
   291 lemma add_left_cancel:
   292      "[| i = j;  i #+ m = j #+ n;  m\<in>nat;  n\<in>nat |] ==> m = n"
   293 by (force dest!: add_left_cancel_natify)
   294 
   295 (*Thanks to Sten Agerholm*)
   296 lemma add_le_elim1_natify: "k#+m le k#+n ==> natify(m) le natify(n)"
   297 apply (rule_tac P = "natify(k) #+m le natify(k) #+n" in rev_mp)
   298 apply (rule_tac [2] n = "natify(k) " in nat_induct)
   299 apply auto
   300 done
   301 
   302 lemma add_le_elim1: "[| k#+m le k#+n; m \<in> nat; n \<in> nat |] ==> m le n"
   303 by (drule add_le_elim1_natify, auto)
   304 
   305 lemma add_lt_elim1_natify: "k#+m < k#+n ==> natify(m) < natify(n)"
   306 apply (rule_tac P = "natify(k) #+m < natify(k) #+n" in rev_mp)
   307 apply (rule_tac [2] n = "natify(k) " in nat_induct)
   308 apply auto
   309 done
   310 
   311 lemma add_lt_elim1: "[| k#+m < k#+n; m \<in> nat; n \<in> nat |] ==> m < n"
   312 by (drule add_lt_elim1_natify, auto)
   313 
   314 lemma zero_less_add: "[| n \<in> nat; m \<in> nat |] ==> 0 < m #+ n <-> (0<m | 0<n)"
   315 by (induct_tac "n", auto)
   316 
   317 
   318 subsection{*Monotonicity of Addition*}
   319 
   320 (*strict, in 1st argument; proof is by rule induction on 'less than'.
   321   Still need j\<in>nat, for consider j = omega.  Then we can have i<omega,
   322   which is the same as i\<in>nat, but natify(j)=0, so the conclusion fails.*)
   323 lemma add_lt_mono1: "[| i<j; j\<in>nat |] ==> i#+k < j#+k"
   324 apply (frule lt_nat_in_nat, assumption)
   325 apply (erule succ_lt_induct)
   326 apply (simp_all add: leI)
   327 done
   328 
   329 text{*strict, in second argument*}
   330 lemma add_lt_mono2: "[| i<j; j\<in>nat |] ==> k#+i < k#+j"
   331 by (simp add: add_commute [of k] add_lt_mono1)
   332 
   333 text{*A [clumsy] way of lifting < monotonicity to @{text "\<le>"} monotonicity*}
   334 lemma Ord_lt_mono_imp_le_mono:
   335   assumes lt_mono: "!!i j. [| i<j; j:k |] ==> f(i) < f(j)"
   336       and ford:    "!!i. i:k ==> Ord(f(i))"
   337       and leij:    "i le j"
   338       and jink:    "j:k"
   339   shows "f(i) le f(j)"
   340 apply (insert leij jink) 
   341 apply (blast intro!: leCI lt_mono ford elim!: leE)
   342 done
   343 
   344 text{*@{text "\<le>"} monotonicity, 1st argument*}
   345 lemma add_le_mono1: "[| i le j; j\<in>nat |] ==> i#+k le j#+k"
   346 apply (rule_tac f = "%j. j#+k" in Ord_lt_mono_imp_le_mono, typecheck) 
   347 apply (blast intro: add_lt_mono1 add_type [THEN nat_into_Ord])+
   348 done
   349 
   350 text{*@{text "\<le>"} monotonicity, both arguments*}
   351 lemma add_le_mono: "[| i le j; k le l; j\<in>nat; l\<in>nat |] ==> i#+k le j#+l"
   352 apply (rule add_le_mono1 [THEN le_trans], assumption+)
   353 apply (subst add_commute, subst add_commute, rule add_le_mono1, assumption+)
   354 done
   355 
   356 text{*Combinations of less-than and less-than-or-equals*}
   357 
   358 lemma add_lt_le_mono: "[| i<j; k\<le>l; j\<in>nat; l\<in>nat |] ==> i#+k < j#+l"
   359 apply (rule add_lt_mono1 [THEN lt_trans2], assumption+)
   360 apply (subst add_commute, subst add_commute, rule add_le_mono1, assumption+)
   361 done
   362 
   363 lemma add_le_lt_mono: "[| i\<le>j; k<l; j\<in>nat; l\<in>nat |] ==> i#+k < j#+l"
   364 by (subst add_commute, subst add_commute, erule add_lt_le_mono, assumption+)
   365 
   366 text{*Less-than: in other words, strict in both arguments*}
   367 lemma add_lt_mono: "[| i<j; k<l; j\<in>nat; l\<in>nat |] ==> i#+k < j#+l"
   368 apply (rule add_lt_le_mono) 
   369 apply (auto intro: leI) 
   370 done
   371 
   372 (** Subtraction is the inverse of addition. **)
   373 
   374 lemma diff_add_inverse: "(n#+m) #- n = natify(m)"
   375 apply (subgoal_tac " (natify(n) #+ m) #- natify(n) = natify(m) ")
   376 apply (rule_tac [2] n = "natify(n) " in nat_induct)
   377 apply auto
   378 done
   379 
   380 lemma diff_add_inverse2: "(m#+n) #- n = natify(m)"
   381 by (simp add: add_commute [of m] diff_add_inverse)
   382 
   383 lemma diff_cancel: "(k#+m) #- (k#+n) = m #- n"
   384 apply (subgoal_tac "(natify(k) #+ natify(m)) #- (natify(k) #+ natify(n)) =
   385                     natify(m) #- natify(n) ")
   386 apply (rule_tac [2] n = "natify(k) " in nat_induct)
   387 apply auto
   388 done
   389 
   390 lemma diff_cancel2: "(m#+k) #- (n#+k) = m #- n"
   391 by (simp add: add_commute [of _ k] diff_cancel)
   392 
   393 lemma diff_add_0: "n #- (n#+m) = 0"
   394 apply (subgoal_tac "natify(n) #- (natify(n) #+ natify(m)) = 0")
   395 apply (rule_tac [2] n = "natify(n) " in nat_induct)
   396 apply auto
   397 done
   398 
   399 lemma pred_0 [simp]: "pred(0) = 0"
   400 by (simp add: pred_def)
   401 
   402 lemma eq_succ_imp_eq_m1: "[|i = succ(j); i\<in>nat|] ==> j = i #- 1 & j \<in>nat"
   403 by simp 
   404 
   405 lemma pred_Un_distrib:
   406     "[|i\<in>nat; j\<in>nat|] ==> pred(i Un j) = pred(i) Un pred(j)"
   407 apply (erule_tac n=i in natE, simp) 
   408 apply (erule_tac n=j in natE, simp) 
   409 apply (simp add:  succ_Un_distrib [symmetric])
   410 done
   411 
   412 lemma pred_type [TC,simp]:
   413     "i \<in> nat ==> pred(i) \<in> nat"
   414 by (simp add: pred_def split: split_nat_case)
   415 
   416 lemma nat_diff_pred: "[|i\<in>nat; j\<in>nat|] ==> i #- succ(j) = pred(i #- j)";
   417 apply (rule_tac m=i and n=j in diff_induct) 
   418 apply (auto simp add: pred_def nat_imp_quasinat split: split_nat_case)
   419 done
   420 
   421 lemma diff_succ_eq_pred: "i #- succ(j) = pred(i #- j)";
   422 apply (insert nat_diff_pred [of "natify(i)" "natify(j)"])
   423 apply (simp add: natify_succ [symmetric]) 
   424 done
   425 
   426 lemma nat_diff_Un_distrib:
   427     "[|i\<in>nat; j\<in>nat; k\<in>nat|] ==> (i Un j) #- k = (i#-k) Un (j#-k)"
   428 apply (rule_tac n=k in nat_induct) 
   429 apply (simp_all add: diff_succ_eq_pred pred_Un_distrib) 
   430 done
   431 
   432 lemma diff_Un_distrib:
   433     "[|i\<in>nat; j\<in>nat|] ==> (i Un j) #- k = (i#-k) Un (j#-k)"
   434 by (insert nat_diff_Un_distrib [of i j "natify(k)"], simp)
   435 
   436 text{*We actually prove @{term "i #- j #- k = i #- (j #+ k)"}*}
   437 lemma diff_diff_left [simplified]:
   438      "natify(i)#-natify(j)#-k = natify(i) #- (natify(j)#+k)";
   439 by (rule_tac m="natify(i)" and n="natify(j)" in diff_induct, auto)
   440 
   441 
   442 (** Lemmas for the CancelNumerals simproc **)
   443 
   444 lemma eq_add_iff: "(u #+ m = u #+ n) <-> (0 #+ m = natify(n))"
   445 apply auto
   446 apply (blast dest: add_left_cancel_natify)
   447 apply (simp add: add_def)
   448 done
   449 
   450 lemma less_add_iff: "(u #+ m < u #+ n) <-> (0 #+ m < natify(n))"
   451 apply (auto simp add: add_lt_elim1_natify)
   452 apply (drule add_lt_mono1)
   453 apply (auto simp add: add_commute [of u])
   454 done
   455 
   456 lemma diff_add_eq: "((u #+ m) #- (u #+ n)) = ((0 #+ m) #- n)"
   457 by (simp add: diff_cancel)
   458 
   459 (*To tidy up the result of a simproc.  Only the RHS will be simplified.*)
   460 lemma eq_cong2: "u = u' ==> (t==u) == (t==u')"
   461 by auto
   462 
   463 lemma iff_cong2: "u <-> u' ==> (t==u) == (t==u')"
   464 by auto
   465 
   466 
   467 subsection{*Multiplication*}
   468 
   469 lemma mult_0 [simp]: "0 #* m = 0"
   470 by (simp add: mult_def)
   471 
   472 lemma mult_succ [simp]: "succ(m) #* n = n #+ (m #* n)"
   473 by (simp add: add_def mult_def natify_succ raw_mult_type)
   474 
   475 (*right annihilation in product*)
   476 lemma mult_0_right [simp]: "m #* 0 = 0"
   477 apply (unfold mult_def)
   478 apply (rule_tac n = "natify(m) " in nat_induct)
   479 apply auto
   480 done
   481 
   482 (*right successor law for multiplication*)
   483 lemma mult_succ_right [simp]: "m #* succ(n) = m #+ (m #* n)"
   484 apply (subgoal_tac "natify(m) #* succ (natify(n)) =
   485                     natify(m) #+ (natify(m) #* natify(n))")
   486 apply (simp (no_asm_use) add: natify_succ add_def mult_def)
   487 apply (rule_tac n = "natify(m) " in nat_induct)
   488 apply (simp_all add: add_ac)
   489 done
   490 
   491 lemma mult_1_natify [simp]: "1 #* n = natify(n)"
   492 by auto
   493 
   494 lemma mult_1_right_natify [simp]: "n #* 1 = natify(n)"
   495 by auto
   496 
   497 lemma mult_1: "n \<in> nat ==> 1 #* n = n"
   498 by simp
   499 
   500 lemma mult_1_right: "n \<in> nat ==> n #* 1 = n"
   501 by simp
   502 
   503 (*Commutative law for multiplication*)
   504 lemma mult_commute: "m #* n = n #* m"
   505 apply (subgoal_tac "natify(m) #* natify(n) = natify(n) #* natify(m) ")
   506 apply (rule_tac [2] n = "natify(m) " in nat_induct)
   507 apply auto
   508 done
   509 
   510 (*addition distributes over multiplication*)
   511 lemma add_mult_distrib: "(m #+ n) #* k = (m #* k) #+ (n #* k)"
   512 apply (subgoal_tac "(natify(m) #+ natify(n)) #* natify(k) =
   513                     (natify(m) #* natify(k)) #+ (natify(n) #* natify(k))")
   514 apply (rule_tac [2] n = "natify(m) " in nat_induct)
   515 apply (simp_all add: add_assoc [symmetric])
   516 done
   517 
   518 (*Distributive law on the left*)
   519 lemma add_mult_distrib_left: "k #* (m #+ n) = (k #* m) #+ (k #* n)"
   520 apply (subgoal_tac "natify(k) #* (natify(m) #+ natify(n)) =
   521                     (natify(k) #* natify(m)) #+ (natify(k) #* natify(n))")
   522 apply (rule_tac [2] n = "natify(m) " in nat_induct)
   523 apply (simp_all add: add_ac)
   524 done
   525 
   526 (*Associative law for multiplication*)
   527 lemma mult_assoc: "(m #* n) #* k = m #* (n #* k)"
   528 apply (subgoal_tac "(natify(m) #* natify(n)) #* natify(k) =
   529                     natify(m) #* (natify(n) #* natify(k))")
   530 apply (rule_tac [2] n = "natify(m) " in nat_induct)
   531 apply (simp_all add: add_mult_distrib)
   532 done
   533 
   534 (*for a/c rewriting*)
   535 lemma mult_left_commute: "m #* (n #* k) = n #* (m #* k)"
   536 apply (rule mult_commute [THEN trans])
   537 apply (rule mult_assoc [THEN trans])
   538 apply (rule mult_commute [THEN subst_context])
   539 done
   540 
   541 lemmas mult_ac = mult_assoc mult_commute mult_left_commute
   542 
   543 
   544 lemma lt_succ_eq_0_disj:
   545      "[| m\<in>nat; n\<in>nat |]
   546       ==> (m < succ(n)) <-> (m = 0 | (\<exists>j\<in>nat. m = succ(j) & j < n))"
   547 by (induct_tac "m", auto)
   548 
   549 lemma less_diff_conv [rule_format]:
   550      "[| j\<in>nat; k\<in>nat |] ==> \<forall>i\<in>nat. (i < j #- k) <-> (i #+ k < j)"
   551 by (erule_tac m = k in diff_induct, auto)
   552 
   553 lemmas nat_typechecks = rec_type nat_0I nat_1I nat_succI Ord_nat
   554 
   555 end