253 apply (induct l) |
253 apply (induct l) |
254 apply (simp_all add: le_add1 le_imp_less_Suc) |
254 apply (simp_all add: le_add1 le_imp_less_Suc) |
255 done |
255 done |
256 |
256 |
257 lemma CONSTANT_case: "CONSTANT k l < ack (k, list_add l)" |
257 lemma CONSTANT_case: "CONSTANT k l < ack (k, list_add l)" |
258 apply simp |
258 by simp |
259 done |
|
260 |
259 |
261 lemma PROJ_case [rule_format]: "\<forall>i. PROJ i l < ack (0, list_add l)" |
260 lemma PROJ_case [rule_format]: "\<forall>i. PROJ i l < ack (0, list_add l)" |
262 apply (simp add: PROJ_def) |
261 apply (simp add: PROJ_def) |
263 apply (induct l) |
262 apply (induct l) |
264 apply simp_all |
263 apply (auto simp add: drop_Cons split: nat.split) |
265 apply (rule allI) |
264 apply (blast intro: less_le_trans le_add2) |
266 apply (case_tac i) |
|
267 apply (simp (no_asm_simp) add: le_add1 le_imp_less_Suc) |
|
268 apply (simp (no_asm_simp)) |
|
269 apply (blast intro: less_le_trans intro!: le_add2) |
|
270 done |
265 done |
271 |
266 |
272 |
267 |
273 text {* @{term COMP} case *} |
268 text {* @{term COMP} case *} |
274 |
269 |
275 lemma COMP_map_aux: "\<forall>f \<in> set fs. PRIMREC f \<and> (\<exists>kf. \<forall>l. f l < ack (kf, list_add l)) |
270 lemma COMP_map_aux: "\<forall>f \<in> set fs. PRIMREC f \<and> (\<exists>kf. \<forall>l. f l < ack (kf, list_add l)) |
276 ==> \<exists>k. \<forall>l. list_add (map (\<lambda>f. f l) fs) < ack (k, list_add l)" |
271 ==> \<exists>k. \<forall>l. list_add (map (\<lambda>f. f l) fs) < ack (k, list_add l)" |
277 apply (induct fs) |
272 apply (induct fs) |
278 apply (rule_tac x = 0 in exI) |
273 apply (rule_tac x = 0 in exI) |
279 apply simp |
274 apply simp |
280 apply simp |
275 apply simp |
281 apply (blast intro: add_less_mono ack_add_bound less_trans) |
276 apply (blast intro: add_less_mono ack_add_bound less_trans) |
282 done |
277 done |
283 |
278 |
326 |
321 |
327 lemma PREC_case: |
322 lemma PREC_case: |
328 "\<forall>l. f l < ack (kf, list_add l) ==> |
323 "\<forall>l. f l < ack (kf, list_add l) ==> |
329 \<forall>l. g l < ack (kg, list_add l) ==> |
324 \<forall>l. g l < ack (kg, list_add l) ==> |
330 \<exists>k. \<forall>l. PREC f g l < ack (k, list_add l)" |
325 \<exists>k. \<forall>l. PREC f g l < ack (k, list_add l)" |
331 apply (rule exI) |
326 by (metis le_less_trans [OF le_add1 PREC_case_aux] ack_add_bound2) |
332 apply (rule allI) |
|
333 apply (rule le_less_trans [OF le_add1 PREC_case_aux]) |
|
334 apply (blast intro: ack_add_bound2)+ |
|
335 done |
|
336 |
327 |
337 lemma ack_bounds_PRIMREC: "PRIMREC f ==> \<exists>k. \<forall>l. f l < ack (k, list_add l)" |
328 lemma ack_bounds_PRIMREC: "PRIMREC f ==> \<exists>k. \<forall>l. f l < ack (k, list_add l)" |
338 apply (erule PRIMREC.induct) |
329 apply (erule PRIMREC.induct) |
339 apply (blast intro: SC_case CONSTANT_case PROJ_case COMP_case PREC_case)+ |
330 apply (blast intro: SC_case CONSTANT_case PROJ_case COMP_case PREC_case)+ |
340 done |
331 done |