229 Addsimps [zero_less_Suc]; |
229 Addsimps [zero_less_Suc]; |
230 |
230 |
231 (** Elimination properties **) |
231 (** Elimination properties **) |
232 |
232 |
233 val prems = goalw Nat.thy [less_def] "n<m ==> ~ m<(n::nat)"; |
233 val prems = goalw Nat.thy [less_def] "n<m ==> ~ m<(n::nat)"; |
234 by(fast_tac (HOL_cs addIs ([wf_pred_nat, wf_trancl RS wf_asym]@prems))1); |
234 by (fast_tac (HOL_cs addIs ([wf_pred_nat, wf_trancl RS wf_asym]@prems))1); |
235 qed "less_not_sym"; |
235 qed "less_not_sym"; |
236 |
236 |
237 (* [| n(m; m(n |] ==> R *) |
237 (* [| n(m; m(n |] ==> R *) |
238 bind_thm ("less_asym", (less_not_sym RS notE)); |
238 bind_thm ("less_asym", (less_not_sym RS notE)); |
239 |
239 |
244 |
244 |
245 (* n(n ==> R *) |
245 (* n(n ==> R *) |
246 bind_thm ("less_anti_refl", (less_not_refl RS notE)); |
246 bind_thm ("less_anti_refl", (less_not_refl RS notE)); |
247 |
247 |
248 goal Nat.thy "!!m. n<m ==> m ~= (n::nat)"; |
248 goal Nat.thy "!!m. n<m ==> m ~= (n::nat)"; |
249 by(fast_tac (HOL_cs addEs [less_anti_refl]) 1); |
249 by (fast_tac (HOL_cs addEs [less_anti_refl]) 1); |
250 qed "less_not_refl2"; |
250 qed "less_not_refl2"; |
251 |
251 |
252 |
252 |
253 val major::prems = goalw Nat.thy [less_def] |
253 val major::prems = goalw Nat.thy [less_def] |
254 "[| i<k; k=Suc(i) ==> P; !!j. [| i<j; k=Suc(j) |] ==> P \ |
254 "[| i<k; k=Suc(i) ==> P; !!j. [| i<j; k=Suc(j) |] ==> P \ |
283 by (fast_tac (HOL_cs addSIs [lessI] |
283 by (fast_tac (HOL_cs addSIs [lessI] |
284 addEs [less_trans, less_SucE]) 1); |
284 addEs [less_trans, less_SucE]) 1); |
285 qed "less_Suc_eq"; |
285 qed "less_Suc_eq"; |
286 |
286 |
287 val prems = goal Nat.thy "m<n ==> n ~= 0"; |
287 val prems = goal Nat.thy "m<n ==> n ~= 0"; |
288 by(res_inst_tac [("n","n")] natE 1); |
288 by (res_inst_tac [("n","n")] natE 1); |
289 by(cut_facts_tac prems 1); |
289 by (cut_facts_tac prems 1); |
290 by(ALLGOALS Asm_full_simp_tac); |
290 by (ALLGOALS Asm_full_simp_tac); |
291 qed "gr_implies_not0"; |
291 qed "gr_implies_not0"; |
292 Addsimps [gr_implies_not0]; |
292 Addsimps [gr_implies_not0]; |
293 |
293 |
294 (** Inductive (?) properties **) |
294 (** Inductive (?) properties **) |
295 |
295 |
333 by (EVERY1 [rtac iffI, etac Suc_less_SucD, etac Suc_mono]); |
333 by (EVERY1 [rtac iffI, etac Suc_less_SucD, etac Suc_mono]); |
334 qed "Suc_less_eq"; |
334 qed "Suc_less_eq"; |
335 Addsimps [Suc_less_eq]; |
335 Addsimps [Suc_less_eq]; |
336 |
336 |
337 goal Nat.thy "~(Suc(n) < n)"; |
337 goal Nat.thy "~(Suc(n) < n)"; |
338 by(fast_tac (HOL_cs addEs [Suc_lessD RS less_anti_refl]) 1); |
338 by (fast_tac (HOL_cs addEs [Suc_lessD RS less_anti_refl]) 1); |
339 qed "not_Suc_n_less_n"; |
339 qed "not_Suc_n_less_n"; |
340 Addsimps [not_Suc_n_less_n]; |
340 Addsimps [not_Suc_n_less_n]; |
341 |
341 |
342 goal Nat.thy "!!i. i<j ==> j<k --> Suc i < k"; |
342 goal Nat.thy "!!i. i<j ==> j<k --> Suc i < k"; |
343 by(nat_ind_tac "k" 1); |
343 by (nat_ind_tac "k" 1); |
344 by(ALLGOALS (asm_simp_tac (!simpset addsimps [less_Suc_eq]))); |
344 by (ALLGOALS (asm_simp_tac (!simpset addsimps [less_Suc_eq]))); |
345 by(fast_tac (HOL_cs addDs [Suc_lessD]) 1); |
345 by (fast_tac (HOL_cs addDs [Suc_lessD]) 1); |
346 qed_spec_mp "less_trans_Suc"; |
346 qed_spec_mp "less_trans_Suc"; |
347 |
347 |
348 (*"Less than" is a linear ordering*) |
348 (*"Less than" is a linear ordering*) |
349 goal Nat.thy "m<n | m=n | n<(m::nat)"; |
349 goal Nat.thy "m<n | m=n | n<(m::nat)"; |
350 by (nat_ind_tac "m" 1); |
350 by (nat_ind_tac "m" 1); |
355 qed "less_linear"; |
355 qed "less_linear"; |
356 |
356 |
357 (*Can be used with less_Suc_eq to get n=m | n<m *) |
357 (*Can be used with less_Suc_eq to get n=m | n<m *) |
358 goal Nat.thy "(~ m < n) = (n < Suc(m))"; |
358 goal Nat.thy "(~ m < n) = (n < Suc(m))"; |
359 by (res_inst_tac [("m","m"),("n","n")] diff_induct 1); |
359 by (res_inst_tac [("m","m"),("n","n")] diff_induct 1); |
360 by(ALLGOALS Asm_simp_tac); |
360 by (ALLGOALS Asm_simp_tac); |
361 qed "not_less_eq"; |
361 qed "not_less_eq"; |
362 |
362 |
363 (*Complete induction, aka course-of-values induction*) |
363 (*Complete induction, aka course-of-values induction*) |
364 val prems = goalw Nat.thy [less_def] |
364 val prems = goalw Nat.thy [less_def] |
365 "[| !!n. [| ! m::nat. m<n --> P(m) |] ==> P(n) |] ==> P(n)"; |
365 "[| !!n. [| ! m::nat. m<n --> P(m) |] ==> P(n) |] ==> P(n)"; |
373 goalw Nat.thy [le_def] "0 <= n"; |
373 goalw Nat.thy [le_def] "0 <= n"; |
374 by (rtac not_less0 1); |
374 by (rtac not_less0 1); |
375 qed "le0"; |
375 qed "le0"; |
376 |
376 |
377 goalw Nat.thy [le_def] "~ Suc n <= n"; |
377 goalw Nat.thy [le_def] "~ Suc n <= n"; |
378 by(Simp_tac 1); |
378 by (Simp_tac 1); |
379 qed "Suc_n_not_le_n"; |
379 qed "Suc_n_not_le_n"; |
380 |
380 |
381 goalw Nat.thy [le_def] "(i <= 0) = (i = 0)"; |
381 goalw Nat.thy [le_def] "(i <= 0) = (i = 0)"; |
382 by(nat_ind_tac "i" 1); |
382 by (nat_ind_tac "i" 1); |
383 by(ALLGOALS Asm_simp_tac); |
383 by (ALLGOALS Asm_simp_tac); |
384 qed "le_0"; |
384 qed "le_0"; |
385 |
385 |
386 Addsimps [less_not_refl, |
386 Addsimps [less_not_refl, |
387 less_Suc_eq, le0, le_0, |
387 less_Suc_eq, le0, le_0, |
388 Suc_Suc_eq, Suc_n_not_le_n, |
388 Suc_Suc_eq, Suc_n_not_le_n, |
411 goalw Nat.thy [le_def] "!!m. ~ m <= n ==> n<(m::nat)"; |
411 goalw Nat.thy [le_def] "!!m. ~ m <= n ==> n<(m::nat)"; |
412 by (fast_tac HOL_cs 1); |
412 by (fast_tac HOL_cs 1); |
413 qed "not_leE"; |
413 qed "not_leE"; |
414 |
414 |
415 goalw Nat.thy [le_def] "!!m. m < n ==> Suc(m) <= n"; |
415 goalw Nat.thy [le_def] "!!m. m < n ==> Suc(m) <= n"; |
416 by(Simp_tac 1); |
416 by (Simp_tac 1); |
417 by (fast_tac (HOL_cs addEs [less_anti_refl,less_asym]) 1); |
417 by (fast_tac (HOL_cs addEs [less_anti_refl,less_asym]) 1); |
418 qed "lessD"; |
418 qed "lessD"; |
419 |
419 |
420 goalw Nat.thy [le_def] "!!m. Suc(m) <= n ==> m <= n"; |
420 goalw Nat.thy [le_def] "!!m. Suc(m) <= n ==> m <= n"; |
421 by(Asm_full_simp_tac 1); |
421 by (Asm_full_simp_tac 1); |
422 by(fast_tac HOL_cs 1); |
422 by (fast_tac HOL_cs 1); |
423 qed "Suc_leD"; |
423 qed "Suc_leD"; |
424 |
424 |
425 goalw Nat.thy [le_def] "!!m. m <= n ==> m <= Suc n"; |
425 goalw Nat.thy [le_def] "!!m. m <= n ==> m <= Suc n"; |
426 by (fast_tac (HOL_cs addDs [Suc_lessD]) 1); |
426 by (fast_tac (HOL_cs addDs [Suc_lessD]) 1); |
427 qed "le_SucI"; |
427 qed "le_SucI"; |
445 goal Nat.thy "(x <= (y::nat)) = (x < y | x=y)"; |
445 goal Nat.thy "(x <= (y::nat)) = (x < y | x=y)"; |
446 by (REPEAT(ares_tac [iffI,less_or_eq_imp_le,le_imp_less_or_eq] 1)); |
446 by (REPEAT(ares_tac [iffI,less_or_eq_imp_le,le_imp_less_or_eq] 1)); |
447 qed "le_eq_less_or_eq"; |
447 qed "le_eq_less_or_eq"; |
448 |
448 |
449 goal Nat.thy "n <= (n::nat)"; |
449 goal Nat.thy "n <= (n::nat)"; |
450 by(simp_tac (!simpset addsimps [le_eq_less_or_eq]) 1); |
450 by (simp_tac (!simpset addsimps [le_eq_less_or_eq]) 1); |
451 qed "le_refl"; |
451 qed "le_refl"; |
452 |
452 |
453 val prems = goal Nat.thy "!!i. [| i <= j; j < k |] ==> i < (k::nat)"; |
453 val prems = goal Nat.thy "!!i. [| i <= j; j < k |] ==> i < (k::nat)"; |
454 by (dtac le_imp_less_or_eq 1); |
454 by (dtac le_imp_less_or_eq 1); |
455 by (fast_tac (HOL_cs addIs [less_trans]) 1); |
455 by (fast_tac (HOL_cs addIs [less_trans]) 1); |