MathLabs
定理証明済み

カントール・シュレーダー・ベルンシュタインの定理

内容

単射 f:A→Bf:A\to B と単射 g:B→Ag:B\to A が二つの集合 AA、BB の間に存在するならば、全単射 h:A→Bh:A\to B が存在する。言い換えれば、∣A∣≤∣B∣|A|\le|B| かつ ∣B∣≤∣A∣|B|\le|A| ならば ∣A∣=∣B∣|A|=|B| である。

なぜ正しいのか?

互いに他方の単射的なコピーを含んでいるというだけで、二つの集合が本当に同じ大きさであることを保証するのに十分である。直接的な全単射を示す必要はなく、うまく組み合わさる二つの一方向の埋め込みがあればよい。

証明の概略

AA の各元について、定義される限り g−1g^{-1} と f−1f^{-1} を交互に適用して逆向きに辿っていく。この経路は A∖g(B)A\setminus g(B) で止まるか、g(B∖f(A))g(B\setminus f(A)) で止まるか、あるいは永遠に続くかのいずれかである。h=fh=f を、経路が AA で止まるか永遠に続く元に対して定義し、h=g−1h=g^{-1} を、経路が BB で止まる元に対して定義する。各場合を確認すると、この hh が well-defined な全単射 A→BA\to B であることが分かる。

提示者

1887年に提示ゲオルク・カントール

この定理を使うトピック

写像と濃度

関連する定理

実数の非可算性(カントールの対角線論法)

ステップごとの証明

この定理のステップごとの証明はまだありません。

参考文献

  1. Kenneth Kunen (1980). Set Theory: An Introduction to Independence Proofs
  2. Paul R. Halmos (1974). Naive Set Theory