カントールの定理
有限集合に対して定理が成立するのは明らかである。n 個の要素からなる集合に対して、空部分集合、ただ 1 つの要素を持つ A の部分集合、等々......と数えると、 2 個の部分集合があり、部分集合の濃度は明らかに大きい(n < 2) 。以下の証明は無限集合に対するものである。
2 つの集合が等濃である(同じ濃度を持つ)こととそれらの間に一対一対応が存在することは同値である。カントールの定理を証明するには、任意の与えられた集合 A に対して、A から A の冪集合へのどんな関数 f も全射になりえないことを示せば十分である。すなわち、 f による A の像の元でない、 A の少なくとも 1 つの部分集合の存在を示せば十分である。そのような部分集合は次の構成によって与えられる:
B = { x ∈ A : x ∉ f ( x ) } . {\displaystyle B=\left\{\,x\in A:x\not \in f(x)\,\right\}.}
これが意味するのは、定義によってすべての x ∈ A に対して x ∈ B ⇔ x ∉ f (x) ということである。すべての x に対して集合 B と f (x) は同じにはなり得ない、なぜならば B は( f による)像が自身を含まないような A の元から構成されていたからである。