（今回の記事については、
と、ここで参考文献としてあげられている、
- 作者: 森毅
- 出版社/メーカー: 共立出版
- 発売日: 1976/12/10
- メディア: 単行本
- この商品を含むブログ (3件) を見る
を参考にさせてもらった。以下の内容は、ほとんど、この Yanofsky の論文を参考にして書いている。）
さて。
この前から、自己言及の問題についてさまざまに書かせてもらっていたわけであるが、ここでは、この「自己言及」を、つまり、まあ、いわゆる「対角線論法」（また、それを一般化した「不動点定理」）が、どれくらい、そういった「パラドックス」の説明になっているのかを、非常にラフなスケッチではあるが書いてみたい。
（あのさ。どうでもいいんだけれど、なんで、いわゆる「現代思想」とかの界隈って、こういうのを本にしないんだろうねｗ）
数学において、さまざまに現れてきた「パラドックス」と呼ばれてきたもの、それは、クレタ人の嘘つきパラドックスに始まり、集合論のパラドックス、ゲーデルの不完全性定理など、それらの多くには、ある
- （見た目上の似た）証明方法
が見られることが分かっている。
さて。その説明に入る前に、代表的な「対角線論法」の例として、カントールの定理をみてみよう。
Ｓ≡{Ｘ:集合}
Ｎ≡{Ｘ:自然数}
Ｒ≡{Ｘ:実数}
∀Ｘ∈Ｓ；card(Ｘ)≡（Ｘの濃度）
∀Ｘ,Ｙ∈Ｓ；Ｆ(Ｘ,Ｙ)≡{f:Ｘ→Ｙ:関数}
としておく。
カントールの定理（ver.1）：
card(Ｎ)
なのだ、と。
カントールの定理（ver.1）の証明：
card(Ｎ)
まあ、こんな感じで見るからに、「対角線」でなんかやってるなー、というか、まあ、ようするに「自己言及」だよな。「自己参照」と言ってもいいけど（しかし、この例は「パラドックス」の例ではないですけどね）。
ということで、これを少し一般化して書いたものが以下：
∀Ｙ∈Ｓ；∀α∈Ｆ(Ｙ,Ｙ)；（α:不動点をもつ）≡（∃y∈Ｙ；α(y)=y）
∀Ｔ∈Ｓ；∀f∈Ｆ(Ｔ×Ｔ,Ｙ)；∀g∈Ｆ(Ｔ,Ｙ)；（f:gを表現可能）≡（∃t∈Ｔ；g(-)=f(-,t)）
∀Ｔ∈Ｓ；∀f∈Ｆ(Ｔ×Ｔ,Ｙ)；（f:Ｆ(Ｔ,Ｙ)を表現可能）≡（∀g∈Ｆ(Ｔ,Ｙ)；f:gを表現可能）
と定義して、
カントールの定理（ver.2）：
Ｙ∈Ｓとする。
∃α∈Ｆ(Ｙ,Ｙ)；（α：不動点をもたない）
⇒
∀Ｔ∈Ｓ；∀f∈Ｆ(Ｔ×Ｔ,Ｙ)；（f:Ｆ(Ｔ,Ｙ)を表現可能でない）
ちなみに、この対偶をとったものが、
ローヴェルの不動点定理（ver.1）：
Ｙ∈Ｓとする。
∃Ｔ∈Ｓ；∃f∈Ｆ(Ｔ×Ｔ,Ｙ)；（f:Ｆ(Ｔ,Ｙ)を表現可能）
⇒
∀α∈Ｆ(Ｙ,Ｙ)；（α：不動点をもつ）
で、こっちの方が肯定文で書いてあるし、証明も構成的に書ける：
不動点定理の証明：
Δ∈Ｆ(Ｔ,Ｔ×Ｔ)：Δ(-)≡(-,-)、とする。
g∈Ｆ(Ｔ,Ｙ)：g(-)≡α(f(Δ(-)))=α(f(-,-))、とする。
よって、∃t∈Ｔ；g(-)=f(-,t)
よって、α(g(t))=α(f(t,t))=g(t)
ちなみに、この「Δ」が「対角線」ということらしいｗ
この証明を見ると、もう少し条件を弱められることが分かる：
ローヴェルの不動点定理（ver.2）：
Ｙ∈Ｓ、α∈Ｆ(Ｙ,Ｙ)、Ｔ∈Ｓ、f∈Ｆ(Ｔ×Ｔ,Ｙ)とする。
g∈Ｆ(Ｔ,Ｙ)：g(-)≡α(f(Δ(-)))、f:gを表現可能（i.e. ∃t∈Ｔ；g(-)=f(-,t)）
⇒
α：不動点をもち、それは、「f(t,t)」と書ける。
さて。
ラッセルのパラドックスの証明:
「Ｙ」として、「真、偽」の二つの値をもつ「真偽値」集合として、「Ｔ」は「Ｓ」とする。
f∈Ｆ(Ｓ×Ｓ,真偽値)：f(Ａ,Ｂ)≡真（Ａ∈Ｂ）、f(Ａ,Ｂ)≡偽（¬（Ａ∈Ｂ））とすると、f:Ｆ(Ｓ,真偽値)を表現可能。
ところが、「真偽値」集合「否定」関数「¬」は不動点をもたないから、⊥。
こうやって見ると、いろんなパラドックスがこの「形式」で記述できることが分かりますよね。
グレリングのパラドックス：
Ａdj≡{Ｘ:日本語の形容詞}
∀Ｘ∈Ａdj：（Ｘ:ヘテロロジカル）≡（Ｘ:この単語が自分自身を表現していない）
（たとえば、「日本語」は「日本語」の単語でもあるから、ヘテロロジカルじゃない、といった感じ。）
¬（ヘテロロジカル：ヘテロロジカル）
グレリングのパラドックスの証明：
f∈Ｆ(Ａdj×Ａdj,真偽値)：f(Ａ,Ｂ)≡真（Ａ：Ｂという単語が表現している）、f(Ａ,Ｂ)≡偽（Ａ：Ｂという単語が表現していない）とすれは、あとは、ラッセルのパラドックスの証明と同じ。
嘘つきのパラドックス：
¬（「この文は間違っている」という文は間違っている）
¬（「私の言ったことは嘘だ」と私が言ったことは嘘だ）
嘘つきのパラドックスの証明：
Ｓnt≡{Ｘ:日本語の文}、または、Ｓnt≡{Ｘ:私が言ったこと}
f∈Ｆ(Ｓnt×Ｓnt,真偽値)：f(Ａ,Ｂ)≡真（Ａ：Ｂという文が表現している）、f(Ａ,Ｂ)≡偽（Ａ：Ｂという文が表現していない）
一応、カントールの定理の二つのヴァージョンの関係についても書いておくと：
カントールの定理の二つのヴァージョンの関係：
「Ｙ」は「真偽値」集合として、「Ｔ」は「Ｎ」とする。
Ｉ≡{0,1}
card(真偽値)=card(Ｉ)
実数を２進数で考えれば、
card([0,1))=card(Ｆ(Ｎ,Ｉ))=card(Ｉ^Ｎ)
また、値が「1」というのを「部分集合」と考えれば、
card(Ｉ^Ｎ)=card(Ｐ(Ｎ))
あとは、ラッセルのパラドックスの「f」の「Ｓ」を「Ｎ」にすればいい。
（集合論において、濃度が一致するということは、「同一視」できる、ということなんですよね。だから、いろんな証明でそこが「省略」されて書いてあったりするｗ。）
ところで、ここで、「否定」関数が大活躍をするわけであるがｗ、上記の最初の論文では少しおもしろいことが書いてある。
ラムダ計算（lambda calculus、λ-calculus）は、プログラムとデータの区別がまったくない、理想化された計算体系である。
長谷川真人「自己言及の論理と計算」
ラムダ計算に馴染みがなくても、
- λx.... を {x|...} （...をみたすxの全体）
- MN を N∈M （NはMの要素）
- f(...) を ¬(...) （...の否定）
と読み替えれば、実は Yf は以下のようになる：
- {x|¬x∈x}∈{x|¬x∈x}
したがって、Yf=f(Yf)はラッセルの逆理に他ならない。
（だからといって、ラムダ計算は矛盾しているというわけではない。むしろ、ラムダ計算のようにすべてのものが不動点をもつ世界では、否定「¬」に相当するものを表現することができない、と考えるのが妥当である。）
長谷川真人「自己言及の論理と計算」
（エディタの emacs が lisp言語で動いているわけだが、これはどうだったかは覚えていないけど、たしか、common-lisp は、プログラムとデータの区別がまったくなかったことを覚えている（つまり、データ上に書かれている「プログラム」を「実行」できる、という感じで）。この辺の世界になってくると、そもそも、なにをやってるのか分かんなくなっていきそうな感じですね...。）
さて。そういうわけで、ゲーデルの不完全性定理なのだが：
Ｌind≡{Ｘ:論理式}
Ｌind^i≡{Ｘ:i個の自由変数をもつ論理式}
∀Ｘ∈Ｌind：Proof(Ｘ)≡{Ｙ:Ｘの証明}
Proof≡{Ｙ:∃Ｘ∈Ｌind；Ｙ∈Proof(Ｘ)}
∀Ｂ∈Lind∪Proof；Ｇ(Ｂ)≡（Ｂのゲーデル数）
Provable≡{Ｘ∈Ｌind：∃Ｙ∈Ｐroof；Ｙ∈Proof(Ｘ)}
Prov:Proof×Ｌind→Ｌind、Prov(y,x)≡（∃Ｘ∈Ｌind；∃Ｙ∈Proof(Ｘ)；Ｇ(Ｙ)=y,Ｇ(Ｘ)=x）
Ｄ:Ｎ→Ｎ、∀Ｂ∈Lind^1；Ｄ(Ｇ(Ｂ(x)))≡Ｇ(Ｂ(Ｇ(Ｂ(x))))
として、
対角線補題：
∀ε∈Ｌind^1；∃Ｃ∈Ｌind^0；（Ｃ⇔ε(Ｇ(Ｃ))）∈Provable
対角線補題の証明：
f:Ｌind^1×Ｌind^1→Ｌind^0、f(Ｂ,Ｈ)≡Ｈ(Ｇ(Ｂ(X)))、とする。
Φ_ε:Ｌind^0→Ｌind^0、Φ_ε(Ｐ)≡ε(Ｇ(Ｐ))、とする（これが不動点をもてばいい）。
g:Ｌind^1→Ｌind^0、g(-)≡Φ_ε(f(Δ(-)))、とする。
- f:gで表現可能
なぜなら、ＧＦ(x)≡ε(Ｄ(x))
とすると、g(Ｂ(x))=ε(Ｇ(Ｂ(Ｇ(Ｂ(x)))))=ε(Ｄ(Ｇ(Ｂ(x))))=ＧＦ(Ｇ(Ｂ(x)))=f(Ｂ(x),ＧＦ(y))ここから、ローヴェルの不動点定理（ver.2）により、Φ_εは、f(ＧＦ(x),ＧＦ(y))という不動点をもつ。
ちなみに、f(ＧＦ(x),ＧＦ(y))=ＧＦ(Ｇ(ＧＦ(x)))
ということで、
うーん。もう少しきれいに書けないものかなあ。ところで、この Yanofsky の論文であるが、読むと、膨大な数のこの「不動点定理」を使った例が紹介されているのだが（まあ、その内容を詳しく書いていないのも含めて）、膨大にあるわけでｗ、せめて、現代思想がどうのこうのと、うんぬんしたがっている連中は、これら＜全部＞を理解してから言ってくれないかな、って、どうせ読みやしないんでしょうけど...。
