ラッセルのパラドックス：傾向と対策 (3.3): 不動点と自己言及パラドックス

logic

どーも、皆様お久しぶりです。前回が10月28日、一ヶ月強の時間が空いてしまいました。今回は前回までのまとめということで、不動点とラッセルのパラドクスの関係をおさらいしたいと思います。

自己言及性の統一的取り扱い

さて、誰もが言うことですが、ラッセルのパラドックスと嘘つきのパラドックスは「似ています」。同じ自己言及型のグレリングのパラドックスも似ています。他に、カントールの |P(X)|> |X| を始め、多くの定理は対角化で証明されますが、それらの証明はとてもよく「似ています」。しかし、似ているのはいいのですが、「似ているよ分析」では困ります：どんな意味で「似ている」のか、もう少しきっちりと語ることはできないものでしょうか。
このような場合、圏論の方法を使い抽象的なアプローチをすることが助けになります。ラッセルのパラドックスの構造を簡単に表示すると、以下の構造になります。

このdiagramはYanofskyの "A Universal Approach to Self-Referential Paradoxes, Incompleteness and Fixed Points" *1のp.8からの引用です。

古典論理上のラッセル・パラドックスの導出

さて、上のdiagramの説明を。

  • Setsは集合全体のあつまり、2={0,1} は真理値の集合を表します。
  • Δ: Sets → (Sets × Sets) として、Δ(s) = (s,s) という埋め込み（対角化！）を考えます。
  • 次に f: (Sets × Sets) → {0,1} を定義します。具体的には以下のような常識的な関数です。
    • f(s,t) = 1 iff s ∈ t
    • f(s,t) = 0 otherwise
  • さて、ラッセル・パラドックスらしくするために、下の辺の関数 g : Sets → 2 を以下のように定義しましょう。
    • g(x) = 1 iff x is not a member of x
    • g(x) = 0 iff x is a member of x

このとき、以下が成立します。

補題：任意の集合 t に関して、ある集合 y が存在し、g(y) ≠ f (y,t) が成立する

証明：関数 α : 2→2 として、以下を定義する：

  • α(0) = 1
  • α(1) = 0

つまり上の f,g は f(x,x)= α(g(x))と書け、また任意の関数についてα(h(x))≠h(x)が成立する。
さて、ある集合 s が存在して、任意の集合 y に関して、g(y)=f(y, s) が成立すると仮定しましょう。このとき、
　　f(s,s)=g(s)=α(f(s,s))
となりますが、f = αf はαの定義から矛盾です。（証明終了）

要は、真理値が {0,1} だけなのでαは不動点を持たない、ということですね。言い忘れましたが、g(x)=α(f(Δ(x)))が成立します。
さて、あとはもう一歩、 g が特性関数となるような集合 R ={x : g(x)=1} を定義できたと仮定しましょう。このとき補題より、ある集合 y が存在して g(y) ≠ f(y, R) となるはずですが、これはRの定義と fの定義に反します。
通常のラッセルのパラドックスの導出では（そして上の補題の証明でも）、yとして集合 R 自身を取ってくればよい、ということまで証明しており、その意味で強い証明になっています。

例：カントールの定理

上のdiagramを使用してラッセルのパラドックスを語ることの意義は、多くの自己言及性を使用した議論が、このdiagramに還元することができ、その意味で「同型」であることが示せることです。例えば、カントールの |P(ω)|> |ω| の証明の場合

  • 左下：ω、左上：ω×ω、右下：2、右上：2。
  • ＜Sn : n∈ω> を任意の自然数の部分集合の可算列としたとき、 f(n,m) = 1 iff n∈Sm (otherwise f(n,m)=0)
  • 集合 G ={ n ∈ω : not (n∈Sn)} を定義し、 g(m) =1 iff m∈G と定義する
  • αは上の例と同じ（このとき g(x)=α(f(x,x))が成立する）

と、全く同じ構造となります。Yanofskyのあげている例では、この構造を共有している例として、矛盾を導く例だけでも

などなどがあります。

対策：矛盾を防ぐには

さて、ラッセルのパラドックスの導出で本質的な役割を果たしているのは、対角化関数Δと矛盾を導く関数αでしょう。従って、矛盾の導出を防ごうとする場合、以下の三つの対策が考えられます。

  1. まずなによりも、R が集合として関数 f,g の domain に出現するから問題が起こる、と言えます。R が Sets の中に現れないようにするため、「集合のサイズ」に制限をつけたり（ZFCなど）、包括原理を適用する文の型に注目したりして（タイプ理論）、パラドクスを解決することができます。どちらもRを集合と認めない解決です。
  2. また、真理値の集合が 2={0,1} だけの場合、α : 2→2には、不動点がありません。つまり0→1および1→0（これが否定を表す真理関数です）とすると、真理値はいっさい保存されません。したがって、もう一つの解決策として、真理値の集合を 2 より膨らませ、そうすることでαとして不動点を持つ関数がとれるようにするという方法があります。これがファジイ論理における解決法です。また、真理値ギャップを認めるような解決法も、こちらに分類されるのかもしれません。注意として、不動点は否定に関してだけ持つと考えると、Moh Shaw-Kweiのパラドクスのようなことが起こるため、全ての論理結合子に関して不動点がとれるようになっている必要があります。
  3. 最後に、Sets を{0,1} に埋め込むことができると考えることが問題だ、という立場もあります。つまり Sets の構造はもっと豊かで、証明論的構造と同型になっており、{0,1} に「潰す」ことなんかできない、と考える立場です。この立場を取るのが、グリシン論理上で包括原理を持つ集合論や、プラヴィッツの正規化可能な証明のみを認める集合論といえるでしょう。

応用：嘘つきのパラドックス

Yanofsky流のアプローチでは、ラッセルのパラドックスの解決法は上の3つに分類することができます（もちろんFefermanのやり方とは違いますが）。
Yanofskyの論文を読むとよくわかりますが、対角化や不動点をとるといった操作は、数理論理学のなかでそこら中で出てきます。それらの構造は、上記の圏論的な視点から見れば同型です。したがって、上はラッセルのパラドックスの例ですが、例えば嘘つきパラドックスやカントールの定理に対しても、上記の三種類のアプローチを取ることができるでしょう。例えば嘘つきパラドックスの場合

  1. 対象言語についての全域的な真理述語は、対象言語には含まれない（タルスキ）
  2. Hajek-Paris-Shephardson やRestall によるファジイ論理上の算術における解決（「嘘つき文の真理値は0.5」）。また真理値ギャップを認める解決法（クリプキも含めて）もここに分類されるのかもしれない。
  3. 嘘つき文は「発話であり、真偽は文脈によって定まる」と考え、嘘つき文は、その文の恒久的な真理値は定まらないが、真理値の依存関係は確定的に定まる（Tappendenの用語では pre-analytic である）と考える立場。個人的には、Gupta-BelnapのRevision theory of truthも、真理値の変化のプロセス自体に注目するという点において、この立場へ分類したい気分です（が当然異論が多いだろうと思います）。

という立場が、上の三例に対応するのでしょう。Parsonsが、嘘つきのパラドックスと集合論におけるパラドックス（当然ラッセルのパラドックスのことも含む）、両者の間のアナロジーについて力説していたことを思い出します。
他のものに関しては・・・今後の課題でしょうか（ご存知の方はお教えください）。

というわけで

今回は、ファジイ論理編のまとめとして、対角化や不動点を圏論的な言葉使いで振り返ってみました。単純だが奥の深い問題であると思っていただければ幸いです。
次回は・・・どうしましょう。Fitchの証明の正規化によるアプローチについて、ぼちぼちとまとめていきたいと思います。毎週という訳にも行かず、頻繁には更新できそうもないとは思いますが、気長にお待ちいただければ幸いです。

*1:今回のタネ元はこちら、内容をご存知の方は今回のエントリーを読む必要は全くありません。