src/HOL/Transitive_Closure.thy
changeset 35216 7641e8d831d2
parent 34970 4c316d777461
child 37391 476270a6c2dc
equal deleted inserted replaced
35215:a03462cbf86f 35216:7641e8d831d2
   462   -- {* primitive recursion for @{text trancl} over finite relations *}
   462   -- {* primitive recursion for @{text trancl} over finite relations *}
   463   apply (rule equalityI)
   463   apply (rule equalityI)
   464    apply (rule subsetI)
   464    apply (rule subsetI)
   465    apply (simp only: split_tupled_all)
   465    apply (simp only: split_tupled_all)
   466    apply (erule trancl_induct, blast)
   466    apply (erule trancl_induct, blast)
   467    apply (blast intro: rtrancl_into_trancl1 trancl_into_rtrancl r_into_trancl trancl_trans)
   467    apply (blast intro: rtrancl_into_trancl1 trancl_into_rtrancl trancl_trans)
   468   apply (rule subsetI)
   468   apply (rule subsetI)
   469   apply (blast intro: trancl_mono rtrancl_mono
   469   apply (blast intro: trancl_mono rtrancl_mono
   470     [THEN [2] rev_subsetD] rtrancl_trancl_trancl rtrancl_into_trancl2)
   470     [THEN [2] rev_subsetD] rtrancl_trancl_trancl rtrancl_into_trancl2)
   471   done
   471   done
   472 
   472 
   501       "!!y z.[| r y z;  r^++ z b;  P(z) |] ==> P(y)"
   501       "!!y z.[| r y z;  r^++ z b;  P(z) |] ==> P(y)"
   502   shows "P a"
   502   shows "P a"
   503   apply (rule tranclp_induct [OF tranclp_converseI, OF conversepI, OF major])
   503   apply (rule tranclp_induct [OF tranclp_converseI, OF conversepI, OF major])
   504    apply (rule cases)
   504    apply (rule cases)
   505    apply (erule conversepD)
   505    apply (erule conversepD)
   506   apply (blast intro: prems dest!: tranclp_converseD conversepD)
   506   apply (blast intro: assms dest!: tranclp_converseD)
   507   done
   507   done
   508 
   508 
   509 lemmas converse_trancl_induct = converse_tranclp_induct [to_set]
   509 lemmas converse_trancl_induct = converse_tranclp_induct [to_set]
   510 
   510 
   511 lemma tranclpD: "R^++ x y ==> EX z. R x z \<and> R^** z y"
   511 lemma tranclpD: "R^++ x y ==> EX z. R x z \<and> R^** z y"