src/ZF/ArithSimp.thy
author wenzelm
Fri, 06 May 2011 17:52:08 +0200
changeset 42711 159c4d1d4c42
parent 41777 1f7cbe39d425
child 46820 c656222c4dc1
permissions -rw-r--r--
removed \underscoreon which is from Larry's iman.sty, not underscore.sty;
Ignore whitespace changes - Everywhere: Within whitespace: At end of lines:
41777
1f7cbe39d425 more precise headers;
wenzelm
parents: 35762
diff changeset
     1
(*  Title:      ZF/ArithSimp.thy
9548
15bee2731e43 instantiated Cancel_Numerals for "nat" in ZF
paulson
parents:
diff changeset
     2
    Author:     Lawrence C Paulson, Cambridge University Computer Laboratory
15bee2731e43 instantiated Cancel_Numerals for "nat" in ZF
paulson
parents:
diff changeset
     3
    Copyright   2000  University of Cambridge
15bee2731e43 instantiated Cancel_Numerals for "nat" in ZF
paulson
parents:
diff changeset
     4
*)
15bee2731e43 instantiated Cancel_Numerals for "nat" in ZF
paulson
parents:
diff changeset
     5
13328
703de709a64b better document preparation
paulson
parents: 13259
diff changeset
     6
header{*Arithmetic with simplification*}
703de709a64b better document preparation
paulson
parents: 13259
diff changeset
     7
15481
fc075ae929e4 the new subst tactic, by Lucas Dixon
paulson
parents: 14060
diff changeset
     8
theory ArithSimp 
fc075ae929e4 the new subst tactic, by Lucas Dixon
paulson
parents: 14060
diff changeset
     9
imports Arith
16417
9bc16273c2d4 migrated theory headers to new format
haftmann
parents: 15481
diff changeset
    10
uses "~~/src/Provers/Arith/cancel_numerals.ML"
15481
fc075ae929e4 the new subst tactic, by Lucas Dixon
paulson
parents: 14060
diff changeset
    11
      "~~/src/Provers/Arith/combine_numerals.ML"
fc075ae929e4 the new subst tactic, by Lucas Dixon
paulson
parents: 14060
diff changeset
    12
      "arith_data.ML"
fc075ae929e4 the new subst tactic, by Lucas Dixon
paulson
parents: 14060
diff changeset
    13
begin
13259
01fa0c8dbc92 conversion of many files to Isar format
paulson
parents: 9548
diff changeset
    14
13356
c9cfe1638bf2 improved presentation markup
paulson
parents: 13328
diff changeset
    15
subsection{*Difference*}
13259
01fa0c8dbc92 conversion of many files to Isar format
paulson
parents: 9548
diff changeset
    16
14046
6616e6c53d48 updating ZF-UNITY with Sidi's new material
paulson
parents: 13784
diff changeset
    17
lemma diff_self_eq_0 [simp]: "m #- m = 0"
13259
01fa0c8dbc92 conversion of many files to Isar format
paulson
parents: 9548
diff changeset
    18
apply (subgoal_tac "natify (m) #- natify (m) = 0")
01fa0c8dbc92 conversion of many files to Isar format
paulson
parents: 9548
diff changeset
    19
apply (rule_tac [2] natify_in_nat [THEN nat_induct], auto)
01fa0c8dbc92 conversion of many files to Isar format
paulson
parents: 9548
diff changeset
    20
done
01fa0c8dbc92 conversion of many files to Isar format
paulson
parents: 9548
diff changeset
    21
01fa0c8dbc92 conversion of many files to Isar format
paulson
parents: 9548
diff changeset
    22
(**Addition is the inverse of subtraction**)
01fa0c8dbc92 conversion of many files to Isar format
paulson
parents: 9548
diff changeset
    23
01fa0c8dbc92 conversion of many files to Isar format
paulson
parents: 9548
diff changeset
    24
(*We need m:nat even if we replace the RHS by natify(m), for consider e.g.
01fa0c8dbc92 conversion of many files to Isar format
paulson
parents: 9548
diff changeset
    25
  n=2, m=omega; then n + (m-n) = 2 + (0-2) = 2 ~= 0 = natify(m).*)
01fa0c8dbc92 conversion of many files to Isar format
paulson
parents: 9548
diff changeset
    26
lemma add_diff_inverse: "[| n le m;  m:nat |] ==> n #+ (m#-n) = m"
01fa0c8dbc92 conversion of many files to Isar format
paulson
parents: 9548
diff changeset
    27
apply (frule lt_nat_in_nat, erule nat_succI)
01fa0c8dbc92 conversion of many files to Isar format
paulson
parents: 9548
diff changeset
    28
apply (erule rev_mp)
13784
b9f6154427a4 tidying (by script)
paulson
parents: 13615
diff changeset
    29
apply (rule_tac m = m and n = n in diff_induct, auto)
13259
01fa0c8dbc92 conversion of many files to Isar format
paulson
parents: 9548
diff changeset
    30
done
01fa0c8dbc92 conversion of many files to Isar format
paulson
parents: 9548
diff changeset
    31
01fa0c8dbc92 conversion of many files to Isar format
paulson
parents: 9548
diff changeset
    32
lemma add_diff_inverse2: "[| n le m;  m:nat |] ==> (m#-n) #+ n = m"
01fa0c8dbc92 conversion of many files to Isar format
paulson
parents: 9548
diff changeset
    33
apply (frule lt_nat_in_nat, erule nat_succI)
01fa0c8dbc92 conversion of many files to Isar format
paulson
parents: 9548
diff changeset
    34
apply (simp (no_asm_simp) add: add_commute add_diff_inverse)
01fa0c8dbc92 conversion of many files to Isar format
paulson
parents: 9548
diff changeset
    35
done
01fa0c8dbc92 conversion of many files to Isar format
paulson
parents: 9548
diff changeset
    36
01fa0c8dbc92 conversion of many files to Isar format
paulson
parents: 9548
diff changeset
    37
(*Proof is IDENTICAL to that of add_diff_inverse*)
01fa0c8dbc92 conversion of many files to Isar format
paulson
parents: 9548
diff changeset
    38
lemma diff_succ: "[| n le m;  m:nat |] ==> succ(m) #- n = succ(m#-n)"
01fa0c8dbc92 conversion of many files to Isar format
paulson
parents: 9548
diff changeset
    39
apply (frule lt_nat_in_nat, erule nat_succI)
01fa0c8dbc92 conversion of many files to Isar format
paulson
parents: 9548
diff changeset
    40
apply (erule rev_mp)
13784
b9f6154427a4 tidying (by script)
paulson
parents: 13615
diff changeset
    41
apply (rule_tac m = m and n = n in diff_induct)
13259
01fa0c8dbc92 conversion of many files to Isar format
paulson
parents: 9548
diff changeset
    42
apply (simp_all (no_asm_simp))
01fa0c8dbc92 conversion of many files to Isar format
paulson
parents: 9548
diff changeset
    43
done
01fa0c8dbc92 conversion of many files to Isar format
paulson
parents: 9548
diff changeset
    44
01fa0c8dbc92 conversion of many files to Isar format
paulson
parents: 9548
diff changeset
    45
lemma zero_less_diff [simp]:
01fa0c8dbc92 conversion of many files to Isar format
paulson
parents: 9548
diff changeset
    46
     "[| m: nat; n: nat |] ==> 0 < (n #- m)   <->   m<n"
13784
b9f6154427a4 tidying (by script)
paulson
parents: 13615
diff changeset
    47
apply (rule_tac m = m and n = n in diff_induct)
13259
01fa0c8dbc92 conversion of many files to Isar format
paulson
parents: 9548
diff changeset
    48
apply (simp_all (no_asm_simp))
01fa0c8dbc92 conversion of many files to Isar format
paulson
parents: 9548
diff changeset
    49
done
01fa0c8dbc92 conversion of many files to Isar format
paulson
parents: 9548
diff changeset
    50
01fa0c8dbc92 conversion of many files to Isar format
paulson
parents: 9548
diff changeset
    51
01fa0c8dbc92 conversion of many files to Isar format
paulson
parents: 9548
diff changeset
    52
(** Difference distributes over multiplication **)
01fa0c8dbc92 conversion of many files to Isar format
paulson
parents: 9548
diff changeset
    53
01fa0c8dbc92 conversion of many files to Isar format
paulson
parents: 9548
diff changeset
    54
lemma diff_mult_distrib: "(m #- n) #* k = (m #* k) #- (n #* k)"
01fa0c8dbc92 conversion of many files to Isar format
paulson
parents: 9548
diff changeset
    55
apply (subgoal_tac " (natify (m) #- natify (n)) #* natify (k) = (natify (m) #* natify (k)) #- (natify (n) #* natify (k))")
01fa0c8dbc92 conversion of many files to Isar format
paulson
parents: 9548
diff changeset
    56
apply (rule_tac [2] m = "natify (m) " and n = "natify (n) " in diff_induct)
01fa0c8dbc92 conversion of many files to Isar format
paulson
parents: 9548
diff changeset
    57
apply (simp_all add: diff_cancel)
01fa0c8dbc92 conversion of many files to Isar format
paulson
parents: 9548
diff changeset
    58
done
01fa0c8dbc92 conversion of many files to Isar format
paulson
parents: 9548
diff changeset
    59
01fa0c8dbc92 conversion of many files to Isar format
paulson
parents: 9548
diff changeset
    60
lemma diff_mult_distrib2: "k #* (m #- n) = (k #* m) #- (k #* n)"
01fa0c8dbc92 conversion of many files to Isar format
paulson
parents: 9548
diff changeset
    61
apply (simp (no_asm) add: mult_commute [of k] diff_mult_distrib)
01fa0c8dbc92 conversion of many files to Isar format
paulson
parents: 9548
diff changeset
    62
done
01fa0c8dbc92 conversion of many files to Isar format
paulson
parents: 9548
diff changeset
    63
01fa0c8dbc92 conversion of many files to Isar format
paulson
parents: 9548
diff changeset
    64
13356
c9cfe1638bf2 improved presentation markup
paulson
parents: 13328
diff changeset
    65
subsection{*Remainder*}
13259
01fa0c8dbc92 conversion of many files to Isar format
paulson
parents: 9548
diff changeset
    66
01fa0c8dbc92 conversion of many files to Isar format
paulson
parents: 9548
diff changeset
    67
(*We need m:nat even with natify*)
01fa0c8dbc92 conversion of many files to Isar format
paulson
parents: 9548
diff changeset
    68
lemma div_termination: "[| 0<n;  n le m;  m:nat |] ==> m #- n < m"
01fa0c8dbc92 conversion of many files to Isar format
paulson
parents: 9548
diff changeset
    69
apply (frule lt_nat_in_nat, erule nat_succI)
01fa0c8dbc92 conversion of many files to Isar format
paulson
parents: 9548
diff changeset
    70
apply (erule rev_mp)
01fa0c8dbc92 conversion of many files to Isar format
paulson
parents: 9548
diff changeset
    71
apply (erule rev_mp)
13784
b9f6154427a4 tidying (by script)
paulson
parents: 13615
diff changeset
    72
apply (rule_tac m = m and n = n in diff_induct)
13259
01fa0c8dbc92 conversion of many files to Isar format
paulson
parents: 9548
diff changeset
    73
apply (simp_all (no_asm_simp) add: diff_le_self)
01fa0c8dbc92 conversion of many files to Isar format
paulson
parents: 9548
diff changeset
    74
done
01fa0c8dbc92 conversion of many files to Isar format
paulson
parents: 9548
diff changeset
    75
01fa0c8dbc92 conversion of many files to Isar format
paulson
parents: 9548
diff changeset
    76
(*for mod and div*)
01fa0c8dbc92 conversion of many files to Isar format
paulson
parents: 9548
diff changeset
    77
lemmas div_rls = 
01fa0c8dbc92 conversion of many files to Isar format
paulson
parents: 9548
diff changeset
    78
    nat_typechecks Ord_transrec_type apply_funtype 
01fa0c8dbc92 conversion of many files to Isar format
paulson
parents: 9548
diff changeset
    79
    div_termination [THEN ltD]
01fa0c8dbc92 conversion of many files to Isar format
paulson
parents: 9548
diff changeset
    80
    nat_into_Ord not_lt_iff_le [THEN iffD1]
01fa0c8dbc92 conversion of many files to Isar format
paulson
parents: 9548
diff changeset
    81
01fa0c8dbc92 conversion of many files to Isar format
paulson
parents: 9548
diff changeset
    82
lemma raw_mod_type: "[| m:nat;  n:nat |] ==> raw_mod (m, n) : nat"
01fa0c8dbc92 conversion of many files to Isar format
paulson
parents: 9548
diff changeset
    83
apply (unfold raw_mod_def)
01fa0c8dbc92 conversion of many files to Isar format
paulson
parents: 9548
diff changeset
    84
apply (rule Ord_transrec_type)
01fa0c8dbc92 conversion of many files to Isar format
paulson
parents: 9548
diff changeset
    85
apply (auto simp add: nat_into_Ord [THEN Ord_0_lt_iff])
01fa0c8dbc92 conversion of many files to Isar format
paulson
parents: 9548
diff changeset
    86
apply (blast intro: div_rls) 
01fa0c8dbc92 conversion of many files to Isar format
paulson
parents: 9548
diff changeset
    87
done
01fa0c8dbc92 conversion of many files to Isar format
paulson
parents: 9548
diff changeset
    88
01fa0c8dbc92 conversion of many files to Isar format
paulson
parents: 9548
diff changeset
    89
lemma mod_type [TC,iff]: "m mod n : nat"
01fa0c8dbc92 conversion of many files to Isar format
paulson
parents: 9548
diff changeset
    90
apply (unfold mod_def)
01fa0c8dbc92 conversion of many files to Isar format
paulson
parents: 9548
diff changeset
    91
apply (simp (no_asm) add: mod_def raw_mod_type)
01fa0c8dbc92 conversion of many files to Isar format
paulson
parents: 9548
diff changeset
    92
done
01fa0c8dbc92 conversion of many files to Isar format
paulson
parents: 9548
diff changeset
    93
01fa0c8dbc92 conversion of many files to Isar format
paulson
parents: 9548
diff changeset
    94
01fa0c8dbc92 conversion of many files to Isar format
paulson
parents: 9548
diff changeset
    95
(** Aribtrary definitions for division by zero.  Useful to simplify 
01fa0c8dbc92 conversion of many files to Isar format
paulson
parents: 9548
diff changeset
    96
    certain equations **)
01fa0c8dbc92 conversion of many files to Isar format
paulson
parents: 9548
diff changeset
    97
01fa0c8dbc92 conversion of many files to Isar format
paulson
parents: 9548
diff changeset
    98
lemma DIVISION_BY_ZERO_DIV: "a div 0 = 0"
01fa0c8dbc92 conversion of many files to Isar format
paulson
parents: 9548
diff changeset
    99
apply (unfold div_def)
01fa0c8dbc92 conversion of many files to Isar format
paulson
parents: 9548
diff changeset
   100
apply (rule raw_div_def [THEN def_transrec, THEN trans])
01fa0c8dbc92 conversion of many files to Isar format
paulson
parents: 9548
diff changeset
   101
apply (simp (no_asm_simp))
01fa0c8dbc92 conversion of many files to Isar format
paulson
parents: 9548
diff changeset
   102
done  (*NOT for adding to default simpset*)
01fa0c8dbc92 conversion of many files to Isar format
paulson
parents: 9548
diff changeset
   103
01fa0c8dbc92 conversion of many files to Isar format
paulson
parents: 9548
diff changeset
   104
lemma DIVISION_BY_ZERO_MOD: "a mod 0 = natify(a)"
01fa0c8dbc92 conversion of many files to Isar format
paulson
parents: 9548
diff changeset
   105
apply (unfold mod_def)
01fa0c8dbc92 conversion of many files to Isar format
paulson
parents: 9548
diff changeset
   106
apply (rule raw_mod_def [THEN def_transrec, THEN trans])
01fa0c8dbc92 conversion of many files to Isar format
paulson
parents: 9548
diff changeset
   107
apply (simp (no_asm_simp))
01fa0c8dbc92 conversion of many files to Isar format
paulson
parents: 9548
diff changeset
   108
done  (*NOT for adding to default simpset*)
01fa0c8dbc92 conversion of many files to Isar format
paulson
parents: 9548
diff changeset
   109
01fa0c8dbc92 conversion of many files to Isar format
paulson
parents: 9548
diff changeset
   110
lemma raw_mod_less: "m<n ==> raw_mod (m,n) = m"
01fa0c8dbc92 conversion of many files to Isar format
paulson
parents: 9548
diff changeset
   111
apply (rule raw_mod_def [THEN def_transrec, THEN trans])
01fa0c8dbc92 conversion of many files to Isar format
paulson
parents: 9548
diff changeset
   112
apply (simp (no_asm_simp) add: div_termination [THEN ltD])
01fa0c8dbc92 conversion of many files to Isar format
paulson
parents: 9548
diff changeset
   113
done
01fa0c8dbc92 conversion of many files to Isar format
paulson
parents: 9548
diff changeset
   114
01fa0c8dbc92 conversion of many files to Isar format
paulson
parents: 9548
diff changeset
   115
lemma mod_less [simp]: "[| m<n; n : nat |] ==> m mod n = m"
01fa0c8dbc92 conversion of many files to Isar format
paulson
parents: 9548
diff changeset
   116
apply (frule lt_nat_in_nat, assumption)
01fa0c8dbc92 conversion of many files to Isar format
paulson
parents: 9548
diff changeset
   117
apply (simp (no_asm_simp) add: mod_def raw_mod_less)
01fa0c8dbc92 conversion of many files to Isar format
paulson
parents: 9548
diff changeset
   118
done
01fa0c8dbc92 conversion of many files to Isar format
paulson
parents: 9548
diff changeset
   119
01fa0c8dbc92 conversion of many files to Isar format
paulson
parents: 9548
diff changeset
   120
lemma raw_mod_geq:
01fa0c8dbc92 conversion of many files to Isar format
paulson
parents: 9548
diff changeset
   121
     "[| 0<n; n le m;  m:nat |] ==> raw_mod (m, n) = raw_mod (m#-n, n)"
01fa0c8dbc92 conversion of many files to Isar format
paulson
parents: 9548
diff changeset
   122
apply (frule lt_nat_in_nat, erule nat_succI)
01fa0c8dbc92 conversion of many files to Isar format
paulson
parents: 9548
diff changeset
   123
apply (rule raw_mod_def [THEN def_transrec, THEN trans])
13611
2edf034c902a Adapted to new simplifier.
berghofe
parents: 13356
diff changeset
   124
apply (simp (no_asm_simp) add: div_termination [THEN ltD] not_lt_iff_le [THEN iffD2], blast)
13259
01fa0c8dbc92 conversion of many files to Isar format
paulson
parents: 9548
diff changeset
   125
done
01fa0c8dbc92 conversion of many files to Isar format
paulson
parents: 9548
diff changeset
   126
01fa0c8dbc92 conversion of many files to Isar format
paulson
parents: 9548
diff changeset
   127
01fa0c8dbc92 conversion of many files to Isar format
paulson
parents: 9548
diff changeset
   128
lemma mod_geq: "[| n le m;  m:nat |] ==> m mod n = (m#-n) mod n"
01fa0c8dbc92 conversion of many files to Isar format
paulson
parents: 9548
diff changeset
   129
apply (frule lt_nat_in_nat, erule nat_succI)
01fa0c8dbc92 conversion of many files to Isar format
paulson
parents: 9548
diff changeset
   130
apply (case_tac "n=0")
01fa0c8dbc92 conversion of many files to Isar format
paulson
parents: 9548
diff changeset
   131
 apply (simp add: DIVISION_BY_ZERO_MOD)
01fa0c8dbc92 conversion of many files to Isar format
paulson
parents: 9548
diff changeset
   132
apply (simp add: mod_def raw_mod_geq nat_into_Ord [THEN Ord_0_lt_iff])
01fa0c8dbc92 conversion of many files to Isar format
paulson
parents: 9548
diff changeset
   133
done
01fa0c8dbc92 conversion of many files to Isar format
paulson
parents: 9548
diff changeset
   134
01fa0c8dbc92 conversion of many files to Isar format
paulson
parents: 9548
diff changeset
   135
13356
c9cfe1638bf2 improved presentation markup
paulson
parents: 13328
diff changeset
   136
subsection{*Division*}
13259
01fa0c8dbc92 conversion of many files to Isar format
paulson
parents: 9548
diff changeset
   137
01fa0c8dbc92 conversion of many files to Isar format
paulson
parents: 9548
diff changeset
   138
lemma raw_div_type: "[| m:nat;  n:nat |] ==> raw_div (m, n) : nat"
01fa0c8dbc92 conversion of many files to Isar format
paulson
parents: 9548
diff changeset
   139
apply (unfold raw_div_def)
01fa0c8dbc92 conversion of many files to Isar format
paulson
parents: 9548
diff changeset
   140
apply (rule Ord_transrec_type)
01fa0c8dbc92 conversion of many files to Isar format
paulson
parents: 9548
diff changeset
   141
apply (auto simp add: nat_into_Ord [THEN Ord_0_lt_iff])
01fa0c8dbc92 conversion of many files to Isar format
paulson
parents: 9548
diff changeset
   142
apply (blast intro: div_rls) 
01fa0c8dbc92 conversion of many files to Isar format
paulson
parents: 9548
diff changeset
   143
done
01fa0c8dbc92 conversion of many files to Isar format
paulson
parents: 9548
diff changeset
   144
01fa0c8dbc92 conversion of many files to Isar format
paulson
parents: 9548
diff changeset
   145
lemma div_type [TC,iff]: "m div n : nat"
01fa0c8dbc92 conversion of many files to Isar format
paulson
parents: 9548
diff changeset
   146
apply (unfold div_def)
01fa0c8dbc92 conversion of many files to Isar format
paulson
parents: 9548
diff changeset
   147
apply (simp (no_asm) add: div_def raw_div_type)
01fa0c8dbc92 conversion of many files to Isar format
paulson
parents: 9548
diff changeset
   148
done
01fa0c8dbc92 conversion of many files to Isar format
paulson
parents: 9548
diff changeset
   149
01fa0c8dbc92 conversion of many files to Isar format
paulson
parents: 9548
diff changeset
   150
lemma raw_div_less: "m<n ==> raw_div (m,n) = 0"
01fa0c8dbc92 conversion of many files to Isar format
paulson
parents: 9548
diff changeset
   151
apply (rule raw_div_def [THEN def_transrec, THEN trans])
01fa0c8dbc92 conversion of many files to Isar format
paulson
parents: 9548
diff changeset
   152
apply (simp (no_asm_simp) add: div_termination [THEN ltD])
01fa0c8dbc92 conversion of many files to Isar format
paulson
parents: 9548
diff changeset
   153
done
01fa0c8dbc92 conversion of many files to Isar format
paulson
parents: 9548
diff changeset
   154
01fa0c8dbc92 conversion of many files to Isar format
paulson
parents: 9548
diff changeset
   155
lemma div_less [simp]: "[| m<n; n : nat |] ==> m div n = 0"
01fa0c8dbc92 conversion of many files to Isar format
paulson
parents: 9548
diff changeset
   156
apply (frule lt_nat_in_nat, assumption)
01fa0c8dbc92 conversion of many files to Isar format
paulson
parents: 9548
diff changeset
   157
apply (simp (no_asm_simp) add: div_def raw_div_less)
01fa0c8dbc92 conversion of many files to Isar format
paulson
parents: 9548
diff changeset
   158
done
01fa0c8dbc92 conversion of many files to Isar format
paulson
parents: 9548
diff changeset
   159
01fa0c8dbc92 conversion of many files to Isar format
paulson
parents: 9548
diff changeset
   160
lemma raw_div_geq: "[| 0<n;  n le m;  m:nat |] ==> raw_div(m,n) = succ(raw_div(m#-n, n))"
01fa0c8dbc92 conversion of many files to Isar format
paulson
parents: 9548
diff changeset
   161
apply (subgoal_tac "n ~= 0")
01fa0c8dbc92 conversion of many files to Isar format
paulson
parents: 9548
diff changeset
   162
prefer 2 apply blast
01fa0c8dbc92 conversion of many files to Isar format
paulson
parents: 9548
diff changeset
   163
apply (frule lt_nat_in_nat, erule nat_succI)
01fa0c8dbc92 conversion of many files to Isar format
paulson
parents: 9548
diff changeset
   164
apply (rule raw_div_def [THEN def_transrec, THEN trans])
13611
2edf034c902a Adapted to new simplifier.
berghofe
parents: 13356
diff changeset
   165
apply (simp (no_asm_simp) add: div_termination [THEN ltD] not_lt_iff_le [THEN iffD2] ) 
13259
01fa0c8dbc92 conversion of many files to Isar format
paulson
parents: 9548
diff changeset
   166
done
01fa0c8dbc92 conversion of many files to Isar format
paulson
parents: 9548
diff changeset
   167
01fa0c8dbc92 conversion of many files to Isar format
paulson
parents: 9548
diff changeset
   168
lemma div_geq [simp]:
01fa0c8dbc92 conversion of many files to Isar format
paulson
parents: 9548
diff changeset
   169
     "[| 0<n;  n le m;  m:nat |] ==> m div n = succ ((m#-n) div n)"
01fa0c8dbc92 conversion of many files to Isar format
paulson
parents: 9548
diff changeset
   170
apply (frule lt_nat_in_nat, erule nat_succI)
01fa0c8dbc92 conversion of many files to Isar format
paulson
parents: 9548
diff changeset
   171
apply (simp (no_asm_simp) add: div_def raw_div_geq)
01fa0c8dbc92 conversion of many files to Isar format
paulson
parents: 9548
diff changeset
   172
done
01fa0c8dbc92 conversion of many files to Isar format
paulson
parents: 9548
diff changeset
   173
01fa0c8dbc92 conversion of many files to Isar format
paulson
parents: 9548
diff changeset
   174
declare div_less [simp] div_geq [simp]
01fa0c8dbc92 conversion of many files to Isar format
paulson
parents: 9548
diff changeset
   175
01fa0c8dbc92 conversion of many files to Isar format
paulson
parents: 9548
diff changeset
   176
01fa0c8dbc92 conversion of many files to Isar format
paulson
parents: 9548
diff changeset
   177
(*A key result*)
01fa0c8dbc92 conversion of many files to Isar format
paulson
parents: 9548
diff changeset
   178
lemma mod_div_lemma: "[| m: nat;  n: nat |] ==> (m div n)#*n #+ m mod n = m"
01fa0c8dbc92 conversion of many files to Isar format
paulson
parents: 9548
diff changeset
   179
apply (case_tac "n=0")
01fa0c8dbc92 conversion of many files to Isar format
paulson
parents: 9548
diff changeset
   180
 apply (simp add: DIVISION_BY_ZERO_MOD)
01fa0c8dbc92 conversion of many files to Isar format
paulson
parents: 9548
diff changeset
   181
apply (simp add: nat_into_Ord [THEN Ord_0_lt_iff])
01fa0c8dbc92 conversion of many files to Isar format
paulson
parents: 9548
diff changeset
   182
apply (erule complete_induct)
01fa0c8dbc92 conversion of many files to Isar format
paulson
parents: 9548
diff changeset
   183
apply (case_tac "x<n")
01fa0c8dbc92 conversion of many files to Isar format
paulson
parents: 9548
diff changeset
   184
txt{*case x<n*}
01fa0c8dbc92 conversion of many files to Isar format
paulson
parents: 9548
diff changeset
   185
apply (simp (no_asm_simp))
01fa0c8dbc92 conversion of many files to Isar format
paulson
parents: 9548
diff changeset
   186
txt{*case n le x*}
01fa0c8dbc92 conversion of many files to Isar format
paulson
parents: 9548
diff changeset
   187
apply (simp add: not_lt_iff_le add_assoc mod_geq div_termination [THEN ltD] add_diff_inverse)
01fa0c8dbc92 conversion of many files to Isar format
paulson
parents: 9548
diff changeset
   188
done
01fa0c8dbc92 conversion of many files to Isar format
paulson
parents: 9548
diff changeset
   189
01fa0c8dbc92 conversion of many files to Isar format
paulson
parents: 9548
diff changeset
   190
lemma mod_div_equality_natify: "(m div n)#*n #+ m mod n = natify(m)"
01fa0c8dbc92 conversion of many files to Isar format
paulson
parents: 9548
diff changeset
   191
apply (subgoal_tac " (natify (m) div natify (n))#*natify (n) #+ natify (m) mod natify (n) = natify (m) ")
01fa0c8dbc92 conversion of many files to Isar format
paulson
parents: 9548
diff changeset
   192
apply force 
01fa0c8dbc92 conversion of many files to Isar format
paulson
parents: 9548
diff changeset
   193
apply (subst mod_div_lemma, auto)
01fa0c8dbc92 conversion of many files to Isar format
paulson
parents: 9548
diff changeset
   194
done
01fa0c8dbc92 conversion of many files to Isar format
paulson
parents: 9548
diff changeset
   195
01fa0c8dbc92 conversion of many files to Isar format
paulson
parents: 9548
diff changeset
   196
lemma mod_div_equality: "m: nat ==> (m div n)#*n #+ m mod n = m"
01fa0c8dbc92 conversion of many files to Isar format
paulson
parents: 9548
diff changeset
   197
apply (simp (no_asm_simp) add: mod_div_equality_natify)
01fa0c8dbc92 conversion of many files to Isar format
paulson
parents: 9548
diff changeset
   198
done
01fa0c8dbc92 conversion of many files to Isar format
paulson
parents: 9548
diff changeset
   199
01fa0c8dbc92 conversion of many files to Isar format
paulson
parents: 9548
diff changeset
   200
13356
c9cfe1638bf2 improved presentation markup
paulson
parents: 13328
diff changeset
   201
subsection{*Further Facts about Remainder*}
c9cfe1638bf2 improved presentation markup
paulson
parents: 13328
diff changeset
   202
c9cfe1638bf2 improved presentation markup
paulson
parents: 13328
diff changeset
   203
text{*(mainly for mutilated chess board)*}
13259
01fa0c8dbc92 conversion of many files to Isar format
paulson
parents: 9548
diff changeset
   204
01fa0c8dbc92 conversion of many files to Isar format
paulson
parents: 9548
diff changeset
   205
lemma mod_succ_lemma:
01fa0c8dbc92 conversion of many files to Isar format
paulson
parents: 9548
diff changeset
   206
     "[| 0<n;  m:nat;  n:nat |]  
01fa0c8dbc92 conversion of many files to Isar format
paulson
parents: 9548
diff changeset
   207
      ==> succ(m) mod n = (if succ(m mod n) = n then 0 else succ(m mod n))"
01fa0c8dbc92 conversion of many files to Isar format
paulson
parents: 9548
diff changeset
   208
apply (erule complete_induct)
01fa0c8dbc92 conversion of many files to Isar format
paulson
parents: 9548
diff changeset
   209
apply (case_tac "succ (x) <n")
01fa0c8dbc92 conversion of many files to Isar format
paulson
parents: 9548
diff changeset
   210
txt{* case succ(x) < n *}
01fa0c8dbc92 conversion of many files to Isar format
paulson
parents: 9548
diff changeset
   211
 apply (simp (no_asm_simp) add: nat_le_refl [THEN lt_trans] succ_neq_self)
01fa0c8dbc92 conversion of many files to Isar format
paulson
parents: 9548
diff changeset
   212
 apply (simp add: ltD [THEN mem_imp_not_eq])
01fa0c8dbc92 conversion of many files to Isar format
paulson
parents: 9548
diff changeset
   213
txt{* case n le succ(x) *}
01fa0c8dbc92 conversion of many files to Isar format
paulson
parents: 9548
diff changeset
   214
apply (simp add: mod_geq not_lt_iff_le)
01fa0c8dbc92 conversion of many files to Isar format
paulson
parents: 9548
diff changeset
   215
apply (erule leE)
01fa0c8dbc92 conversion of many files to Isar format
paulson
parents: 9548
diff changeset
   216
 apply (simp (no_asm_simp) add: mod_geq div_termination [THEN ltD] diff_succ)
01fa0c8dbc92 conversion of many files to Isar format
paulson
parents: 9548
diff changeset
   217
txt{*equality case*}
01fa0c8dbc92 conversion of many files to Isar format
paulson
parents: 9548
diff changeset
   218
apply (simp add: diff_self_eq_0)
01fa0c8dbc92 conversion of many files to Isar format
paulson
parents: 9548
diff changeset
   219
done
01fa0c8dbc92 conversion of many files to Isar format
paulson
parents: 9548
diff changeset
   220
01fa0c8dbc92 conversion of many files to Isar format
paulson
parents: 9548
diff changeset
   221
lemma mod_succ:
01fa0c8dbc92 conversion of many files to Isar format
paulson
parents: 9548
diff changeset
   222
  "n:nat ==> succ(m) mod n = (if succ(m mod n) = n then 0 else succ(m mod n))"
01fa0c8dbc92 conversion of many files to Isar format
paulson
parents: 9548
diff changeset
   223
apply (case_tac "n=0")
01fa0c8dbc92 conversion of many files to Isar format
paulson
parents: 9548
diff changeset
   224
 apply (simp (no_asm_simp) add: natify_succ DIVISION_BY_ZERO_MOD)
01fa0c8dbc92 conversion of many files to Isar format
paulson
parents: 9548
diff changeset
   225
apply (subgoal_tac "natify (succ (m)) mod n = (if succ (natify (m) mod n) = n then 0 else succ (natify (m) mod n))")
01fa0c8dbc92 conversion of many files to Isar format
paulson
parents: 9548
diff changeset
   226
 prefer 2
01fa0c8dbc92 conversion of many files to Isar format
paulson
parents: 9548
diff changeset
   227
 apply (subst natify_succ)
01fa0c8dbc92 conversion of many files to Isar format
paulson
parents: 9548
diff changeset
   228
 apply (rule mod_succ_lemma)
01fa0c8dbc92 conversion of many files to Isar format
paulson
parents: 9548
diff changeset
   229
  apply (auto simp del: natify_succ simp add: nat_into_Ord [THEN Ord_0_lt_iff])
01fa0c8dbc92 conversion of many files to Isar format
paulson
parents: 9548
diff changeset
   230
done
01fa0c8dbc92 conversion of many files to Isar format
paulson
parents: 9548
diff changeset
   231
01fa0c8dbc92 conversion of many files to Isar format
paulson
parents: 9548
diff changeset
   232
lemma mod_less_divisor: "[| 0<n;  n:nat |] ==> m mod n < n"
01fa0c8dbc92 conversion of many files to Isar format
paulson
parents: 9548
diff changeset
   233
apply (subgoal_tac "natify (m) mod n < n")
01fa0c8dbc92 conversion of many files to Isar format
paulson
parents: 9548
diff changeset
   234
apply (rule_tac [2] i = "natify (m) " in complete_induct)
01fa0c8dbc92 conversion of many files to Isar format
paulson
parents: 9548
diff changeset
   235
apply (case_tac [3] "x<n", auto) 
01fa0c8dbc92 conversion of many files to Isar format
paulson
parents: 9548
diff changeset
   236
txt{* case n le x*}
01fa0c8dbc92 conversion of many files to Isar format
paulson
parents: 9548
diff changeset
   237
apply (simp add: mod_geq not_lt_iff_le div_termination [THEN ltD])
01fa0c8dbc92 conversion of many files to Isar format
paulson
parents: 9548
diff changeset
   238
done
01fa0c8dbc92 conversion of many files to Isar format
paulson
parents: 9548
diff changeset
   239
01fa0c8dbc92 conversion of many files to Isar format
paulson
parents: 9548
diff changeset
   240
lemma mod_1_eq [simp]: "m mod 1 = 0"
13784
b9f6154427a4 tidying (by script)
paulson
parents: 13615
diff changeset
   241
by (cut_tac n = 1 in mod_less_divisor, auto)
13259
01fa0c8dbc92 conversion of many files to Isar format
paulson
parents: 9548
diff changeset
   242
01fa0c8dbc92 conversion of many files to Isar format
paulson
parents: 9548
diff changeset
   243
lemma mod2_cases: "b<2 ==> k mod 2 = b | k mod 2 = (if b=1 then 0 else 1)"
01fa0c8dbc92 conversion of many files to Isar format
paulson
parents: 9548
diff changeset
   244
apply (subgoal_tac "k mod 2: 2")
01fa0c8dbc92 conversion of many files to Isar format
paulson
parents: 9548
diff changeset
   245
 prefer 2 apply (simp add: mod_less_divisor [THEN ltD])
01fa0c8dbc92 conversion of many files to Isar format
paulson
parents: 9548
diff changeset
   246
apply (drule ltD, auto)
01fa0c8dbc92 conversion of many files to Isar format
paulson
parents: 9548
diff changeset
   247
done
01fa0c8dbc92 conversion of many files to Isar format
paulson
parents: 9548
diff changeset
   248
01fa0c8dbc92 conversion of many files to Isar format
paulson
parents: 9548
diff changeset
   249
lemma mod2_succ_succ [simp]: "succ(succ(m)) mod 2 = m mod 2"
01fa0c8dbc92 conversion of many files to Isar format
paulson
parents: 9548
diff changeset
   250
apply (subgoal_tac "m mod 2: 2")
01fa0c8dbc92 conversion of many files to Isar format
paulson
parents: 9548
diff changeset
   251
 prefer 2 apply (simp add: mod_less_divisor [THEN ltD])
01fa0c8dbc92 conversion of many files to Isar format
paulson
parents: 9548
diff changeset
   252
apply (auto simp add: mod_succ)
01fa0c8dbc92 conversion of many files to Isar format
paulson
parents: 9548
diff changeset
   253
done
01fa0c8dbc92 conversion of many files to Isar format
paulson
parents: 9548
diff changeset
   254
01fa0c8dbc92 conversion of many files to Isar format
paulson
parents: 9548
diff changeset
   255
lemma mod2_add_more [simp]: "(m#+m#+n) mod 2 = n mod 2"
01fa0c8dbc92 conversion of many files to Isar format
paulson
parents: 9548
diff changeset
   256
apply (subgoal_tac " (natify (m) #+natify (m) #+n) mod 2 = n mod 2")
01fa0c8dbc92 conversion of many files to Isar format
paulson
parents: 9548
diff changeset
   257
apply (rule_tac [2] n = "natify (m) " in nat_induct)
01fa0c8dbc92 conversion of many files to Isar format
paulson
parents: 9548
diff changeset
   258
apply auto
01fa0c8dbc92 conversion of many files to Isar format
paulson
parents: 9548
diff changeset
   259
done
01fa0c8dbc92 conversion of many files to Isar format
paulson
parents: 9548
diff changeset
   260
01fa0c8dbc92 conversion of many files to Isar format
paulson
parents: 9548
diff changeset
   261
lemma mod2_add_self [simp]: "(m#+m) mod 2 = 0"
13784
b9f6154427a4 tidying (by script)
paulson
parents: 13615
diff changeset
   262
by (cut_tac n = 0 in mod2_add_more, auto)
13259
01fa0c8dbc92 conversion of many files to Isar format
paulson
parents: 9548
diff changeset
   263
01fa0c8dbc92 conversion of many files to Isar format
paulson
parents: 9548
diff changeset
   264
13356
c9cfe1638bf2 improved presentation markup
paulson
parents: 13328
diff changeset
   265
subsection{*Additional theorems about @{text "\<le>"}*}
13259
01fa0c8dbc92 conversion of many files to Isar format
paulson
parents: 9548
diff changeset
   266
01fa0c8dbc92 conversion of many files to Isar format
paulson
parents: 9548
diff changeset
   267
lemma add_le_self: "m:nat ==> m le (m #+ n)"
01fa0c8dbc92 conversion of many files to Isar format
paulson
parents: 9548
diff changeset
   268
apply (simp (no_asm_simp))
01fa0c8dbc92 conversion of many files to Isar format
paulson
parents: 9548
diff changeset
   269
done
01fa0c8dbc92 conversion of many files to Isar format
paulson
parents: 9548
diff changeset
   270
01fa0c8dbc92 conversion of many files to Isar format
paulson
parents: 9548
diff changeset
   271
lemma add_le_self2: "m:nat ==> m le (n #+ m)"
01fa0c8dbc92 conversion of many files to Isar format
paulson
parents: 9548
diff changeset
   272
apply (simp (no_asm_simp))
01fa0c8dbc92 conversion of many files to Isar format
paulson
parents: 9548
diff changeset
   273
done
01fa0c8dbc92 conversion of many files to Isar format
paulson
parents: 9548
diff changeset
   274
01fa0c8dbc92 conversion of many files to Isar format
paulson
parents: 9548
diff changeset
   275
(*** Monotonicity of Multiplication ***)
01fa0c8dbc92 conversion of many files to Isar format
paulson
parents: 9548
diff changeset
   276
01fa0c8dbc92 conversion of many files to Isar format
paulson
parents: 9548
diff changeset
   277
lemma mult_le_mono1: "[| i le j; j:nat |] ==> (i#*k) le (j#*k)"
01fa0c8dbc92 conversion of many files to Isar format
paulson
parents: 9548
diff changeset
   278
apply (subgoal_tac "natify (i) #*natify (k) le j#*natify (k) ")
01fa0c8dbc92 conversion of many files to Isar format
paulson
parents: 9548
diff changeset
   279
apply (frule_tac [2] lt_nat_in_nat)
01fa0c8dbc92 conversion of many files to Isar format
paulson
parents: 9548
diff changeset
   280
apply (rule_tac [3] n = "natify (k) " in nat_induct)
01fa0c8dbc92 conversion of many files to Isar format
paulson
parents: 9548
diff changeset
   281
apply (simp_all add: add_le_mono)
01fa0c8dbc92 conversion of many files to Isar format
paulson
parents: 9548
diff changeset
   282
done
01fa0c8dbc92 conversion of many files to Isar format
paulson
parents: 9548
diff changeset
   283
01fa0c8dbc92 conversion of many files to Isar format
paulson
parents: 9548
diff changeset
   284
(* le monotonicity, BOTH arguments*)
01fa0c8dbc92 conversion of many files to Isar format
paulson
parents: 9548
diff changeset
   285
lemma mult_le_mono: "[| i le j; k le l; j:nat; l:nat |] ==> i#*k le j#*l"
01fa0c8dbc92 conversion of many files to Isar format
paulson
parents: 9548
diff changeset
   286
apply (rule mult_le_mono1 [THEN le_trans], assumption+)
01fa0c8dbc92 conversion of many files to Isar format
paulson
parents: 9548
diff changeset
   287
apply (subst mult_commute, subst mult_commute, rule mult_le_mono1, assumption+)
01fa0c8dbc92 conversion of many files to Isar format
paulson
parents: 9548
diff changeset
   288
done
01fa0c8dbc92 conversion of many files to Isar format
paulson
parents: 9548
diff changeset
   289
01fa0c8dbc92 conversion of many files to Isar format
paulson
parents: 9548
diff changeset
   290
(*strict, in 1st argument; proof is by induction on k>0.
01fa0c8dbc92 conversion of many files to Isar format
paulson
parents: 9548
diff changeset
   291
  I can't see how to relax the typing conditions.*)
01fa0c8dbc92 conversion of many files to Isar format
paulson
parents: 9548
diff changeset
   292
lemma mult_lt_mono2: "[| i<j; 0<k; j:nat; k:nat |] ==> k#*i < k#*j"
01fa0c8dbc92 conversion of many files to Isar format
paulson
parents: 9548
diff changeset
   293
apply (erule zero_lt_natE)
01fa0c8dbc92 conversion of many files to Isar format
paulson
parents: 9548
diff changeset
   294
apply (frule_tac [2] lt_nat_in_nat)
01fa0c8dbc92 conversion of many files to Isar format
paulson
parents: 9548
diff changeset
   295
apply (simp_all (no_asm_simp))
01fa0c8dbc92 conversion of many files to Isar format
paulson
parents: 9548
diff changeset
   296
apply (induct_tac "x")
01fa0c8dbc92 conversion of many files to Isar format
paulson
parents: 9548
diff changeset
   297
apply (simp_all (no_asm_simp) add: add_lt_mono)
01fa0c8dbc92 conversion of many files to Isar format
paulson
parents: 9548
diff changeset
   298
done
01fa0c8dbc92 conversion of many files to Isar format
paulson
parents: 9548
diff changeset
   299
01fa0c8dbc92 conversion of many files to Isar format
paulson
parents: 9548
diff changeset
   300
lemma mult_lt_mono1: "[| i<j; 0<k; j:nat; k:nat |] ==> i#*k < j#*k"
01fa0c8dbc92 conversion of many files to Isar format
paulson
parents: 9548
diff changeset
   301
apply (simp (no_asm_simp) add: mult_lt_mono2 mult_commute [of _ k])
01fa0c8dbc92 conversion of many files to Isar format
paulson
parents: 9548
diff changeset
   302
done
01fa0c8dbc92 conversion of many files to Isar format
paulson
parents: 9548
diff changeset
   303
01fa0c8dbc92 conversion of many files to Isar format
paulson
parents: 9548
diff changeset
   304
lemma add_eq_0_iff [iff]: "m#+n = 0 <-> natify(m)=0 & natify(n)=0"
01fa0c8dbc92 conversion of many files to Isar format
paulson
parents: 9548
diff changeset
   305
apply (subgoal_tac "natify (m) #+ natify (n) = 0 <-> natify (m) =0 & natify (n) =0")
01fa0c8dbc92 conversion of many files to Isar format
paulson
parents: 9548
diff changeset
   306
apply (rule_tac [2] n = "natify (m) " in natE)
01fa0c8dbc92 conversion of many files to Isar format
paulson
parents: 9548
diff changeset
   307
 apply (rule_tac [4] n = "natify (n) " in natE)
01fa0c8dbc92 conversion of many files to Isar format
paulson
parents: 9548
diff changeset
   308
apply auto
01fa0c8dbc92 conversion of many files to Isar format
paulson
parents: 9548
diff changeset
   309
done
01fa0c8dbc92 conversion of many files to Isar format
paulson
parents: 9548
diff changeset
   310
01fa0c8dbc92 conversion of many files to Isar format
paulson
parents: 9548
diff changeset
   311
lemma zero_lt_mult_iff [iff]: "0 < m#*n <-> 0 < natify(m) & 0 < natify(n)"
01fa0c8dbc92 conversion of many files to Isar format
paulson
parents: 9548
diff changeset
   312
apply (subgoal_tac "0 < natify (m) #*natify (n) <-> 0 < natify (m) & 0 < natify (n) ")
01fa0c8dbc92 conversion of many files to Isar format
paulson
parents: 9548
diff changeset
   313
apply (rule_tac [2] n = "natify (m) " in natE)
01fa0c8dbc92 conversion of many files to Isar format
paulson
parents: 9548
diff changeset
   314
 apply (rule_tac [4] n = "natify (n) " in natE)
01fa0c8dbc92 conversion of many files to Isar format
paulson
parents: 9548
diff changeset
   315
  apply (rule_tac [3] n = "natify (n) " in natE)
01fa0c8dbc92 conversion of many files to Isar format
paulson
parents: 9548
diff changeset
   316
apply auto
01fa0c8dbc92 conversion of many files to Isar format
paulson
parents: 9548
diff changeset
   317
done
01fa0c8dbc92 conversion of many files to Isar format
paulson
parents: 9548
diff changeset
   318
01fa0c8dbc92 conversion of many files to Isar format
paulson
parents: 9548
diff changeset
   319
lemma mult_eq_1_iff [iff]: "m#*n = 1 <-> natify(m)=1 & natify(n)=1"
01fa0c8dbc92 conversion of many files to Isar format
paulson
parents: 9548
diff changeset
   320
apply (subgoal_tac "natify (m) #* natify (n) = 1 <-> natify (m) =1 & natify (n) =1")
01fa0c8dbc92 conversion of many files to Isar format
paulson
parents: 9548
diff changeset
   321
apply (rule_tac [2] n = "natify (m) " in natE)
01fa0c8dbc92 conversion of many files to Isar format
paulson
parents: 9548
diff changeset
   322
 apply (rule_tac [4] n = "natify (n) " in natE)
01fa0c8dbc92 conversion of many files to Isar format
paulson
parents: 9548
diff changeset
   323
apply auto
01fa0c8dbc92 conversion of many files to Isar format
paulson
parents: 9548
diff changeset
   324
done
01fa0c8dbc92 conversion of many files to Isar format
paulson
parents: 9548
diff changeset
   325
01fa0c8dbc92 conversion of many files to Isar format
paulson
parents: 9548
diff changeset
   326
01fa0c8dbc92 conversion of many files to Isar format
paulson
parents: 9548
diff changeset
   327
lemma mult_is_zero: "[|m: nat; n: nat|] ==> (m #* n = 0) <-> (m = 0 | n = 0)"
01fa0c8dbc92 conversion of many files to Isar format
paulson
parents: 9548
diff changeset
   328
apply auto
01fa0c8dbc92 conversion of many files to Isar format
paulson
parents: 9548
diff changeset
   329
apply (erule natE)
01fa0c8dbc92 conversion of many files to Isar format
paulson
parents: 9548
diff changeset
   330
apply (erule_tac [2] natE, auto)
01fa0c8dbc92 conversion of many files to Isar format
paulson
parents: 9548
diff changeset
   331
done
01fa0c8dbc92 conversion of many files to Isar format
paulson
parents: 9548
diff changeset
   332
01fa0c8dbc92 conversion of many files to Isar format
paulson
parents: 9548
diff changeset
   333
lemma mult_is_zero_natify [iff]:
01fa0c8dbc92 conversion of many files to Isar format
paulson
parents: 9548
diff changeset
   334
     "(m #* n = 0) <-> (natify(m) = 0 | natify(n) = 0)"
01fa0c8dbc92 conversion of many files to Isar format
paulson
parents: 9548
diff changeset
   335
apply (cut_tac m = "natify (m) " and n = "natify (n) " in mult_is_zero)
01fa0c8dbc92 conversion of many files to Isar format
paulson
parents: 9548
diff changeset
   336
apply auto
01fa0c8dbc92 conversion of many files to Isar format
paulson
parents: 9548
diff changeset
   337
done
01fa0c8dbc92 conversion of many files to Isar format
paulson
parents: 9548
diff changeset
   338
01fa0c8dbc92 conversion of many files to Isar format
paulson
parents: 9548
diff changeset
   339
13356
c9cfe1638bf2 improved presentation markup
paulson
parents: 13328
diff changeset
   340
subsection{*Cancellation Laws for Common Factors in Comparisons*}
13259
01fa0c8dbc92 conversion of many files to Isar format
paulson
parents: 9548
diff changeset
   341
01fa0c8dbc92 conversion of many files to Isar format
paulson
parents: 9548
diff changeset
   342
lemma mult_less_cancel_lemma:
01fa0c8dbc92 conversion of many files to Isar format
paulson
parents: 9548
diff changeset
   343
     "[| k: nat; m: nat; n: nat |] ==> (m#*k < n#*k) <-> (0<k & m<n)"
01fa0c8dbc92 conversion of many files to Isar format
paulson
parents: 9548
diff changeset
   344
apply (safe intro!: mult_lt_mono1)
01fa0c8dbc92 conversion of many files to Isar format
paulson
parents: 9548
diff changeset
   345
apply (erule natE, auto)
01fa0c8dbc92 conversion of many files to Isar format
paulson
parents: 9548
diff changeset
   346
apply (rule not_le_iff_lt [THEN iffD1])
01fa0c8dbc92 conversion of many files to Isar format
paulson
parents: 9548
diff changeset
   347
apply (drule_tac [3] not_le_iff_lt [THEN [2] rev_iffD2])
01fa0c8dbc92 conversion of many files to Isar format
paulson
parents: 9548
diff changeset
   348
prefer 5 apply (blast intro: mult_le_mono1, auto)
01fa0c8dbc92 conversion of many files to Isar format
paulson
parents: 9548
diff changeset
   349
done
01fa0c8dbc92 conversion of many files to Isar format
paulson
parents: 9548
diff changeset
   350
01fa0c8dbc92 conversion of many files to Isar format
paulson
parents: 9548
diff changeset
   351
lemma mult_less_cancel2 [simp]:
01fa0c8dbc92 conversion of many files to Isar format
paulson
parents: 9548
diff changeset
   352
     "(m#*k < n#*k) <-> (0 < natify(k) & natify(m) < natify(n))"
01fa0c8dbc92 conversion of many files to Isar format
paulson
parents: 9548
diff changeset
   353
apply (rule iff_trans)
01fa0c8dbc92 conversion of many files to Isar format
paulson
parents: 9548
diff changeset
   354
apply (rule_tac [2] mult_less_cancel_lemma, auto)
01fa0c8dbc92 conversion of many files to Isar format
paulson
parents: 9548
diff changeset
   355
done
01fa0c8dbc92 conversion of many files to Isar format
paulson
parents: 9548
diff changeset
   356
01fa0c8dbc92 conversion of many files to Isar format
paulson
parents: 9548
diff changeset
   357
lemma mult_less_cancel1 [simp]:
01fa0c8dbc92 conversion of many files to Isar format
paulson
parents: 9548
diff changeset
   358
     "(k#*m < k#*n) <-> (0 < natify(k) & natify(m) < natify(n))"
01fa0c8dbc92 conversion of many files to Isar format
paulson
parents: 9548
diff changeset
   359
apply (simp (no_asm) add: mult_less_cancel2 mult_commute [of k])
01fa0c8dbc92 conversion of many files to Isar format
paulson
parents: 9548
diff changeset
   360
done
01fa0c8dbc92 conversion of many files to Isar format
paulson
parents: 9548
diff changeset
   361
01fa0c8dbc92 conversion of many files to Isar format
paulson
parents: 9548
diff changeset
   362
lemma mult_le_cancel2 [simp]: "(m#*k le n#*k) <-> (0 < natify(k) --> natify(m) le natify(n))"
01fa0c8dbc92 conversion of many files to Isar format
paulson
parents: 9548
diff changeset
   363
apply (simp (no_asm_simp) add: not_lt_iff_le [THEN iff_sym])
01fa0c8dbc92 conversion of many files to Isar format
paulson
parents: 9548
diff changeset
   364
apply auto
01fa0c8dbc92 conversion of many files to Isar format
paulson
parents: 9548
diff changeset
   365
done
01fa0c8dbc92 conversion of many files to Isar format
paulson
parents: 9548
diff changeset
   366
01fa0c8dbc92 conversion of many files to Isar format
paulson
parents: 9548
diff changeset
   367
lemma mult_le_cancel1 [simp]: "(k#*m le k#*n) <-> (0 < natify(k) --> natify(m) le natify(n))"
01fa0c8dbc92 conversion of many files to Isar format
paulson
parents: 9548
diff changeset
   368
apply (simp (no_asm_simp) add: not_lt_iff_le [THEN iff_sym])
01fa0c8dbc92 conversion of many files to Isar format
paulson
parents: 9548
diff changeset
   369
apply auto
01fa0c8dbc92 conversion of many files to Isar format
paulson
parents: 9548
diff changeset
   370
done
01fa0c8dbc92 conversion of many files to Isar format
paulson
parents: 9548
diff changeset
   371
01fa0c8dbc92 conversion of many files to Isar format
paulson
parents: 9548
diff changeset
   372
lemma mult_le_cancel_le1: "k : nat ==> k #* m le k \<longleftrightarrow> (0 < k \<longrightarrow> natify(m) le 1)"
13784
b9f6154427a4 tidying (by script)
paulson
parents: 13615
diff changeset
   373
by (cut_tac k = k and m = m and n = 1 in mult_le_cancel1, auto)
13259
01fa0c8dbc92 conversion of many files to Isar format
paulson
parents: 9548
diff changeset
   374
01fa0c8dbc92 conversion of many files to Isar format
paulson
parents: 9548
diff changeset
   375
lemma Ord_eq_iff_le: "[| Ord(m); Ord(n) |] ==> m=n <-> (m le n & n le m)"
01fa0c8dbc92 conversion of many files to Isar format
paulson
parents: 9548
diff changeset
   376
by (blast intro: le_anti_sym)
01fa0c8dbc92 conversion of many files to Isar format
paulson
parents: 9548
diff changeset
   377
01fa0c8dbc92 conversion of many files to Isar format
paulson
parents: 9548
diff changeset
   378
lemma mult_cancel2_lemma:
01fa0c8dbc92 conversion of many files to Isar format
paulson
parents: 9548
diff changeset
   379
     "[| k: nat; m: nat; n: nat |] ==> (m#*k = n#*k) <-> (m=n | k=0)"
01fa0c8dbc92 conversion of many files to Isar format
paulson
parents: 9548
diff changeset
   380
apply (simp (no_asm_simp) add: Ord_eq_iff_le [of "m#*k"] Ord_eq_iff_le [of m])
01fa0c8dbc92 conversion of many files to Isar format
paulson
parents: 9548
diff changeset
   381
apply (auto simp add: Ord_0_lt_iff)
01fa0c8dbc92 conversion of many files to Isar format
paulson
parents: 9548
diff changeset
   382
done
01fa0c8dbc92 conversion of many files to Isar format
paulson
parents: 9548
diff changeset
   383
01fa0c8dbc92 conversion of many files to Isar format
paulson
parents: 9548
diff changeset
   384
lemma mult_cancel2 [simp]:
01fa0c8dbc92 conversion of many files to Isar format
paulson
parents: 9548
diff changeset
   385
     "(m#*k = n#*k) <-> (natify(m) = natify(n) | natify(k) = 0)"
01fa0c8dbc92 conversion of many files to Isar format
paulson
parents: 9548
diff changeset
   386
apply (rule iff_trans)
01fa0c8dbc92 conversion of many files to Isar format
paulson
parents: 9548
diff changeset
   387
apply (rule_tac [2] mult_cancel2_lemma, auto)
01fa0c8dbc92 conversion of many files to Isar format
paulson
parents: 9548
diff changeset
   388
done
01fa0c8dbc92 conversion of many files to Isar format
paulson
parents: 9548
diff changeset
   389
01fa0c8dbc92 conversion of many files to Isar format
paulson
parents: 9548
diff changeset
   390
lemma mult_cancel1 [simp]:
01fa0c8dbc92 conversion of many files to Isar format
paulson
parents: 9548
diff changeset
   391
     "(k#*m = k#*n) <-> (natify(m) = natify(n) | natify(k) = 0)"
01fa0c8dbc92 conversion of many files to Isar format
paulson
parents: 9548
diff changeset
   392
apply (simp (no_asm) add: mult_cancel2 mult_commute [of k])
01fa0c8dbc92 conversion of many files to Isar format
paulson
parents: 9548
diff changeset
   393
done
01fa0c8dbc92 conversion of many files to Isar format
paulson
parents: 9548
diff changeset
   394
01fa0c8dbc92 conversion of many files to Isar format
paulson
parents: 9548
diff changeset
   395
01fa0c8dbc92 conversion of many files to Isar format
paulson
parents: 9548
diff changeset
   396
(** Cancellation law for division **)
01fa0c8dbc92 conversion of many files to Isar format
paulson
parents: 9548
diff changeset
   397
01fa0c8dbc92 conversion of many files to Isar format
paulson
parents: 9548
diff changeset
   398
lemma div_cancel_raw:
01fa0c8dbc92 conversion of many files to Isar format
paulson
parents: 9548
diff changeset
   399
     "[| 0<n; 0<k; k:nat; m:nat; n:nat |] ==> (k#*m) div (k#*n) = m div n"
13784
b9f6154427a4 tidying (by script)
paulson
parents: 13615
diff changeset
   400
apply (erule_tac i = m in complete_induct)
13259
01fa0c8dbc92 conversion of many files to Isar format
paulson
parents: 9548
diff changeset
   401
apply (case_tac "x<n")
01fa0c8dbc92 conversion of many files to Isar format
paulson
parents: 9548
diff changeset
   402
 apply (simp add: div_less zero_lt_mult_iff mult_lt_mono2)
01fa0c8dbc92 conversion of many files to Isar format
paulson
parents: 9548
diff changeset
   403
apply (simp add: not_lt_iff_le zero_lt_mult_iff le_refl [THEN mult_le_mono]
01fa0c8dbc92 conversion of many files to Isar format
paulson
parents: 9548
diff changeset
   404
          div_geq diff_mult_distrib2 [symmetric] div_termination [THEN ltD])
01fa0c8dbc92 conversion of many files to Isar format
paulson
parents: 9548
diff changeset
   405
done
01fa0c8dbc92 conversion of many files to Isar format
paulson
parents: 9548
diff changeset
   406
01fa0c8dbc92 conversion of many files to Isar format
paulson
parents: 9548
diff changeset
   407
lemma div_cancel:
01fa0c8dbc92 conversion of many files to Isar format
paulson
parents: 9548
diff changeset
   408
     "[| 0 < natify(n);  0 < natify(k) |] ==> (k#*m) div (k#*n) = m div n"
01fa0c8dbc92 conversion of many files to Isar format
paulson
parents: 9548
diff changeset
   409
apply (cut_tac k = "natify (k) " and m = "natify (m)" and n = "natify (n)" 
01fa0c8dbc92 conversion of many files to Isar format
paulson
parents: 9548
diff changeset
   410
       in div_cancel_raw)
01fa0c8dbc92 conversion of many files to Isar format
paulson
parents: 9548
diff changeset
   411
apply auto
01fa0c8dbc92 conversion of many files to Isar format
paulson
parents: 9548
diff changeset
   412
done
01fa0c8dbc92 conversion of many files to Isar format
paulson
parents: 9548
diff changeset
   413
01fa0c8dbc92 conversion of many files to Isar format
paulson
parents: 9548
diff changeset
   414
13356
c9cfe1638bf2 improved presentation markup
paulson
parents: 13328
diff changeset
   415
subsection{*More Lemmas about Remainder*}
13259
01fa0c8dbc92 conversion of many files to Isar format
paulson
parents: 9548
diff changeset
   416
01fa0c8dbc92 conversion of many files to Isar format
paulson
parents: 9548
diff changeset
   417
lemma mult_mod_distrib_raw:
01fa0c8dbc92 conversion of many files to Isar format
paulson
parents: 9548
diff changeset
   418
     "[| k:nat; m:nat; n:nat |] ==> (k#*m) mod (k#*n) = k #* (m mod n)"
01fa0c8dbc92 conversion of many files to Isar format
paulson
parents: 9548
diff changeset
   419
apply (case_tac "k=0")
01fa0c8dbc92 conversion of many files to Isar format
paulson
parents: 9548
diff changeset
   420
 apply (simp add: DIVISION_BY_ZERO_MOD)
01fa0c8dbc92 conversion of many files to Isar format
paulson
parents: 9548
diff changeset
   421
apply (case_tac "n=0")
01fa0c8dbc92 conversion of many files to Isar format
paulson
parents: 9548
diff changeset
   422
 apply (simp add: DIVISION_BY_ZERO_MOD)
01fa0c8dbc92 conversion of many files to Isar format
paulson
parents: 9548
diff changeset
   423
apply (simp add: nat_into_Ord [THEN Ord_0_lt_iff])
13784
b9f6154427a4 tidying (by script)
paulson
parents: 13615
diff changeset
   424
apply (erule_tac i = m in complete_induct)
13259
01fa0c8dbc92 conversion of many files to Isar format
paulson
parents: 9548
diff changeset
   425
apply (case_tac "x<n")
01fa0c8dbc92 conversion of many files to Isar format
paulson
parents: 9548
diff changeset
   426
 apply (simp (no_asm_simp) add: mod_less zero_lt_mult_iff mult_lt_mono2)
01fa0c8dbc92 conversion of many files to Isar format
paulson
parents: 9548
diff changeset
   427
apply (simp add: not_lt_iff_le zero_lt_mult_iff le_refl [THEN mult_le_mono] 
01fa0c8dbc92 conversion of many files to Isar format
paulson
parents: 9548
diff changeset
   428
         mod_geq diff_mult_distrib2 [symmetric] div_termination [THEN ltD])
01fa0c8dbc92 conversion of many files to Isar format
paulson
parents: 9548
diff changeset
   429
done
01fa0c8dbc92 conversion of many files to Isar format
paulson
parents: 9548
diff changeset
   430
01fa0c8dbc92 conversion of many files to Isar format
paulson
parents: 9548
diff changeset
   431
lemma mod_mult_distrib2: "k #* (m mod n) = (k#*m) mod (k#*n)"
01fa0c8dbc92 conversion of many files to Isar format
paulson
parents: 9548
diff changeset
   432
apply (cut_tac k = "natify (k) " and m = "natify (m)" and n = "natify (n)" 
01fa0c8dbc92 conversion of many files to Isar format
paulson
parents: 9548
diff changeset
   433
       in mult_mod_distrib_raw)
01fa0c8dbc92 conversion of many files to Isar format
paulson
parents: 9548
diff changeset
   434
apply auto
01fa0c8dbc92 conversion of many files to Isar format
paulson
parents: 9548
diff changeset
   435
done
01fa0c8dbc92 conversion of many files to Isar format
paulson
parents: 9548
diff changeset
   436
01fa0c8dbc92 conversion of many files to Isar format
paulson
parents: 9548
diff changeset
   437
lemma mult_mod_distrib: "(m mod n) #* k = (m#*k) mod (n#*k)"
01fa0c8dbc92 conversion of many files to Isar format
paulson
parents: 9548
diff changeset
   438
apply (simp (no_asm) add: mult_commute mod_mult_distrib2)
01fa0c8dbc92 conversion of many files to Isar format
paulson
parents: 9548
diff changeset
   439
done
01fa0c8dbc92 conversion of many files to Isar format
paulson
parents: 9548
diff changeset
   440
01fa0c8dbc92 conversion of many files to Isar format
paulson
parents: 9548
diff changeset
   441
lemma mod_add_self2_raw: "n \<in> nat ==> (m #+ n) mod n = m mod n"
01fa0c8dbc92 conversion of many files to Isar format
paulson
parents: 9548
diff changeset
   442
apply (subgoal_tac " (n #+ m) mod n = (n #+ m #- n) mod n")
01fa0c8dbc92 conversion of many files to Isar format
paulson
parents: 9548
diff changeset
   443
apply (simp add: add_commute) 
01fa0c8dbc92 conversion of many files to Isar format
paulson
parents: 9548
diff changeset
   444
apply (subst mod_geq [symmetric], auto) 
01fa0c8dbc92 conversion of many files to Isar format
paulson
parents: 9548
diff changeset
   445
done
01fa0c8dbc92 conversion of many files to Isar format
paulson
parents: 9548
diff changeset
   446
01fa0c8dbc92 conversion of many files to Isar format
paulson
parents: 9548
diff changeset
   447
lemma mod_add_self2 [simp]: "(m #+ n) mod n = m mod n"
01fa0c8dbc92 conversion of many files to Isar format
paulson
parents: 9548
diff changeset
   448
apply (cut_tac n = "natify (n) " in mod_add_self2_raw)
01fa0c8dbc92 conversion of many files to Isar format
paulson
parents: 9548
diff changeset
   449
apply auto
01fa0c8dbc92 conversion of many files to Isar format
paulson
parents: 9548
diff changeset
   450
done
01fa0c8dbc92 conversion of many files to Isar format
paulson
parents: 9548
diff changeset
   451
01fa0c8dbc92 conversion of many files to Isar format
paulson
parents: 9548
diff changeset
   452
lemma mod_add_self1 [simp]: "(n#+m) mod n = m mod n"
01fa0c8dbc92 conversion of many files to Isar format
paulson
parents: 9548
diff changeset
   453
apply (simp (no_asm_simp) add: add_commute mod_add_self2)
01fa0c8dbc92 conversion of many files to Isar format
paulson
parents: 9548
diff changeset
   454
done
01fa0c8dbc92 conversion of many files to Isar format
paulson
parents: 9548
diff changeset
   455
01fa0c8dbc92 conversion of many files to Isar format
paulson
parents: 9548
diff changeset
   456
lemma mod_mult_self1_raw: "k \<in> nat ==> (m #+ k#*n) mod n = m mod n"
01fa0c8dbc92 conversion of many files to Isar format
paulson
parents: 9548
diff changeset
   457
apply (erule nat_induct)
01fa0c8dbc92 conversion of many files to Isar format
paulson
parents: 9548
diff changeset
   458
apply (simp_all (no_asm_simp) add: add_left_commute [of _ n])
01fa0c8dbc92 conversion of many files to Isar format
paulson
parents: 9548
diff changeset
   459
done
01fa0c8dbc92 conversion of many files to Isar format
paulson
parents: 9548
diff changeset
   460
01fa0c8dbc92 conversion of many files to Isar format
paulson
parents: 9548
diff changeset
   461
lemma mod_mult_self1 [simp]: "(m #+ k#*n) mod n = m mod n"
01fa0c8dbc92 conversion of many files to Isar format
paulson
parents: 9548
diff changeset
   462
apply (cut_tac k = "natify (k) " in mod_mult_self1_raw)
01fa0c8dbc92 conversion of many files to Isar format
paulson
parents: 9548
diff changeset
   463
apply auto
01fa0c8dbc92 conversion of many files to Isar format
paulson
parents: 9548
diff changeset
   464
done
01fa0c8dbc92 conversion of many files to Isar format
paulson
parents: 9548
diff changeset
   465
01fa0c8dbc92 conversion of many files to Isar format
paulson
parents: 9548
diff changeset
   466
lemma mod_mult_self2 [simp]: "(m #+ n#*k) mod n = m mod n"
01fa0c8dbc92 conversion of many files to Isar format
paulson
parents: 9548
diff changeset
   467
apply (simp (no_asm) add: mult_commute mod_mult_self1)
01fa0c8dbc92 conversion of many files to Isar format
paulson
parents: 9548
diff changeset
   468
done
01fa0c8dbc92 conversion of many files to Isar format
paulson
parents: 9548
diff changeset
   469
01fa0c8dbc92 conversion of many files to Isar format
paulson
parents: 9548
diff changeset
   470
(*Lemma for gcd*)
01fa0c8dbc92 conversion of many files to Isar format
paulson
parents: 9548
diff changeset
   471
lemma mult_eq_self_implies_10: "m = m#*n ==> natify(n)=1 | m=0"
01fa0c8dbc92 conversion of many files to Isar format
paulson
parents: 9548
diff changeset
   472
apply (subgoal_tac "m: nat")
01fa0c8dbc92 conversion of many files to Isar format
paulson
parents: 9548
diff changeset
   473
 prefer 2 
01fa0c8dbc92 conversion of many files to Isar format
paulson
parents: 9548
diff changeset
   474
 apply (erule ssubst)
01fa0c8dbc92 conversion of many files to Isar format
paulson
parents: 9548
diff changeset
   475
 apply simp  
01fa0c8dbc92 conversion of many files to Isar format
paulson
parents: 9548
diff changeset
   476
apply (rule disjCI)
01fa0c8dbc92 conversion of many files to Isar format
paulson
parents: 9548
diff changeset
   477
apply (drule sym)
01fa0c8dbc92 conversion of many files to Isar format
paulson
parents: 9548
diff changeset
   478
apply (rule Ord_linear_lt [of "natify(n)" 1])
01fa0c8dbc92 conversion of many files to Isar format
paulson
parents: 9548
diff changeset
   479
apply simp_all  
01fa0c8dbc92 conversion of many files to Isar format
paulson
parents: 9548
diff changeset
   480
 apply (subgoal_tac "m #* n = 0", simp) 
01fa0c8dbc92 conversion of many files to Isar format
paulson
parents: 9548
diff changeset
   481
 apply (subst mult_natify2 [symmetric])
01fa0c8dbc92 conversion of many files to Isar format
paulson
parents: 9548
diff changeset
   482
 apply (simp del: mult_natify2)
01fa0c8dbc92 conversion of many files to Isar format
paulson
parents: 9548
diff changeset
   483
apply (drule nat_into_Ord [THEN Ord_0_lt, THEN [2] mult_lt_mono2], auto)
01fa0c8dbc92 conversion of many files to Isar format
paulson
parents: 9548
diff changeset
   484
done
01fa0c8dbc92 conversion of many files to Isar format
paulson
parents: 9548
diff changeset
   485
01fa0c8dbc92 conversion of many files to Isar format
paulson
parents: 9548
diff changeset
   486
lemma less_imp_succ_add [rule_format]:
01fa0c8dbc92 conversion of many files to Isar format
paulson
parents: 9548
diff changeset
   487
     "[| m<n; n: nat |] ==> EX k: nat. n = succ(m#+k)"
01fa0c8dbc92 conversion of many files to Isar format
paulson
parents: 9548
diff changeset
   488
apply (frule lt_nat_in_nat, assumption)
01fa0c8dbc92 conversion of many files to Isar format
paulson
parents: 9548
diff changeset
   489
apply (erule rev_mp)
01fa0c8dbc92 conversion of many files to Isar format
paulson
parents: 9548
diff changeset
   490
apply (induct_tac "n")
01fa0c8dbc92 conversion of many files to Isar format
paulson
parents: 9548
diff changeset
   491
apply (simp_all (no_asm) add: le_iff)
01fa0c8dbc92 conversion of many files to Isar format
paulson
parents: 9548
diff changeset
   492
apply (blast elim!: leE intro!: add_0_right [symmetric] add_succ_right [symmetric])
01fa0c8dbc92 conversion of many files to Isar format
paulson
parents: 9548
diff changeset
   493
done
01fa0c8dbc92 conversion of many files to Isar format
paulson
parents: 9548
diff changeset
   494
01fa0c8dbc92 conversion of many files to Isar format
paulson
parents: 9548
diff changeset
   495
lemma less_iff_succ_add:
01fa0c8dbc92 conversion of many files to Isar format
paulson
parents: 9548
diff changeset
   496
     "[| m: nat; n: nat |] ==> (m<n) <-> (EX k: nat. n = succ(m#+k))"
01fa0c8dbc92 conversion of many files to Isar format
paulson
parents: 9548
diff changeset
   497
by (auto intro: less_imp_succ_add)
01fa0c8dbc92 conversion of many files to Isar format
paulson
parents: 9548
diff changeset
   498
14055
a3f592e3f4bd Further tweaks of ZF/UNITY
paulson
parents: 14046
diff changeset
   499
lemma add_lt_elim2:
a3f592e3f4bd Further tweaks of ZF/UNITY
paulson
parents: 14046
diff changeset
   500
     "\<lbrakk>a #+ d = b #+ c; a < b; b \<in> nat; c \<in> nat; d \<in> nat\<rbrakk> \<Longrightarrow> c < d"
a3f592e3f4bd Further tweaks of ZF/UNITY
paulson
parents: 14046
diff changeset
   501
by (drule less_imp_succ_add, auto) 
a3f592e3f4bd Further tweaks of ZF/UNITY
paulson
parents: 14046
diff changeset
   502
a3f592e3f4bd Further tweaks of ZF/UNITY
paulson
parents: 14046
diff changeset
   503
lemma add_le_elim2:
a3f592e3f4bd Further tweaks of ZF/UNITY
paulson
parents: 14046
diff changeset
   504
     "\<lbrakk>a #+ d = b #+ c; a le b; b \<in> nat; c \<in> nat; d \<in> nat\<rbrakk> \<Longrightarrow> c le d"
a3f592e3f4bd Further tweaks of ZF/UNITY
paulson
parents: 14046
diff changeset
   505
by (drule less_imp_succ_add, auto) 
a3f592e3f4bd Further tweaks of ZF/UNITY
paulson
parents: 14046
diff changeset
   506
13356
c9cfe1638bf2 improved presentation markup
paulson
parents: 13328
diff changeset
   507
c9cfe1638bf2 improved presentation markup
paulson
parents: 13328
diff changeset
   508
subsubsection{*More Lemmas About Difference*}
13259
01fa0c8dbc92 conversion of many files to Isar format
paulson
parents: 9548
diff changeset
   509
01fa0c8dbc92 conversion of many files to Isar format
paulson
parents: 9548
diff changeset
   510
lemma diff_is_0_lemma:
01fa0c8dbc92 conversion of many files to Isar format
paulson
parents: 9548
diff changeset
   511
     "[| m: nat; n: nat |] ==> m #- n = 0 <-> m le n"
13784
b9f6154427a4 tidying (by script)
paulson
parents: 13615
diff changeset
   512
apply (rule_tac m = m and n = n in diff_induct, simp_all)
13259
01fa0c8dbc92 conversion of many files to Isar format
paulson
parents: 9548
diff changeset
   513
done
01fa0c8dbc92 conversion of many files to Isar format
paulson
parents: 9548
diff changeset
   514
01fa0c8dbc92 conversion of many files to Isar format
paulson
parents: 9548
diff changeset
   515
lemma diff_is_0_iff: "m #- n = 0 <-> natify(m) le natify(n)"
01fa0c8dbc92 conversion of many files to Isar format
paulson
parents: 9548
diff changeset
   516
by (simp add: diff_is_0_lemma [symmetric])
01fa0c8dbc92 conversion of many files to Isar format
paulson
parents: 9548
diff changeset
   517
01fa0c8dbc92 conversion of many files to Isar format
paulson
parents: 9548
diff changeset
   518
lemma nat_lt_imp_diff_eq_0:
01fa0c8dbc92 conversion of many files to Isar format
paulson
parents: 9548
diff changeset
   519
     "[| a:nat; b:nat; a<b |] ==> a #- b = 0"
01fa0c8dbc92 conversion of many files to Isar format
paulson
parents: 9548
diff changeset
   520
by (simp add: diff_is_0_iff le_iff) 
01fa0c8dbc92 conversion of many files to Isar format
paulson
parents: 9548
diff changeset
   521
14055
a3f592e3f4bd Further tweaks of ZF/UNITY
paulson
parents: 14046
diff changeset
   522
lemma raw_nat_diff_split:
13259
01fa0c8dbc92 conversion of many files to Isar format
paulson
parents: 9548
diff changeset
   523
     "[| a:nat; b:nat |] ==>  
01fa0c8dbc92 conversion of many files to Isar format
paulson
parents: 9548
diff changeset
   524
      (P(a #- b)) <-> ((a < b -->P(0)) & (ALL d:nat. a = b #+ d --> P(d)))"
01fa0c8dbc92 conversion of many files to Isar format
paulson
parents: 9548
diff changeset
   525
apply (case_tac "a < b")
01fa0c8dbc92 conversion of many files to Isar format
paulson
parents: 9548
diff changeset
   526
 apply (force simp add: nat_lt_imp_diff_eq_0)
13784
b9f6154427a4 tidying (by script)
paulson
parents: 13615
diff changeset
   527
apply (rule iffI, force, simp) 
13259
01fa0c8dbc92 conversion of many files to Isar format
paulson
parents: 9548
diff changeset
   528
apply (drule_tac x="a#-b" in bspec)
01fa0c8dbc92 conversion of many files to Isar format
paulson
parents: 9548
diff changeset
   529
apply (simp_all add: Ordinal.not_lt_iff_le add_diff_inverse) 
01fa0c8dbc92 conversion of many files to Isar format
paulson
parents: 9548
diff changeset
   530
done
01fa0c8dbc92 conversion of many files to Isar format
paulson
parents: 9548
diff changeset
   531
14055
a3f592e3f4bd Further tweaks of ZF/UNITY
paulson
parents: 14046
diff changeset
   532
lemma nat_diff_split:
a3f592e3f4bd Further tweaks of ZF/UNITY
paulson
parents: 14046
diff changeset
   533
   "(P(a #- b)) <-> 
a3f592e3f4bd Further tweaks of ZF/UNITY
paulson
parents: 14046
diff changeset
   534
    (natify(a) < natify(b) -->P(0)) & (ALL d:nat. natify(a) = b #+ d --> P(d))"
a3f592e3f4bd Further tweaks of ZF/UNITY
paulson
parents: 14046
diff changeset
   535
apply (cut_tac P=P and a="natify(a)" and b="natify(b)" in raw_nat_diff_split)
a3f592e3f4bd Further tweaks of ZF/UNITY
paulson
parents: 14046
diff changeset
   536
apply simp_all
a3f592e3f4bd Further tweaks of ZF/UNITY
paulson
parents: 14046
diff changeset
   537
done
a3f592e3f4bd Further tweaks of ZF/UNITY
paulson
parents: 14046
diff changeset
   538
14060
c0c4af41fa3b Adding the theory UNITY/AllocImpl.thy, with supporting lemmas
paulson
parents: 14055
diff changeset
   539
text{*Difference and less-than*}
c0c4af41fa3b Adding the theory UNITY/AllocImpl.thy, with supporting lemmas
paulson
parents: 14055
diff changeset
   540
c0c4af41fa3b Adding the theory UNITY/AllocImpl.thy, with supporting lemmas
paulson
parents: 14055
diff changeset
   541
lemma diff_lt_imp_lt: "[|(k#-i) < (k#-j); i\<in>nat; j\<in>nat; k\<in>nat|] ==> j<i"
c0c4af41fa3b Adding the theory UNITY/AllocImpl.thy, with supporting lemmas
paulson
parents: 14055
diff changeset
   542
apply (erule rev_mp)
c0c4af41fa3b Adding the theory UNITY/AllocImpl.thy, with supporting lemmas
paulson
parents: 14055
diff changeset
   543
apply (simp split add: nat_diff_split, auto)
c0c4af41fa3b Adding the theory UNITY/AllocImpl.thy, with supporting lemmas
paulson
parents: 14055
diff changeset
   544
 apply (blast intro: add_le_self lt_trans1)
c0c4af41fa3b Adding the theory UNITY/AllocImpl.thy, with supporting lemmas
paulson
parents: 14055
diff changeset
   545
apply (rule not_le_iff_lt [THEN iffD1], auto)
c0c4af41fa3b Adding the theory UNITY/AllocImpl.thy, with supporting lemmas
paulson
parents: 14055
diff changeset
   546
apply (subgoal_tac "i #+ da < j #+ d", force)
c0c4af41fa3b Adding the theory UNITY/AllocImpl.thy, with supporting lemmas
paulson
parents: 14055
diff changeset
   547
apply (blast intro: add_le_lt_mono) 
c0c4af41fa3b Adding the theory UNITY/AllocImpl.thy, with supporting lemmas
paulson
parents: 14055
diff changeset
   548
done
c0c4af41fa3b Adding the theory UNITY/AllocImpl.thy, with supporting lemmas
paulson
parents: 14055
diff changeset
   549
c0c4af41fa3b Adding the theory UNITY/AllocImpl.thy, with supporting lemmas
paulson
parents: 14055
diff changeset
   550
lemma lt_imp_diff_lt: "[|j<i; i\<le>k; k\<in>nat|] ==> (k#-i) < (k#-j)" 
c0c4af41fa3b Adding the theory UNITY/AllocImpl.thy, with supporting lemmas
paulson
parents: 14055
diff changeset
   551
apply (frule le_in_nat, assumption)
c0c4af41fa3b Adding the theory UNITY/AllocImpl.thy, with supporting lemmas
paulson
parents: 14055
diff changeset
   552
apply (frule lt_nat_in_nat, assumption)
c0c4af41fa3b Adding the theory UNITY/AllocImpl.thy, with supporting lemmas
paulson
parents: 14055
diff changeset
   553
apply (simp split add: nat_diff_split, auto)
c0c4af41fa3b Adding the theory UNITY/AllocImpl.thy, with supporting lemmas
paulson
parents: 14055
diff changeset
   554
  apply (blast intro: lt_asym lt_trans2)
c0c4af41fa3b Adding the theory UNITY/AllocImpl.thy, with supporting lemmas
paulson
parents: 14055
diff changeset
   555
 apply (blast intro: lt_irrefl lt_trans2)
c0c4af41fa3b Adding the theory UNITY/AllocImpl.thy, with supporting lemmas
paulson
parents: 14055
diff changeset
   556
apply (rule not_le_iff_lt [THEN iffD1], auto)
c0c4af41fa3b Adding the theory UNITY/AllocImpl.thy, with supporting lemmas
paulson
parents: 14055
diff changeset
   557
apply (subgoal_tac "j #+ d < i #+ da", force)
c0c4af41fa3b Adding the theory UNITY/AllocImpl.thy, with supporting lemmas
paulson
parents: 14055
diff changeset
   558
apply (blast intro: add_lt_le_mono) 
c0c4af41fa3b Adding the theory UNITY/AllocImpl.thy, with supporting lemmas
paulson
parents: 14055
diff changeset
   559
done
c0c4af41fa3b Adding the theory UNITY/AllocImpl.thy, with supporting lemmas
paulson
parents: 14055
diff changeset
   560
c0c4af41fa3b Adding the theory UNITY/AllocImpl.thy, with supporting lemmas
paulson
parents: 14055
diff changeset
   561
c0c4af41fa3b Adding the theory UNITY/AllocImpl.thy, with supporting lemmas
paulson
parents: 14055
diff changeset
   562
lemma diff_lt_iff_lt: "[|i\<le>k; j\<in>nat; k\<in>nat|] ==> (k#-i) < (k#-j) <-> j<i"
c0c4af41fa3b Adding the theory UNITY/AllocImpl.thy, with supporting lemmas
paulson
parents: 14055
diff changeset
   563
apply (frule le_in_nat, assumption)
c0c4af41fa3b Adding the theory UNITY/AllocImpl.thy, with supporting lemmas
paulson
parents: 14055
diff changeset
   564
apply (blast intro: lt_imp_diff_lt diff_lt_imp_lt) 
c0c4af41fa3b Adding the theory UNITY/AllocImpl.thy, with supporting lemmas
paulson
parents: 14055
diff changeset
   565
done
c0c4af41fa3b Adding the theory UNITY/AllocImpl.thy, with supporting lemmas
paulson
parents: 14055
diff changeset
   566
9548
15bee2731e43 instantiated Cancel_Numerals for "nat" in ZF
paulson
parents:
diff changeset
   567
end