src/HOL/Library/Enum.thy
changeset 33639 603320b93668
parent 33635 dcaada178c6f
child 37601 2a4fb776ca53
equal deleted inserted replaced
33638:548a34929e98 33639:603320b93668
    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"