54 |
54 |
55 (*Mathematical induction*) |
55 (*Mathematical induction*) |
56 val major::prems = goal Nat.thy |
56 val major::prems = goal Nat.thy |
57 "[| n: nat; P(0); !!x. [| x: nat; P(x) |] ==> P(succ(x)) |] ==> P(n)"; |
57 "[| n: nat; P(0); !!x. [| x: nat; P(x) |] ==> P(succ(x)) |] ==> P(n)"; |
58 by (rtac ([nat_def, nat_bnd_mono, major] MRS def_induct) 1); |
58 by (rtac ([nat_def, nat_bnd_mono, major] MRS def_induct) 1); |
59 by (fast_tac (!claset addIs prems) 1); |
59 by (fast_tac (claset() addIs prems) 1); |
60 qed "nat_induct"; |
60 qed "nat_induct"; |
61 |
61 |
62 (*Perform induction on n, then prove the n:nat subgoal using prems. *) |
62 (*Perform induction on n, then prove the n:nat subgoal using prems. *) |
63 fun nat_ind_tac a prems i = |
63 fun nat_ind_tac a prems i = |
64 EVERY [res_inst_tac [("n",a)] nat_induct i, |
64 EVERY [res_inst_tac [("n",a)] nat_induct i, |
91 by (etac nat_induct 1); |
91 by (etac nat_induct 1); |
92 by (REPEAT (ares_tac [empty_subsetI,succ_subsetI] 1)); |
92 by (REPEAT (ares_tac [empty_subsetI,succ_subsetI] 1)); |
93 qed "Ord_nat"; |
93 qed "Ord_nat"; |
94 |
94 |
95 goalw Nat.thy [Limit_def] "Limit(nat)"; |
95 goalw Nat.thy [Limit_def] "Limit(nat)"; |
96 by (safe_tac (!claset addSIs [ltI, nat_succI, Ord_nat])); |
96 by (safe_tac (claset() addSIs [ltI, nat_succI, Ord_nat])); |
97 by (etac ltD 1); |
97 by (etac ltD 1); |
98 qed "Limit_nat"; |
98 qed "Limit_nat"; |
99 |
99 |
100 Addsimps [Ord_nat, Limit_nat]; |
100 Addsimps [Ord_nat, Limit_nat]; |
101 AddSIs [Ord_nat, Limit_nat]; |
101 AddSIs [Ord_nat, Limit_nat]; |
102 |
102 |
103 goal Nat.thy "!!i. Limit(i) ==> nat le i"; |
103 goal Nat.thy "!!i. Limit(i) ==> nat le i"; |
104 by (rtac subset_imp_le 1); |
104 by (rtac subset_imp_le 1); |
105 by (rtac subsetI 1); |
105 by (rtac subsetI 1); |
106 by (etac nat_induct 1); |
106 by (etac nat_induct 1); |
107 by (blast_tac (!claset addIs [Limit_has_succ RS ltD, ltI, Limit_is_Ord]) 2); |
107 by (blast_tac (claset() addIs [Limit_has_succ RS ltD, ltI, Limit_is_Ord]) 2); |
108 by (REPEAT (ares_tac [Limit_has_0 RS ltD, |
108 by (REPEAT (ares_tac [Limit_has_0 RS ltD, |
109 Ord_nat, Limit_is_Ord] 1)); |
109 Ord_nat, Limit_is_Ord] 1)); |
110 qed "nat_le_Limit"; |
110 qed "nat_le_Limit"; |
111 |
111 |
112 (* succ(i): nat ==> i: nat *) |
112 (* succ(i): nat ==> i: nat *) |
132 \ !!x. [| x: nat; m le x; P(x) |] ==> P(succ(x)) \ |
132 \ !!x. [| x: nat; m le x; P(x) |] ==> P(succ(x)) \ |
133 \ |] ==> m le n --> P(m) --> P(n)"; |
133 \ |] ==> m le n --> P(m) --> P(n)"; |
134 by (nat_ind_tac "n" prems 1); |
134 by (nat_ind_tac "n" prems 1); |
135 by (ALLGOALS |
135 by (ALLGOALS |
136 (asm_simp_tac |
136 (asm_simp_tac |
137 (!simpset addsimps (prems@distrib_simps@[le0_iff, le_succ_iff])))); |
137 (simpset() addsimps (prems@distrib_simps@[le0_iff, le_succ_iff])))); |
138 qed "nat_induct_from_lemma"; |
138 qed "nat_induct_from_lemma"; |
139 |
139 |
140 (*Induction starting from m rather than 0*) |
140 (*Induction starting from m rather than 0*) |
141 val prems = goal Nat.thy |
141 val prems = goal Nat.thy |
142 "[| m le n; m: nat; n: nat; \ |
142 "[| m le n; m: nat; n: nat; \ |
184 qed "succ_lt_induct"; |
184 qed "succ_lt_induct"; |
185 |
185 |
186 (** nat_case **) |
186 (** nat_case **) |
187 |
187 |
188 goalw Nat.thy [nat_case_def] "nat_case(a,b,0) = a"; |
188 goalw Nat.thy [nat_case_def] "nat_case(a,b,0) = a"; |
189 by (blast_tac (!claset addIs [the_equality]) 1); |
189 by (blast_tac (claset() addIs [the_equality]) 1); |
190 qed "nat_case_0"; |
190 qed "nat_case_0"; |
191 |
191 |
192 goalw Nat.thy [nat_case_def] "nat_case(a,b,succ(m)) = b(m)"; |
192 goalw Nat.thy [nat_case_def] "nat_case(a,b,succ(m)) = b(m)"; |
193 by (blast_tac (!claset addIs [the_equality]) 1); |
193 by (blast_tac (claset() addIs [the_equality]) 1); |
194 qed "nat_case_succ"; |
194 qed "nat_case_succ"; |
195 |
195 |
196 Addsimps [nat_case_0, nat_case_succ]; |
196 Addsimps [nat_case_0, nat_case_succ]; |
197 |
197 |
198 val major::prems = goal Nat.thy |
198 val major::prems = goal Nat.thy |
199 "[| n: nat; a: C(0); !!m. m: nat ==> b(m): C(succ(m)) \ |
199 "[| n: nat; a: C(0); !!m. m: nat ==> b(m): C(succ(m)) \ |
200 \ |] ==> nat_case(a,b,n) : C(n)"; |
200 \ |] ==> nat_case(a,b,n) : C(n)"; |
201 by (rtac (major RS nat_induct) 1); |
201 by (rtac (major RS nat_induct) 1); |
202 by (ALLGOALS (asm_simp_tac (!simpset addsimps prems))); |
202 by (ALLGOALS (asm_simp_tac (simpset() addsimps prems))); |
203 qed "nat_case_type"; |
203 qed "nat_case_type"; |
204 |
204 |
205 |
205 |
206 (** nat_rec -- used to define eclose and transrec, then obsolete; |
206 (** nat_rec -- used to define eclose and transrec, then obsolete; |
207 rec, from arith.ML, has fewer typing conditions **) |
207 rec, from arith.ML, has fewer typing conditions **) |
214 qed "nat_rec_0"; |
214 qed "nat_rec_0"; |
215 |
215 |
216 val [prem] = goal Nat.thy |
216 val [prem] = goal Nat.thy |
217 "m: nat ==> nat_rec(succ(m),a,b) = b(m, nat_rec(m,a,b))"; |
217 "m: nat ==> nat_rec(succ(m),a,b) = b(m, nat_rec(m,a,b))"; |
218 by (rtac nat_rec_trans 1); |
218 by (rtac nat_rec_trans 1); |
219 by (simp_tac (!simpset addsimps [prem, Memrel_iff, vimage_singleton_iff]) 1); |
219 by (simp_tac (simpset() addsimps [prem, Memrel_iff, vimage_singleton_iff]) 1); |
220 qed "nat_rec_succ"; |
220 qed "nat_rec_succ"; |
221 |
221 |
222 (** The union of two natural numbers is a natural number -- their maximum **) |
222 (** The union of two natural numbers is a natural number -- their maximum **) |
223 |
223 |
224 goal Nat.thy "!!i j. [| i: nat; j: nat |] ==> i Un j: nat"; |
224 goal Nat.thy "!!i j. [| i: nat; j: nat |] ==> i Un j: nat"; |