src/HOL/Nat.ML
changeset 1552 6f71b5d46700
parent 1531 e5eb247ad13c
child 1618 372880456b5b
equal deleted inserted replaced
1551:4a617e14d12c 1552:6f71b5d46700
   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);