src/HOL/NatDef.ML
changeset 3343 45986997f1fe
parent 3308 da002cef7090
child 3355 0d955bcf8e0a
equal deleted inserted replaced
3342:ec3b55fcb165 3343:45986997f1fe
   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,