素朴に「モノの集まり」のことを集合と定義する素朴集合論では様々な形で矛盾が引き起こされることが知られていて,なかでもラッセルのパラドックスとカントールのパラドックスと呼ばれるものが有名である.この2つのパラドックスは似ている面もあって,たまに混同している人も見かけるのでメモを残しておく.
や のように のみを自由変数として含む開論理式を命題関数 で表す. は の性質を述べる述語と思える.素朴に「モノの集まり」を集合とすると, を満たす 全体を集めた\begin{align} X=\{ x \mid P(x)\}\end{align}も集合ということになる.しかし,このような形のものを何でもかんでも集合としてしまうと矛盾が引き起こされる.
ラッセルのパラドックス
が の場合を考える.すなわち \begin{align} X=\{x \mid x\not\in x\} \end{align}とする.
排中律より または だが,
- のとき, の定義より となり矛盾.
- のとき, の定義より となり矛盾.
となりいずれの場合も矛盾している.よりシンプルに, の定義より となり矛盾,ということもできる.
カントールのパラドックス
を集合とする. が の場合を考えると \begin{align}\wp(A)=\{x \mid x\subset A\}\end{align}という集合ができる. は の部分集合全体である.これを のべき集合と呼ぶ.次の定理の証明は対角線論法という名前でよく知られている.
(証明) が全射であると仮定する. とすると, より,ある が存在して となる.
- とすると の定義より となり,矛盾.
- とすると の定義より となり,矛盾.
いずれ場合も矛盾するので,背理法*1より は全射ではない.(証明終)
さて, が恒真式を表す命題定数 のとき( のようなトートロジーで代用してもよい),すなわち \begin{align}X=\{x \mid \top\}\end{align}を考えると,この は「集合全体の集合」になっている.この のべき集合 を考えると, は集合全体の集合だったので である.すると,次のような写像 を定義することができる \begin{align}
f(a)=
\left\{
\begin{array}{lc}
a & (a\in \wp(X))\\
X & (a\not\in \wp(X))
\end{array}
\right.
\end{align}つまり, は要素 を の要素に対応付けるものであるが, が の部分集合 に含まれる場合は として,そうでない場合は の要素である に対応付けしてやるのである.
であるので,明らかに は全射であるが,これは先ほどの定理1に矛盾する.つまり,「集合全体の集合」というものを認めてしまうと,矛盾が導かれるのである.これをカントールのパラドックスと呼ぶ.
さて,この写像 に対し,先ほどの定理1の証明をあてはめてみると,矛盾が導かれる理屈がラッセルのパラドックスとほぼ同じであることに気付くだろう.つまり,いま与えられている全射 に対し,\begin{align}
B=\{ x \mid (x\in X) \land (x\not\in f(x)) \}
\end{align}を考えると, より である.よって の定義より となり矛盾する.