矛盾の無い集合論

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

領域という個体の数が 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)

理解のタイムラグ

『世界記憶力グランドマスターが教える脳にまかせる勉強法』池田義博著を読んだ。その中でも「3サイクル反復速習法」が独創的だったので今実行してみている。要するに1回の読書でベージを3回読み返しながら読み進めていく方法だが、その読み進め方が独特だ。1ページを読み終わって次のページに進む前に、そのページの一つ前のページから読み返すのだ。

今読んでいるページを読み終えたら、次のページに進む前に今読んでいるページの一つ前のページを読み返す。その後今読んでいるページをもう一度読み、それから、次のページに進むのだ。このサイクルを繰り返していくと、一回の読書で同じページを3回読むことになる。

面倒くさそうに見えるが、やってみるとそれほどでもない。速度が気になるなら、スキミングすればよい。実際にやってみると面白いことに気がついた。それは、次のページに移る前に今読んでいる一つ前のページを読むと内容がよく分かるのだ。それは繰り返しの3回目だからというだけでなく、書いてあることの構成や著者の意図が1回目に読んだときよりはるかによく見える。

そこで思いついたのは、3回目というタイムラグの間に、脳が1回目に読んだことを咀嚼して理解を深めているのではないかということだ。つまり一回目の読書では文字情報から内容を読み取るが、その内容を理解するために少しタイムラグが発生するのではないだろうか。さらに、文字情報の読み取りと同時に、意識には上らないが、意識下でそれを既存の記憶に関連付けて理解するという作業が行われているのではないだろうか。

どうやら、読書の際には文字情報から内容を読み取るという作業と、読み取った内容を既存の記憶と関連付けて理解するという2つの作業が同時進行的に行われており、読み取る作業とそれを理解する作業の間には少しのタイムラグがあるようなのだ。この理解する作業は意識下で行われているため読み取り作業の表面には現れないが、読み返す操作で意識に上らせることができる。この意識下の作業を読み返しで意識に上らせることで記憶の再定着ができるのだろう。

読み返しの操作は、ある程度細切れに行うのが有効だ。おそらく、本を3回通読してもこの分かったという感じはおこらないだろう。脳が新しい情報を処理するための適切な情報量があるに違いない。その情報の単位というのはどうも新書版1ページくらいのようだ。専門分野の教科書などは1ページの情報量が多く、読み返しの効果が薄れるような気がする。この場合は参考書の1ページ分を3等分して、それを新書の1ページとして取り扱うといいかもしれない。

この考えはノートの取り方にも応用できるのではないだろうか。参考書を読みながら丸写しするのではなく、前のページを読み返すときにノートに記入するのだ。あるいは脳が疲れなければ、前のページの内容を思い出して記入しても良い。いずれにせよ、意識的な読み取り作業に隠れている同時進行の意識下の理解の作業を有効活用することが大切だ。

[PR]
# by tnomura9 | 2017-10-02 06:05 | 考えるということ | Comments(0)

府立登美丘高校ダンス部

面白い、ユニーク、パワフル、キレキレ、サービス精神、楽しい、ひたむき、かわいい。

府立登美丘高校ダンス部 YouTube


コーチの才能を感じる。

作品は衣装やフォーメーションや振り付けが独特で、物語性がある。
しかし、地獄の特訓についていく子どもたちもすごい。

全力投球、青春真っ只中。がんばれ〜。






なんか幸せな気持ちになるのはなぜなんだろう?

おまけ



[PR]
# by tnomura9 | 2017-09-22 13:02 | ボーカロイド | 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)

全称命題はメタ命題

領域 D の対象が a, b, c, ... で命題が A, B, C, ... のとき命題は対象と述語のペア A(a) で表される。対象を変数 x で表した A(x) は命題関数だが x に置き換える対象が変われば真理値が変るので、命題論理の命題変数とみなす事ができる。A(x) が T になる対象を集めた集合 A* は述語 A の真理集合だ。

A(x) ∧ B(x) のような命題変数を論理結合子で結合した論理式の真理集合は A* ∩ B* のように真理集合の集合演算となる。また、真理集合の集合演算の値は領域 D の部分集合だ。つまり、領域 D の命題に関する論理的な操作は領域 D の冪集合の集合演算として全て表現することができる。命題 A(x) と真理集合 A* を同一視すれば、領域 D の論理的な操作は、領域 D の冪集合の集合演算として捉えることができる。

非常に分かりやすいモデルだが、全称命題 ∀x.A(x) はこの枠組にはいらない。∀x.A(x) は確かに真理値を持つので命題ではあるが、その真理値は A(x) がトートロジーのとき T となり、そうでないとき F となる、命題の性質を表すメタ命題であるからだ。

例えば A(x) -> B(x) の真理表は次のようになる。

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

この真理表では A(x) -> B(x) はトートロジーではないので ∀x.(A(x) -> B(x)) の真理値は F だ。一方 A(x) の真理集合 A* と B(x) の真理集合 B* の間に A* ⊂ B* という包含関係があるときは、x ∈ A* ならば x ∈ B* なので A(x) が T なら B(x) が F となることはないので真理表は次のようになる。

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

この場合 A(x) -> B(x) はトートロジーになるので ∀x.(A(x) -> B(x)) の真理値は T だ。もちろんこれも真理値をとる命題なので A(x) ∧ ∀x.(A(x) -> B(x)) のように論理結合子で結合することができる。しかし、この論理式から直接にB(x) を演繹することはできない。演繹は ∀x.(A(x) -> B(x)) が真のとき A(x) -> B(x) がトートロジーであることを利用するので真理表は次のようになる。

A(x) | ∀x.(A(x) -> B(x)) | A(x) -> B(x) | B(x)
T | T | T | T
T | F | * | *
F | T | T | *
F | F | * | *

つまり、A(x) と ∀x.(A(x) -> B(x)) が共に T のときは B(x) も T で、それ以外では B(x) の真理値は不定だ。従って「ソクラテスが哲学者ならソクラテスは人間であるという推論は次のようになる。

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

∀x.P(x) ならば P(x) を推論規則とすると、A(x) -> B(x) は定理である。A(x) -> B(x) は定理なので A(a) -> B(a) も定理である。A(a) は仮定であるので、modus ponens の推論規則から B(a) は定理である。

全称命題の中の論理式を使う推論はそのままでは論理演算は利用できない。そのため、全称命題がメタ命題であることを意識して、中の論理式がトートロジーであることを利用して推論を行わないといけない。

全称命題がメタ命題であることをはっきりと意識すると、命題論理の推論の見通しが良くなるのではないだろうか。


[PR]
# by tnomura9 | 2017-09-18 09:24 | ラッセルのパラドックス | Comments(0)

LQ 公理系の推論規則がなんか変

LQ 公理系の推論規則に C -> A ならば C -> ∀x.A というのがあるが、なんとなく納得できなかった。C -> A がトートロジーであっても C が F であれば A は T の値も F の値もとれるので、∀x.A すなわち A はいつも T とは言えない。そこで次のように真理表を作ってみた。

C | A | ∀x.A | C -> A | C -> ∀x.A | (C -> A) -> (C -> Ax.A)
T | T | F | T | F | F
T | F | F | F | F | T
F | T | F | T | T | T
F | F | F | T | T | T

この真理表は領域 D について A の真理値が T の場合も F の場合もある時のものだ。この場合当然 ∀x.A の真理値は F だ。しかし C -> A が定理だとすると、この場合 C -> A が F となることはありえないので、真理表は次のようにならないといけない。

C | A | ∀x.A | C -> A | C -> ∀x.A | (C -> A) -> (C -> ∀x.A)
T | T | F | T | F | F
F | T | F | T | T | T
F | F | F | T | T | T

しかし、この場合でも C と A が共に T の場合 (C -> A) -> (C -> ∀x.A) の真理値は F になってしまう。つまり、どう考えても (C -> A) -> (C -> ∀x.A) はトートロジーにはならないのだ。実際、対象 a について C(a) と A(a) の真理値が共に T であっても、領域 D 全体を見たとき、A(b) が F になるような対象 b があったときは ∀x.A の真理値は F である。もっとも、NQ の自然演繹では、

A ならば ∀x.A

であるがこれは納得できる。A が常に T であれば当然領域 D の全ての対象 x について A の真理値は T である。したがって A が常に真なら ∀x.A の真理値は T だ。しかし、これと (C -> A) -> (C -> ∀x.A) とでは話が違う。どうしてもこのような推論をしたいのなら、C, C -> A ならば C -> ∀x.A ではないのだろうか。しかし、それであれば推論規則は NQ のように、

A ならば ∀x.A

とすべきなのではないだろうか。

全称命題の真理表については以前の記事に書いたが、量化子のつく命題の真理値のパターンによって真理値を真理表上に決めることができる。ただ、その命題の真理値の現れ方にしたがって、T も F もあらわれる場合、T のみの場合、F のみの場合と3つの真理表をつくらなければならない。このように3つの真理表を作った場合でも、2つの命題の真理値がどの真理表の場合も一致すればそれらは同値ということができる。例として ∀x.A と ~∃x.~A が同値であることを次に示す。

A | ~A | ∀x.A | ~∃x.~A
T | F | F | F
F | T | F | F

A | ~A | ∀x.A | ~∃x.~A
T | F | T | T

A | ~A | ∀x.A | ~∃x.~A
F | T | F | F

C -> A ならば C -> ∀x.A という推論規則を適用した証明では C も定理の場合は問題ないのだろうが、やっぱりなんか変。


[PR]
# by tnomura9 | 2017-09-18 02:03 | ラッセルのパラドックス | Comments(0)

わかりやすい命題論理の完全性定理

A -> B のような論理式の真偽は要素命題 A, B に真理値を割り当てることによって真偽が判別できる。そのなかでも A -> (B -> A) のような論理式は、A, Bにどんな真理値を割り当てても常に真になり、トートロジーと呼ばれる。

ある論理式がトートロジーであるかどうかを見極めるには、要素命題に起こり得る真理値をすべて割り当てた時の論理式の真理値を確かめなければならない。その操作をシステム的に行うのが真理表だ。A -> (B -> C) のような命題がトートロジーであるかどうかは、真理表をつくることによってその意味を確認しなければならないから、これは論理式に対する意味論的なアプローチだ。

一方、論理式についての分析は要素命題に真理値をわりあてる方法とは別に、公理と推論規則によって演繹した論理式が定理になるという方法がある。これは要素命題や命題結合子を文法規則によって並べた論理式について、公理と推論規則によって演繹できるものを定理として特別視する。つまり、論理式は命題論理の文法規則に従っていれば自由に作ることができるが、それらの中でも定理と呼ばれるものは公理と演繹規則というルールをもとに演繹されたものでないといけない。

この方法では、要素命題 A, B の真偽は問わない。演繹規則によって演繹された論理式を次々に作っていき、それによって目的の論理式を作り出すことができれば、それは定理となる。論理式が定理であるかどうかを文法と演繹規則によってのみ判別するので、この方法は論理式に対する構文論的なアプローチだ。

命題論理の完全性定理では、これらの論理式の意味論的なトートロジーと構文論的な定理が同値であることを主張している。つまりある論理式がトートロジーであればそれは定理であり、それが定理であればトートロジーであると主張する。これは、トートロジーの定義と公理系の定理の定義が質的に異なっているため必ずしも自明ではない。

ところで、命題論理の完全性定理とプログラミングには関連性がある。コンピュータのプログラミングではアプリケーションのプログラムを作ったとしてもそれを実行ファイルにコンパイルしないと動かない。つまり、コンピュータのプログラムは命題論理の論理式にあたり、実行ファイルは命題論理の真理値表の真理値にあたる。コンピュータのプログラムについても、プログラムの統語論的なアプローチと、その実行ファイルとしての意味論的なアプローチが必要になる。

一般的に、プログラミングで作成したプログラムがきちんと動作するかどうかはそれを実行してデバッグしなくては分からない。プログラムでは動くと思っていたのに、実際にはそのプログラムが実は無限ループであったり、不正なメモリのアクセスを行ってしまっていてエラーになってしまうということがよくあるからだ。デバッグの際には起こり得る様々な可能性を考えてテストしないと、プログラムを運用するために思っても見なかったエラーが発生してしまう事がある。これはプログラムに対する意味論的なアプローチである。

他方でプログラムは実行ファイルを作成する前にプログラム言語の文法に従ってテキストファイルとして作成される。プログラムが完成しても、それはコンパイルされない限り実行できないのでただの文字列である。この意味でプログラムのソースの作成はプログラムについての統語論的なアプローチだ。

コンピュータのプログラムではこのようにプログラムのソースが適正であっても、コンパイルした実行ファイルがきちんと動くとは限らない。きちんと動くかどうかは実行ファイルをテストしてバグがないかどうかを調べなくてはならない。コンピュータのプログラムではプログラムの統語論的な意味と、実行ファイルの意味論的な意味が厳密は対応していない場合があるからだ。また、実行ファイルのデバッグは、ソースファイルの作成以上に労力がかかる事が多い。起こりえる全ての可能性についてテストしないとエラーが起きないと断定できないからだ。ソースファイルを作成した時点で、そのソースが意味論的にもエラーを含まなければ、プログラムの作成の労力の殆どがソースファイルの作成で住んでしまうので効率的だ。

命題論理では論理式についての意味論的なアプローチと統語論的なアプローチが同値であることを証明している。コンピュータのプログラムで言えば、ソースプログラムが適正なら、それは必ず実行時にエラーを起こさないことを意味している。

それでは命題論理において、意味論的なアプローチと統語論的なアプローチが同値であることはどのようにしてわかるのだろうか。それを証明するのが命題論理の完全性定理だ。

先ず、論理式への統語論的なアプローチで定理とされた論理式が全てトートロジーであるのは理解しやすい。公理系の公理は全てトートロジーであるので、公理の命題の要素命題をどのような論理式で置き換えても、定理がトートロジーであることに変わりはない。また、2つの定理に推論規則 modes ponens を適用して得られる論理式もトートロジーになる。たとえば、A -> B がトートロジーで A がトートロジーのとき、B の真理値は必ず真になるのでトートロジーになる。

反対にトートロジーであるとわかっている論理式が公理系で演繹された定理であるということは簡単には言えない。論理式がトートロジーであるということが分かっていても、それが公理と推論規則で演繹された定理であるということをいうのは難しいからだ。命題論理の証明で躓くのはこのトートロジーならば定理であるという部分の証明だ。

この記事の範囲でこの証明を全て紹介するのは難しい、詳細はやはり参考書を読んで理解する必要がある。しかし、この記事では、この意味論的なアプローチが統語論的なアプローチでも定理であるという証明のアイディアの概観を述べてみたい。何をやっているかという意図が分かって証明を読むのと、それがわからずに手探りで理解していくのは随分と効率が違うからだ。

まず、適当に選んだ論理式の真理表からそれに関連する命題論理の証明があることが保証されていることを示す。論理式の例としては A -> B を用いる。最初に A -> B の真理表を作る。

A | B | A -> B
T | T | T
T | F | F
F | T | T
F | F | T

これを作るのは簡単だ。そこで、これを LP 系の証明に変換することを考えてみる。それは次のようになる。

A, B |- A -> B
A, ~B |- ~(A -> B)
~A, B |- A -> B
~A, ~B |- A -> B

この4つの証明の作り方は簡単だ、上の真理表で要素命題 A の真理値が T のときは仮定を A とし、偽のときは ~A を仮定にとる。要素命題 B についても同様だ。また、論理式 A -> B についてもそれが真のときは A -> B とし、偽のときは ~(A -> B) とする。要するに真理表を公理系の証明に置き換えただけだ。うれしいことに、こうして作った証明は全て LP 公理系で証明可能であることが証明されている。再帰的に証明された証明の詳細については参考書を参照して欲しい。要は論理式の真理表から逐語的に公理系の証明に置き換えることができるということだ。

この証明では要素命題 A, B の真理値については考慮されていない。公理系による証明では記号の配列のみが問題にされるので、たとえ A, B |- A -> B の仮定 A の真理値が偽であってもこの証明は正当なものである。

そこで、トートロジー A -> (B -> A) についてこのような証明を作成してみる。

A, B |- A -> (B -> A)
A, ~B |- A -> (B -> A)
~A, B |- A -> (B -> A)
A, B |- A -> (B -> A)

A -> (B -> A) はトートロジーなので仮定が A, ~A, B, ~ B のどれであってもおなじ論理式 A -> (B -> A) の証明が存在する。

ここで、演繹定理を用いて仮定 B または ~B を |- の右に移してみる。

A |- B -> (A -> (B -> A))
A |- ~B -> (A -> (B -> A))
~A |- B -> (A -> (B -> A))
~A |- ~B -> (A -> (B -> A))

この4つの証明は全て正当な証明だから、命題論理の定理 (A -> B) -> ((~A -> B) -> B)) を適用すると、

A |- A -> (B -> A)
~A |- A -> (B -> A)

と仮定の B が抜けてしまう。これにさらに演繹定理と上の定理を適用すると、

|- A -> (B -> A)

となり A -> (B -> A) が仮定のない定理であることが証明される。すなわち、トートロジー A -> (B -> A) は LP 公理系で証明可能な定理である事がわかる。また、A -> (B -> A) 以外のどのようなトートロジーについても同様な証明で LP 公理系で証明可能な定理であることを証明することができる。

数学の証明は一般的に記述するため、アイディアの骨子が見えにくいことが多い。参考書の分かりにくい完全性定理についての証明も上のようなイメージで読み解いていくと理解しやすい。

命題論理では統語論的に作成された論理式はすべてトートロジーである。Haskell の場合も文法チェックをパスしたプログラムは原則的にはすべて実行可能だ。このように統語論と意味論が同値な言語はデバッグの時間を短縮し、プログラムの生産性を飛躍的に上げることができる。

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