カントールの定理
カントールは 1891 年に出版された論文 Über eine elementare Frage der Mannigfaltigkeitslehre (多様体論の初等的問題に関して)においてこの証明を本質的に与えた。この論文では実数の非可算性のための対角線論法もまた初めて現れる(なお、カントールは以前に他の手法によって実数の非可算性を証明していた(英語版))。この論文における証明は、集合の部分集合ではなく集合上の指示関数の言葉で表現された。カントールは、 f を X 上で定義された X の 2-値関数とすると 2-値関数 G (x) = 1 − f (x)(x) は f の値域に含まれないことを示した。
バートランド・ラッセルは Principles of Mathematics (1903, section 348) において非常によく似た証明をしており、彼は対象よりも命題関数の方がたくさんあることを示した。
証明を理解するために、元の集合が可算無限集合 X である場合を考えよう。一般性を失うことなく X = N = {1, 2, 3,...} (自然数の集合)ととれる。
N とその冪集合 P(N) は等濃と仮定する。P(N) の具体的な例を見よう:
P ( N ) = { ∅ , { 1 , 2 } , { 1 , 2 , 3 } , { 4 } , { 1 , 5 } , { 3 , 4 , 6 } , { 2 , 4 , 6 , ... } , ... } . {\displaystyle P(\mathbb {N} )=\{\varnothing ,\{1,2\},\{1,2,3\},\{4\},\{1,5\},\{3,4,6\},\{2,4,6,\dots \},\dots \}.}
P(N) は、すべての偶数の集合 {2, 4, 6,...} や空集合など、N の無限個の部分集合を含む。
さて P(N) の具体的な元がわかっているから、これらの無限集合が等濃であることを示すために、N と P(N) のそれぞれの元をペアにしてみよう。言い換えると、N の各元が無限集合 P(N) の元とペアになるようにして、どちらの無限集合の元もペアにならないまま残ることがないようにする。このように元をペアにすると以下のようになるだろう: