equal
deleted
inserted
replaced
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" |