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)