ラッセルのパラドックスとカントールのパラドックスがよく似ている件

素朴に「モノの集まり」のことを集合と定義する素朴集合論では様々な形で矛盾が引き起こされることが知られていて，なかでもラッセルのパラドックスとカントールのパラドックスと呼ばれるものが有名である．この2つのパラドックスは似ている面もあって，たまに混同している人も見かけるのでメモを残しておく．

$x>0$ や $x^2+2x+3=0$ のように $x$ のみを自由変数として含む開論理式を命題関数 $P(x)$ で表す． $P(x)$ は $x$ の性質を述べる述語と思える．素朴に「モノの集まり」を集合とすると， $P(x)$ を満たす $x$ 全体を集めた\begin{align} X=\{ x \mid P(x)\}\end{align}も集合ということになる．しかし，このような形のものを何でもかんでも集合としてしまうと矛盾が引き起こされる．

ラッセルのパラドックス

$P(x)$ が $x\not\in x$ の場合を考える．すなわち \begin{align} X=\{x \mid x\not\in x\} \end{align}とする．

排中律より $X\in X$ または $X\not\in X$ だが，

$X\in X$ のとき， $X$ の定義より $X\not\in X$ となり矛盾．
$X\not\in X$ のとき， $X$ の定義より $X\in X$ となり矛盾．

となりいずれの場合も矛盾している．よりシンプルに， $X$ の定義より $X\in X \Leftrightarrow X\not\in X$ となり矛盾，ということもできる．

つまり， $\exists X \forall x (x\in X \leftrightarrow x\not\in x)$ という論理式から自然演繹により矛盾が導かれるということである．これをラッセルのパラドックスと呼ぶ．

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

$A$ を集合とする． $P(x)$ が $x\subset A$ の場合を考えると \begin{align}\wp(A)=\{x \mid x\subset A\}\end{align}という集合ができる． $\wp(A)$ は $A$ の部分集合全体である．これを $A$ のべき集合と呼ぶ．次の定理の証明は対角線論法という名前でよく知られている．

定理1 任意の集合 $A$ と任意の写像 $f: A\to \wp(A)$ に対し $f$ は全射ではない．

（証明） $f$ が全射であると仮定する． $B=\{ x \mid (x\in A) \land (x\not\in f(x)) \}$ とすると， $B \in \wp(A)$ より，ある $b\in A$ が存在して $f(b)=B$ となる．

$b\in B$ とすると $B$ の定義より $b\not \in f(b)=B$ となり，矛盾．
$b\not\in B$ とすると $B$ の定義より $b\in B$ となり，矛盾．

いずれ場合も矛盾するので，背理法 *1より $f$ は全射ではない．（証明終）

さて， $P(x)$ が恒真式を表す命題定数 $\top$ のとき（ $x=x$ のようなトートロジーで代用してもよい），すなわち \begin{align}X=\{x \mid \top\}\end{align}を考えると，この $X$ は「集合全体の集合」になっている．この $X$ のべき集合 $\wp(X)$ を考えると， $X$ は集合全体の集合だったので $\wp(X)\subset X$ である．すると，次のような写像 $f:X\to \wp(X)$ を定義することができる \begin{align}
f(a)=
\left\{
\begin{array}{lc}
a & (a\in \wp(X))\\
X & (a\not\in \wp(X))
\end{array}
\right.
\end{align}つまり， $f$ は要素 $a\in X$ を $\wp(X)$ の要素に対応付けるものであるが， $a$ が $X$ の部分集合 $\wp(X)$ に含まれる場合は $f(a)=a$ として，そうでない場合は $\wp(X)$ の要素である $X$ に対応付けしてやるのである．

$\wp(X) \subset X$ であるので，明らかに $f$ は全射であるが，これは先ほどの定理1に矛盾する．つまり，「集合全体の集合」というものを認めてしまうと，矛盾が導かれるのである．これをカントールのパラドックスと呼ぶ．

さて，この写像 $f$ に対し，先ほどの定理1の証明をあてはめてみると，矛盾が導かれる理屈がラッセルのパラドックスとほぼ同じであることに気付くだろう．つまり，いま与えられている全射 $f: X\to \wp(X)$ に対し，\begin{align}
B=\{ x \mid (x\in X) \land (x\not\in f(x)) \}
\end{align}を考えると， $B\in \wp(X)$ より $f(B)=B$ である．よって $B$ の定義より $B\in B \Leftrightarrow B\not\in B$ となり矛盾する．

このような見方をすると，ラッセルのパラドックスとカントールのパラドックスはよく似たものである．

*1:正確には $\lnot$ 導入規則である． $\lnot P$ を仮定して矛盾が導かれた場合 $P$ を結論付けるのが背理法で， $P$ を仮定して矛盾が導かれた場合 $\lnot P$ を結論付けるのは $\lnot$ 導入規則である．しかし二重否定の除去を認める古典論理ではこの2つを区別する必要もないので，どちらも背理法と呼ばれることが多い．直観主義論理では背理法は認められないが， $\lnot$ 導入規則は認められる（ $P$ から矛盾が導かれることを $\lnot P$ の定義とすることもある）．ある実数が無理数であることの定義を「有理数でないこと」とすると，よく知られた $\sqrt{2}$ が無理数であることの背理法を用いた証明は，正確には $\lnot$ 導入規則であることになる．