ラッセルのパラドックスとY-コンビネータ

『自己言及の論理と計算』長谷川真人著の7ページには、ローヴィルの不動点定理について次のように説明してある。

ここからは,より一般的な観点から,ラッセルの逆理やカントールの対角線論法などの背後に共通する数学的な仕組みについて考えてみよう.ここでは,一種の不動点定理を拠所にして,種々の同様な現象へのシステマティックなアプローチを試みる.
 まず,ややインフォーマルな説明をしよう.φ : A × A → B について,以下のことが成り立っているものとする.
任意の g : A → B に対しある a ∈ A が存在して g(x) = φ(a, x) が成り立つ (このような a を g のインデックスと呼ぶ).

このとき,任意の f : B → B は不動点を持つ.具体的には,g0 : A → B を g0(x) =f(φ(x, x)) で定義してやり, a0 ∈ A を g0 のインデックスとすると, φ(a0, a0) は fの不動点になっている.実際,f(φ(a0, a0)) = g0(a0) = φ(a0, a0).
ほとんど自明とも思われる結果だが,ここには,インデックス付けによる数え上げ,対角成分への着目 (関数の自分自身のインデックスへの自己適用) による不動点の構成といった,数理論理学や計算の理論の基礎的なアイデアが,端的なかたちであらわれている.
 より正確には,有限直積をもつ任意の圏について,以下の結果が知られている (ローヴィル4 の不動点定理).圏論の言葉になじみのない人には,上記の説明で十分なので,とばしてもらってかまわない.

この不動点定理の説明で A を対象の集合、Bを真理値の2値集合 {0, 1}、φを対象の直積から2値集合 {0, 1} への関数、つまり対象間の帰属関係をあらわす判別関数とすると、この不動点定理を素朴集合論の世界に適用できる。

すなわち、g(x) はある集合 a が任意の対象 x を要素として含むかどうかの判別関数であり、素朴集合論の世界では任意の対象(集合)a がそういう判別関数を持っているので、g(x) = φ (a, x) だ。このとき対象(集合)a は g(x) のインデックスになる。g(x) = 1 となる対象 x を集めると対象 a の外延である対称の集まりを求めることができる。{x| g(x) = 1} は a の内包的定義になる。

関数 f : B -> B は真理値から真理値への関数つまり、1引数の論理演算子だ。g0(x) = f(φ(x,x)) なので、g0(x) は対象 x が自分自身を要素として含むかどうかの真理値に論理演算子 f を適用したときの判別関数だ。対角線成分に f が関数適用されていることになる。

この判別関数 g0 のインデックス a0 は対角線成分に f を適用して得られる集合 a0 を表している。すると素朴集合論の世界では次の不動点が存在する。

f(φ(a0, a0)) = g0(a0) = φ(a0, a0)

f が否定演算子 ¬ の場合この不動点はラッセルのパラドックスを発生する。すなわち、a0 が自分自身を要素として含んでいなければ(¬(φ(a0, a0)) a0 は自分自身を要素として含む (φ(a0, a0))が同時に起きる。この時判別関数 g0(x) のインデックス a0 は「自分自身を要素として含まない集合の集合」である。

どこに問題があるのかというと、

任意の g : A → B に対しある a ∈ A が存在して g(x) = φ(a, x) が成
り立つ (このような a を g のインデックスと呼ぶ).

という仮定だ。つまり、全ての集合がその要素を判別するための判別関数(内包的定義)を持つと考える素朴集合論の世界では、否定論理演算子 ¬ についての不動点のためにパラドックスが発生してしまうのだ。

このパラドックスの解決は上の仮定が成立しないことを認めることだ。すなわち、インデックス a を持たない判別関数 g : A -> B が存在する。対象(集合)の集合の要素をその冪集合の要素と全単射させることは不可能なため(要素数のほうが圧倒的に不足する)、判別関数 g(x) によって定められる対象の集合でありながら、そのインデックス a を持たないものが存在しているのだ。その対象からなる全ての集合を判別関数(内包的定義)で定義するには要素数(濃度)が不足するということだ。

しかし、対象の集合の部分集合を表す記号を、対象の集合の外に求めれば、この問題は起きない。言い方を変えると、集合の世界を「帰属関係の定義された対象の集合」として捉えようとしても、その集合の全ての部分集合を表すためには、対象の数が不足してしまうが、集合をあらわすインデックスを対象の集合以外に求めれば問題は解決する。集合を表すインデックスが対象の集合の外にあれば、不動点は発生せず、任意の判別関数に対し集合のインデックスを求めることができる。

ただし、このことはインデックスを対象の集合の要素に求められないというわけではなく、対象のうちインデックスとすることができるものはそうすればいいのだ。この観点から見ると、対象の集合の部分集合のインデックスは対象の外にあり、これを「広義のクラス」と考える。また、対象の集合の要素にインデックスを求めることができる場合は、これを「集合」と考える。対象の集合の要素にインデックスを求められない要素の(部分)集合に対しては、これを「狭義のクラス」と考えるのだ。こうすれば、対象の集合の全ての部分集合に対し「広義のクラス」のインデックスを求めることができ、内包的定義はかならず「広義のクラス」を定めることが分かる。

こう考えると公理的集合論の公理がなぜあのように複雑なのかが分かる。これらの公理は、対象の集合内にインデックスを持つ集合だけを取り出すためのルールなのだ。

ところで、上の不動点の議論のかなめとなるのが、

f(φ(a0, a0)) = g0(a0) = φ(a0, a0)

となる任意の関数 f の不動点 φ(a0, a0) の存在だ。これは、Y-コンビネータによる不動点、

Y g = g (Y g)

と対応している。Y−コンビネータはラッセルのパラドックスと同じメカニズムなのが分かる。

[PR]
by tnomura9 | 2017-11-22 07:48 | ラッセルのパラドックス | Comments(0)
<< 集合とは何か 関数の自己適用 >>