src/HOL/ex/Primrec.thy
changeset 24551 af7ef6bcc149
parent 23776 2215169c93fa
child 24742 73b8b42a36b6
equal deleted inserted replaced
24550:ec228ae5a620 24551:af7ef6bcc149
   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