ベルンシュタインの定理

集合論にベルンシュタインの定理という定理がある。
カントールの対角線論法と並んで集合論の基本的な定理である。

AからBへの単射 f と、BからAへの単射 g が存在するとき、AとBには1対１対応h が存在する。すなわち、AとBの基数（濃度）が等しい。

諸定義:

• fが集合Aから集合Bへの写像であるとは、各a∈A(Aの要素a)に対して、b∈B(Bの要素b)が定まることをいう。この時bをf(a)と表す。また、{f(a)|a∈A}をfによるAの像といい、f(A)で表す。
• AからBへの写像fが単射であるとは、 f(x) = f(y) の時、必ず x = y となることをいう。
• AからBへの写像fが全射であるとは、どんな b∈B に対しても、 a∈A があって f(a) = b となる。つまり、f(A) = B である。
• AからBへの写像fが1対1対応（全単射）であるとは、fが単射でかつ全射であることをいう。
• AからBへの1対1対応（全単射）fが存在するときAとBは基数(濃度)が等しいという。

[Link]「ベルンシュタインの定理 - Wikipedia」 http://ja.wikipedia.org/wiki/%E3%83%99%E3%83%AB%E3%83%B3%E3%82%B7%E3%83%A5%E3%82%BF%E3%82%A4%E3%83%B3%E3%81%AE%E5%AE%9A%E7%90%86
Wikipediaに簡潔な証明があるが、あえてここでも証明してみる。

1. からへの単射 と、からへの単射 により 全単射 を構成すればよい。
2. まず、はとに分けられる。
3. をと書く。つまり、というからへの単射を考える。
4. はの要素全体を繰り返し任意回で写した像である。
5. この時、の適用回数が違う同士は共通要素を持たない。なぜならはと共通要素を持たず、1回でもを適用した場合に含まれ は単射であるからである。
6. ここで、におけるの要素に対してはとする。
7. それ以外のAの要素 は の要素ではないので に含まれる。つまり、あるの要素が存在して となる。ここで と定義する。この場合に、さらにの要素に対しても とすると、 となり、がに含まれていないことに矛盾する。
8. よって、は単射である。
9. においてとなる要素に対して、の要素があり、となる。
10. それ以外の要素に関しては、はには含まれないはずだから、となる。
11. よって、は全射である。
12. からへの全単射が存在することがいえた。（証明終わり）

図つきで再エントリしました！↓
IIJIMASの日記 - ベルンシュタインの定理（図つき）