equal
deleted
inserted
replaced
11 (*specialized form of induction needed below*) |
11 (*specialized form of induction needed below*) |
12 val prems = goal Nat.thy "[| P(0); !!n. P(Suc(n)) |] ==> !n. P(n)"; |
12 val prems = goal Nat.thy "[| P(0); !!n. P(Suc(n)) |] ==> !n. P(n)"; |
13 by (EVERY1 [rtac (nat_induct RS allI), resolve_tac prems, resolve_tac prems]); |
13 by (EVERY1 [rtac (nat_induct RS allI), resolve_tac prems, resolve_tac prems]); |
14 qed "nat_exh"; |
14 qed "nat_exh"; |
15 |
15 |
16 goal Puzzle.thy "! n. k=f(n) --> n <= f(n)"; |
16 Goal "! n. k=f(n) --> n <= f(n)"; |
17 by (res_inst_tac [("n","k")] less_induct 1); |
17 by (res_inst_tac [("n","k")] less_induct 1); |
18 by (rtac nat_exh 1); |
18 by (rtac nat_exh 1); |
19 by (Simp_tac 1); |
19 by (Simp_tac 1); |
20 by (rtac impI 1); |
20 by (rtac impI 1); |
21 by (rtac classical 1); |
21 by (rtac classical 1); |
25 by (rtac Suc_leI 1); |
25 by (rtac Suc_leI 1); |
26 by (fast_tac (claset() delrules [order_refl] |
26 by (fast_tac (claset() delrules [order_refl] |
27 addIs [Puzzle.f_ax, le_less_trans]) 1); |
27 addIs [Puzzle.f_ax, le_less_trans]) 1); |
28 val lemma = result() RS spec RS mp; |
28 val lemma = result() RS spec RS mp; |
29 |
29 |
30 goal Puzzle.thy "n <= f(n)"; |
30 Goal "n <= f(n)"; |
31 by (fast_tac (claset() addIs [lemma]) 1); |
31 by (fast_tac (claset() addIs [lemma]) 1); |
32 qed "lemma1"; |
32 qed "lemma1"; |
33 |
33 |
34 goal Puzzle.thy "f(n) < f(Suc(n))"; |
34 Goal "f(n) < f(Suc(n))"; |
35 by (deepen_tac (claset() addIs [Puzzle.f_ax, le_less_trans, lemma1]) 0 1); |
35 by (deepen_tac (claset() addIs [Puzzle.f_ax, le_less_trans, lemma1]) 0 1); |
36 qed "lemma2"; |
36 qed "lemma2"; |
37 |
37 |
38 val prems = goal Puzzle.thy "(!!n. f(n) <= f(Suc(n))) ==> m<n --> f(m) <= f(n)"; |
38 val prems = goal Puzzle.thy "(!!n. f(n) <= f(Suc(n))) ==> m<n --> f(m) <= f(n)"; |
39 by (res_inst_tac[("n","n")]nat_induct 1); |
39 by (res_inst_tac[("n","n")]nat_induct 1); |
51 |
51 |
52 val prems = goal Puzzle.thy "m <= n ==> f(m) <= f(n)"; |
52 val prems = goal Puzzle.thy "m <= n ==> f(m) <= f(n)"; |
53 by (fast_tac (claset() addIs ([mono_lemma,less_imp_le,lemma2]@prems)) 1); |
53 by (fast_tac (claset() addIs ([mono_lemma,less_imp_le,lemma2]@prems)) 1); |
54 qed "f_mono"; |
54 qed "f_mono"; |
55 |
55 |
56 goal Puzzle.thy "f(n) = n"; |
56 Goal "f(n) = n"; |
57 by (rtac le_anti_sym 1); |
57 by (rtac le_anti_sym 1); |
58 by (rtac lemma1 2); |
58 by (rtac lemma1 2); |
59 by (fast_tac (claset() addIs [Puzzle.f_ax,leI] addDs [leD,f_mono,Suc_leI]) 1); |
59 by (fast_tac (claset() addIs [Puzzle.f_ax,leI] addDs [leD,f_mono,Suc_leI]) 1); |
60 result(); |
60 result(); |