86 lemma one_less_int_card: "1 < int CARD('a::card2)" |
86 lemma one_less_int_card: "1 < int CARD('a::card2)" |
87 using one_less_card [where 'a='a] by simp |
87 using one_less_card [where 'a='a] by simp |
88 |
88 |
89 subsection {* A type class for computing the cardinality of types *} |
89 subsection {* A type class for computing the cardinality of types *} |
90 |
90 |
|
91 definition is_list_UNIV :: "'a list \<Rightarrow> bool" |
|
92 where "is_list_UNIV xs = (let c = CARD('a) in if c = 0 then False else size (remdups xs) = c)" |
|
93 |
|
94 lemmas [code_unfold] = is_list_UNIV_def[abs_def] |
|
95 |
|
96 lemma is_list_UNIV_iff: "is_list_UNIV xs \<longleftrightarrow> set xs = UNIV" |
|
97 by(auto simp add: is_list_UNIV_def Let_def card_eq_0_iff List.card_set[symmetric] |
|
98 dest: subst[where P="finite", OF _ finite_set] card_eq_UNIV_imp_eq_UNIV) |
|
99 |
|
100 lemma card_UNIV_eq_0_is_list_UNIV_False: |
|
101 "CARD('a) = 0 \<Longrightarrow> is_list_UNIV = (\<lambda>xs :: 'a list. False)" |
|
102 by(simp add: is_list_UNIV_def[abs_def]) |
|
103 |
91 class card_UNIV = |
104 class card_UNIV = |
92 fixes card_UNIV :: "'a itself \<Rightarrow> nat" |
105 fixes card_UNIV :: "'a itself \<Rightarrow> nat" |
93 assumes card_UNIV: "card_UNIV x = card (UNIV :: 'a set)" |
106 assumes card_UNIV: "card_UNIV x = CARD('a)" |
94 begin |
107 |
95 |
108 lemma card_UNIV_code [code_unfold]: "CARD('a :: card_UNIV) = card_UNIV TYPE('a)" |
96 lemma card_UNIV_neq_0_finite_UNIV: |
109 by(simp add: card_UNIV) |
97 "card_UNIV x \<noteq> 0 \<longleftrightarrow> finite (UNIV :: 'a set)" |
|
98 by(simp add: card_UNIV card_eq_0_iff) |
|
99 |
|
100 lemma card_UNIV_ge_0_finite_UNIV: |
|
101 "card_UNIV x > 0 \<longleftrightarrow> finite (UNIV :: 'a set)" |
|
102 by(auto simp add: card_UNIV intro: card_ge_0_finite finite_UNIV_card_ge_0) |
|
103 |
|
104 lemma card_UNIV_eq_0_infinite_UNIV: |
|
105 "card_UNIV x = 0 \<longleftrightarrow> \<not> finite (UNIV :: 'a set)" |
|
106 by(simp add: card_UNIV card_eq_0_iff) |
|
107 |
|
108 definition is_list_UNIV :: "'a list \<Rightarrow> bool" |
|
109 where "is_list_UNIV xs = (let c = card_UNIV (TYPE('a)) in if c = 0 then False else size (remdups xs) = c)" |
|
110 |
|
111 lemma is_list_UNIV_iff: fixes xs :: "'a list" |
|
112 shows "is_list_UNIV xs \<longleftrightarrow> set xs = UNIV" |
|
113 proof |
|
114 assume "is_list_UNIV xs" |
|
115 hence c: "card_UNIV (TYPE('a)) > 0" and xs: "size (remdups xs) = card_UNIV (TYPE('a))" |
|
116 unfolding is_list_UNIV_def by(simp_all add: Let_def split: split_if_asm) |
|
117 from c have fin: "finite (UNIV :: 'a set)" by(auto simp add: card_UNIV_ge_0_finite_UNIV) |
|
118 have "card (set (remdups xs)) = size (remdups xs)" by(subst distinct_card) auto |
|
119 also note set_remdups |
|
120 finally show "set xs = UNIV" using fin unfolding xs card_UNIV by-(rule card_eq_UNIV_imp_eq_UNIV) |
|
121 next |
|
122 assume xs: "set xs = UNIV" |
|
123 from finite_set[of xs] have fin: "finite (UNIV :: 'a set)" unfolding xs . |
|
124 hence "card_UNIV (TYPE ('a)) \<noteq> 0" unfolding card_UNIV_neq_0_finite_UNIV . |
|
125 moreover have "size (remdups xs) = card (set (remdups xs))" |
|
126 by(subst distinct_card) auto |
|
127 ultimately show "is_list_UNIV xs" using xs by(simp add: is_list_UNIV_def Let_def card_UNIV) |
|
128 qed |
|
129 |
|
130 lemma card_UNIV_eq_0_is_list_UNIV_False: |
|
131 assumes cU0: "card_UNIV x = 0" |
|
132 shows "is_list_UNIV = (\<lambda>xs. False)" |
|
133 proof(rule ext) |
|
134 fix xs :: "'a list" |
|
135 from cU0 have "\<not> finite (UNIV :: 'a set)" |
|
136 by(auto simp only: card_UNIV_eq_0_infinite_UNIV) |
|
137 moreover have "finite (set xs)" by(rule finite_set) |
|
138 ultimately have "(UNIV :: 'a set) \<noteq> set xs" by(auto simp del: finite_set) |
|
139 thus "is_list_UNIV xs = False" unfolding is_list_UNIV_iff by simp |
|
140 qed |
|
141 |
|
142 end |
|
143 |
110 |
144 subsection {* Instantiations for @{text "card_UNIV"} *} |
111 subsection {* Instantiations for @{text "card_UNIV"} *} |
145 |
112 |
146 subsubsection {* @{typ "nat"} *} |
113 subsubsection {* @{typ "nat"} *} |
147 |
114 |
313 by (metis Compl_eq_Diff_UNIV card_Diff_subset top_greatest) |
280 by (metis Compl_eq_Diff_UNIV card_Diff_subset top_greatest) |
314 |
281 |
315 lemma eq_set_code [code]: |
282 lemma eq_set_code [code]: |
316 fixes xs ys :: "'a :: card_UNIV list" |
283 fixes xs ys :: "'a :: card_UNIV list" |
317 defines "rhs \<equiv> |
284 defines "rhs \<equiv> |
318 let n = card_UNIV TYPE('a) |
285 let n = CARD('a) |
319 in if n = 0 then False else |
286 in if n = 0 then False else |
320 let xs' = remdups xs; ys' = remdups ys |
287 let xs' = remdups xs; ys' = remdups ys |
321 in length xs' + length ys' = n \<and> (\<forall>x \<in> set xs'. x \<notin> set ys') \<and> (\<forall>y \<in> set ys'. y \<notin> set xs')" |
288 in length xs' + length ys' = n \<and> (\<forall>x \<in> set xs'. x \<notin> set ys') \<and> (\<forall>y \<in> set ys'. y \<notin> set xs')" |
322 shows "eq_set (List.coset xs) (set ys) \<longleftrightarrow> rhs" (is ?thesis1) |
289 shows "eq_set (List.coset xs) (set ys) \<longleftrightarrow> rhs" (is ?thesis1) |
323 and "eq_set (set ys) (List.coset xs) \<longleftrightarrow> rhs" (is ?thesis2) |
290 and "eq_set (set ys) (List.coset xs) \<longleftrightarrow> rhs" (is ?thesis2) |