src/HOL/Transitive_Closure.thy
changeset 79806 ba8fb71587ae
parent 79773 0e8620af9c91
child 79937 d26c53bc6ce1
equal deleted inserted replaced
79804:1f7dcfdb3e67 79806:ba8fb71587ae
    91 lemma reflclp_idemp [simp]: "(P\<^sup>=\<^sup>=)\<^sup>=\<^sup>= = P\<^sup>=\<^sup>="
    91 lemma reflclp_idemp [simp]: "(P\<^sup>=\<^sup>=)\<^sup>=\<^sup>= = P\<^sup>=\<^sup>="
    92   by blast
    92   by blast
    93 
    93 
    94 lemma reflclp_ident_if_reflp[simp]: "reflp R \<Longrightarrow> R\<^sup>=\<^sup>= = R"
    94 lemma reflclp_ident_if_reflp[simp]: "reflp R \<Longrightarrow> R\<^sup>=\<^sup>= = R"
    95   by (auto dest: reflpD)
    95   by (auto dest: reflpD)
       
    96 
       
    97 text \<open>The following are special cases of @{thm [source] reflclp_ident_if_reflp},
       
    98 but they appear duplicated in multiple, independent theories, which causes name clashes.\<close>
       
    99 
       
   100 lemma (in preorder) reflclp_less_eq[simp]: "(\<le>)\<^sup>=\<^sup>= = (\<le>)"
       
   101   using reflp_on_le by (simp only: reflclp_ident_if_reflp)
       
   102 
       
   103 lemma (in preorder) reflclp_greater_eq[simp]: "(\<ge>)\<^sup>=\<^sup>= = (\<ge>)"
       
   104   using reflp_on_ge by (simp only: reflclp_ident_if_reflp)
    96 
   105 
    97 
   106 
    98 subsection \<open>Reflexive-transitive closure\<close>
   107 subsection \<open>Reflexive-transitive closure\<close>
    99 
   108 
   100 lemma r_into_rtrancl [intro]: "\<And>p. p \<in> r \<Longrightarrow> p \<in> r\<^sup>*"
   109 lemma r_into_rtrancl [intro]: "\<And>p. p \<in> r \<Longrightarrow> p \<in> r\<^sup>*"
   339 next
   348 next
   340   fix x y
   349   fix x y
   341   show "R x y \<Longrightarrow> R\<^sup>*\<^sup>* x y"
   350   show "R x y \<Longrightarrow> R\<^sup>*\<^sup>* x y"
   342     using r_into_rtranclp .
   351     using r_into_rtranclp .
   343 qed
   352 qed
       
   353 
       
   354 text \<open>The following are special cases of @{thm [source] rtranclp_ident_if_reflp_and_transp},
       
   355 but they appear duplicated in multiple, independent theories, which causes name clashes.\<close>
       
   356 
       
   357 lemma (in preorder) rtranclp_less_eq[simp]: "(\<le>)\<^sup>*\<^sup>* = (\<le>)"
       
   358   using reflp_on_le transp_on_le by (simp only: rtranclp_ident_if_reflp_and_transp)
       
   359 
       
   360 lemma (in preorder) rtranclp_greater_eq[simp]: "(\<ge>)\<^sup>*\<^sup>* = (\<ge>)"
       
   361   using reflp_on_ge transp_on_ge by (simp only: rtranclp_ident_if_reflp_and_transp)
   344 
   362 
   345 
   363 
   346 subsection \<open>Transitive closure\<close>
   364 subsection \<open>Transitive closure\<close>
   347 
   365 
   348 lemma totalp_on_tranclp: "totalp_on A R \<Longrightarrow> totalp_on A (tranclp R)"
   366 lemma totalp_on_tranclp: "totalp_on A R \<Longrightarrow> totalp_on A (tranclp R)"
   775   fix x y
   793   fix x y
   776   show "R x y \<Longrightarrow> R\<^sup>+\<^sup>+ x y"
   794   show "R x y \<Longrightarrow> R\<^sup>+\<^sup>+ x y"
   777     using tranclp.r_into_trancl .
   795     using tranclp.r_into_trancl .
   778 qed
   796 qed
   779 
   797 
       
   798 text \<open>The following are special cases of @{thm [source] tranclp_ident_if_transp},
       
   799 but they appear duplicated in multiple, independent theories, which causes name clashes.\<close>
       
   800 
       
   801 lemma (in preorder) tranclp_less[simp]: "(<)\<^sup>+\<^sup>+ = (<)"
       
   802   using transp_on_less by (simp only: tranclp_ident_if_transp)
       
   803 
       
   804 lemma (in preorder) tranclp_less_eq[simp]: "(\<le>)\<^sup>+\<^sup>+ = (\<le>)"
       
   805   using transp_on_le by (simp only: tranclp_ident_if_transp)
       
   806 
       
   807 lemma (in preorder) tranclp_greater[simp]: "(>)\<^sup>+\<^sup>+ = (>)"
       
   808   using transp_on_greater by (simp only: tranclp_ident_if_transp)
       
   809 
       
   810 lemma (in preorder) tranclp_greater_eq[simp]: "(\<ge>)\<^sup>+\<^sup>+ = (\<ge>)"
       
   811   using transp_on_ge by (simp only: tranclp_ident_if_transp)
   780 
   812 
   781 subsection \<open>Symmetric closure\<close>
   813 subsection \<open>Symmetric closure\<close>
   782 
   814 
   783 definition symclp :: "('a \<Rightarrow> 'a \<Rightarrow> bool) \<Rightarrow> 'a \<Rightarrow> 'a \<Rightarrow> bool"
   815 definition symclp :: "('a \<Rightarrow> 'a \<Rightarrow> bool) \<Rightarrow> 'a \<Rightarrow> 'a \<Rightarrow> bool"
   784 where "symclp r x y \<longleftrightarrow> r x y \<or> r y x"
   816 where "symclp r x y \<longleftrightarrow> r x y \<or> r y x"