集合論のパラドックス

素朴集合論には興味深いパラドックスがいくつかあり、それがきっかけとなって、もっと厳密な集合論がつくられました。これらのパラドックスの多くは、従来の素朴な集合論では集合が自分自身を要素として含んでもよい、という点にもとづいています。

ラッセルのパラドックス

最も有名なパラドックスの1つが、ラッセルのパラドックスです。次のように定義できます。自分自身を要素として含まない集合全体の集合 N を考えます。つまり、ある集合が自分自身を要素として含むなら、その集合は集合 N に属しません。自分自身を含まないなら、集合 N に属します。

では、集合 N は集合 N、つまり自分自身を要素として含むでしょうか。

場合分けをして調べると、次のようになります。集合 N が N を含まないなら、それは自分自身を含まない集合なので、集合 N に含まれるはずです。つまり、N ∈ N が成り立つはずです。

一方、集合 N が要素 N を含むなら、N ∈ N は成り立たないはずです。集合 N は、自分自身を要素として含まない集合しか含まないからです。

つまりパラドックスは、どちらの場合も条件のどれかに反してしまうことにあります。N ∈ N なら、集合 N の定義（自分自身を含まない集合だけを含む）に反します。ここでは明らかに N が N を要素として含んでいるからです。N ∈ N が成り立たないなら、やはり N の定義に反します。

したがって、このような集合はつくれません。正しい集合論では、こういうことが起こってはいけないのです。

ラッセルのパラドックスには、身近なたとえもいくつかあります。たとえば床屋のパラドックスです。ある町に、自分でひげをそらない人のひげだけを、すべてそる床屋がいます。では、この床屋は自分のひげをそるのでしょうか。

カントールのパラドックス

もう1つのパラドックスは、カントールのパラドックスです。これは、集合 M があるとき、そのべき集合 P(M)（集合 M のすべての部分集合の集合）の濃度は、いつももとの集合より大きい、ということにもとづいています。有限集合ではひと目でわかりますし、無限集合でも簡単に証明できます。この主張はカントールの定理と呼ばれ、正確な内容と証明はウィキペディアにあります。

パラドックスそのものは、前のものより簡単です。すべての集合の集合を考え、それを M とします。つまり、どんな集合 N についても N ∈ M が成り立ちます。ところが、カントールの定理によると、べき集合 P(M) の濃度は M の濃度より大きくなります。これは、M がすべての集合を含むことに矛盾します。集合 P(M) が M より大きいなら、M に含まれない要素をかならず含んでいるはずだからです。