綠色箭頭代表可能的映射關係，紅色箭頭代表不可能的映射關係。圓圈表示集合或子集。 ZFC集合論 中，康托爾定理 （英語：Cantor's theorem ）斷言對任意集合
A
{\displaystyle A}
冪集 （所有子集 的集合 ）的勢 嚴格大於
A
{\displaystyle A}
對於有限集合 該結論是顯然的。對勢為
n
{\displaystyle n}
2
n
{\displaystyle 2^{n}}
非負整數
n
{\displaystyle n}
2
n
>
n
{\displaystyle 2^{n}>n}
滿射 。
但更重要的是對任意無限集合 ，康托爾定理也成立。這同時證明了，可數無限 集合構造的冪集 的基數是嚴格大於任何可數無限，以此創造出不可數無限 的概念。
證明：對任何的集合
S
{\displaystyle S}
P
(
S
)
{\displaystyle {\mathcal {P}}(S)}
（利用歸謬法）假設：可以找到一個集合
A
{\displaystyle A}
f
:
A
→
P
(
A
)
{\displaystyle f:A\to {\mathcal {P}}(A)}
對於
A
{\displaystyle A}
s
{\displaystyle s}
s
{\displaystyle s}
f
(
s
)
{\displaystyle f(s)}
f
(
s
)
{\displaystyle f(s)}
我們假設
T
=
{
x
∈
A
|
x
∉
f
(
x
)
}
{\displaystyle T=\{x\in A\,|\,x\notin f(x)\}}
T
∈
P
(
A
)
{\displaystyle T\in {\mathcal {P}}(A)}
x
{\displaystyle x}
f
(
x
)
=
T
{\displaystyle f(x)=T}
（1）如果
x
∈
T
{\displaystyle x\in T}
T
{\displaystyle T}
x
∉
f
(
x
)
{\displaystyle x\notin f(x)}
f
(
x
)
=
T
{\displaystyle f(x)=T}
x
∉
T
{\displaystyle x\notin T}
（2）如果
x
∉
T
{\displaystyle x\notin T}
T
{\displaystyle T}
x
∈
f
(
x
)
{\displaystyle x\in f(x)}
f
(
x
)
=
T
{\displaystyle f(x)=T}
x
∈
T
{\displaystyle x\in T}
兩者都矛盾。因此我們對於存在函數
f
{\displaystyle f}
[ 1]
集合的個數為可數無限 時可以用對角線法證明康托爾定理。不失一般性地，我們考慮自然數 的集合。
欲證：不存在從自然數集
N
{\displaystyle \mathbb {N} }
冪集
P
(
N
)
{\displaystyle {\mathcal {P}}(\mathbb {N} )}
雙射 函數
f
:
N
→
P
(
N
)
{\displaystyle f:\mathbb {N} \to {\mathcal {P}}(\mathbb {N} )}
（利用歸謬法）假設：存在從自然數集
N
{\displaystyle \mathbb {N} }
P
(
N
)
{\displaystyle {\mathcal {P}}(\mathbb {N} )}
f
:
N
→
P
(
N
)
{\displaystyle f:\mathbb {N} \to {\mathcal {P}}(\mathbb {N} )}
那麼我們就可以依序將所有兩個集合之間的「對應」如下列出（這裡的數字只是示例），表中含有所有「自然數構成的集合」：
X
{
1
⟺
{
4
,
5
}
2
⟺
{
1
,
2
,
3
}
3
⟺
{
4
,
5
,
6
}
4
⟺
{
1
,
3
,
5
}
⋮
⋮
⋮
}
P
(
N
)
{\displaystyle X{\begin{Bmatrix}1&\Longleftrightarrow &\{4,5\}\\2&\Longleftrightarrow &\{1,2,3\}\\3&\Longleftrightarrow &\{4,5,6\}\\4&\Longleftrightarrow &\{1,3,5\}\\\vdots &\vdots &\vdots \end{Bmatrix}}P(\mathbb {N} )}
雖然在集合中，元素的順序不重要，但我們假設從左到右以由小到大的方式記錄冪集合中的元素，以便討論。
通過這個「對應表」，我們可以構造一個自然數集合
W
{\displaystyle W}
當左側的自然數「屬於」它對應的冪集合，我們就在
W
{\displaystyle W}
反之當左側的自然數「不屬於」它對應的冪集合，我們就在
W
{\displaystyle W}
1
⟺
{
4
,
5
}
,
1
∉
{
4
,
5
}
{\displaystyle 1\Longleftrightarrow \{4,5\},1\notin \{4,5\}}
1
∈
W
{\displaystyle 1\in W}
W
{\displaystyle W}
2
⟺
{
1
,
2
,
3
}
,
2
∈
{
1
,
2
,
3
}
{\displaystyle 2\Longleftrightarrow \{1,2,3\},2\in \{1,2,3\}}
2
∉
W
{\displaystyle 2\notin W}
W
{\displaystyle W}
......
W
{\displaystyle W}
但
W
{\displaystyle W}
因此假設的
f
{\displaystyle f}
P
(
N
)
{\displaystyle {\mathcal {P}}(\mathbb {N} )}
勢 和自然數的勢不相等。
雖然用歸謬法沒能得知哪個集合的勢更大，但由於
P
(
N
)
{\displaystyle {\mathcal {P}}(\mathbb {N} )}
單元素集合
{
n
}
{\displaystyle \{n\}}
P
(
N
)
{\displaystyle {\mathcal {P}}(\mathbb {N} )}
P
(
N
)
{\displaystyle {\mathcal {P}}(\mathbb {N} )}
N
{\displaystyle \mathbb {N} }
綜上，
P
(
N
)
{\displaystyle {\mathcal {P}}(\mathbb {N} )}
N
{\displaystyle \mathbb {N} }
格奧爾格·康托爾 在1891年發表的論文《Über eine elementare Frage der Mannigfaltigkeitslehre》中本質上給出了這個證明，實數 不可數的對角論證法 也首次在這裡出現。在這個論文中給出的這個論證的版本使用的是在集合上的指示函數 而不是集合子集。他證明了如果f 是定義在X 上的函數，它的值是在X 上的二值函數，則二值函數G (x ) = 1 − f (x )(x )不在f 的值域 中。
羅素在《數學原理》（1903, section 348）中給出了一個非常類似的證明，在這裡他證明了命題函數 要比對象多。「假設所有對象和所有和它們相關的命題函數之間有一種對應，並令phi-x 為x 所對應的命題函數。則'非-phi-x (x )'，也即"phi-x 對於x 不成立",是一個在這個對應中沒有出現的命題函數；因為它在phi-x 假的時候為真，在phi-x 真的時候為假，因此它和任何一個x 所對應的phi-x 不同」。他在康托爾之後貢獻了這個想法。
恩斯特·策梅洛 在他1908年發表的成為現代集合論基礎的論文《Untersuchungen über die Grundlagen der Mengenlehre I》中有一個定理（他稱之為康托爾定理）同於上面的論證形式。
康托爾定理的一個推論請參見beth數 。
^ Stenphen Fletcher Hewson, 數學橋——對高等數學的一次觀賞之旅 ：1.1.7 超越無限大. 数学桥——对高等数学的一次观赏之旅 ：1.1.7 超越無限大. 上海科技教育出版社. 2010/8/7: p.12. ISBN 978-7-5428-4981-6
Paul Halmos, Naive set theory . Princeton, NJ: D. Van Nostrand Company, 1960. Reprinted by Springer-Verlag, New York, 1974. ISBN 0-387-90092-6 (Springer-Verlag edition).
Jech, Thomas, 2003. Set Theory: The Third Millennium Edition, Revised and Expanded . Springer. ISBN 3-540-44085-2 .
