src/HOL/Nat.ML
changeset 1264 3eb91524b938
parent 1024 b86042000035
child 1301 42782316d510
equal deleted inserted replaced
1263:290c4dfc34ba 1264:3eb91524b938
   108 by (REPEAT (resolve_tac [Rep_Nat, Suc_RepI] 1));
   108 by (REPEAT (resolve_tac [Rep_Nat, Suc_RepI] 1));
   109 by (dtac (inj_Suc_Rep RS injD) 1);
   109 by (dtac (inj_Suc_Rep RS injD) 1);
   110 by (etac (inj_Rep_Nat RS injD) 1);
   110 by (etac (inj_Rep_Nat RS injD) 1);
   111 qed "inj_Suc";
   111 qed "inj_Suc";
   112 
   112 
   113 val Suc_inject = inj_Suc RS injD;;
   113 val Suc_inject = inj_Suc RS injD;
   114 
   114 
   115 goal Nat.thy "(Suc(m)=Suc(n)) = (m=n)";
   115 goal Nat.thy "(Suc(m)=Suc(n)) = (m=n)";
   116 by (EVERY1 [rtac iffI, etac Suc_inject, etac arg_cong]); 
   116 by (EVERY1 [rtac iffI, etac Suc_inject, etac arg_cong]); 
   117 qed "Suc_Suc_eq";
   117 qed "Suc_Suc_eq";
   118 
   118 
   119 goal Nat.thy "n ~= Suc(n)";
   119 goal Nat.thy "n ~= Suc(n)";
   120 by (nat_ind_tac "n" 1);
   120 by (nat_ind_tac "n" 1);
   121 by (ALLGOALS(asm_simp_tac (HOL_ss addsimps [Zero_not_Suc,Suc_Suc_eq])));
   121 by (ALLGOALS(asm_simp_tac (!simpset addsimps [Zero_not_Suc,Suc_Suc_eq])));
   122 qed "n_not_Suc_n";
   122 qed "n_not_Suc_n";
   123 
   123 
   124 val Suc_n_not_n = n_not_Suc_n RS not_sym;
   124 val Suc_n_not_n = n_not_Suc_n RS not_sym;
   125 
   125 
   126 (*** nat_case -- the selection operator for nat ***)
   126 (*** nat_case -- the selection operator for nat ***)
   162 
   162 
   163 (** conversion rules **)
   163 (** conversion rules **)
   164 
   164 
   165 goal Nat.thy "nat_rec 0 c h = c";
   165 goal Nat.thy "nat_rec 0 c h = c";
   166 by (rtac (nat_rec_unfold RS trans) 1);
   166 by (rtac (nat_rec_unfold RS trans) 1);
   167 by (simp_tac (HOL_ss addsimps [nat_case_0]) 1);
   167 by (simp_tac (!simpset addsimps [nat_case_0]) 1);
   168 qed "nat_rec_0";
   168 qed "nat_rec_0";
   169 
   169 
   170 goal Nat.thy "nat_rec (Suc n) c h = h n (nat_rec n c h)";
   170 goal Nat.thy "nat_rec (Suc n) c h = h n (nat_rec n c h)";
   171 by (rtac (nat_rec_unfold RS trans) 1);
   171 by (rtac (nat_rec_unfold RS trans) 1);
   172 by (simp_tac (HOL_ss addsimps [nat_case_Suc, pred_natI, cut_apply]) 1);
   172 by (simp_tac (!simpset addsimps [nat_case_Suc, pred_natI, cut_apply]) 1);
   173 qed "nat_rec_Suc";
   173 qed "nat_rec_Suc";
   174 
   174 
   175 (*These 2 rules ease the use of primitive recursion.  NOTE USE OF == *)
   175 (*These 2 rules ease the use of primitive recursion.  NOTE USE OF == *)
   176 val [rew] = goal Nat.thy
   176 val [rew] = goal Nat.thy
   177     "[| !!n. f(n) == nat_rec n c h |] ==> f(0) = c";
   177     "[| !!n. f(n) == nat_rec n c h |] ==> f(0) = c";
   326 qed "less_linear";
   326 qed "less_linear";
   327 
   327 
   328 (*Can be used with less_Suc_eq to get n=m | n<m *)
   328 (*Can be used with less_Suc_eq to get n=m | n<m *)
   329 goal Nat.thy "(~ m < n) = (n < Suc(m))";
   329 goal Nat.thy "(~ m < n) = (n < Suc(m))";
   330 by (res_inst_tac [("m","m"),("n","n")] diff_induct 1);
   330 by (res_inst_tac [("m","m"),("n","n")] diff_induct 1);
   331 by(ALLGOALS(asm_simp_tac (HOL_ss addsimps
   331 by(ALLGOALS(asm_simp_tac (!simpset addsimps
   332                           [not_less0,zero_less_Suc,Suc_less_eq])));
   332                           [not_less0,zero_less_Suc,Suc_less_eq])));
   333 qed "not_less_eq";
   333 qed "not_less_eq";
   334 
   334 
   335 (*Complete induction, aka course-of-values induction*)
   335 (*Complete induction, aka course-of-values induction*)
   336 val prems = goalw Nat.thy [less_def]
   336 val prems = goalw Nat.thy [less_def]
   344 
   344 
   345 goalw Nat.thy [le_def] "0 <= n";
   345 goalw Nat.thy [le_def] "0 <= n";
   346 by (rtac not_less0 1);
   346 by (rtac not_less0 1);
   347 qed "le0";
   347 qed "le0";
   348 
   348 
   349 val nat_simps = [not_less0, less_not_refl, zero_less_Suc, lessI, 
   349 Addsimps [not_less0, less_not_refl, zero_less_Suc, lessI, 
   350 		 Suc_less_eq, less_Suc_eq, le0, not_Suc_n_less_n,
   350           Suc_less_eq, less_Suc_eq, le0, not_Suc_n_less_n,
   351 		 Suc_not_Zero, Zero_not_Suc, Suc_Suc_eq,
   351           Suc_not_Zero, Zero_not_Suc, Suc_Suc_eq,
   352 		 n_not_Suc_n, Suc_n_not_n,
   352           n_not_Suc_n, Suc_n_not_n,
   353 		 nat_case_0, nat_case_Suc, nat_rec_0, nat_rec_Suc];
   353           nat_case_0, nat_case_Suc, nat_rec_0, nat_rec_Suc];
   354 
       
   355 val nat_ss0 = sum_ss  addsimps  nat_simps;
       
   356 
   354 
   357 (*Prevents simplification of f and g: much faster*)
   355 (*Prevents simplification of f and g: much faster*)
   358 qed_goal "nat_case_weak_cong" Nat.thy
   356 qed_goal "nat_case_weak_cong" Nat.thy
   359   "m=n ==> nat_case a f m = nat_case a f n"
   357   "m=n ==> nat_case a f m = nat_case a f n"
   360   (fn [prem] => [rtac (prem RS arg_cong) 1]);
   358   (fn [prem] => [rtac (prem RS arg_cong) 1]);
   376 goalw Nat.thy [le_def] "!!m. ~ m <= n ==> n<(m::nat)";
   374 goalw Nat.thy [le_def] "!!m. ~ m <= n ==> n<(m::nat)";
   377 by (fast_tac HOL_cs 1);
   375 by (fast_tac HOL_cs 1);
   378 qed "not_leE";
   376 qed "not_leE";
   379 
   377 
   380 goalw Nat.thy [le_def] "!!m. m < n ==> Suc(m) <= n";
   378 goalw Nat.thy [le_def] "!!m. m < n ==> Suc(m) <= n";
   381 by(simp_tac nat_ss0 1);
   379 by(Simp_tac 1);
   382 by (fast_tac (HOL_cs addEs [less_anti_refl,less_asym]) 1);
   380 by (fast_tac (HOL_cs addEs [less_anti_refl,less_asym]) 1);
   383 qed "lessD";
   381 qed "lessD";
   384 
   382 
   385 goalw Nat.thy [le_def] "!!m. Suc(m) <= n ==> m <= n";
   383 goalw Nat.thy [le_def] "!!m. Suc(m) <= n ==> m <= n";
   386 by(asm_full_simp_tac nat_ss0 1);
   384 by(Asm_full_simp_tac 1);
   387 by(fast_tac HOL_cs 1);
   385 by(fast_tac HOL_cs 1);
   388 qed "Suc_leD";
   386 qed "Suc_leD";
   389 
   387 
   390 goalw Nat.thy [le_def] "!!m. m < n ==> m <= (n::nat)";
   388 goalw Nat.thy [le_def] "!!m. m < n ==> m <= (n::nat)";
   391 by (fast_tac (HOL_cs addEs [less_asym]) 1);
   389 by (fast_tac (HOL_cs addEs [less_asym]) 1);
   405 goal Nat.thy "(x <= (y::nat)) = (x < y | x=y)";
   403 goal Nat.thy "(x <= (y::nat)) = (x < y | x=y)";
   406 by (REPEAT(ares_tac [iffI,less_or_eq_imp_le,le_imp_less_or_eq] 1));
   404 by (REPEAT(ares_tac [iffI,less_or_eq_imp_le,le_imp_less_or_eq] 1));
   407 qed "le_eq_less_or_eq";
   405 qed "le_eq_less_or_eq";
   408 
   406 
   409 goal Nat.thy "n <= (n::nat)";
   407 goal Nat.thy "n <= (n::nat)";
   410 by(simp_tac (HOL_ss addsimps [le_eq_less_or_eq]) 1);
   408 by(simp_tac (!simpset addsimps [le_eq_less_or_eq]) 1);
   411 qed "le_refl";
   409 qed "le_refl";
   412 
   410 
   413 val prems = goal Nat.thy "!!i. [| i <= j; j < k |] ==> i < (k::nat)";
   411 val prems = goal Nat.thy "!!i. [| i <= j; j < k |] ==> i < (k::nat)";
   414 by (dtac le_imp_less_or_eq 1);
   412 by (dtac le_imp_less_or_eq 1);
   415 by (fast_tac (HOL_cs addIs [less_trans]) 1);
   413 by (fast_tac (HOL_cs addIs [less_trans]) 1);
   429 by (EVERY1[dtac le_imp_less_or_eq, dtac le_imp_less_or_eq,
   427 by (EVERY1[dtac le_imp_less_or_eq, dtac le_imp_less_or_eq,
   430           fast_tac (HOL_cs addEs [less_anti_refl,less_asym])]);
   428           fast_tac (HOL_cs addEs [less_anti_refl,less_asym])]);
   431 qed "le_anti_sym";
   429 qed "le_anti_sym";
   432 
   430 
   433 goal Nat.thy "(Suc(n) <= Suc(m)) = (n <= m)";
   431 goal Nat.thy "(Suc(n) <= Suc(m)) = (n <= m)";
   434 by (simp_tac (nat_ss0 addsimps [le_eq_less_or_eq]) 1);
   432 by (simp_tac (!simpset addsimps [le_eq_less_or_eq]) 1);
   435 qed "Suc_le_mono";
   433 qed "Suc_le_mono";
   436 
   434 
   437 val nat_ss = nat_ss0 addsimps [le_refl,Suc_le_mono];
   435 Addsimps [le_refl,Suc_le_mono];