diff -r badee348c5fb -r ad4242285560 src/HOL/List.thy --- a/src/HOL/List.thy Thu Dec 01 15:41:48 2011 +0100 +++ b/src/HOL/List.thy Thu Dec 01 15:41:58 2011 +0100 @@ -505,6 +505,8 @@ qed qed +lemma inj_split_Cons: "inj_on (\(xs, n). n#xs) X" + by (auto intro!: inj_onI) subsubsection {* @{const length} *} @@ -3709,18 +3711,18 @@ thus ?case .. qed -lemma finite_lists_length_eq: -assumes "finite A" -shows "finite {xs. set xs \ A \ length xs = n}" (is "finite (?S n)") -proof(induct n) - case 0 show ?case by simp -next - case (Suc n) - have "?S (Suc n) = (\x\A. (\xs. x#xs) ` ?S n)" - by (auto simp:length_Suc_conv) - then show ?case using `finite A` - by (auto intro: Suc) (* FIXME metis? *) -qed +lemma lists_length_Suc_eq: + "{xs. set xs \ A \ length xs = Suc n} = + (\(xs, n). n#xs) ` ({xs. set xs \ A \ length xs = n} \ A)" + by (auto simp: length_Suc_conv) + +lemma + assumes "finite A" + shows finite_lists_length_eq: "finite {xs. set xs \ A \ length xs = n}" + and card_lists_length_eq: "card {xs. set xs \ A \ length xs = n} = (card A)^n" + using `finite A` + by (induct n) + (auto simp: card_image inj_split_Cons lists_length_Suc_eq cong: conj_cong) lemma finite_lists_length_le: assumes "finite A" shows "finite {xs. set xs \ A \ length xs \ n}" @@ -3730,6 +3732,18 @@ thus ?thesis by (auto intro: finite_lists_length_eq[OF `finite A`]) qed +lemma card_lists_length_le: + assumes "finite A" shows "card {xs. set xs \ A \ length xs \ n} = (\i\n. card A^i)" +proof - + have "(\i\n. card A^i) = card (\i\n. {xs. set xs \ A \ length xs = i})" + using `finite A` + by (subst card_UN_disjoint) + (auto simp add: card_lists_length_eq finite_lists_length_eq) + also have "(\i\n. {xs. set xs \ A \ length xs = i}) = {xs. set xs \ A \ length xs \ n}" + by auto + finally show ?thesis by simp +qed + lemma infinite_UNIV_listI: "~ finite(UNIV::'a list set)" apply(rule notI) apply(drule finite_maxlen)