カントールの定理
より具体的には以下のとおりである。任意の x ∈ A を考えると、 x ∈ f (x) かまたは x ∉ f (x) である。前者の場合には、 x ∈ f (x) である一方 B の構成から x ∉ B であるため、 f (x) と B は等しくない。後者の場合には、 x ∉ f (x) である一方 B の構成から x ∈ B であるため、やはり f (x) と B は等しくない。
したがって f (x)=B なる x は存在しない。言い換えると B は f の像に含まれない。B は A の冪集合に含まれるから、A の冪集合は A 自身よりも大きい濃度を持つ。
別の証明方法としては、 B が空集合であるかどうかにかかわらず、つねに A の冪集合に含まれることを用いる。f が全射であるためには、 A のある元は B に写らなければならないが、これは矛盾であることを示す。 B の構成より、B のどの元も B に写らない。したがって B に写る元は B の元ではない。しかしこれは B の構成における元の判定条件を満たし、矛盾。したがって A のある元が B に写るという仮定は誤りである。したがって f は全射ではない。
式 "x ∉ f (x)" において x が 2 回出現するため、これは対角線論法である。
「すべての対象といくつかの命題関数の相関関係が影響を受けると仮定し、φx を x の相関とする。すると "not φx(x)" すなわち "φx が x について成り立たない" はこの相関に含まれない命題関数となる。 x の真偽と φx の真偽が反転するからである。したがって、これはどの x の値についても φx と異なる。」ラッセルの証明の考え方はカントールのものに基づく。
エルンスト・ツェルメロは、 1908 年に出版された現代的集合論の基礎となった論文 ("Untersuchungen über die Grundlagen der Mengenlehre I"(集合論の基礎についての研究 I )) において、前述の形に同一な(ツェルメロが「カントールの定理」と呼ぶ)定理を与えた。ツェルメロ集合論を参照。
カントールの定理に基づく結果は、ベート数も参照せよ。
任意の集合 A に対して、A のすべての部分集合の集合( A の冪集合)は A 自身よりも真に大きい濃度を持つ。