2178 "[|inj_on f A; f ` A \<subseteq> B; inj_on g B; g ` B \<subseteq> A; |
2178 "[|inj_on f A; f ` A \<subseteq> B; inj_on g B; g ` B \<subseteq> A; |
2179 finite A; finite B |] ==> card A = card B" |
2179 finite A; finite B |] ==> card A = card B" |
2180 by (auto intro: le_antisym card_inj_on_le) |
2180 by (auto intro: le_antisym card_inj_on_le) |
2181 |
2181 |
2182 |
2182 |
|
2183 subsubsection {* Pigeonhole Principles *} |
|
2184 |
|
2185 lemma pigeonhole: "finite(A) \<Longrightarrow> card A > card(f ` A) \<Longrightarrow> ~ inj_on f A " |
|
2186 by (auto dest: card_image less_irrefl_nat) |
|
2187 |
|
2188 lemma pigeonhole_infinite: |
|
2189 assumes "~ finite A" and "finite(f`A)" |
|
2190 shows "EX a0:A. ~finite{a:A. f a = f a0}" |
|
2191 proof - |
|
2192 have "finite(f`A) \<Longrightarrow> ~ finite A \<Longrightarrow> EX a0:A. ~finite{a:A. f a = f a0}" |
|
2193 proof(induct "f`A" arbitrary: A rule: finite_induct) |
|
2194 case empty thus ?case by simp |
|
2195 next |
|
2196 case (insert b F) |
|
2197 show ?case |
|
2198 proof cases |
|
2199 assume "finite{a:A. f a = b}" |
|
2200 hence "~ finite(A - {a:A. f a = b})" using `\<not> finite A` by simp |
|
2201 also have "A - {a:A. f a = b} = {a:A. f a \<noteq> b}" by blast |
|
2202 finally have "~ finite({a:A. f a \<noteq> b})" . |
|
2203 from insert(3)[OF _ this] |
|
2204 show ?thesis using insert(2,4) by simp (blast intro: rev_finite_subset) |
|
2205 next |
|
2206 assume 1: "~finite{a:A. f a = b}" |
|
2207 hence "{a \<in> A. f a = b} \<noteq> {}" by force |
|
2208 thus ?thesis using 1 by blast |
|
2209 qed |
|
2210 qed |
|
2211 from this[OF assms(2,1)] show ?thesis . |
|
2212 qed |
|
2213 |
|
2214 lemma pigeonhole_infinite_rel: |
|
2215 assumes "~finite A" and "finite B" and "ALL a:A. EX b:B. R a b" |
|
2216 shows "EX b:B. ~finite{a:A. R a b}" |
|
2217 proof - |
|
2218 let ?F = "%a. {b:B. R a b}" |
|
2219 from finite_Pow_iff[THEN iffD2, OF `finite B`] |
|
2220 have "finite(?F ` A)" by(blast intro: rev_finite_subset) |
|
2221 from pigeonhole_infinite[where f = ?F, OF assms(1) this] |
|
2222 obtain a0 where "a0\<in>A" and 1: "\<not> finite {a\<in>A. ?F a = ?F a0}" .. |
|
2223 obtain b0 where "b0 : B" and "R a0 b0" using `a0:A` assms(3) by blast |
|
2224 { assume "finite{a:A. R a b0}" |
|
2225 then have "finite {a\<in>A. ?F a = ?F a0}" |
|
2226 using `b0 : B` `R a0 b0` by(blast intro: rev_finite_subset) |
|
2227 } |
|
2228 with 1 `b0 : B` show ?thesis by blast |
|
2229 qed |
|
2230 |
|
2231 |
2183 subsubsection {* Cardinality of sums *} |
2232 subsubsection {* Cardinality of sums *} |
2184 |
2233 |
2185 lemma card_Plus: |
2234 lemma card_Plus: |
2186 assumes "finite A" and "finite B" |
2235 assumes "finite A" and "finite B" |
2187 shows "card (A <+> B) = card A + card B" |
2236 shows "card (A <+> B) = card A + card B" |
2208 apply (simp add: card_image Pow_insert) |
2257 apply (simp add: card_image Pow_insert) |
2209 apply (unfold inj_on_def) |
2258 apply (unfold inj_on_def) |
2210 apply (blast elim!: equalityE) |
2259 apply (blast elim!: equalityE) |
2211 done |
2260 done |
2212 |
2261 |
2213 text {* Relates to equivalence classes. Based on a theorem of F. Kammüller. *} |
2262 text {* Relates to equivalence classes. Based on a theorem of F. Kammüller. *} |
2214 |
2263 |
2215 lemma dvd_partition: |
2264 lemma dvd_partition: |
2216 "finite (Union C) ==> |
2265 "finite (Union C) ==> |
2217 ALL c : C. k dvd card c ==> |
2266 ALL c : C. k dvd card c ==> |
2218 (ALL c1: C. ALL c2: C. c1 \<noteq> c2 --> c1 Int c2 = {}) ==> |
2267 (ALL c1: C. ALL c2: C. c1 \<noteq> c2 --> c1 Int c2 = {}) ==> |