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