src/HOL/Library/Permutations.thy
changeset 69895 6b03a8cf092d
parent 67673 c8caefb20564
child 72302 d7d90ed4c74e
equal deleted inserted replaced
69894:2eade8651b93 69895:6b03a8cf092d
   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