「 HOTEL N 」（第４幕）の解説。
自然数の集合 N の部分集合全体を S とおきます。S = { A | A ⊆ N }
（これを N のべき集合といい P(N) とあらわします。）
ここでは自然数の集合 N のベキ集合 S = P(N) が可算集合ではない
（すなわち N と対等ではない）ことを示しています。
（証明）
背理法を用いて証明します。
もし、S が可算集合であったと仮定します。
すると、全単射な写像
f : N → S
が存在します。
この時、集合 B を
B = { k ∈ N | k は f(k) に含まれない } と定義します。
これは、N の部分集合を明確に定義しています。よって B ∈ S です。
写像 f は 全射なので f(t) = B をみたす自然数 t が存在します。
もし、「t ∈ B」 ならば、B の定義より
「 t は f(t) に含まれない」ことになります。しかし f(t) = B なので
「t ∈ B」 ならば、「 t は B に含まれない」ことになり、矛盾がおこります。
もし、「 t が B に含まれない」ならば、B の定義より
「 t ∈ f(t) = B 」となり、やはり、矛盾がおこります。
よって、最初の仮定「 S が可算集合である」が正しくないことが分かります。
（証明終わり）
したがって、可算集合ではない無限集合が存在することが示せました。
例えば、実数全体の集合 R は可算集合ではない無限集合です。
連続体の濃度を持つ集合といいます。
上の証明をそのまま拡張すれば、
集合 A の部分集合全体の作る集合 P(A) の 濃度は
A の濃度よりも大きいことが確かめられます。
濃度を調べたり、大小を比較することに関しては、
ここでは詳しく述べませんが、
「濃度が等しくない無限集合が存在する。」
ということと
「与えられた無限集合よりも濃度の大きい集合が存在する。」
ということを覚えておきましょう。