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