src/HOL/Finite_Set.thy
changeset 40703 d1fc454d6735
parent 40702 cf26dd7395e4
child 40716 a92d744bca5f
equal deleted inserted replaced
40702:cf26dd7395e4 40703:d1fc454d6735
  2177 lemma card_bij_eq:
  2177 lemma card_bij_eq:
  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 lemma bij_betw_finite:
       
  2183   assumes "bij_betw f A B"
       
  2184   shows "finite A \<longleftrightarrow> finite B"
       
  2185 using assms unfolding bij_betw_def
       
  2186 using finite_imageD[of f A] by auto
  2182 
  2187 
  2183 subsubsection {* Pigeonhole Principles *}
  2188 subsubsection {* Pigeonhole Principles *}
  2184 
  2189 
  2185 lemma pigeonhole: "card A > card(f ` A) \<Longrightarrow> ~ inj_on f A "
  2190 lemma pigeonhole: "card A > card(f ` A) \<Longrightarrow> ~ inj_on f A "
  2186 by (auto dest: card_image less_irrefl_nat)
  2191 by (auto dest: card_image less_irrefl_nat)