23 |
23 |
24 (**Addition is the inverse of subtraction**) |
24 (**Addition is the inverse of subtraction**) |
25 |
25 |
26 (*We need m:nat even if we replace the RHS by natify(m), for consider e.g. |
26 (*We need m:nat even if we replace the RHS by natify(m), for consider e.g. |
27 n=2, m=omega; then n + (m-n) = 2 + (0-2) = 2 \<noteq> 0 = natify(m).*) |
27 n=2, m=omega; then n + (m-n) = 2 + (0-2) = 2 \<noteq> 0 = natify(m).*) |
28 lemma add_diff_inverse: "[| n \<le> m; m:nat |] ==> n #+ (m#-n) = m" |
28 lemma add_diff_inverse: "\<lbrakk>n \<le> m; m:nat\<rbrakk> \<Longrightarrow> n #+ (m#-n) = m" |
29 apply (frule lt_nat_in_nat, erule nat_succI) |
29 apply (frule lt_nat_in_nat, erule nat_succI) |
30 apply (erule rev_mp) |
30 apply (erule rev_mp) |
31 apply (rule_tac m = m and n = n in diff_induct, auto) |
31 apply (rule_tac m = m and n = n in diff_induct, auto) |
32 done |
32 done |
33 |
33 |
34 lemma add_diff_inverse2: "[| n \<le> m; m:nat |] ==> (m#-n) #+ n = m" |
34 lemma add_diff_inverse2: "\<lbrakk>n \<le> m; m:nat\<rbrakk> \<Longrightarrow> (m#-n) #+ n = m" |
35 apply (frule lt_nat_in_nat, erule nat_succI) |
35 apply (frule lt_nat_in_nat, erule nat_succI) |
36 apply (simp (no_asm_simp) add: add_commute add_diff_inverse) |
36 apply (simp (no_asm_simp) add: add_commute add_diff_inverse) |
37 done |
37 done |
38 |
38 |
39 (*Proof is IDENTICAL to that of add_diff_inverse*) |
39 (*Proof is IDENTICAL to that of add_diff_inverse*) |
40 lemma diff_succ: "[| n \<le> m; m:nat |] ==> succ(m) #- n = succ(m#-n)" |
40 lemma diff_succ: "\<lbrakk>n \<le> m; m:nat\<rbrakk> \<Longrightarrow> succ(m) #- n = succ(m#-n)" |
41 apply (frule lt_nat_in_nat, erule nat_succI) |
41 apply (frule lt_nat_in_nat, erule nat_succI) |
42 apply (erule rev_mp) |
42 apply (erule rev_mp) |
43 apply (rule_tac m = m and n = n in diff_induct) |
43 apply (rule_tac m = m and n = n in diff_induct) |
44 apply (simp_all (no_asm_simp)) |
44 apply (simp_all (no_asm_simp)) |
45 done |
45 done |
46 |
46 |
47 lemma zero_less_diff [simp]: |
47 lemma zero_less_diff [simp]: |
48 "[| m: nat; n: nat |] ==> 0 < (n #- m) \<longleftrightarrow> m<n" |
48 "\<lbrakk>m: nat; n: nat\<rbrakk> \<Longrightarrow> 0 < (n #- m) \<longleftrightarrow> m<n" |
49 apply (rule_tac m = m and n = n in diff_induct) |
49 apply (rule_tac m = m and n = n in diff_induct) |
50 apply (simp_all (no_asm_simp)) |
50 apply (simp_all (no_asm_simp)) |
51 done |
51 done |
52 |
52 |
53 |
53 |
65 |
65 |
66 |
66 |
67 subsection\<open>Remainder\<close> |
67 subsection\<open>Remainder\<close> |
68 |
68 |
69 (*We need m:nat even with natify*) |
69 (*We need m:nat even with natify*) |
70 lemma div_termination: "[| 0<n; n \<le> m; m:nat |] ==> m #- n < m" |
70 lemma div_termination: "\<lbrakk>0<n; n \<le> m; m:nat\<rbrakk> \<Longrightarrow> m #- n < m" |
71 apply (frule lt_nat_in_nat, erule nat_succI) |
71 apply (frule lt_nat_in_nat, erule nat_succI) |
72 apply (erule rev_mp) |
72 apply (erule rev_mp) |
73 apply (erule rev_mp) |
73 apply (erule rev_mp) |
74 apply (rule_tac m = m and n = n in diff_induct) |
74 apply (rule_tac m = m and n = n in diff_induct) |
75 apply (simp_all (no_asm_simp) add: diff_le_self) |
75 apply (simp_all (no_asm_simp) add: diff_le_self) |
79 lemmas div_rls = |
79 lemmas div_rls = |
80 nat_typechecks Ord_transrec_type apply_funtype |
80 nat_typechecks Ord_transrec_type apply_funtype |
81 div_termination [THEN ltD] |
81 div_termination [THEN ltD] |
82 nat_into_Ord not_lt_iff_le [THEN iffD1] |
82 nat_into_Ord not_lt_iff_le [THEN iffD1] |
83 |
83 |
84 lemma raw_mod_type: "[| m:nat; n:nat |] ==> raw_mod (m, n) \<in> nat" |
84 lemma raw_mod_type: "\<lbrakk>m:nat; n:nat\<rbrakk> \<Longrightarrow> raw_mod (m, n) \<in> nat" |
85 apply (unfold raw_mod_def) |
85 apply (unfold raw_mod_def) |
86 apply (rule Ord_transrec_type) |
86 apply (rule Ord_transrec_type) |
87 apply (auto simp add: nat_into_Ord [THEN Ord_0_lt_iff]) |
87 apply (auto simp add: nat_into_Ord [THEN Ord_0_lt_iff]) |
88 apply (blast intro: div_rls) |
88 apply (blast intro: div_rls) |
89 done |
89 done |
107 apply (unfold mod_def) |
107 apply (unfold mod_def) |
108 apply (rule raw_mod_def [THEN def_transrec, THEN trans]) |
108 apply (rule raw_mod_def [THEN def_transrec, THEN trans]) |
109 apply (simp (no_asm_simp)) |
109 apply (simp (no_asm_simp)) |
110 done (*NOT for adding to default simpset*) |
110 done (*NOT for adding to default simpset*) |
111 |
111 |
112 lemma raw_mod_less: "m<n ==> raw_mod (m,n) = m" |
112 lemma raw_mod_less: "m<n \<Longrightarrow> raw_mod (m,n) = m" |
113 apply (rule raw_mod_def [THEN def_transrec, THEN trans]) |
113 apply (rule raw_mod_def [THEN def_transrec, THEN trans]) |
114 apply (simp (no_asm_simp) add: div_termination [THEN ltD]) |
114 apply (simp (no_asm_simp) add: div_termination [THEN ltD]) |
115 done |
115 done |
116 |
116 |
117 lemma mod_less [simp]: "[| m<n; n \<in> nat |] ==> m mod n = m" |
117 lemma mod_less [simp]: "\<lbrakk>m<n; n \<in> nat\<rbrakk> \<Longrightarrow> m mod n = m" |
118 apply (frule lt_nat_in_nat, assumption) |
118 apply (frule lt_nat_in_nat, assumption) |
119 apply (simp (no_asm_simp) add: mod_def raw_mod_less) |
119 apply (simp (no_asm_simp) add: mod_def raw_mod_less) |
120 done |
120 done |
121 |
121 |
122 lemma raw_mod_geq: |
122 lemma raw_mod_geq: |
123 "[| 0<n; n \<le> m; m:nat |] ==> raw_mod (m, n) = raw_mod (m#-n, n)" |
123 "\<lbrakk>0<n; n \<le> m; m:nat\<rbrakk> \<Longrightarrow> raw_mod (m, n) = raw_mod (m#-n, n)" |
124 apply (frule lt_nat_in_nat, erule nat_succI) |
124 apply (frule lt_nat_in_nat, erule nat_succI) |
125 apply (rule raw_mod_def [THEN def_transrec, THEN trans]) |
125 apply (rule raw_mod_def [THEN def_transrec, THEN trans]) |
126 apply (simp (no_asm_simp) add: div_termination [THEN ltD] not_lt_iff_le [THEN iffD2], blast) |
126 apply (simp (no_asm_simp) add: div_termination [THEN ltD] not_lt_iff_le [THEN iffD2], blast) |
127 done |
127 done |
128 |
128 |
129 |
129 |
130 lemma mod_geq: "[| n \<le> m; m:nat |] ==> m mod n = (m#-n) mod n" |
130 lemma mod_geq: "\<lbrakk>n \<le> m; m:nat\<rbrakk> \<Longrightarrow> m mod n = (m#-n) mod n" |
131 apply (frule lt_nat_in_nat, erule nat_succI) |
131 apply (frule lt_nat_in_nat, erule nat_succI) |
132 apply (case_tac "n=0") |
132 apply (case_tac "n=0") |
133 apply (simp add: DIVISION_BY_ZERO_MOD) |
133 apply (simp add: DIVISION_BY_ZERO_MOD) |
134 apply (simp add: mod_def raw_mod_geq nat_into_Ord [THEN Ord_0_lt_iff]) |
134 apply (simp add: mod_def raw_mod_geq nat_into_Ord [THEN Ord_0_lt_iff]) |
135 done |
135 done |
136 |
136 |
137 |
137 |
138 subsection\<open>Division\<close> |
138 subsection\<open>Division\<close> |
139 |
139 |
140 lemma raw_div_type: "[| m:nat; n:nat |] ==> raw_div (m, n) \<in> nat" |
140 lemma raw_div_type: "\<lbrakk>m:nat; n:nat\<rbrakk> \<Longrightarrow> raw_div (m, n) \<in> nat" |
141 apply (unfold raw_div_def) |
141 apply (unfold raw_div_def) |
142 apply (rule Ord_transrec_type) |
142 apply (rule Ord_transrec_type) |
143 apply (auto simp add: nat_into_Ord [THEN Ord_0_lt_iff]) |
143 apply (auto simp add: nat_into_Ord [THEN Ord_0_lt_iff]) |
144 apply (blast intro: div_rls) |
144 apply (blast intro: div_rls) |
145 done |
145 done |
147 lemma div_type [TC,iff]: "m div n \<in> nat" |
147 lemma div_type [TC,iff]: "m div n \<in> nat" |
148 apply (unfold div_def) |
148 apply (unfold div_def) |
149 apply (simp (no_asm) add: div_def raw_div_type) |
149 apply (simp (no_asm) add: div_def raw_div_type) |
150 done |
150 done |
151 |
151 |
152 lemma raw_div_less: "m<n ==> raw_div (m,n) = 0" |
152 lemma raw_div_less: "m<n \<Longrightarrow> raw_div (m,n) = 0" |
153 apply (rule raw_div_def [THEN def_transrec, THEN trans]) |
153 apply (rule raw_div_def [THEN def_transrec, THEN trans]) |
154 apply (simp (no_asm_simp) add: div_termination [THEN ltD]) |
154 apply (simp (no_asm_simp) add: div_termination [THEN ltD]) |
155 done |
155 done |
156 |
156 |
157 lemma div_less [simp]: "[| m<n; n \<in> nat |] ==> m div n = 0" |
157 lemma div_less [simp]: "\<lbrakk>m<n; n \<in> nat\<rbrakk> \<Longrightarrow> m div n = 0" |
158 apply (frule lt_nat_in_nat, assumption) |
158 apply (frule lt_nat_in_nat, assumption) |
159 apply (simp (no_asm_simp) add: div_def raw_div_less) |
159 apply (simp (no_asm_simp) add: div_def raw_div_less) |
160 done |
160 done |
161 |
161 |
162 lemma raw_div_geq: "[| 0<n; n \<le> m; m:nat |] ==> raw_div(m,n) = succ(raw_div(m#-n, n))" |
162 lemma raw_div_geq: "\<lbrakk>0<n; n \<le> m; m:nat\<rbrakk> \<Longrightarrow> raw_div(m,n) = succ(raw_div(m#-n, n))" |
163 apply (subgoal_tac "n \<noteq> 0") |
163 apply (subgoal_tac "n \<noteq> 0") |
164 prefer 2 apply blast |
164 prefer 2 apply blast |
165 apply (frule lt_nat_in_nat, erule nat_succI) |
165 apply (frule lt_nat_in_nat, erule nat_succI) |
166 apply (rule raw_div_def [THEN def_transrec, THEN trans]) |
166 apply (rule raw_div_def [THEN def_transrec, THEN trans]) |
167 apply (simp (no_asm_simp) add: div_termination [THEN ltD] not_lt_iff_le [THEN iffD2] ) |
167 apply (simp (no_asm_simp) add: div_termination [THEN ltD] not_lt_iff_le [THEN iffD2] ) |
168 done |
168 done |
169 |
169 |
170 lemma div_geq [simp]: |
170 lemma div_geq [simp]: |
171 "[| 0<n; n \<le> m; m:nat |] ==> m div n = succ ((m#-n) div n)" |
171 "\<lbrakk>0<n; n \<le> m; m:nat\<rbrakk> \<Longrightarrow> m div n = succ ((m#-n) div n)" |
172 apply (frule lt_nat_in_nat, erule nat_succI) |
172 apply (frule lt_nat_in_nat, erule nat_succI) |
173 apply (simp (no_asm_simp) add: div_def raw_div_geq) |
173 apply (simp (no_asm_simp) add: div_def raw_div_geq) |
174 done |
174 done |
175 |
175 |
176 declare div_less [simp] div_geq [simp] |
176 declare div_less [simp] div_geq [simp] |
177 |
177 |
178 |
178 |
179 (*A key result*) |
179 (*A key result*) |
180 lemma mod_div_lemma: "[| m: nat; n: nat |] ==> (m div n)#*n #+ m mod n = m" |
180 lemma mod_div_lemma: "\<lbrakk>m: nat; n: nat\<rbrakk> \<Longrightarrow> (m div n)#*n #+ m mod n = m" |
181 apply (case_tac "n=0") |
181 apply (case_tac "n=0") |
182 apply (simp add: DIVISION_BY_ZERO_MOD) |
182 apply (simp add: DIVISION_BY_ZERO_MOD) |
183 apply (simp add: nat_into_Ord [THEN Ord_0_lt_iff]) |
183 apply (simp add: nat_into_Ord [THEN Ord_0_lt_iff]) |
184 apply (erule complete_induct) |
184 apply (erule complete_induct) |
185 apply (case_tac "x<n") |
185 apply (case_tac "x<n") |
193 apply (subgoal_tac " (natify (m) div natify (n))#*natify (n) #+ natify (m) mod natify (n) = natify (m) ") |
193 apply (subgoal_tac " (natify (m) div natify (n))#*natify (n) #+ natify (m) mod natify (n) = natify (m) ") |
194 apply force |
194 apply force |
195 apply (subst mod_div_lemma, auto) |
195 apply (subst mod_div_lemma, auto) |
196 done |
196 done |
197 |
197 |
198 lemma mod_div_equality: "m: nat ==> (m div n)#*n #+ m mod n = m" |
198 lemma mod_div_equality: "m: nat \<Longrightarrow> (m div n)#*n #+ m mod n = m" |
199 apply (simp (no_asm_simp) add: mod_div_equality_natify) |
199 apply (simp (no_asm_simp) add: mod_div_equality_natify) |
200 done |
200 done |
201 |
201 |
202 |
202 |
203 subsection\<open>Further Facts about Remainder\<close> |
203 subsection\<open>Further Facts about Remainder\<close> |
204 |
204 |
205 text\<open>(mainly for mutilated chess board)\<close> |
205 text\<open>(mainly for mutilated chess board)\<close> |
206 |
206 |
207 lemma mod_succ_lemma: |
207 lemma mod_succ_lemma: |
208 "[| 0<n; m:nat; n:nat |] |
208 "\<lbrakk>0<n; m:nat; n:nat\<rbrakk> |
209 ==> succ(m) mod n = (if succ(m mod n) = n then 0 else succ(m mod n))" |
209 \<Longrightarrow> succ(m) mod n = (if succ(m mod n) = n then 0 else succ(m mod n))" |
210 apply (erule complete_induct) |
210 apply (erule complete_induct) |
211 apply (case_tac "succ (x) <n") |
211 apply (case_tac "succ (x) <n") |
212 txt\<open>case succ(x) < n\<close> |
212 txt\<open>case succ(x) < n\<close> |
213 apply (simp (no_asm_simp) add: nat_le_refl [THEN lt_trans] succ_neq_self) |
213 apply (simp (no_asm_simp) add: nat_le_refl [THEN lt_trans] succ_neq_self) |
214 apply (simp add: ltD [THEN mem_imp_not_eq]) |
214 apply (simp add: ltD [THEN mem_imp_not_eq]) |
219 txt\<open>equality case\<close> |
219 txt\<open>equality case\<close> |
220 apply (simp add: diff_self_eq_0) |
220 apply (simp add: diff_self_eq_0) |
221 done |
221 done |
222 |
222 |
223 lemma mod_succ: |
223 lemma mod_succ: |
224 "n:nat ==> succ(m) mod n = (if succ(m mod n) = n then 0 else succ(m mod n))" |
224 "n:nat \<Longrightarrow> succ(m) mod n = (if succ(m mod n) = n then 0 else succ(m mod n))" |
225 apply (case_tac "n=0") |
225 apply (case_tac "n=0") |
226 apply (simp (no_asm_simp) add: natify_succ DIVISION_BY_ZERO_MOD) |
226 apply (simp (no_asm_simp) add: natify_succ DIVISION_BY_ZERO_MOD) |
227 apply (subgoal_tac "natify (succ (m)) mod n = (if succ (natify (m) mod n) = n then 0 else succ (natify (m) mod n))") |
227 apply (subgoal_tac "natify (succ (m)) mod n = (if succ (natify (m) mod n) = n then 0 else succ (natify (m) mod n))") |
228 prefer 2 |
228 prefer 2 |
229 apply (subst natify_succ) |
229 apply (subst natify_succ) |
230 apply (rule mod_succ_lemma) |
230 apply (rule mod_succ_lemma) |
231 apply (auto simp del: natify_succ simp add: nat_into_Ord [THEN Ord_0_lt_iff]) |
231 apply (auto simp del: natify_succ simp add: nat_into_Ord [THEN Ord_0_lt_iff]) |
232 done |
232 done |
233 |
233 |
234 lemma mod_less_divisor: "[| 0<n; n:nat |] ==> m mod n < n" |
234 lemma mod_less_divisor: "\<lbrakk>0<n; n:nat\<rbrakk> \<Longrightarrow> m mod n < n" |
235 apply (subgoal_tac "natify (m) mod n < n") |
235 apply (subgoal_tac "natify (m) mod n < n") |
236 apply (rule_tac [2] i = "natify (m) " in complete_induct) |
236 apply (rule_tac [2] i = "natify (m) " in complete_induct) |
237 apply (case_tac [3] "x<n", auto) |
237 apply (case_tac [3] "x<n", auto) |
238 txt\<open>case \<^term>\<open>n \<le> x\<close>\<close> |
238 txt\<open>case \<^term>\<open>n \<le> x\<close>\<close> |
239 apply (simp add: mod_geq not_lt_iff_le div_termination [THEN ltD]) |
239 apply (simp add: mod_geq not_lt_iff_le div_termination [THEN ltD]) |
240 done |
240 done |
241 |
241 |
242 lemma mod_1_eq [simp]: "m mod 1 = 0" |
242 lemma mod_1_eq [simp]: "m mod 1 = 0" |
243 by (cut_tac n = 1 in mod_less_divisor, auto) |
243 by (cut_tac n = 1 in mod_less_divisor, auto) |
244 |
244 |
245 lemma mod2_cases: "b<2 ==> k mod 2 = b | k mod 2 = (if b=1 then 0 else 1)" |
245 lemma mod2_cases: "b<2 \<Longrightarrow> k mod 2 = b | k mod 2 = (if b=1 then 0 else 1)" |
246 apply (subgoal_tac "k mod 2: 2") |
246 apply (subgoal_tac "k mod 2: 2") |
247 prefer 2 apply (simp add: mod_less_divisor [THEN ltD]) |
247 prefer 2 apply (simp add: mod_less_divisor [THEN ltD]) |
248 apply (drule ltD, auto) |
248 apply (drule ltD, auto) |
249 done |
249 done |
250 |
250 |
264 by (cut_tac n = 0 in mod2_add_more, auto) |
264 by (cut_tac n = 0 in mod2_add_more, auto) |
265 |
265 |
266 |
266 |
267 subsection\<open>Additional theorems about \<open>\<le>\<close>\<close> |
267 subsection\<open>Additional theorems about \<open>\<le>\<close>\<close> |
268 |
268 |
269 lemma add_le_self: "m:nat ==> m \<le> (m #+ n)" |
269 lemma add_le_self: "m:nat \<Longrightarrow> m \<le> (m #+ n)" |
270 apply (simp (no_asm_simp)) |
270 apply (simp (no_asm_simp)) |
271 done |
271 done |
272 |
272 |
273 lemma add_le_self2: "m:nat ==> m \<le> (n #+ m)" |
273 lemma add_le_self2: "m:nat \<Longrightarrow> m \<le> (n #+ m)" |
274 apply (simp (no_asm_simp)) |
274 apply (simp (no_asm_simp)) |
275 done |
275 done |
276 |
276 |
277 (*** Monotonicity of Multiplication ***) |
277 (*** Monotonicity of Multiplication ***) |
278 |
278 |
279 lemma mult_le_mono1: "[| i \<le> j; j:nat |] ==> (i#*k) \<le> (j#*k)" |
279 lemma mult_le_mono1: "\<lbrakk>i \<le> j; j:nat\<rbrakk> \<Longrightarrow> (i#*k) \<le> (j#*k)" |
280 apply (subgoal_tac "natify (i) #*natify (k) \<le> j#*natify (k) ") |
280 apply (subgoal_tac "natify (i) #*natify (k) \<le> j#*natify (k) ") |
281 apply (frule_tac [2] lt_nat_in_nat) |
281 apply (frule_tac [2] lt_nat_in_nat) |
282 apply (rule_tac [3] n = "natify (k) " in nat_induct) |
282 apply (rule_tac [3] n = "natify (k) " in nat_induct) |
283 apply (simp_all add: add_le_mono) |
283 apply (simp_all add: add_le_mono) |
284 done |
284 done |
285 |
285 |
286 (* @{text"\<le>"} monotonicity, BOTH arguments*) |
286 (* @{text"\<le>"} monotonicity, BOTH arguments*) |
287 lemma mult_le_mono: "[| i \<le> j; k \<le> l; j:nat; l:nat |] ==> i#*k \<le> j#*l" |
287 lemma mult_le_mono: "\<lbrakk>i \<le> j; k \<le> l; j:nat; l:nat\<rbrakk> \<Longrightarrow> i#*k \<le> j#*l" |
288 apply (rule mult_le_mono1 [THEN le_trans], assumption+) |
288 apply (rule mult_le_mono1 [THEN le_trans], assumption+) |
289 apply (subst mult_commute, subst mult_commute, rule mult_le_mono1, assumption+) |
289 apply (subst mult_commute, subst mult_commute, rule mult_le_mono1, assumption+) |
290 done |
290 done |
291 |
291 |
292 (*strict, in 1st argument; proof is by induction on k>0. |
292 (*strict, in 1st argument; proof is by induction on k>0. |
293 I can't see how to relax the typing conditions.*) |
293 I can't see how to relax the typing conditions.*) |
294 lemma mult_lt_mono2: "[| i<j; 0<k; j:nat; k:nat |] ==> k#*i < k#*j" |
294 lemma mult_lt_mono2: "\<lbrakk>i<j; 0<k; j:nat; k:nat\<rbrakk> \<Longrightarrow> k#*i < k#*j" |
295 apply (erule zero_lt_natE) |
295 apply (erule zero_lt_natE) |
296 apply (frule_tac [2] lt_nat_in_nat) |
296 apply (frule_tac [2] lt_nat_in_nat) |
297 apply (simp_all (no_asm_simp)) |
297 apply (simp_all (no_asm_simp)) |
298 apply (induct_tac "x") |
298 apply (induct_tac "x") |
299 apply (simp_all (no_asm_simp) add: add_lt_mono) |
299 apply (simp_all (no_asm_simp) add: add_lt_mono) |
300 done |
300 done |
301 |
301 |
302 lemma mult_lt_mono1: "[| i<j; 0<k; j:nat; k:nat |] ==> i#*k < j#*k" |
302 lemma mult_lt_mono1: "\<lbrakk>i<j; 0<k; j:nat; k:nat\<rbrakk> \<Longrightarrow> i#*k < j#*k" |
303 apply (simp (no_asm_simp) add: mult_lt_mono2 mult_commute [of _ k]) |
303 apply (simp (no_asm_simp) add: mult_lt_mono2 mult_commute [of _ k]) |
304 done |
304 done |
305 |
305 |
306 lemma add_eq_0_iff [iff]: "m#+n = 0 \<longleftrightarrow> natify(m)=0 & natify(n)=0" |
306 lemma add_eq_0_iff [iff]: "m#+n = 0 \<longleftrightarrow> natify(m)=0 & natify(n)=0" |
307 apply (subgoal_tac "natify (m) #+ natify (n) = 0 \<longleftrightarrow> natify (m) =0 & natify (n) =0") |
307 apply (subgoal_tac "natify (m) #+ natify (n) = 0 \<longleftrightarrow> natify (m) =0 & natify (n) =0") |
340 |
340 |
341 |
341 |
342 subsection\<open>Cancellation Laws for Common Factors in Comparisons\<close> |
342 subsection\<open>Cancellation Laws for Common Factors in Comparisons\<close> |
343 |
343 |
344 lemma mult_less_cancel_lemma: |
344 lemma mult_less_cancel_lemma: |
345 "[| k: nat; m: nat; n: nat |] ==> (m#*k < n#*k) \<longleftrightarrow> (0<k & m<n)" |
345 "\<lbrakk>k: nat; m: nat; n: nat\<rbrakk> \<Longrightarrow> (m#*k < n#*k) \<longleftrightarrow> (0<k & m<n)" |
346 apply (safe intro!: mult_lt_mono1) |
346 apply (safe intro!: mult_lt_mono1) |
347 apply (erule natE, auto) |
347 apply (erule natE, auto) |
348 apply (rule not_le_iff_lt [THEN iffD1]) |
348 apply (rule not_le_iff_lt [THEN iffD1]) |
349 apply (drule_tac [3] not_le_iff_lt [THEN [2] rev_iffD2]) |
349 apply (drule_tac [3] not_le_iff_lt [THEN [2] rev_iffD2]) |
350 prefer 5 apply (blast intro: mult_le_mono1, auto) |
350 prefer 5 apply (blast intro: mult_le_mono1, auto) |
369 lemma mult_le_cancel1 [simp]: "(k#*m \<le> k#*n) \<longleftrightarrow> (0 < natify(k) \<longrightarrow> natify(m) \<le> natify(n))" |
369 lemma mult_le_cancel1 [simp]: "(k#*m \<le> k#*n) \<longleftrightarrow> (0 < natify(k) \<longrightarrow> natify(m) \<le> natify(n))" |
370 apply (simp (no_asm_simp) add: not_lt_iff_le [THEN iff_sym]) |
370 apply (simp (no_asm_simp) add: not_lt_iff_le [THEN iff_sym]) |
371 apply auto |
371 apply auto |
372 done |
372 done |
373 |
373 |
374 lemma mult_le_cancel_le1: "k \<in> nat ==> k #* m \<le> k \<longleftrightarrow> (0 < k \<longrightarrow> natify(m) \<le> 1)" |
374 lemma mult_le_cancel_le1: "k \<in> nat \<Longrightarrow> k #* m \<le> k \<longleftrightarrow> (0 < k \<longrightarrow> natify(m) \<le> 1)" |
375 by (cut_tac k = k and m = m and n = 1 in mult_le_cancel1, auto) |
375 by (cut_tac k = k and m = m and n = 1 in mult_le_cancel1, auto) |
376 |
376 |
377 lemma Ord_eq_iff_le: "[| Ord(m); Ord(n) |] ==> m=n \<longleftrightarrow> (m \<le> n & n \<le> m)" |
377 lemma Ord_eq_iff_le: "\<lbrakk>Ord(m); Ord(n)\<rbrakk> \<Longrightarrow> m=n \<longleftrightarrow> (m \<le> n & n \<le> m)" |
378 by (blast intro: le_anti_sym) |
378 by (blast intro: le_anti_sym) |
379 |
379 |
380 lemma mult_cancel2_lemma: |
380 lemma mult_cancel2_lemma: |
381 "[| k: nat; m: nat; n: nat |] ==> (m#*k = n#*k) \<longleftrightarrow> (m=n | k=0)" |
381 "\<lbrakk>k: nat; m: nat; n: nat\<rbrakk> \<Longrightarrow> (m#*k = n#*k) \<longleftrightarrow> (m=n | k=0)" |
382 apply (simp (no_asm_simp) add: Ord_eq_iff_le [of "m#*k"] Ord_eq_iff_le [of m]) |
382 apply (simp (no_asm_simp) add: Ord_eq_iff_le [of "m#*k"] Ord_eq_iff_le [of m]) |
383 apply (auto simp add: Ord_0_lt_iff) |
383 apply (auto simp add: Ord_0_lt_iff) |
384 done |
384 done |
385 |
385 |
386 lemma mult_cancel2 [simp]: |
386 lemma mult_cancel2 [simp]: |
396 |
396 |
397 |
397 |
398 (** Cancellation law for division **) |
398 (** Cancellation law for division **) |
399 |
399 |
400 lemma div_cancel_raw: |
400 lemma div_cancel_raw: |
401 "[| 0<n; 0<k; k:nat; m:nat; n:nat |] ==> (k#*m) div (k#*n) = m div n" |
401 "\<lbrakk>0<n; 0<k; k:nat; m:nat; n:nat\<rbrakk> \<Longrightarrow> (k#*m) div (k#*n) = m div n" |
402 apply (erule_tac i = m in complete_induct) |
402 apply (erule_tac i = m in complete_induct) |
403 apply (case_tac "x<n") |
403 apply (case_tac "x<n") |
404 apply (simp add: div_less zero_lt_mult_iff mult_lt_mono2) |
404 apply (simp add: div_less zero_lt_mult_iff mult_lt_mono2) |
405 apply (simp add: not_lt_iff_le zero_lt_mult_iff le_refl [THEN mult_le_mono] |
405 apply (simp add: not_lt_iff_le zero_lt_mult_iff le_refl [THEN mult_le_mono] |
406 div_geq diff_mult_distrib2 [symmetric] div_termination [THEN ltD]) |
406 div_geq diff_mult_distrib2 [symmetric] div_termination [THEN ltD]) |
407 done |
407 done |
408 |
408 |
409 lemma div_cancel: |
409 lemma div_cancel: |
410 "[| 0 < natify(n); 0 < natify(k) |] ==> (k#*m) div (k#*n) = m div n" |
410 "\<lbrakk>0 < natify(n); 0 < natify(k)\<rbrakk> \<Longrightarrow> (k#*m) div (k#*n) = m div n" |
411 apply (cut_tac k = "natify (k) " and m = "natify (m)" and n = "natify (n)" |
411 apply (cut_tac k = "natify (k) " and m = "natify (m)" and n = "natify (n)" |
412 in div_cancel_raw) |
412 in div_cancel_raw) |
413 apply auto |
413 apply auto |
414 done |
414 done |
415 |
415 |
416 |
416 |
417 subsection\<open>More Lemmas about Remainder\<close> |
417 subsection\<open>More Lemmas about Remainder\<close> |
418 |
418 |
419 lemma mult_mod_distrib_raw: |
419 lemma mult_mod_distrib_raw: |
420 "[| k:nat; m:nat; n:nat |] ==> (k#*m) mod (k#*n) = k #* (m mod n)" |
420 "\<lbrakk>k:nat; m:nat; n:nat\<rbrakk> \<Longrightarrow> (k#*m) mod (k#*n) = k #* (m mod n)" |
421 apply (case_tac "k=0") |
421 apply (case_tac "k=0") |
422 apply (simp add: DIVISION_BY_ZERO_MOD) |
422 apply (simp add: DIVISION_BY_ZERO_MOD) |
423 apply (case_tac "n=0") |
423 apply (case_tac "n=0") |
424 apply (simp add: DIVISION_BY_ZERO_MOD) |
424 apply (simp add: DIVISION_BY_ZERO_MOD) |
425 apply (simp add: nat_into_Ord [THEN Ord_0_lt_iff]) |
425 apply (simp add: nat_into_Ord [THEN Ord_0_lt_iff]) |
438 |
438 |
439 lemma mult_mod_distrib: "(m mod n) #* k = (m#*k) mod (n#*k)" |
439 lemma mult_mod_distrib: "(m mod n) #* k = (m#*k) mod (n#*k)" |
440 apply (simp (no_asm) add: mult_commute mod_mult_distrib2) |
440 apply (simp (no_asm) add: mult_commute mod_mult_distrib2) |
441 done |
441 done |
442 |
442 |
443 lemma mod_add_self2_raw: "n \<in> nat ==> (m #+ n) mod n = m mod n" |
443 lemma mod_add_self2_raw: "n \<in> nat \<Longrightarrow> (m #+ n) mod n = m mod n" |
444 apply (subgoal_tac " (n #+ m) mod n = (n #+ m #- n) mod n") |
444 apply (subgoal_tac " (n #+ m) mod n = (n #+ m #- n) mod n") |
445 apply (simp add: add_commute) |
445 apply (simp add: add_commute) |
446 apply (subst mod_geq [symmetric], auto) |
446 apply (subst mod_geq [symmetric], auto) |
447 done |
447 done |
448 |
448 |
484 apply (simp del: mult_natify2) |
484 apply (simp del: mult_natify2) |
485 apply (drule nat_into_Ord [THEN Ord_0_lt, THEN [2] mult_lt_mono2], auto) |
485 apply (drule nat_into_Ord [THEN Ord_0_lt, THEN [2] mult_lt_mono2], auto) |
486 done |
486 done |
487 |
487 |
488 lemma less_imp_succ_add [rule_format]: |
488 lemma less_imp_succ_add [rule_format]: |
489 "[| m<n; n: nat |] ==> \<exists>k\<in>nat. n = succ(m#+k)" |
489 "\<lbrakk>m<n; n: nat\<rbrakk> \<Longrightarrow> \<exists>k\<in>nat. n = succ(m#+k)" |
490 apply (frule lt_nat_in_nat, assumption) |
490 apply (frule lt_nat_in_nat, assumption) |
491 apply (erule rev_mp) |
491 apply (erule rev_mp) |
492 apply (induct_tac "n") |
492 apply (induct_tac "n") |
493 apply (simp_all (no_asm) add: le_iff) |
493 apply (simp_all (no_asm) add: le_iff) |
494 apply (blast elim!: leE intro!: add_0_right [symmetric] add_succ_right [symmetric]) |
494 apply (blast elim!: leE intro!: add_0_right [symmetric] add_succ_right [symmetric]) |
495 done |
495 done |
496 |
496 |
497 lemma less_iff_succ_add: |
497 lemma less_iff_succ_add: |
498 "[| m: nat; n: nat |] ==> (m<n) \<longleftrightarrow> (\<exists>k\<in>nat. n = succ(m#+k))" |
498 "\<lbrakk>m: nat; n: nat\<rbrakk> \<Longrightarrow> (m<n) \<longleftrightarrow> (\<exists>k\<in>nat. n = succ(m#+k))" |
499 by (auto intro: less_imp_succ_add) |
499 by (auto intro: less_imp_succ_add) |
500 |
500 |
501 lemma add_lt_elim2: |
501 lemma add_lt_elim2: |
502 "\<lbrakk>a #+ d = b #+ c; a < b; b \<in> nat; c \<in> nat; d \<in> nat\<rbrakk> \<Longrightarrow> c < d" |
502 "\<lbrakk>a #+ d = b #+ c; a < b; b \<in> nat; c \<in> nat; d \<in> nat\<rbrakk> \<Longrightarrow> c < d" |
503 by (drule less_imp_succ_add, auto) |
503 by (drule less_imp_succ_add, auto) |
508 |
508 |
509 |
509 |
510 subsubsection\<open>More Lemmas About Difference\<close> |
510 subsubsection\<open>More Lemmas About Difference\<close> |
511 |
511 |
512 lemma diff_is_0_lemma: |
512 lemma diff_is_0_lemma: |
513 "[| m: nat; n: nat |] ==> m #- n = 0 \<longleftrightarrow> m \<le> n" |
513 "\<lbrakk>m: nat; n: nat\<rbrakk> \<Longrightarrow> m #- n = 0 \<longleftrightarrow> m \<le> n" |
514 apply (rule_tac m = m and n = n in diff_induct, simp_all) |
514 apply (rule_tac m = m and n = n in diff_induct, simp_all) |
515 done |
515 done |
516 |
516 |
517 lemma diff_is_0_iff: "m #- n = 0 \<longleftrightarrow> natify(m) \<le> natify(n)" |
517 lemma diff_is_0_iff: "m #- n = 0 \<longleftrightarrow> natify(m) \<le> natify(n)" |
518 by (simp add: diff_is_0_lemma [symmetric]) |
518 by (simp add: diff_is_0_lemma [symmetric]) |
519 |
519 |
520 lemma nat_lt_imp_diff_eq_0: |
520 lemma nat_lt_imp_diff_eq_0: |
521 "[| a:nat; b:nat; a<b |] ==> a #- b = 0" |
521 "\<lbrakk>a:nat; b:nat; a<b\<rbrakk> \<Longrightarrow> a #- b = 0" |
522 by (simp add: diff_is_0_iff le_iff) |
522 by (simp add: diff_is_0_iff le_iff) |
523 |
523 |
524 lemma raw_nat_diff_split: |
524 lemma raw_nat_diff_split: |
525 "[| a:nat; b:nat |] ==> |
525 "\<lbrakk>a:nat; b:nat\<rbrakk> \<Longrightarrow> |
526 (P(a #- b)) \<longleftrightarrow> ((a < b \<longrightarrow>P(0)) & (\<forall>d\<in>nat. a = b #+ d \<longrightarrow> P(d)))" |
526 (P(a #- b)) \<longleftrightarrow> ((a < b \<longrightarrow>P(0)) & (\<forall>d\<in>nat. a = b #+ d \<longrightarrow> P(d)))" |
527 apply (case_tac "a < b") |
527 apply (case_tac "a < b") |
528 apply (force simp add: nat_lt_imp_diff_eq_0) |
528 apply (force simp add: nat_lt_imp_diff_eq_0) |
529 apply (rule iffI, force, simp) |
529 apply (rule iffI, force, simp) |
530 apply (drule_tac x="a#-b" in bspec) |
530 apply (drule_tac x="a#-b" in bspec) |
538 apply simp_all |
538 apply simp_all |
539 done |
539 done |
540 |
540 |
541 text\<open>Difference and less-than\<close> |
541 text\<open>Difference and less-than\<close> |
542 |
542 |
543 lemma diff_lt_imp_lt: "[|(k#-i) < (k#-j); i\<in>nat; j\<in>nat; k\<in>nat|] ==> j<i" |
543 lemma diff_lt_imp_lt: "\<lbrakk>(k#-i) < (k#-j); i\<in>nat; j\<in>nat; k\<in>nat\<rbrakk> \<Longrightarrow> j<i" |
544 apply (erule rev_mp) |
544 apply (erule rev_mp) |
545 apply (simp split: nat_diff_split, auto) |
545 apply (simp split: nat_diff_split, auto) |
546 apply (blast intro: add_le_self lt_trans1) |
546 apply (blast intro: add_le_self lt_trans1) |
547 apply (rule not_le_iff_lt [THEN iffD1], auto) |
547 apply (rule not_le_iff_lt [THEN iffD1], auto) |
548 apply (subgoal_tac "i #+ da < j #+ d", force) |
548 apply (subgoal_tac "i #+ da < j #+ d", force) |
549 apply (blast intro: add_le_lt_mono) |
549 apply (blast intro: add_le_lt_mono) |
550 done |
550 done |
551 |
551 |
552 lemma lt_imp_diff_lt: "[|j<i; i\<le>k; k\<in>nat|] ==> (k#-i) < (k#-j)" |
552 lemma lt_imp_diff_lt: "\<lbrakk>j<i; i\<le>k; k\<in>nat\<rbrakk> \<Longrightarrow> (k#-i) < (k#-j)" |
553 apply (frule le_in_nat, assumption) |
553 apply (frule le_in_nat, assumption) |
554 apply (frule lt_nat_in_nat, assumption) |
554 apply (frule lt_nat_in_nat, assumption) |
555 apply (simp split: nat_diff_split, auto) |
555 apply (simp split: nat_diff_split, auto) |
556 apply (blast intro: lt_asym lt_trans2) |
556 apply (blast intro: lt_asym lt_trans2) |
557 apply (blast intro: lt_irrefl lt_trans2) |
557 apply (blast intro: lt_irrefl lt_trans2) |