カントールの対角線論法
Xを任意の集合とするとき、XからXの冪集合2への全射が存在しない(従って特に全単射が存在しない)。つまり、Xの濃度より2の濃度のほうが真に大きい。
これは以下のように対角線論法を用いて次のように示される。
Xから2への全射ψが存在したとする。 Y = { x ∈ X : x ∉ ψ ( x ) } {\displaystyle Y=\{x\in X:x\notin \psi (x)\}} により定義すると、対角線論法より、ψ(x)=Yとなるx∈Xは存在しない。これはψの全射性に反する。
上の Y の構成はラッセルのパラドックスで用いられる「自分自身を含まないような集合」と酷似していることに注意されたい。 X を「全ての集合を含む集合」として同じことを行うと、2 は X の部分集合でありながらしかも X より濃度が大きくなり矛盾を生じる(カントールのパラドックス)。したがって、(公理的集合論の立場では)「すべての集合を含む集合」は集合ではなく、真のクラスになる。