# HG changeset patch # User desharna # Date 1741873652 -3600 # Node ID 8183a7d8a69512dd3f86a53e131f9ab89d7f47c8 # Parent 3ef81164c3f781e413033370922f8114b0022393 added lemma quotient_disj_strong diff -r 3ef81164c3f7 -r 8183a7d8a695 NEWS --- a/NEWS Thu Mar 13 10:39:41 2025 +0100 +++ b/NEWS Thu Mar 13 14:47:32 2025 +0100 @@ -38,6 +38,10 @@ total_relation_ofD trans_relation_of[simp] +* Theory "HOL.Equiv_Relation": + - Added lemmas. + quotient_disj_strong + * Theory "HOL-Library.Multiset": - Renamed lemmas. Minor INCOMPATIBILITY. filter_image_mset ~> filter_mset_image_mset diff -r 3ef81164c3f7 -r 8183a7d8a695 src/HOL/Equiv_Relations.thy --- a/src/HOL/Equiv_Relations.thy Thu Mar 13 10:39:41 2025 +0100 +++ b/src/HOL/Equiv_Relations.thy Thu Mar 13 14:47:32 2025 +0100 @@ -135,18 +135,31 @@ lemma Union_quotient: "equiv A r \ \(A//r) = A" unfolding equiv_def refl_on_def quotient_def by blast -lemma quotient_disj: - assumes "equiv A r" and "X \ A//r" and "Y \ A//r" +lemma quotient_disj_strong: + assumes "r \ A \ A" and "sym_on A r" and "trans_on A r" and "X \ A//r" and "Y \ A//r" shows "X = Y \ X \ Y = {}" proof - - have "sym r" and "trans r" - using \equiv A r\ - by (auto elim: equivE) - thus ?thesis - using assms(2,3) - unfolding quotient_def equiv_def trans_def sym_def by blast + obtain x where "x \ A" and "X = {x'. (x, x') \ r}" + using \X \ A//r\ unfolding quotient_def UN_iff by blast + + moreover obtain y where "y \ A" and "Y = {y'. (y, y') \ r}" + using \Y \ A//r\ unfolding quotient_def UN_iff by blast + + have f8: "\a aa. (aa, a) \ r \ (a, aa) \ r" + using \r \ A \ A\[unfolded subset_eq] \sym_on A r\[THEN sym_onD] by blast + have f9: "\a aa ab. (aa, ab) \ r \ (aa, a) \ r \ (a, ab) \ r" + using \r \ A \ A\[unfolded subset_eq] \trans_on A r\[THEN trans_onD] by blast + then have "\a aa. aa \ Y \ (y, a) \ r \ (a, aa) \ r" + using \Y = {y'. (y, y') \ r}\ by simp + then show ?thesis + using f9 f8 \X = {x'. (x, x') \ r}\ \Y = {y'. (y, y') \ r}\ + Collect_cong disjoint_iff_not_equal mem_Collect_eq by blast qed +lemma quotient_disj: "equiv A r \ X \ A//r \ Y \ A//r \ X = Y \ X \ Y = {}" + by (rule quotient_disj_strong[of r A X Y]) + (auto elim: equivE intro: sym_on_subset trans_on_subset) + lemma quotient_eqI: assumes "equiv A r" "X \ A//r" "Y \ A//r" and xy: "x \ X" "y \ Y" "(x, y) \ r" shows "X = Y"