数学 › 組合せ論 › 数え上げと母関数

鳩の巣原理

定理 7.5（「数え上げと母関数」§7） ・ ✓公理まで証明済み

  1. A,BA,B を有限集合、f:A→Bf:A\to B を写像、k≥1k\ge1 とする。∣A∣>k∣B∣|A|>k|B| ならば、ある b∈Bb\in B について ∣f−1(b)∣≥k+1|f^{-1}(b)|\ge k+1 である。とくに k=1k=1 では、∣A∣>∣B∣|A|>|B| ならば ff は単射でない。
  2. AA が無限集合、BB が有限集合なら、任意の写像 f:A→Bf:A\to B について、ある b∈Bb\in B の逆像 f−1(b)f^{-1}(b) は無限集合である。

本文で読む（証明と前後の説明）→

閉包の状態

✓ 公理まで証明済み

証明が使う定理を 前提 としてたどると、Rikai の中の証明だけで定義・公理（物理では基本仮定）までつながっています（前提の定理類 1 件、定義なども含めて 1 件）。

印の意味: ✓公理まで証明済み ・ △証明あり（閉包未完）・ ※主張のみ。テーマごとの集計は 閉包の状況。

前提をたどる 証明が使う定理・定義（直接 1 件）

▸ を開くと、その項目の証明が使う前提が出ます。深い先は各項目のページでたどれます。

これを使っている定理 証明で参照している 15 件