equal
deleted
inserted
replaced
110 unfolding permutes_def Fun.swap_def fun_upd_def by auto metis |
110 unfolding permutes_def Fun.swap_def fun_upd_def by auto metis |
111 |
111 |
112 lemma permutes_superset: "p permutes S \<Longrightarrow> (\<forall>x \<in> S - T. p x = x) \<Longrightarrow> p permutes T" |
112 lemma permutes_superset: "p permutes S \<Longrightarrow> (\<forall>x \<in> S - T. p x = x) \<Longrightarrow> p permutes T" |
113 by (simp add: Ball_def permutes_def) metis |
113 by (simp add: Ball_def permutes_def) metis |
114 |
114 |
115 (* Next three lemmas contributed by Lukas Bulwahn *) |
115 lemma permutes_bij_inv_into: \<^marker>\<open>contributor \<open>Lukas Bulwahn\<close>\<close> |
116 lemma permutes_bij_inv_into: |
|
117 fixes A :: "'a set" |
116 fixes A :: "'a set" |
118 and B :: "'b set" |
117 and B :: "'b set" |
119 assumes "p permutes A" |
118 assumes "p permutes A" |
120 and "bij_betw f A B" |
119 and "bij_betw f A B" |
121 shows "(\<lambda>x. if x \<in> B then f (p (inv_into A f x)) else x) permutes B" |
120 shows "(\<lambda>x. if x \<in> B then f (p (inv_into A f x)) else x) permutes B" |
130 fix x |
129 fix x |
131 assume "x \<notin> B" |
130 assume "x \<notin> B" |
132 then show "(if x \<in> B then f (p (inv_into A f x)) else x) = x" by auto |
131 then show "(if x \<in> B then f (p (inv_into A f x)) else x) = x" by auto |
133 qed |
132 qed |
134 |
133 |
135 lemma permutes_image_mset: |
134 lemma permutes_image_mset: \<^marker>\<open>contributor \<open>Lukas Bulwahn\<close>\<close> |
136 assumes "p permutes A" |
135 assumes "p permutes A" |
137 shows "image_mset p (mset_set A) = mset_set A" |
136 shows "image_mset p (mset_set A) = mset_set A" |
138 using assms by (metis image_mset_mset_set bij_betw_imp_inj_on permutes_imp_bij permutes_image) |
137 using assms by (metis image_mset_mset_set bij_betw_imp_inj_on permutes_imp_bij permutes_image) |
139 |
138 |
140 lemma permutes_implies_image_mset_eq: |
139 lemma permutes_implies_image_mset_eq: \<^marker>\<open>contributor \<open>Lukas Bulwahn\<close>\<close> |
141 assumes "p permutes A" "\<And>x. x \<in> A \<Longrightarrow> f x = f' (p x)" |
140 assumes "p permutes A" "\<And>x. x \<in> A \<Longrightarrow> f x = f' (p x)" |
142 shows "image_mset f' (mset_set A) = image_mset f (mset_set A)" |
141 shows "image_mset f' (mset_set A) = image_mset f (mset_set A)" |
143 proof - |
142 proof - |
144 have "f x = f' (p x)" if "x \<in># mset_set A" for x |
143 have "f x = f' (p x)" if "x \<in># mset_set A" for x |
145 using assms(2)[of x] that by (cases "finite A") auto |
144 using assms(2)[of x] that by (cases "finite A") auto |