nat.ML
changeset 45 3d5b2b874e14
parent 40 ac7b7003f177
child 57 194d088c1511
equal deleted inserted replaced
44:64eda8afe2b4 45:3d5b2b874e14
   120 goal Nat.thy "n ~= Suc(n)";
   120 goal Nat.thy "n ~= Suc(n)";
   121 by (nat_ind_tac "n" 1);
   121 by (nat_ind_tac "n" 1);
   122 by (ALLGOALS(asm_simp_tac (HOL_ss addsimps [Zero_not_Suc,Suc_Suc_eq])));
   122 by (ALLGOALS(asm_simp_tac (HOL_ss addsimps [Zero_not_Suc,Suc_Suc_eq])));
   123 val n_not_Suc_n = result();
   123 val n_not_Suc_n = result();
   124 
   124 
       
   125 val Suc_n_not_n = n_not_Suc_n RS not_sym;
       
   126 
   125 (*** nat_case -- the selection operator for nat ***)
   127 (*** nat_case -- the selection operator for nat ***)
   126 
   128 
   127 goalw Nat.thy [nat_case_def] "nat_case(0, a, f) = a";
   129 goalw Nat.thy [nat_case_def] "nat_case(0, a, f) = a";
   128 by (fast_tac (set_cs addIs [select_equality] addEs [Zero_neq_Suc]) 1);
   130 by (fast_tac (set_cs addIs [select_equality] addEs [Zero_neq_Suc]) 1);
   129 val nat_case_0 = result();
   131 val nat_case_0 = result();
   214 by (rtac lessI 1);
   216 by (rtac lessI 1);
   215 val zero_less_Suc = result();
   217 val zero_less_Suc = result();
   216 
   218 
   217 (** Elimination properties **)
   219 (** Elimination properties **)
   218 
   220 
   219 goalw Nat.thy [less_def] "n<m --> ~ m<n::nat";
   221 val prems = goalw Nat.thy [less_def] "n<m ==> ~ m<n::nat";
   220 by (rtac (wf_pred_nat RS wf_trancl RS wf_anti_sym RS notI RS impI) 1);
   222 by(fast_tac (HOL_cs addIs ([wf_pred_nat, wf_trancl RS wf_anti_sym]@prems))1);
   221 by (assume_tac 1);
       
   222 by (assume_tac 1);
       
   223 val less_not_sym = result();
   223 val less_not_sym = result();
   224 
   224 
   225 (* [| n<m; m<n |] ==> R *)
   225 (* [| n<m; m<n |] ==> R *)
   226 val less_anti_sym = standard (less_not_sym RS mp RS notE);
   226 val less_anti_sym = standard (less_not_sym RS notE);
   227 
       
   228 
   227 
   229 goalw Nat.thy [less_def] "~ n<n::nat";
   228 goalw Nat.thy [less_def] "~ n<n::nat";
   230 by (rtac notI 1);
   229 by (rtac notI 1);
   231 by (etac (wf_pred_nat RS wf_trancl RS wf_anti_refl) 1);
   230 by (etac (wf_pred_nat RS wf_trancl RS wf_anti_refl) 1);
   232 val less_not_refl = result();
   231 val less_not_refl = result();
   233 
   232 
   234 (* n<n ==> R *)
   233 (* n<n ==> R *)
   235 val less_anti_refl = standard (less_not_refl RS notE);
   234 val less_anti_refl = standard (less_not_refl RS notE);
       
   235 
       
   236 goal Nat.thy "!!m. n<m ==> m ~= n::nat";
       
   237 by(fast_tac (HOL_cs addEs [less_anti_refl]) 1);
       
   238 val less_not_refl2 = result();
   236 
   239 
   237 
   240 
   238 val major::prems = goalw Nat.thy [less_def]
   241 val major::prems = goalw Nat.thy [less_def]
   239     "[| i<k;  k=Suc(i) ==> P;  !!j. [| i<j;  k=Suc(j) |] ==> P \
   242     "[| i<k;  k=Suc(i) ==> P;  !!j. [| i<j;  k=Suc(j) |] ==> P \
   240 \    |] ==> P";
   243 \    |] ==> P";
   308 
   311 
   309 goal Nat.thy "(Suc(m) < Suc(n)) = (m<n)";
   312 goal Nat.thy "(Suc(m) < Suc(n)) = (m<n)";
   310 by (EVERY1 [rtac iffI, etac Suc_less_SucD, etac Suc_mono]);
   313 by (EVERY1 [rtac iffI, etac Suc_less_SucD, etac Suc_mono]);
   311 val Suc_less_eq = result();
   314 val Suc_less_eq = result();
   312 
   315 
   313 val [major] = goal Nat.thy "Suc(n)<n ==> P";
   316 goal Nat.thy "~(Suc(n) < n)";
   314 by (rtac (major RS Suc_lessD RS less_anti_refl) 1);
   317 by(fast_tac (HOL_cs addEs [Suc_lessD RS less_anti_refl]) 1);
   315 val not_Suc_n_less_n = result();
   318 val not_Suc_n_less_n = result();
   316 
   319 
   317 (*"Less than" is a linear ordering*)
   320 (*"Less than" is a linear ordering*)
   318 goal Nat.thy "m<n | m=n | n<m::nat";
   321 goal Nat.thy "m<n | m=n | n<m::nat";
   319 by (nat_ind_tac "m" 1);
   322 by (nat_ind_tac "m" 1);
   343 goalw Nat.thy [le_def] "0 <= n";
   346 goalw Nat.thy [le_def] "0 <= n";
   344 by (rtac not_less0 1);
   347 by (rtac not_less0 1);
   345 val le0 = result();
   348 val le0 = result();
   346 
   349 
   347 val nat_simps = [not_less0, less_not_refl, zero_less_Suc, lessI, 
   350 val nat_simps = [not_less0, less_not_refl, zero_less_Suc, lessI, 
   348 	     Suc_less_eq, less_Suc_eq, le0, 
   351 	     Suc_less_eq, less_Suc_eq, le0, not_Suc_n_less_n,
   349 	     Suc_not_Zero, Zero_not_Suc, Suc_Suc_eq, 
   352 	     Suc_not_Zero, Zero_not_Suc, Suc_Suc_eq,
       
   353              n_not_Suc_n, Suc_n_not_n,
   350 	     nat_case_0, nat_case_Suc, nat_rec_0, nat_rec_Suc];
   354 	     nat_case_0, nat_case_Suc, nat_rec_0, nat_rec_Suc];
   351 
   355 
   352 val nat_ss = sum_ss  addsimps  nat_simps;
   356 val nat_ss = sum_ss  addsimps  nat_simps;
   353 
   357 
   354 (*Prevents simplification of f and g: much faster*)
   358 (*Prevents simplification of f and g: much faster*)
   373 goalw Nat.thy [le_def] "!!m. ~ m <= n ==> n<m::nat";
   377 goalw Nat.thy [le_def] "!!m. ~ m <= n ==> n<m::nat";
   374 by (fast_tac HOL_cs 1);
   378 by (fast_tac HOL_cs 1);
   375 val not_leE = result();
   379 val not_leE = result();
   376 
   380 
   377 goalw Nat.thy [le_def] "!!m. m < n ==> Suc(m) <= n";
   381 goalw Nat.thy [le_def] "!!m. m < n ==> Suc(m) <= n";
   378 by(simp_tac (HOL_ss addsimps [less_Suc_eq]) 1);
   382 by(simp_tac nat_ss 1);
   379 by (fast_tac (HOL_cs addEs [less_anti_refl,less_anti_sym]) 1);
   383 by (fast_tac (HOL_cs addEs [less_anti_refl,less_anti_sym]) 1);
   380 val lessD = result();
   384 val lessD = result();
   381 
   385 
   382 goalw Nat.thy [le_def] "!!m. Suc(m) <= n ==> m <= n";
   386 goalw Nat.thy [le_def] "!!m. Suc(m) <= n ==> m <= n";
   383 by(asm_full_simp_tac (HOL_ss addsimps [less_Suc_eq]) 1);
   387 by(asm_full_simp_tac nat_ss 1);
   384 by(fast_tac HOL_cs 1);
   388 by(fast_tac HOL_cs 1);
   385 val Suc_leD = result();
   389 val Suc_leD = result();
   386 
   390 
   387 goalw Nat.thy [le_def] "!!m. m < n ==> m <= n::nat";
   391 goalw Nat.thy [le_def] "!!m. m < n ==> m <= n::nat";
   388 by (fast_tac (HOL_cs addEs [less_anti_sym]) 1);
   392 by (fast_tac (HOL_cs addEs [less_anti_sym]) 1);