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