カテゴリ:ラッセルのパラドックス( 59 )

関数の自己適用

Y - コンビネータのλ式は次のようになる。

Y = (λf . (λx . f (x x)) (λx . f (x x)))

このコードには不可解な点が多いが、先ず目につくのは (x x) という関数の自己適用だ。関数 x をそれ自身の x に適用させている。Y-コンビネータはさらにこの関数の自己適用でできた関数を利用して、(f (x x)) (f (x x)) とさらに2重の関数の自己適用を行っている。おそらく、これが、Y-コンビネータの無名関数で再帰的定義の関数をつくるという離れ業の原因だろう。

そこで、まず、最も単純な (x x) という形の関数の自己適用について考えてみた。この形の関数の自己適用が行われたときに x について必要な条件はなんだろうか。まず、x は関数 x を引数として取るので高階関数でなくてはならない。x に 2 を代入して (2 2) としてもこれは動作しない。

それでは x = λy.(y*2) の場合はどうだろうか。この場合 (x x) = ((λy.(y*2)) (λy.(y*2))) となるが、これも動作しない。λy.(y*2) は数値の引数をとり、数値を戻り値として返す関数だ。別の言い方をすると、この関数の domain は数値の集合で、codomain も数値の集合である。従って λy.(y*2) は関数である λy.(y*2) を引数にとることはできない。

こんどは x = id の場合を考えてみる。id x 関数は次のように定義され、引数 y をそのまま返す関数だ。

id y = y

この関数 id は (id id) のように関数の自己適用ができるだろうか。これは可能だ。id は引数 id をそのまま帰すので (id id) = id となる。これは次のように Haskell でも試してみることができる。

Prelude> let id x = x
Prelude> id 2
2
Prelude> ((id id) 2)
2
Prelude> ((id (id id)) 2)
2
Prelude> ((id (id (id id))) 2)
2

(id id) = id なので (id (id id)) や (id (id (id id))) のようなものも全て id と等しくなる。つまり、(x x) という関数の自己適用は、

(x x) = (x (x x)) = (x (x (x x)) = (x(x(x(.... (x x)....))))

と無限に展開するラムダ式を発生させることができる。まるで合わせ鏡のように、(x x) という簡潔な表現の中に無限を閉じ込めることができるのだ。x が関数の場合、x のdomain は関数の集合で、x の codomain も関数の集合なので、この展開は無現に続けることができる。

そこで改めて Y-コンビネータ (f (x x)) (f (x x)) を展開してみよう。

(f (x x)) (f (x x))
= (f ((f (x x)) (f (x x)))
= (f (f ((f (x x)) (f (x x))))
= (f (f (f (f .... ((f (x x)) (f (x x))) .... ))))

やはり、この式が無限に展開できることが分かる。これは f (x x) のように f が合わせ鏡の関数を引数に取るために、それを展開すると f ((f (x x)) (f (x x))) となり、展開された f の引数が ((f (x x)) (f (x x)) のように元のλ式になってしまうからだ。

Y-コンビネータの場合、任意の関数 g を上の f にあてはめることができるので、つぎの等式が成立する

Y g = g (Yg)

したがって g に階乗を求める関数をとると、

(Y g) 5 = 5 * (g (Y g) 4)) = 5 * 4 * (g (Y g) 3) = ...

となって遅延評価の関数言語であれば、階乗の計算ができることになる。それだけではなく、g に任意の再帰関数をとれば、任意の再帰関数の定義が Y g でできることが分かる。

Haskell では遅延評価なのでつぎのように簡単に階乗を計算する無名関数を記述することができる。

Prelude> let y x = x (y x)
Prelude> (y (\f n -> if (n == 1) then 1 else n*(f (n-1)))) 5
120

このように関数が first-order のデータであるような言語では、高階関数の自己適用により合わせ鏡のような関数を記述でき、そのなかに無限の操作を導入することができる。ただし、その場合無限の展開が終わらない場合も出てくるので、絶対に停止するプログラムだけを作ることはできなくなる。

ラッセルのパラドックスのメカニズムも自己言及が原因なので、このような合わせ鏡のメカニズムが関係している可能性がある。素朴集合論の世界は、プログラム記述可能な世界と同じものなのだろう。素朴集合論の世界でも無限を全て捉えたと考えてくると矛盾がでてくるが、プログラムの世界も無限の全体を捉えることはできない。しかし、どちらも無限にそれを展開していくことができるという可能無限な世界なのだ。

[PR]
by tnomura9 | 2017-11-19 07:05 | ラッセルのパラドックス | Comments(0)

Z - コンビネータ

Y - コンビネータのλ式は次のようになる。

Y = (λf . (λx . f (x x)) (λx . f (x x)))

これを任意の関数 g に関数適用するとつぎのように Y g が g についての不動点になる。

Y g
= (λf . (λx . f (x x)) (λx . f (x x))) g
= (λx . g (x x)) (λx . g (x x))
= (λy . g (y y)) (λx . g (x x))
= g ((λx . g (x x)) (λx . g (x x)))
= g (Y g)

このとき、g が第1引数に関数、第2引数に整数を取るような場合、たとえば g f n = n * f(n - 1) のような場合、

(Y g) 5 = (g (Y g)) 5 = g (Y g) 5 = 5 * ((Y g) 4) = 5 * (4 * ((Y g) 3)) ....

のように再帰的な計算ができることになる。ところが、Y - コンビネータの定義をそのまま Scheme のλ式にコーディングしても動作しない。それは、プログラムのパースのときに、

Y g = g (Y g) = g (g (Y g)) = g (g (g (Y g))) = ....

と無限の展開が行われるからだ。これを解決するためにはつぎのような Z - コンビネータを利用する。

Z = λf. (λx. f (λy. x x y)) (λx. f (λy. x x y))

これは Y - コンビネータの定義に変数 y を付け加え Y - コンビネータの (x x) を λy. x x y に置き換えただけだ。この置き換えは η 変換と言うらしい。変数を1つ付け加えることで Z g の展開は次のように整数 n を巻き込む形になるので、Y g 部分の無限の展開が起きず再帰は base case で停止することができる。

(Z g) n
= (λf. (λx. f (λy. x x y)) (λx. f (λy. x x y)) g) n
= ((λx. g (λy. x x y)) (λx. g (λy. x x y))) n
= g (λy. (λx. g (λy. x x y)) (λx. g (λy. x x y)) y) n
= g (λy. (λf. (λx. f (λy. x x y)) (λx. f (λy. x x y))) g) y) n
= g (λy. (Z g) y) n)
= g (Z g) n

Scheme で実行すると次のようになる。

1 ]=> (define z (lambda(f)((lambda(x)(f(lambda(y)((x x)y)))) (lambda(x)(f(lambda(y)((x x)y)))))))

;Value: z

1 ]=> ((z (lambda(f)(lambda(n) (if (zero? n) 1 (* n (f (- n 1))))))) 5)

;Value: 120

λ計算の面白いところは任意の関数 g についての不動点を作り出す Y - コンビネータの動作が、記号列の等価変換だけで証明できるということだ。不動点による無限の再帰もλ式の記号列の変換だけで定義できる。

しかし、その中には無限の再帰が存在するために、プログラムを解釈して実行するプログラム言語による意味論的な解釈によっては無限の再帰に陥ってプログラムが動作しなくなる場合がある。

プログラムの動作をプログラムの記号列だけが決定しているのであれば、プログラムの記号列を検査するだけでそのプログラムがきちんと動くかどうかを決定できる。しかし、残念ながら任意のプログラムが動作するかどうかを決定するプログラムをλ式で作ることはできないことが証明されているらしい。

ヒルベルトの夢は数学をこのような記号列の変換に閉じ込めようとしたことだ。しかしそれは、

「対角式は証明できない」の対角式は証明できない

という不動点を作り出すことができることをゲーデルが証明し、証明もその否定も証明できない命題が存在することが分かってしまった。(上の命題が証明可能であるとすると「対角式が証明できない」という語の対角式はその命題自身になってしまうのでその命題は証明不可能ということになる。「対角式は証明できない」の対角式が証明不可能であるとすると、その対角式である上の命題が証明可能であるということになるので、いずれもパラドックスになってしまうのだ。

どうやら、プログラム言語を含め、言語には不動点がつきもので、そのことが、絶対に動くプログラムや、全ての真理を網羅した言語を作らせないようになっているらしい。

[PR]
by tnomura9 | 2017-11-15 23:25 | ラッセルのパラドックス | Comments(0)

λ記法とは何か

プログラマの視点からはλ記法は無名関数を記述できる一種の魔法だ。さらに、無名関数で再帰的定義を可能にする Y コンビネーターのようなものが出てくると、ますます魔法の呪文感が強くなってくる。

しかし、λ計算の本質を考えると、それは、等価な記号列を作るための簡潔な規則でしかない。つまり、λ計算の本質とは、ある文字列からそれと等価な文字列を作るための記号の置き換えの規則に過ぎないのだ。おまけにその規則は3つしかない。つまりα-変換、β-簡約、η-変換の3つだ。λ計算はこれらの規則を使って、等価な文字列を次々に作って行くという意味しかない。

α-変換と言っても単なる変数名の付け替えだし、β-簡約は変数を値で置き換えることで、η-変換は関数 X の変数を表に出すか出さないか、つまり λx.X x = X という置き換え規則でしかない。

λ記法でプログラムが書けるように思えるのは、コンパイラやインタープリターが勝手に文字列を解釈して実行するからだ。λ計算自体は単なる記号の置き換えでしかない。Haskell や Scheme でラムダ記法で書いたプログラムが動いたり動かなかったりするのは、その記号列をそれらの処理系が意味論的に翻訳する時の問題で、ラムダ記法は本来は意味論とは無関係な統語論的な規則なのだ。

統語論的という意味は、その記号列にプログラムとしての意味があるかどうかは無関係に、記号の置き換えのルールに従って記号を置き換えて等価な記号列に変形していくということだ。

たとえば、つぎのような Y コンビネータには (x x) のような関数の自己適用があったりして呪文感が半端ないが、

Y = (λf . (λx . f (x x)) (λx . f (x x)))

Y を任意の関数 g に関数適用して不動点 Yg を作り出すことの証明は、単に変数を引数で置き換えたり、その逆をやったり、変数の名前を付け替えたりしているに過ぎない。

Y g
= (λf . (λx . f (x x)) (λx . f (x x))) g(Yの定義より)
= (λx . g (x x)) (λx . g (x x))(λfのβ簡約、主関数をgに適用)
= (λy . g (y y)) (λx . g (x x))(α変換、束縛変数の名前を変える)
= g ((λx . g (x x)) (λx . g (x x)))(λyのβ簡約、左の関数を右の関数に適用)
= g (Y g)(第2式より)

これは中学校のときに習った2次方程式 ax^2 + bx + c = 0 の一般解を求める時の操作と同じことをしているだけだ。

したがって、関数の自己適用 (x x) のようなものもその意味を考える必要はないのだ。自己適用のある関数 (x x) を更に自己適用する ((f (x x)) (f (x x))) という不可思議な呪文も、単に文字列として捉えれば、それを等価変換していくと Y g = g (Y g) という不動点にたどり着くだけのことだ。

このようにλ計算そのものは単に記号の置き換えだと考えると、そこにはなんの不思議な事もない。しかし、関数の自己適用とは何かなどと、(x x) の意味論まで考えてしまうと、迷宮に迷い込んでしまう。

このように、λ計算は記号列の統語論的な変換規則なのだと割り切ってしまうと、その意味が理解しやすくなる。

[PR]
by tnomura9 | 2017-11-13 06:36 | ラッセルのパラドックス | Comments(0)

Haskell の Y コンビネータ

Yコンビネータの情報を探していたら Haskell でもできるという記事を見つけた。Haskell は型つきラムダ記法なので再帰関数はラムダ記法では定義できないはずだと不審に思ったが、次のように試してみた。

Prelude> let y x = x (y x)
Prelude> y (\f n -> if (n == 1) then 1 else (n * (f (n - 1)))) 5
120

...... 動いてしまった。

厳密には Y コンビネータ y の定義はラムダ記法ではないが、y x = x (y x) という動作をする高階関数の引数にラムダ記法の関数を与えると、第1引数にその関数自身がバインドされて再帰関数が定義できることが分かった。

Y コンビネータの威力が y x = x (y x) という不動点 (y x) で発揮されることが分かる。なぜそういうことが起きるのか考えてみた。

y x = x (y x)

なのでコンビネータ y は関数をひとつ引数に取る1変数関数だ。また、再帰関数を定義するときは x に上の階乗の例から分かるように関数と数値を引数に取る2変数関数を与える。そこで階乗を計算するための関数 g を g f x のように関数 f と整数 x を引数に取る2変数関数で表現してみる。すると、

y g = g (y g)

なので、(y g) を整数 3 に関数適用すると次のようになる。

(y g) 3 = (g (y g)) 3 = g (y g) 3

これは関数 g = \f n -> if n == 1 then 1 else n = n * (f (n - 1)) の f に (y g) がバインドされ、n に 3 がバインドされていることを示すので、

(y g) 3 = g (y g) 3 = 3 * ((y g) 2)

である。

同様に、(y g) 2 = 2 * ((y g) 1), (y g) 1 = 1

となるから、結局

(y g) 3 = g (y g) 3 = 3 * ((y g) 2) = 3 * 2 * ((y g) 1) = 3 * 2 * 1 = 6

と不動点 (y g) による再帰的計算が行われ 3 の階乗の 6 が計算される。つまり、高階関数 y が、

y x = x (y x)

のように不動点 (y x) を作り出す関数であれば、これを関数と整数の2つの引数をもつ2変数関数に関数適用すると、どのような再帰関数も作り出すことができることになる。この場合、どのような再帰関数を y コンビネータで定義しても、その(局所)関数名は (y x) という不動点になる。

Scheme で作った複雑な Y コンビネータも結局は y x = x (y x) という不動点を作り出す関数を定義したに過ぎない。Scheme の場合は Y コンビネータの定義もλ記法でできるので、型なしλ計算が再帰関数を記述できる根拠となる。しかし、Haskell でも y x = x (y x) のように y を定義するだけで、簡単に不動点を作り、無名再帰関数を記述できることが分かる。

追記

同じ発想で Scheme でもできないかと思ってやってみたが、スタックオーバーフローになってしまった。

y g = g (y g) = g (g (y g) = g (g (g (y g))) = ...

と永遠に β 変換をやり続けたためらしい。これを防ぐために前回の記事では Z コンビネータが使われていたようだが、これを y x = x (y x) の形にすることができなかった。β 変換の順序次第で無限ループになってしまうところが λ 計算の面白いところだ。真実はひとつではない?

[PR]
by tnomura9 | 2017-10-25 12:32 | ラッセルのパラドックス | Comments(0)

Y コンビネータの使い方

型なしラムダ計算の勉強のために Scheme をインストールした。

Linux : > sudo apt-get install mit-shceme
Mac : > brew install mit-scheme
Windows : Gaushe のインストーラをダウンロードした。(MIT Scheme が何故か動かなかった。)

型なしラムダ計算を学習しようと思ったのは、関数の自己適用がラッセルのパラドックスと関係があるのではないかと思ったからだ。ラムダ計算で関数の自己適用が現れるのは不動点コンビネータの Y コンビネータだ。ラムダ計算の教科書の説明では1ページくらいで解説してあるが、Scheme で実行しようとして躓いた。

そこでネット検索で、Y コンビネータで再帰的プログラムがかけることがわかった。再帰的プログラムの代表は階乗の計算だ。Scheme では次のように書ける。

1 ]=> (define (factorial n) (if (zero? n) 1 (* n (factorial (- n 1)))))

;Value: factorial

1 ]=> (factorial 5)

;Value: 120

しかしながら、これは自分自身を呼び出すのに関数名を必要としているので、ラムダ計算は使えない。

ところが、Y コンビネータを使うとラムダ計算でも再帰関数を定義できる。ラムダ計算の Y コンビネータは次のようになる。

Y = (λf . (λx . f (x x)) (λx . f (x x)))

何のことか分からないが、Scheme で記述した Y コンビネータは次のようになる。

1 ]=> (define yc (lambda (f) ((lambda (x) (f (lambda (n) ((x x) n)))) (lambda (x) (f (lambda (n) ((x x) n)))))))

;Value: yc

関数 (x x) に値を与えるための変数 n をλ記法で確保した以外はほぼ上のλ計算の Y コンビネータと同じものだ。Y コンビネータの一種で Z コンビネータというらしい。λ計算の Y コンビネータには任意の関数 g に関数適用することによって。

Y g = g (Y g)

となり、Y g が g の不動点になることがわかっている。とは言え、この Y でどうやって再帰関数を記述することができるのだろうか。

いろいろな解説をウェブで見たが、はっきりわからなかったのでこの記事を書いたわけだが、とにかく動くプログラムを作って動作させて見ることにした。Y コンビネータを使った階乗の関数は次のようになるが、実際に動作しているのが分かる。

1 ]=> (define fact (yc (lambda (f) (lambda (n) (if (zero? n) 1 (* n (f (- n 1))))))))

;Value: fact

1 ]=> (fact 5)

;Value: 120

そこで、階乗の計算を定義した部分を g とすると、上の定義は、

fact 5 = (Y g) 5 = g (Y g) 5

となるが、g(f, n) の引数 f に Yg がはいり、g の引数 n に5が入るので、

fact 5
= (g (Y g) 5)
= (if (zero? 5) 1 (* 5 ((Y g) 4)))
= 5 * ((Y g) 4)
= 5 * (g (Y g) 4)
= 5 * (if (zero? 4) 1 (* 4 ((Y g) 3)))
= 5 * 4 * ((Y g) 3)
...
= 5 * 4 * 3 * 2 * 1 * 1 = 120

と毎回関数 (Y g) が g の引数 f に入るので再帰関数の計算ができることになる。

要するに、λ記法で記述された関数に Y を関数適用すると第1引数を使ってその関数自身を利用するという、再帰的定義ができるのだ。無名関数であるλ記法で再帰的定義ができるという不思議な現象が起きてしまうが、このことによってλ記法はループのあるプログラムを作ることができるのが分かる。

Y コンビネータとは何かと考えるのは大変だが、Y コンビネータを使って再帰関数を定義する方法は意外に簡単だった。

[PR]
by tnomura9 | 2017-10-24 07:21 | ラッセルのパラドックス | Comments(0)

矛盾の無い集合論

素朴集合論にラッセルのパラドックスが発生するのは、集合と個体を同じレベルで論じたからだ。

領域という個体の数が N であるとき、その(部分)集合の数はは2の N 乗になるので、個体間の帰属関係で個体に集合を代表させようとしても圧倒的に数が不足する。領域の個体数を無限に増やしても、個体間の帰属関係を表す演算表は正方行列になるので、対角線論法とそれによるパラドックスを許してしまう。

集合を矛盾なく表現するためには、領域の個体とその集合は別の空間に分ける必要があるのだ。たとえば領域 D = {a, b, c} のときその領域における集合は、その部分集合の空間を S = {(), {a}, {b}, {c}, {a,b}, {a,c}, {b,c}, {a,b,c}} をすると S は D の要素からなる全ての集合を表すことができる。また、S は D における個体の集合の全ての演算について閉じている。このように、領域 D の個体とその集合を分けることで、ラッセルのパラドックスは全く発生しない。

しかし、この表現では集合の集合は表現できない。素朴集合論の個体も集合も個体として捉える方法は、集合の集合のような複雑な概念を統一的に表現することができる。上に述べた方法ではそれは不可能なような気がする。

そこで、S = {s0, s1, s2, ... , s8} ただし s0 = {}, S1 = {a}, ... とすると集合の集合 {{}, {a}} を表す集合の集合の空間 G = { {}, {s1}, {s2}, .... , {s1,s2}, .... } を考えることができる。この場合も G は領域 D の個体の集合の集合からなる空間を余すところなく表現できるので、ラッセルのパラドックスは発生しない。

新しい集合のデータ構造を考えるたびに新しい空間を作り出さなければならないが、ラッセルのパラドックスは発生しない。

これらはラッセルのタイプ理論と同じ考え方だ。ただし、タイプ理論では論理についての議論が複雑になりすぎたため、公理的集合論が採用された。しかし、素朴集合論の矛盾を解消するという意味では、公理的集合論よりも本質的に見える。

タイプ理論は複雑すぎて実用的に見えないが、個体の集まりである領域とその集合の空間を分ける考え方は、型付きラムダ計算とおなじだ。型付きラムダ計算は Haskell などの関数型プログラミング言語の基礎となっているが。こちらの方は十分実用的にプログラムを組むことができる。

乱暴な議論かもしれないが、型付きラムダ計算こそが矛盾を含まない集合論のモデルだと考えることができるのではないだろうか。もしかしたら、公理的集合論は型付きラムダ計算と同等なのかもしれない。


[PR]
by tnomura9 | 2017-10-15 23:36 | ラッセルのパラドックス | Comments(0)

なぜ素朴集合論は矛盾するのか

素朴集合論では集合は「ものの集まりというもの」であると考える。この考え方が便利なのはものの集まりである集合を1つのものと考えることによって、その集合を要素とする集合を考えることができることだ。また、集合を単なる個体と同列に置くことで、個体と集合からなる集合のようなものも簡単に考えることができる。

このことは、集合の要素として様々なレベルの集合を等しくとり得ることを意味するので、複雑な概念を簡潔に表現することができる。これは、個体や個体の集合や集合の集合などを同列のものとして取り扱うことができることによる、概念の操作の革命だ。数学に現れる複雑な概念の構造は集合の考え方を使うことで簡潔な表現を手に入れることになる。

しかし、物の集まりと集合としてのものの関係をどう表現したらいいだろうか、a, b, c というものがあったとしてそれを集合としてまとめた {a, b, c} という集合をひとつのものとして扱うとき、この集合という「もの」は a, b, c というものの集まりとは異なる。この区別が分かりやすいように {a, b, c} に A という名前をつけてみよう。すなわち、

A = {a, b, c}

とする。こうすると A と a, b, c の集まりの関係がはっきりしてくる。つまり、A は a, b, c の集まりそのものではないが、a, b, c の集まりを指し示す記号の役割を果たしている。素朴集合論ではこのような A と a, b, c を同列の対象として扱うから、A を要素とする {A} や {a, A} のような集合も作ることができる。

このように素朴集合論では個体も集合も集合の集合もおしなべてもの(対象)として扱うことができるからこれを区別せずに a, b, c, .... で表すことにする。このような対象の集まりを領域 D と呼ぶことにする。この領域 D ではたして集合はきちんと表現できるのだろうか。

このような領域 D にはどれが個体でどれが集合であるというような区別はない。しかし、個々の対象を取り上げたとき、そこには帰属関係という関係性がある。つまり、a という対象が b という対象をその要素とするとき(b が a に帰属しているとき)その関係を、

a ∋ b

で表すことができる。これはこの対象の集まりのどの2つの対象についても一方が他方に帰属するかどうかという関係を考えることができる。したがって、素朴集合の世界は、このように2つの対象の間に帰属関係が定義された対象のネットワークの全てと考えることができないだろうか。

このネットワークは2つの構成要素からできている。1つは対象の集まりであり、もう一つは対象と対象の帰属関係を表す評価関数 ψ(x, y) である。ψ(x, y) は2つの対象を引数とし、x が y を要素としていれば、すなわち x ∋ y なら1の値をとり、そうでなければ 0 の値をとる。ψ(x, y) は全ての対象間の帰属関係を表現できるので、このネットワークで全ての集合を表すことができそうに思える。

ところで、対象 a が集合のときその外延すなわち {b, c, d} という対象の集まりをどのようにして見つけることができるだろうか。それは評価関数 ψ(x, y) を使うことで簡単にできる。対象 x の外延を見つけるために全ての対象 a, b, c, ... に対して ψ(x, a), ψ(x, b), ... と評価関数の値を求めその数列を求める。その数列はたとえば 0, 1, 0, 0, 1, ... のようになっているかもしれない。x の外延はこの数列の値が 1 になっている要素を集めることで得ることができる。例えば上の数列の場合、x = {b, e, ... } である。

そこで、縦に対象をとり横にその対象が要素として含む可能性のある対象を並べ、各行列に評価関数 ψ(x, y) の値をおいた次のような正方行列を考える。

** a b c ...
a 0 1 0 ...
b 1 1 0 ...
c 0 0 1 ...

この正方行列の演算表は対象と対象の全ての帰属関係を記述している。そうして、この演算表の横の行の数列は、その行の対象に帰属する対象の集まり、すなわち外延を表していることが分かる。なぜなら、その数列の値が1になるような対象はすべてその行の対象に帰属しているからだ。

ところで、この演算表を見たときあれっと思う人は多いだろう。そのとおりでこれはカントールの定理に出てきた対角線論法の表と同じものだ。したがって、この演算表には致命的な欠陥がある。つまり、この演算表の対角線部分を反転させて作る数列 1 0 0 ... はある対象の集合を表しているが、この数列は上の演算表のどこにも現れない。なぜなら、演算表のどの行とも対角線部分で異なっているからだ。

このことは、素朴集合の世界の全てを対象とその帰属関係というネットワークで表すことはできないことを示している。つまり、全ての集合を対象とその帰属関係で表すことは不可能なのだ。対角線部分を逆転した数列がしめす集合は自分自身を要素として含まない集合の集合だが、そのような集合をこの演算表の上に表すことはできないのだ。

なぜこのようなことが起きるのか領域 D = {a, b, c} の場合を考えてみよう。領域 D の要素を集めた集合は次のように8個ある。

{}, {a}, {b}, {c}, {a,b}, {a,c}, {b,c}, {a,b,c}

この集合を全て対象 a, b, c だけで表すことは明らかに不可能だ。強いて帰属関係で表そうとすれば次のように対象を追加して演算表を作らなければならないが、これは正方行列にはならない。

** a b c
a 0 0 0
b 1 0 0
c 0 1 0
d 0 0 1
e 1 1 0
f 1 0 1
g 0 1 1
h 1 1 1

また、領域 D が無限集合であったとしても正方行列の演算表では全ての集合をあらわすことはできない。これを全ての集合は対象と帰属関係で表現できるとしたところが、素朴集合論にあらわれた矛盾の正体だったのだ。

ほとんどの数学的対象で集合は矛盾を起こさないように見える。この場合は数学では領域 D は実数などの集合であり、その要素の中には集合は含まれない。自分自身を要素として含まない集合の集合などは領域 D の要素には存在しないため矛盾が起きないのだろう。

追記

素朴集合論の世界を対象と対象間の帰属関係というネットワークでとらえようとしたところが素朴集合論の矛盾の原因だ。領域 D の対象の冪集合の要素(すなわち領域 D の部分集合)全てを領域 D の対象だけで代表させることは不可能なのに、それができると仮定するからだ。その仮定に立てば、領域 D の要素間の正方演算表で全ての領域 D の集合を表すことができなければならないが、そうではないので、対角線論法による矛盾が発生する。

領域 D の部分集合を表す記号を領域 D の内部に求めなければ、領域 D の部分集合全てを表す記号を考えることはできるので、矛盾は発生しない。たとえば、領域 D = {a, b, c} のときその部分集合を x = {}, y = {a}, z = {b} のように集合の空間 S = {x, y, z, ...} で捉えることにすると、領域 D の全ての集合を集合の空間 S で表現でき、領域 D の全ての部分集合間の演算は、S の上で完結している。数学で多用される集合で矛盾が見られないように思われるのは、数学の対象 では領域 D は実数などの集合でその要素に集合を含まないため、領域 D の部分集合の空間 S が領域 D とは独立しているからではないだろうか。

[PR]
by tnomura9 | 2017-10-08 09:11 | ラッセルのパラドックス | Comments(0)

命題関数 A(x) 七変化

命題関数は関数だ、関数だから定義域と値域があるはずだが参考書やネットの解説を読んでも一定していない。定義域は対象の集合である領域 D であるというのは変わりないが、値域がある説明では命題であるとされていたり、ある説明では真理値 {T, F} であるとされている。また、教科書によっては命題関数という用語すらないものもある。

そこで、命題関数を定義するのはあきらめて、なんとなく述語と対象のペアで表現される何かと考えることにした。それというのも、命題関数を表現する A(x) には実に多様な意味づけができるからだ。

1)単純に考えると A(x) とは述語 A と領域 D の対象のどれかとペアでできた命題だ。また、その命題の真理値 {T, F} を表している。

2)A(x) はその変数 x を対象 a, b, c, ... に置き換えて A(a) とすると命題を作ることができるから、A(x) は述語そのものと考えることができる。

3)A(x) は特別な命題を表しているわけではなく x にどの対象を当てはめるかによって真理値 {T, F} が変る。すなわち、A(x) は真理値が T でも F でもあるようなある命題を表している。これは命題論理の命題変数の性質と同じだ。つまり、A(x) は命題変数と考えることができる。したがって、命題変数 A(x) と B(y) から次のような真理表を作ることができる。

A(x) | B(y) | A(x) -> B(y)
T | T | T
T | F | F
F | T | T
F | F | T

A と B で変数を x と y のように別の変数を使ったのは一般性を保つためだ。A(x) と B(x) では述語は異なるが対象が同じ命題になる。

4)A(x) を命題変数と考えると A(x) -> B(x) のような複合命題を作ることができる。対象 x は述語 A と B で共通である必要はなく、A(x) -> B(y) のような複合命題も考えることができる。

5)A(x) を述語と考えると、C(x) = A(x) -> B(x) のように新しい述語を考えることができる。このように新しい述語をつくるためには A, B, C の対象変数は同じ x である必要がある。A(x) -> B(y) のように変数が異なっている場合の述語も考えることができるが、この場合 C(x,y) = A(x) -> B(y) となり、述語 C は2変数(アリティ)の述語となる。

6)A(x) を A(x) が真になる複数の命題を表していると考えることもできる。この場合 A(x) は述語 A を満たす命題の集合を表していると考えられる。この場合 A(x) ∩ B(x) というような表記もできる。

7)上の例では A(x) を A(x) が真である複数の命題を表しているとしたが、A(x) を真とするような領域 D の対象の集合と考えることもできる。この場合は A(x) は述語 A の真理集合になる。A(x) は述語でもあったので述語 A(x) と真理集合 A(x) を同一視できる。つまり、述語の種類がどんなに多くても、その真理集合は領域 D の冪集合に収まっている。また、論理結合子の演算は領域 D の冪集合について閉じている。このことは、一階述語論理の上の理論は、領域 D の冪集合について閉じていることを示している。そのことが、一階述語論理の汎用性の本質である。

A(x) の意味付けがちょうど7つになったので記事を終わるが、他にもいろいろな意味付けがあるかもしれない。命題関数 A(x) の意味合いの多様さと自由さは述語論理の魅力の一つだ。

[PR]
by tnomura9 | 2017-09-21 00:48 | ラッセルのパラドックス | Comments(0)

命題関数とは何か

領域 D の対象 a, b, c, ... に対し述語 A, B, C, ... が定義されているとき、命題は対象と命題のペア A(a) で表すことができる。一階述語論理の命題は基本的にはこのペアで表現された A(a) のみだ。A(a) には真理値がありそれは T か F のどちらかだ。これは命題論理の命題の定義とも一致する。したがって、一階述語論理の真理値表を作るときは次のように命題 A(a), B(e) などについて作成されなければならない。

A(a) | B(e) | A(a) -> B(e)
T | T | T
T | F | F
F | T | F
F | F | T

この命題の表現 A(a) の対象の部分を変数 x にしたもの A(x) は命題関数と呼ばれ、対象を引数にとり真理値を値とする関数と紹介されているが、はたしてそうだろうか。A(x) の値がそのような関数であれば、A(x) は命題とは言えず、次のような真理表も作成できないはずだ。

A(x) | B(x) | A(x) -> B(x)
T | T | T
T | F | F
F | T | T
F | F | F

確かに A(x) は変数の x にどの対象を当てはめるかによって T または F の真理値をとるので、一種の命題と言えないこともない。しかし、A(a) 型の命題では T と F のどの真理値を持つかは決定しているが A(x) の真理値は T とも F とも言うことはできないのでこれを命題ということはできないのではないだろうか。

したがって、命題関数の値は真理値ではなく命題だと考えるべきだ。命題関数 A(x) は引数に領域 D の対象を取り、値が A(a) のような命題である関数なのだ。命題 A(a) は真理値をとるので、命題関数の値が真理値ともいうことができるかもしれないが、A(x) の値はあくまでも命題と考えたほうが取扱いに整合性ができてくる。

たとえば上のような真理値表は、命題関数 A(x) の値が命題であれば、対象 x が共通な命題の間の真理値表とみることができる。ところが、命題関数の値が命題であるという考え方からは、この真理値表は対象が共通でない命題どうしの間でも作成でき、それは次のようになる。

A(x) | B(y) | A(x) -> B(y)
T | T | T
T | F | F
F | T | T
F | F | T

あきらかに、この真理表と対象 x が共通な命題どうしの真理表の意味合いは違う。これは、命題関数の値が命題であると考えることで区別することができるが、命題関数の値が真理値であると考えるとその差異が曖昧になってしまう。命題関数の値は真理値ではなく命題であると考えることで議論に整合性が出てくるのだ。

しかし、命題関数 A(x) の値が真理値であると考える考え方は便利な点がある。つまり、命題関数を真にする対象の集合を A(x) = T で表すことができることだ。A(x) が命題であるとこのような芸当はできない。しかし、このような問題も命題を引数としその命題の真理値を値とするような関数 V(x) を考えると V(A(x)) = T で同様のことができる。むしろ、この方が意味合いの紛れがない。やはり、A(x) の値は命題だと考えたほうが良いと思う。

命題関数の値が命題であると考えることで、全称命題のような量化命題の意味も変わってくる。命題関数 A(x) の値が命題であるという立場からは、∀x.A(x) というのは述語 A と領域 D の対象とのペアで作られた命題の真理値が全て T であることを意味している。このとき、∃y.A(y) は述語が A である命題のうち真理値が T であるもののいくつかを表しているから、自然に、

∀x.A(x) -> ∃y.A(y)

という関係が理解できる。

命題関数の意味合いにはこの他にもいろいろな物がある。たとえば A(x) を述語 A とのペアで真理値が T となる領域 D の対象の集合と考える考え方だ。この考え方には述語 A を満たす領域 D の部分集合である真理集合 A* を考えることができるので便利だ。これを A(x) の値が命題であるという考え方で説明しょうとすると少々面倒な操作が必要になる。したがって、実際には命題関数の意味は TPO によって使い分けたほうが便利だ。しかし、それらの意味付けが干渉しあって混乱したときは、A(x) の値が命題であるという立場に戻ることによってそれらを整理することができる。

[PR]
by tnomura9 | 2017-09-20 06:22 | ラッセルのパラドックス | Comments(0)

量化命題の脱カプセル化

全称命題 ∀x.A(x) はそのままでは量化子にカプセル化された命題 A(x) を利用できない。そのため、∀x.(A(x) -> B(x)), A(a) という仮定があってもそのままでは演繹ができない。A(x) -> B(x) を何らかの手段で取り出す必要がある。

全称命題 ∀x.A(x) の真理値が T のときは、領域 D の全ての x について A(x) が T であるから A(x) はトートロジーである。一階述語論理の完全性定理から同時に定理でもある。従って、∀x.A(x) が仮定あるいは定理のとき、カプセルの中身の A(x) も定理である。すなわち、次の証明が可能だ。

|- ∀x.A(x)
|- A(x)

A(x) が定理であれば対象変数 x にどのような対象をとっても、命題 A(a) は真である。これを利用すると、∀x.(A(x) -> B(x)) と A(a) という仮定からつぎのように B(a) を証明することができる。

|- ∀x.(A(x) -> B(x))
|- A(a)
|- A(x) -> B(x)
|- A(a) -> B(a)
|- B(a)

それでは存在命題 ∃x.A(x) の場合はどうだろうか。これは A(x) の真理値を T とするような領域 D の対象が少なくとも1つ存在していることを示している。つまり、∃x.A(x) が定理のとき A(a) も定理となる。この場合 a は領域 D の特定の要素である。

|- ∃x.A(x)
|- A(a)

このとき

|- ∀x.~A(x) (仮定)
|- ~A(x)
|- ~A(a)
|- A(a) と ~ A(a) が同時に証明可能なので矛盾する

ゆえに

|- ~∀x.~A(x)
|- ∃x.A(x) -> ~∀x.~A(x)

このように、全称命題と存在命題は一階述語論理の次の2つのルールで脱カプセル化できる。

∀x.A(x) -> A(x) ...... 全称特例化 ( universal instantiation )
∃x.A(x) -> A(a) ...... 存在特例化 ( existential instantiation )

逆もできる

A(x) (が定理ならば) -> ∀x.A(x) ...... 全称一般化 ( universal generalization )
A(a) -> ∃x.A(x) ...... 存在一般化 ( existential generalization )

量化命題の脱カプセル化という視点を持つことで、一階述語論理の議論を命題論理の問題として考えることができる。

[PR]
by tnomura9 | 2017-09-19 00:27 | ラッセルのパラドックス | Comments(0)