diff --git a/src/HOL/Library/List_Permutation.thy b/src/HOL/Library/List_Permutation.thy --- a/src/HOL/Library/List_Permutation.thy +++ b/src/HOL/Library/List_Permutation.thy @@ -1,174 +1,174 @@ (* Title: HOL/Library/List_Permutation.thy Author: Lawrence C Paulson and Thomas M Rasmussen and Norbert Voelker *) section \Permuted Lists\ theory List_Permutation imports Multiset begin -subsection \An inductive definition\\ +subsection \An inductive definition \ldots\ inductive perm :: "'a list \ 'a list \ bool" (infixr \<~~>\ 50) where Nil [intro!]: "[] <~~> []" | swap [intro!]: "y # x # l <~~> x # y # l" | Cons [intro!]: "xs <~~> ys \ z # xs <~~> z # ys" | trans [intro]: "xs <~~> ys \ ys <~~> zs \ xs <~~> zs" proposition perm_refl [iff]: "l <~~> l" by (induct l) auto -text \\that is equivalent to an already existing notion:\ +text \\ldots that is equivalent to an already existing notion:\ lemma perm_iff_eq_mset: \xs <~~> ys \ mset xs = mset ys\ proof assume \mset xs = mset ys\ then show \xs <~~> ys\ proof (induction xs arbitrary: ys) case Nil then show ?case by simp next case (Cons x xs) from Cons.prems [symmetric] have \mset xs = mset (remove1 x ys)\ by simp then have \xs <~~> remove1 x ys\ by (rule Cons.IH) then have \x # xs <~~> x # remove1 x ys\ by (rule perm.Cons) moreover from Cons.prems have \x \ set ys\ by (auto dest: union_single_eq_member) then have \x # remove1 x ys <~~> ys\ by (induction ys) auto ultimately show \x # xs <~~> ys\ by (rule perm.trans) qed next assume \xs <~~> ys\ then show \mset xs = mset ys\ by induction simp_all qed theorem mset_eq_perm: \mset xs = mset ys \ xs <~~> ys\ by (simp add: perm_iff_eq_mset) subsection \Nontrivial conclusions\ proposition perm_swap: \xs[i := xs ! j, j := xs ! i] <~~> xs\ if \i < length xs\ \j < length xs\ using that by (simp add: perm_iff_eq_mset mset_swap) proposition mset_le_perm_append: "mset xs \# mset ys \ (\zs. xs @ zs <~~> ys)" by (auto simp add: perm_iff_eq_mset mset_subset_eq_exists_conv ex_mset dest: sym) proposition perm_set_eq: "xs <~~> ys \ set xs = set ys" by (rule mset_eq_setD) (simp add: perm_iff_eq_mset) proposition perm_distinct_iff: "xs <~~> ys \ distinct xs \ distinct ys" by (rule mset_eq_imp_distinct_iff) (simp add: perm_iff_eq_mset) theorem eq_set_perm_remdups: "set xs = set ys \ remdups xs <~~> remdups ys" by (simp add: perm_iff_eq_mset set_eq_iff_mset_remdups_eq) proposition perm_remdups_iff_eq_set: "remdups x <~~> remdups y \ set x = set y" by (simp add: perm_iff_eq_mset set_eq_iff_mset_remdups_eq) theorem permutation_Ex_bij: assumes "xs <~~> ys" shows "\f. bij_betw f {.. (\imset ys = mset xs\ by (simp add: perm_iff_eq_mset) then obtain f where \bij_betw f {.. \xs = map (\n. ys ! f n) [0.. by (rule mset_eq_permutation) then show ?thesis by auto qed proposition perm_finite: "finite {B. B <~~> A}" using mset_eq_finite by (auto simp add: perm_iff_eq_mset) subsection \Trivial conclusions:\ proposition perm_empty_imp: "[] <~~> ys \ ys = []" by (simp add: perm_iff_eq_mset) text \\medskip This more general theorem is easier to understand!\ proposition perm_length: "xs <~~> ys \ length xs = length ys" by (rule mset_eq_length) (simp add: perm_iff_eq_mset) proposition perm_sym: "xs <~~> ys \ ys <~~> xs" by (simp add: perm_iff_eq_mset) text \We can insert the head anywhere in the list.\ proposition perm_append_Cons: "a # xs @ ys <~~> xs @ a # ys" by (simp add: perm_iff_eq_mset) proposition perm_append_swap: "xs @ ys <~~> ys @ xs" by (simp add: perm_iff_eq_mset) proposition perm_append_single: "a # xs <~~> xs @ [a]" by (simp add: perm_iff_eq_mset) proposition perm_rev: "rev xs <~~> xs" by (simp add: perm_iff_eq_mset) proposition perm_append1: "xs <~~> ys \ l @ xs <~~> l @ ys" by (simp add: perm_iff_eq_mset) proposition perm_append2: "xs <~~> ys \ xs @ l <~~> ys @ l" by (simp add: perm_iff_eq_mset) proposition perm_empty [iff]: "[] <~~> xs \ xs = []" by (simp add: perm_iff_eq_mset) proposition perm_empty2 [iff]: "xs <~~> [] \ xs = []" by (simp add: perm_iff_eq_mset) proposition perm_sing_imp: "ys <~~> xs \ xs = [y] \ ys = [y]" by (simp add: perm_iff_eq_mset) proposition perm_sing_eq [iff]: "ys <~~> [y] \ ys = [y]" by (simp add: perm_iff_eq_mset) proposition perm_sing_eq2 [iff]: "[y] <~~> ys \ ys = [y]" by (simp add: perm_iff_eq_mset) proposition perm_remove: "x \ set ys \ ys <~~> x # remove1 x ys" by (simp add: perm_iff_eq_mset) text \\medskip Congruence rule\ proposition perm_remove_perm: "xs <~~> ys \ remove1 z xs <~~> remove1 z ys" by (simp add: perm_iff_eq_mset) proposition remove_hd [simp]: "remove1 z (z # xs) = xs" by (simp add: perm_iff_eq_mset) proposition cons_perm_imp_perm: "z # xs <~~> z # ys \ xs <~~> ys" by (simp add: perm_iff_eq_mset) proposition cons_perm_eq [simp]: "z#xs <~~> z#ys \ xs <~~> ys" by (simp add: perm_iff_eq_mset) proposition append_perm_imp_perm: "zs @ xs <~~> zs @ ys \ xs <~~> ys" by (simp add: perm_iff_eq_mset) proposition perm_append1_eq [iff]: "zs @ xs <~~> zs @ ys \ xs <~~> ys" by (simp add: perm_iff_eq_mset) proposition perm_append2_eq [iff]: "xs @ zs <~~> ys @ zs \ xs <~~> ys" by (simp add: perm_iff_eq_mset) end