equal
deleted
inserted
replaced
70 |
70 |
71 lemma n_lists_Nil [simp]: "n_lists n [] = (if n = 0 then [[]] else [])" |
71 lemma n_lists_Nil [simp]: "n_lists n [] = (if n = 0 then [[]] else [])" |
72 by (induct n) simp_all |
72 by (induct n) simp_all |
73 |
73 |
74 lemma length_n_lists: "length (n_lists n xs) = length xs ^ n" |
74 lemma length_n_lists: "length (n_lists n xs) = length xs ^ n" |
75 by (induct n) (auto simp add: length_concat map_compose [symmetric] o_def listsum_triv) |
75 by (induct n) (auto simp add: length_concat o_def listsum_triv) |
76 |
76 |
77 lemma length_n_lists_elem: "ys \<in> set (n_lists n xs) \<Longrightarrow> length ys = n" |
77 lemma length_n_lists_elem: "ys \<in> set (n_lists n xs) \<Longrightarrow> length ys = n" |
78 by (induct n arbitrary: ys) auto |
78 by (induct n arbitrary: ys) auto |
79 |
79 |
80 lemma set_n_lists: "set (n_lists n xs) = {ys. length ys = n \<and> set ys \<subseteq> set xs}" |
80 lemma set_n_lists: "set (n_lists n xs) = {ys. length ys = n \<and> set ys \<subseteq> set xs}" |
244 proof - |
244 proof - |
245 have aux: "\<And>x A. set ` Cons x ` A = insert x ` set ` A" |
245 have aux: "\<And>x A. set ` Cons x ` A = insert x ` set ` A" |
246 by (auto simp add: image_def) |
246 by (auto simp add: image_def) |
247 have "set (map set (sublists xs)) = Pow (set xs)" |
247 have "set (map set (sublists xs)) = Pow (set xs)" |
248 by (induct xs) |
248 by (induct xs) |
249 (simp_all add: aux Let_def Pow_insert Un_commute) |
249 (simp_all add: aux Let_def Pow_insert Un_commute comp_def del: map_map) |
250 then show ?thesis by simp |
250 then show ?thesis by simp |
251 qed |
251 qed |
252 |
252 |
253 lemma distinct_set_sublists: |
253 lemma distinct_set_sublists: |
254 assumes "distinct xs" |
254 assumes "distinct xs" |