床屋のパラドックスと不動点

圏論では自己言及のパラドックスは関数の不動点の問題として統一的に論じられるらしい。長谷川真人著『自己言及の論理と計算』には、不動点定理のインフォーマルな説明として次のように書いてある。

まず、ややインフォーマルな説明をしよう。φ: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).


これを読んでもほとんど何のことかわからないので、床屋のパラドックスの例に当てはめてみる。

いま、Aを村人の集合とする。Aの直積集合 A×A は村人の考えられる全てのペアからなる集合だ。A×Aの要素 (a, b) は村人a と村人 b のペアだ。(a, a) のように自分自身とのペアも考えることができる。ここで、2値集合 {true, false} へのA×Aからの写像 φ を次のように定義する。

φ(x, y) = true (xがyのヒゲを剃るとき), false (xがyのヒゲを剃らないとき)

このとき、φ(a, a) がtrue なら a は自分で自分のヒゲを剃るし、false なら自分で自分のヒゲを剃らない。

ここで、2値集合{true, false} から2値集合{true, false} への写像 f を次のように定義する。

f ( φ(x,x) ) = true (φ(x,x) がfalse のとき), false (φ(x,x)がtrue の時)

この関数 f を使うと、Aの要素つまり村人のうち、自分のヒゲを剃らないで他の人にヒゲを剃られた人を表す関数 g0(x) を次のように定義できる。

g0(x) = f( φ(x,x) ) = true (φ(x,x) がfalseのとき), false (φ(x,x) がtrue の時)

一方、a0 を床屋とすると、g0(x)がtrueのとき床屋a0はxのヒゲを剃るので、g0(x) は次のように表すことができる。

g0(x) = φ(a0, x)

これは、a0 が村人 x のうち自分のヒゲを剃らない人のヒゲを剃ることを表している。つまり、a0 は g0 のインデックスである。

そこで、a0 が自分のヒゲを剃るかどうかを、関数 f で判断してみよう。a0 が自分のヒゲを剃るかどうかの判別関数は φ(a0, a0) だから、関数 f で自分のヒゲを剃られたかどうかを判断すると、

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

ここで、f( φ(a0, a0) ) は、a0 が自分でヒゲを剃る人かどうかを判別してそれに応じてヒゲが剃られるかどうかを判断している。これは、インデックスa0で表したg0(x)と同値だから、g0(a0) と同じ値だ。g0(x) はxが床屋にヒゲを剃られるかどうかという判別関数なので、g0(a0) は、a0 が a0 にヒゲを剃られるかどうかの判別関数 φ(a0, a0) と同値である。したがって結局 φ(a0, a0) は f の不動点となっている。なぜなら、この値の関数 f による像がこの値自身になっているからだ。

このため、φ(a0, a0) がtrueであると仮定すると、φ(a0, a0) は false でなければならないことになり、パラドックスが発生してしまう。

集合Aから集合B への写像 g が、集合Aの直積集合A×Aで表現できるとき、写像 g に対応するインデックス a を求めることができる。このようなインデックスを持った関数の場合、BからBへの写像 f は不動点をもつことになる。この特殊な場合が自己言及によるパラドックスの発生の原因だった。

パラドックスは特殊な写像のもつ性質だったというわけだ。
[PR]
by tnomura9 | 2010-07-03 07:03 | 考えるということ | Comments(0)
<< 床屋のパラドックスの道具立て 床屋のパラドックス >>