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]; |