ラッセルのパラドックス

今日は有名なラッセルのパラドックスが起きるメカニズムを考えてみます。

ラッセルのパラドックスは数学の基礎である集合論に対する重要な問題提起となったものですが，ラッセルのパラドックスが起きるメカニズム自体には集合論は関係ないというお話です。

ラッセルのパラドックスとは「自分自身を含まない集合全体を考えると矛盾が生じる」というものです。

ラッセルのパラドックス (素朴集合論)
自分自身を要素として含まない集合全体の集合 $R=\{x \mid x\not\in x\}$ の存在から矛盾が導かれる。

証明
排中律より， $R\in R$ または $R\not\in R$ だが， $R\in R$ とすると $R$ の定義より $R\not\in R$ となり矛盾， $R\not\in R$ とすると $R$ の定義より $R\in R$ となり矛盾。いずれにしても矛盾することが示された。
証明終

ラッセルのパラドックスから得られる教訓は「 $\{x\mid P(x)\}$ という形のものを何でもかんでも集合を思うと痛い目を見るぞ！」ということです。集合の扱いを明確に規定しない素朴集合論を数学の基礎とするのは危険だ，ということで，現代では公理的集合論というものが使われています。

公理的集合論でのラッセルのパラドックス

公理的集合論の代表選手であるZFC集合論において，ラッセルのパラドックスはどのような扱いになるのか見てみましょう。

公理的集合論 - Wikipedia

ZFCは1階述語論理の上に構築された公理系です。ZFCでは項の型は１種類しかいないので「○○は集合である」という文を表すための記号はありません。項の型が１種類なので「出てくるものは何でもかんでも集合である」と思ってもいいですが，そもそも集合以外のものがないので，「集合である」という概念自体が必要ありません。

「山田さんは日本人である」という命題が必要なのは世の中にイタリア人もベトナム人もいるからで，もし世の中に日本人しかいない世界ならば，「日本人である」という概念そのものが必要ないのと同じことです。

1階述語論理では個体変項・個体定項・述語記号・関数記号といった文字（記号）と，論理記号 $\vee, \wedge, \to, \leftrightarrow, \forall, \exists, \perp$ を使います。 $\perp$ は「矛盾」を表す記号です。ZFCにおける $x\in y$ は2項述語記号の一種で，普通の記法 $p(x,y)$ に合わせるなら $\in(x,y)$ と書くべきかもしれませんが，慣習により $x\in y$ と書かれます。 $x\not\in y$ は $\lnot (x\in y)$ を省略したものです。

$A \leftrightarrow B$ は $(A\to B)\wedge (B\to A)$ を省略したもの， $A\to B$ は $\lnot A\vee B$ を省略したものとします。

ZFCにおいて，ラッセルのパラドックスに出てくる「集合 $R=\{x \mid x\not\in x\}$ の存在」を表す論理式は\begin{align}\exists y~\forall x~ (x\in y \leftrightarrow x \not\in x)\end{align}になります。この論理式を仮定すると矛盾が導かれる，というのがZFCにおけるラッセルのパラドックスです。

1階述語論理の推論体系として，自然演繹を採用しましょう。詳しくは次のpdfファイルを見てください。
http://abelard.flet.keio.ac.jp/person/takemura/class/2011/print-folnat.pdf(日本大学竹村亮准教授の講義資料 pdf file)

推論規則として，いくつかの導入規則・除去規則，そして背理法が定義されています。論理式の集合 $\Gamma$ から，自然演繹で論理式 $A$ が導出されることを $\Gamma~\vdash~A$ で表します。

$\vee$ 除去規則は，いわゆる場合分けによる証明を形式化したものです。特別な場合として $B, C$ が共に $A$ の場合を考えると $A\vee A \vdash A$ を得ることができます。

$\exists$ 除去規則で $C$ が $A[x:=t]$ の場合を考えると $\exists x A[x]\vdash A[x:=t]$ が得られます。これは例えば「ある $x$ が存在して $x^2+3x+1=0$ が成り立つ」ことが示されているとき，その存在するという $x$ を $t$ とおき，「 $t^2+3t+1=0$ 」とするといった，存在が示されたものに固有の記号を割り当てる操作を形式化したものです。

さて，次がZFCにおけるラッセルのパラドックスです。

ラッセルのパラドックス (ZFC集合論)\begin{align}\exists y~\forall x~ (x\in y \leftrightarrow x \not\in x) ~\vdash~ \perp\end{align}

証明
個体定項の記号として $r$ が用意されているとする。

$\exists y~\forall x~ (x\in y \leftrightarrow x \not\in x)$
$\forall x~ (x\in r \leftrightarrow x \not\in x)$ 　　［ $\exists$ 除去規則］
$(r\in r \leftrightarrow r \not\in r)$ 　　［ $\forall$ 除去規則］
$( (r\in r \rightarrow r \not\in r) )\wedge ( (r\not\in r \rightarrow r \in r) )$ 　　［ $\leftrightarrow$ の定義］
$( (r\not\in r) \vee (r \not\in r) )\wedge ( (r\in r) \vee (r\in r) )$ 　　［ $\rightarrow$ の定義］
$(r\not\in r) \vee (r \not\in r)$ 　　［5 に $\wedge$ 除去規則］
$(r\not\in r)$ 　　［6 に $\vee$ 除去規則］
$(r\in r) \vee (r \in r)$ 　　［5 に $\wedge$ 除去規則］
$(r\in r)$ 　　［8 に $\vee$ 除去規則］
$(r\in r)\wedge (r\not\in r)$ 　　［9, 7 に $\wedge$ 導入規則］
$\perp$ 　　［ $\lnot$ 除去規則］

証明終

この証明をよく見てみると，ZFCの公理は一切出てきません。1階述語論理の推論規則だけから矛盾を導くことができるのです。述語記号 $x\in y$ を集合論の記号として性格付けしているのは ZFC の公理系なので，この証明は集合論とは何の関係もないと言っていいでしょう。

もちろん集合論の公理系と全く無関係という訳でなく「 $\exists y~\forall x~ (x\in y \leftrightarrow x \not\in x)$ が導かれてしまうような強すぎる公理は採用したらダメ」ということを教えてくれています。

1階述語論理でのラッセルのパラドックス

ラッセルのパラドックスの証明に集合論の公理は何の関係もありませんでした。 $x\in y$ という集合論の述語記号でなくても，任意の述語記号 $p(x,y)$ に対して同じように矛盾を導くことができます。繰り返しになりますが証明も一応書いておきましょう。

ラッセルのパラドックス (1階述語論理)
$p(x,y)$ を2項述語記号とする。\begin{align}\exists y~\forall x ~(p(x,y) \leftrightarrow \lnot p(x,x)) ~\vdash~ \perp\end{align}

証明
個体定項の記号として $c$ が用意されているとする。

$\exists y~\forall x~ (p(x,y) \leftrightarrow\lnot p(x,x) )$
$\forall x~ (p(x,c) \leftrightarrow \lnot p(x,x) )$ 　　［ $\exists$ 除去規則］
$(p(c,c) \leftrightarrow\lnot p(c,c) )$ 　　［ $\forall$ 除去規則)］
$( (p(c,c) \rightarrow \lnot p(c,c)) )\wedge ( (\lnot p(c,c) \rightarrow p(c,c) )$ 　　［ $\leftrightarrow$ の定義］
$( \lnot p(c,c) \vee \lnot p(c,c) )\wedge (p(c,c) \vee p(c,c) )$ 　　［ $\rightarrow$ の定義］
$\lnot p(c,c) \vee \lnot p(c,c)$ 　　［5 に $\wedge$ 除去規則］
$\lnot p(c,c)$ 　　［6 に $\vee$ 除去規則］
$p(c,c) \vee p(c,c)$ 　　［5 に $\wedge$ 除去規則］
$p(c,c)$ 　　［8 に $\vee$ 除去規則］
$p(c,c)\wedge \lnot p(c,c)$ 　　［9, 7 に $\wedge$ 導入規則］
$\perp$ 　　［ $\lnot$ 除去規則］

証明終

ZFCはラッセルのパラドックスを回避できているか?

ラッセルのパラドックスなどのパラドックスを回避することが公理的集合論ができる動機の１つだったのは間違いないでしょう。Wikipedia：公理的集合論の中には以下のような記述があります。

公理的集合論 - Wikipedia

パラドックスの回避

ツェルメロが ZF の元となる公理系を1908年に発表した最大の動機は、実数が整列可能だとする彼の証明を弁護することであった。しかし、同時に彼はその当時すでに知られていたパラドックスを回避しなければいけないこともわかっていた。代表的なものとしては、ラッセルのパラドックス、リシャールのパラドックス、ブラリ＝フォルティのパラドックスがある。これらのパラドックスは、集合を構成する方法に制限を付けている ZFC の中では展開できない。例えば、ラッセルのパラドックスで用いられる\begin{align}{\displaystyle \{x\mid x\notin x\}}\end{align}という集まりは ZFC の中では構成できないし、リシャールのパラドックスで用いられる構成は論理式で記述できない。

ZFCではラッセルのパラドックスを回避できていると言っているように読めますが本当でしょうか？問題はZFCの公理系から自然演繹でラッセルのパラドックスを表す \begin{align}\exists y~\forall x~ (x\in y \leftrightarrow x \not\in x)\end{align}という論理式を導出できるかどうかです。

$\exists y~\forall x~ (x\in y \leftrightarrow x \not\in x)$ から矛盾 $\perp$ が導かれるのですから，もしZFCが無矛盾なら当然この論理式は導出されません。一方でもしZFCが矛盾しているなら，矛盾している公理系からはどんな論理式も導出できるので，この論理式も導出できることになります。つまりZFCがラッセルのパラドックスを回避できているかどうかはZFCの無矛盾かどうかに依ります。しかし，ZFCの無矛盾性は証明されていないので，ZFCがラッセルのパラドックスを回避できていることもまだ証明されていない事になります。

まあ，これはちょっとひねくれた見方ですかね。「ZFC集合論では素朴集合論のような単純な形ではラッセルのパラドックスは起きない。ZFCの無矛盾性は多くの人が信じているので，ZFCがラッセルのパラドックスを回避できていることも多くの人が信じている」といったところでしょうか。

ラッセルのパラドックスの応用

定理を証明したら，何かおもしろい応用がないか考えてみることは大切です。せっかくなのでラッセルのパラドックスの応用も考えてみました。

有限集合 $S$ の要素数を $|S|$ で表すことにします。

定理
$U$ を有限集合とし， $X\subset 2^U$ を $U$ の部分集合族とする。
このとき，次の条件1, 2 を満たす $A\in X$ は存在しない。

$B\in X$ かつ $|B|=5$ ならば， $B\not\subset A$ 。
$B\in X$ かつ $|B|\neq 5$ ならば， $|A\cap B|=5$ 。

$B_1, B_2\in X$ に対し，命題「 $|B_1\cap B_2|\neq 5$ 」を $P(B_1,B_2)$ で表すことにすると，条件1, 2を満たす $A\in X$ が存在するという命題は\begin{align}\exists A\in X~(\lnot P(B,B) \Leftrightarrow P(A,B))\end{align}と書くことができる。

定理の主張を背理法で示す。条件1, 2 を満たす $A$ が存在したと仮定する。

論理式の集合 $\Gamma =\{\exists y~\forall x ~(p(x,y) \leftrightarrow \lnot p(x,x))\}$ を考える。 $X$ を定義域とし，2変数述語記号 $p$ を命題 $P$ と解釈すると，これは $\Gamma$ のモデルになっている。しかし， $\Gamma \vdash \perp$ だったので，1階述語論理の健全性により $\Gamma$ はモデルを持たない。これは矛盾。

よって，背理法により条件1, 2 を満たす $A$ は存在しない。
証明終

もちろんこんな持ってまわった証明をせずに， $|A|=5$ のとき条件1より $A\not\subset A$ となり矛盾， $|A|\neq 5$ のとき条件2より $|A|=|A\cap A|=5$ となり矛盾，というやり方でも証明できます。素朴集合論でのラッセルのパラドックスの証明と同じやり方です。ラッセルのパラドックスで起きる矛盾は割と素朴なものなので，あまり複雑な例は作れないですね。