400 |
400 |
401 goalw thy [le_def] "(m <= n) = (m < Suc n)"; |
401 goalw thy [le_def] "(m <= n) = (m < Suc n)"; |
402 by (rtac not_less_eq 1); |
402 by (rtac not_less_eq 1); |
403 qed "le_eq_less_Suc"; |
403 qed "le_eq_less_Suc"; |
404 |
404 |
|
405 (* m<=n ==> m < Suc n *) |
|
406 bind_thm ("le_imp_less_Suc", le_eq_less_Suc RS iffD1); |
|
407 |
405 goalw thy [le_def] "0 <= n"; |
408 goalw thy [le_def] "0 <= n"; |
406 by (rtac not_less0 1); |
409 by (rtac not_less0 1); |
407 qed "le0"; |
410 qed "le0"; |
408 |
411 |
409 goalw thy [le_def] "~ Suc n <= n"; |
412 goalw thy [le_def] "~ Suc n <= n"; |
462 qed "not_leE"; |
465 qed "not_leE"; |
463 |
466 |
464 goalw thy [le_def] "!!m. m < n ==> Suc(m) <= n"; |
467 goalw thy [le_def] "!!m. m < n ==> Suc(m) <= n"; |
465 by (simp_tac (!simpset addsimps [less_Suc_eq]) 1); |
468 by (simp_tac (!simpset addsimps [less_Suc_eq]) 1); |
466 by (blast_tac (!claset addSEs [less_irrefl,less_asym]) 1); |
469 by (blast_tac (!claset addSEs [less_irrefl,less_asym]) 1); |
467 qed "lessD"; |
470 qed "Suc_leI"; (*formerly called lessD*) |
468 |
471 |
469 goalw thy [le_def] "!!m. Suc(m) <= n ==> m <= n"; |
472 goalw thy [le_def] "!!m. Suc(m) <= n ==> m <= n"; |
470 by (asm_full_simp_tac (!simpset addsimps [less_Suc_eq]) 1); |
473 by (asm_full_simp_tac (!simpset addsimps [less_Suc_eq]) 1); |
471 qed "Suc_leD"; |
474 qed "Suc_leD"; |
472 |
475 |
477 by (cut_facts_tac [less_linear] 1); |
480 by (cut_facts_tac [less_linear] 1); |
478 by (Blast_tac 1); |
481 by (Blast_tac 1); |
479 qed "Suc_le_lessD"; |
482 qed "Suc_le_lessD"; |
480 |
483 |
481 goal thy "(Suc m <= n) = (m < n)"; |
484 goal thy "(Suc m <= n) = (m < n)"; |
482 by (blast_tac (!claset addIs [lessD, Suc_le_lessD]) 1); |
485 by (blast_tac (!claset addIs [Suc_leI, Suc_le_lessD]) 1); |
483 qed "Suc_le_eq"; |
486 qed "Suc_le_eq"; |
484 |
487 |
485 goalw thy [le_def] "!!m. m <= n ==> m <= Suc n"; |
488 goalw thy [le_def] "!!m. m <= n ==> m <= Suc n"; |
486 by (blast_tac (!claset addDs [Suc_lessD]) 1); |
489 by (blast_tac (!claset addDs [Suc_lessD]) 1); |
487 qed "le_SucI"; |
490 qed "le_SucI"; |
491 |
494 |
492 goalw thy [le_def] "!!m. m < n ==> m <= (n::nat)"; |
495 goalw thy [le_def] "!!m. m < n ==> m <= (n::nat)"; |
493 by (blast_tac (!claset addEs [less_asym]) 1); |
496 by (blast_tac (!claset addEs [less_asym]) 1); |
494 qed "less_imp_le"; |
497 qed "less_imp_le"; |
495 |
498 |
|
499 (** Equivalence of m<=n and m<n | m=n **) |
|
500 |
496 goalw thy [le_def] "!!m. m <= n ==> m < n | m=(n::nat)"; |
501 goalw thy [le_def] "!!m. m <= n ==> m < n | m=(n::nat)"; |
497 by (cut_facts_tac [less_linear] 1); |
502 by (cut_facts_tac [less_linear] 1); |
498 by (blast_tac (!claset addEs [less_irrefl,less_asym]) 1); |
503 by (blast_tac (!claset addEs [less_irrefl,less_asym]) 1); |
499 qed "le_imp_less_or_eq"; |
504 qed "le_imp_less_or_eq"; |
500 |
505 |
501 goalw thy [le_def] "!!m. m<n | m=n ==> m <=(n::nat)"; |
506 goalw thy [le_def] "!!m. m<n | m=n ==> m <=(n::nat)"; |
502 by (cut_facts_tac [less_linear] 1); |
507 by (cut_facts_tac [less_linear] 1); |
503 by (blast_tac (!claset addSEs [less_irrefl] addEs [less_asym]) 1); |
508 by (blast_tac (!claset addSEs [less_irrefl] addEs [less_asym]) 1); |
504 qed "less_or_eq_imp_le"; |
509 qed "less_or_eq_imp_le"; |
505 |
510 |
506 goal thy "(x <= (y::nat)) = (x < y | x=y)"; |
511 goal thy "(m <= (n::nat)) = (m < n | m=n)"; |
507 by (REPEAT(ares_tac [iffI,less_or_eq_imp_le,le_imp_less_or_eq] 1)); |
512 by (REPEAT(ares_tac [iffI,less_or_eq_imp_le,le_imp_less_or_eq] 1)); |
508 qed "le_eq_less_or_eq"; |
513 qed "le_eq_less_or_eq"; |
509 |
514 |
510 goal thy "n <= (n::nat)"; |
515 goal thy "n <= (n::nat)"; |
511 by (simp_tac (!simpset addsimps [le_eq_less_or_eq]) 1); |
516 by (simp_tac (!simpset addsimps [le_eq_less_or_eq]) 1); |
640 val less_incr = Suc_mono; |
645 val less_incr = Suc_mono; |
641 val less_decr = Suc_less_SucD; |
646 val less_decr = Suc_less_SucD; |
642 val less_incr_rhs = Suc_mono RS Suc_lessD; |
647 val less_incr_rhs = Suc_mono RS Suc_lessD; |
643 val less_decr_lhs = Suc_lessD; |
648 val less_decr_lhs = Suc_lessD; |
644 val less_trans_Suc = less_trans_Suc; |
649 val less_trans_Suc = less_trans_Suc; |
645 val leI = lessD RS (Suc_le_mono RS iffD1); |
650 val leI = Suc_leI RS (Suc_le_mono RS iffD1); |
646 val not_lessI = leI RS leD |
651 val not_lessI = leI RS leD |
647 val not_leI = prove_goal thy "!!m::nat. n < m ==> ~ m <= n" |
652 val not_leI = prove_goal thy "!!m::nat. n < m ==> ~ m <= n" |
648 (fn _ => [etac swap2 1, etac leD 1]); |
653 (fn _ => [etac swap2 1, etac leD 1]); |
649 val eqI = prove_goal thy "!!m. [| m < Suc n; n < Suc m |] ==> m=n" |
654 val eqI = prove_goal thy "!!m. [| m < Suc n; n < Suc m |] ==> m=n" |
650 (fn _ => [etac less_SucE 1, |
655 (fn _ => [etac less_SucE 1, |