人気ブログランキング | 話題のタグを見る

不動点定理のおもちゃ

ψ: X × X -> {0, 1} について、g(x) = ψ(a0, x) と定義する。このとき g(x) = f(ψ(x,x)) であれば、すなわち、g(x) = ψ(a0, x) = f(ψ(x,x)) であれば、ψ(a0, a0) は f に対して不動点になる。なぜなら f(ψ(a0, a0)) = g(a0) = ψ(a0, a0) である。この不動点定理はわかりやすいが、いや、わかったと思いやすいがこのモデルになる ψ(x,y) を作ろうと思うと結構難しい。

そこで、おもちゃのような例を考えてみた。X = {1, 2, 3} という有限集合について ψ(x, y) を考えてみる。ψ(x, y) : X × X -> {0,1} は次のような表で表現できる。行と列の数字は引数の値を表し、行と列の交点の値が ψ(x,y) の値である。例えば次のような表ができる。

_ 1 2 3
1 0 0 0
2 0 1 0
3 0 1 1

すぐにわかるように3列に配置される0と1の組み合わせは上に採用した3つだけでなく 2^3 = 8 個ある。

0 0 0
0 0 1
0 1 0
0 1 1
1 0 0
1 0 1
1 1 0
1 1 1

したがって ψ(x, y) の値としてはこの8つのうちの3つだけしか使えないことになるが、ここでは冒頭に示した例に戻る。冒頭の計算表がここで定義した ψ(x,y) の振る舞いの全てを尽くしていることは明らかだ。このとき g1(x) = ψ(1, x) とおくと、

g1(1) = 0, g1(2) = 0, g1(3) = 0

になる。同様に、

g2(1) = 0, g2(2) = 1, g2(3) = 0
g3(1) = 0, g3(2) =1, g3(3) = 1

である。またψの対角線部分については ψ(1,1) = 0, ψ(2,2) = 1, ψ(3,3) = 1 である。

ここで引数が {0, 1} の要素であるブール代数 f を次のように定義する。

f(x) = ¬(1 ∨ x)
を考える。この関数は常に 0 を出力するつまり、f(0) = 0, f(1) = 1 である。この f を使って g(x) を定義する。

g(x) = f(ψ(x,x))

この関数の値は、

g(1) = f(ψ(1,1)) = f(0) = 0
g(2) = f(ψ(2,2)) = f(1) = 0
g(3) = f(ψ(3,3)) = f(1) = 0

明らかにこの g(x) は g1(x) と同じものだ。そこで f(ψ(1,1)) を計算すると、

f(ψ(1,1)) = f(0) = 0 = ψ(1,1)

となり、ψ(1,1) = 0 が f の不動点になっていることがわかる。ちなみに、ψ(2,2) は f の不動点ではない。

f(ψ(2,2)) = f(1) = 0 /= ψ(2,2)

しかしどのような f に対しても ψ(a0, a0) が不動点となるわけではない。上の例で g(x) = ¬ ψ(x,x) で定義すると、

g(1) = ¬ ψ(1,1) = ¬ 0 = 1
g(2) = ¬ ψ(2,2)) = ¬ 1 = 0
g(3) = f(ψ(3,3)) = ¬ 1 = 0

となり、このような関数 g(x) は ψ の計算表の中に見つけることはできない。

これは可能な8個の可能性のどの3つを採用しても同様である。したがって、g(x) = ¬ ψ(x,x) に対応する a0 を見つけることはできない。この関係は集合 X に採用する自然数の範囲をどんなに広げても同じである。

上の gn(x) という関数は値が 1 のところの自然数を拾っていくと自然数の集合を規定しているので、結局のところ自然数と自然数のべき集合の全単射ができないことの証明になる。この証明の利点は、どの自然数が議論に使われているかが明確なところだ。全ての自然数をシステム的に考慮しているのが明白だ。カントールの対角線論法では、全ての自然数について考慮されているかどうかが必ずしも明白でない。

ψ(x,y) は2項演算だが、これを集合の所属関係 ∈ と考えるとそのままラッセルのパラドックスになる。

自然数と偶数の全単射を考えるとき、要素が無限大になるのは一方向だけだ。どちらも再帰的に要素が1つずつ増加していく。しかし、自然数の直積の関数を考えるときは値の可能性が 2^n - 2^(n-1) ずつ増加する。このことが再帰的定義で全単射が作れない理由なのではないだろうか。要は再帰関数の性質の違いなのだろう。無限を数え尽くすことはできないのだから、問題はその過程に存在するはずだからだ。

by tnomura9 | 2015-11-02 23:37 | ラッセルのパラドックス | Comments(0)
<< 床屋のパラドックスと不動点 対角線論法の意味 >>