カントールの定理
カントールの定理(カントールのていり、Cantor's theorem)は、集合論における基本的な定理の一つで、冪集合の濃度について述べたものである。最初にこれを証明したドイツ人数学者ゲオルク・カントールにちなむ。
定義によって冪集合 P(N) は自然数からなるすべての集合を含み、したがってこの集合 D を元として含む。写像が全単射であれば、D は対応するある自然数 d とペアになっていなければならない。しかしこれは問題を起こす。d が D に含まれれば、 d が対応する集合に含まれるから d は利己的であるが、これは D の定義に矛盾する。 d が D に含まれなければ、 d は非利己的である一方で D の元でなければならない。したがって D に写るような元 d は存在しない。
D とペアにできる自然数は存在しないから、もとの仮定「 N と P(N) の間に全単射が存在すること」に矛盾する。
集合 D は空かもしれないことに注意しよう。これはすべての自然数 x は x を含む自然数の集合に写ることを意味する。すると、すべての自然数は空でない集合に写り、どんな数も空集合に写らない。しかし空集合は P(N) の元であるので、写像は全射にならない。
この背理法を通して、 N と P(N) の濃度が等しくないことが示された。また、 P(N) の濃度が N の濃度よりも小さくないこともわかる。なぜならば P(N) は定義によってすべての一元集合を含み、これらの一元集合は P(N) の中で N の「コピー」となるからである。したがって、 P(N) の濃度は N の濃度よりも真に大きく、カントールの定理が証明された。