人気ブログランキング |

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

有限集合のみで構成される世界

有限集合のみで構成される世界を考えてみた。まず、有限集合を有限個集めてみる。次にそれらの集合とその要素ををすべて集めて領域 R を作る。すると、領域 R はそのような集合の系の全ての要素と集合を含むことができる。そのような世界では、全ての集合について集合和、共通部分、補集合などの全ての演算が閉じている。

しかし、それらの集合の演算を定義するためには、要素と集合の所属関係が定義されていなければならない。それは、領域 R の要素の直積を作り、所属関係があれば 1 なければ 0 となるような対照表を作ればいい。そのような対照表には領域全ての要素について互いの所属関係が記述される。

ところが、この対照表は領域の直積であるので、それは領域には含まれない。つまり、有限集合を有限個集めた領域にあっても、集合の所属関係のような基本的な関係でさえ、領域内で完結することができない。それらは集合の世界の外の論理になるのだ。

また、この対照表自体にも問題がある。この対照表は n 個までの集合しか表現できないが、領域に n 個の要素がある場合、それらの要素を含む可能な集合は 2^ n 個になるからだ。この意味でも領域 R の要素では全ての集合を表せないことが分かる。

おそらく、集合の数や要素の数を無限に増やしてもこれらの事情は変わらないのではないだろうか。

ラッセルのパラドックスのようなものも、本来は集合の領域内で完結できないはずの論理を、その集合の領域内で完結させようとしたところに問題が発生したのではないだろうか。

そこで、どのような集合の系であれば、論理と整合性を保てるのだろうかと考えてみた。最も単純なモデルは、領域 R を先に決めておいて、集合とはその部分集合だけを指すことにする場合だ。一言で言うとベン図の世界だ。このモデルでは集合を表すのに領域の要素は用いない。集合の名前空間は領域とは別のところに作る。そうすると、領域の要素数による集合の名前空間の制限がないので、領域で考えられる可能な集合を列挙することができる。

そこで、領域 R で考えられる全ての集合を指す名前空間を Set とする。Set と 領域 R の直積から真理値への関数を elem :: Set -> R -> Bool とすると、これは領域 R の部分集合と領域 R の要素の間の全ての帰属関係を記述できる。また、Set を行に、R の要素を列に並べて elem の値を表にした対照表を作ると、これは n × (2^n) の表になる。この対照表は領域 R の部分集合を全て記述することができる。このとき、Set に集合和、共通部分、補集合などの集合演算を定義することができ、それは Set について閉じている。

また述語 P(x) を

P(x) = elem (S, x)

で定義できて、P(x) は領域 R の全ての要素について True または False の値をとる。このような定義ではなく任意の述語 Q(x) を考えこれは R の要素 x について True または False の値を取るものと考えると、これは P(x) = elem (S, x) のどれかと一致する。すなわち、任意の述語 Q(x) は elem (S,x) のどれかと同値である。このモデルについては、素朴集合論の演算と、一階述語論理について閉じている。これが、論理と整合性のある素朴集合のモデルだ。このモデルには自分自身を要素とする集合は存在しない。名前空間が異なるので、帰属関係が定義できないからだ。

集合には冪集合が存在する。それは Set の要素の集合である。したがって、集合 S の冪集合の名前空間は Set とは異なる名前空間になる。また、集合の直積 A × B もまた、Set とは異なる名前空間に属する。このように、集合の集合のような Set の要素から作られる集合は Set とは異なる名前空間を与えると、ラッセルのパラドックスのような矛盾は一切生じない。

このような型付きラムダ計算ではどのように集合が複雑に構成されていっても論理との矛盾が生じないのではないだろうか。型付きラムダ計算は煩雑に見えるが、Haskell でプログラムが自在に記述できるのを見ると。取扱はそうむずかしいものでもないような気がする。

by tnomura9 | 2019-10-16 05:25 | ラッセルのパラドックス | Comments(0)

型なしラムダ計算とラッセルのパラドックス

型なしラムダ計算の学習をしていたら、これが、ラッセルのパラドックスをすっきり説明できるのではないかと思いついたので書いてみる。

初めに、集合を全て集めたクラスを考える。そのクラスについて述語 P(x) と集合 P を次のように定義する。

x ∈ P ⇔ P(x) = True

P(x) は集合 x を引数とし、真か偽の真理値をとる関数である。これは集合の内包的定義を用いると次のように表せる。

P = {x | P(x) = true }

これは P(x) が真となるような集合 x を集めると集合 P になることを示している。

そこで、上の定義を利用してラッセルのパラドックスにあるような x ∈ x のような自己言及を定義できないかどうか考えてみるが、これは上の定義から次のようになる。

x ∈ x ⇔ x(x) = True

この定義には、しかし問題がある。x(x) の右側の x は述語でなければならないのに対し、左側の x は集合であるからだ。集合 x を集合の関数である述語として使うのは問題があるので、本来 x(x) のような自己言及は上のような集合の内包的定義では定義できない。

そこで少し工夫をして集合を表すのに述語を使うことを考えてみる。つまり集合 P の述語 P(x) で集合を表すことを考える。P(x) は集合ではないが P = {x | P(x)} のようにいつでも内包的定義で集合にすることができる。そして集合 P の集合 a への関数適用を次のように定義する。

P a(x) = P(a(x))

こうすれば述語 P の引数は述語であり、述語 a(x) を引数とすることができる。そうして P (a(x)) は述語になる。このようにすれば、集合の世界と、集合の述語からなる世界の対応が作られるので、集合の述語の世界で x(x) のような自己言及を作ることができる。述語 P(x) を集合 P と同一視し、述語 a(x) を A として集合 A と同一視することにすると、上の関数適用は、

P A = (P . a) (x)

となる。これで、めでたく集合 P を 集合 A に関数適用できることになる。もちろん自己言及 X X も可能である。全てが関数である述語の世界を考えると自己言及は可能になる。

そこで、関数適用 P A に対し関数抽象 λ を導入すると、次の λA.(P A) は集合 A を引数とし集合 P A を返す関数となる。

λA.(P A)

したがって、

(λA.(P A)) B = (P B)

である。さらに、

λPA.(P A)

は集合 P を引数とし、集合 A を引数とする関数 λA.(P A) を返す高階関数である。これは集合と集合の関数適用を考えたときに、集合が型のないラムダ計算のなかに埋め込まれることを意味している。集合の述語は型のないラムダ計算の要素と考えることができるのだ。このように集合の述語による言及が型なしラムダ計算の世界で表現できることが分かったので、集合の自己言及を型なしラムダ計算の枠組みで考えてみる。

さて、集合 A を集合 A に自己言及させた次のラムダ項は何になるのだろうか。

A A

これは A が A に属していれば true で属していなければ false である。ただし、この true や false はラムダ計算の世界で定義されたものになる。

したがって、上の自己言及を λ 抽象した次のラムダ項は任意の集合についてそれが自分自身を要素としていれば true 要素としていなければ false を返す述語になる。

λx.(x x)

また、集合をラムダ計算に埋め込むことで、上の述語は集合と同一視することができる。したがって、次のラムダ項は自分自身を要素として含む集合が自分自身を集合として含むかどうかを判別する関数適用になる。

(λx.xx) (λx.xx)

しかし、これは次のように β 簡約しても無限に自分自身となるのでどうやっても true にも false にもたどり着くことができない。

(λx.xx) (λx.xx) = (λx.xx) (λx.xx) = (λx.xx) (λx.xx) = ...

それではラッセルの集合はどうだろうか。これは自分自身を要素としては含まない集合の集合だから次のようになる。

¬(λx.xx)

これが自分自身を要素として含むかどうかの関数適用は次のようになる。

(¬(λx.xx))(¬(λx.xx)) = ¬(¬(λx.xx))(¬(λx.xx)) = ¬(¬(¬(λx.xx))(¬(λx.xx)))) = ...

と、これもやはり true にも false にもたどり着けない。

自分自身を要素として含む集合や、自分自身を要素として含まない集合は本来は内包的定義にそぐわない表現だが、自然言語で表現すると見逃がしやすい。ふつうに考える集合の世界には、これらの述語は発生しないはずだ。ただし、これはラムダ計算の体系の中では表現できる。しかし、この場合もまた不動点コンビネータを形成してしまうので真理値を得ることはできない。

ラッセルのパラドックスは結局のところ内包的定義としては表現できない定義を導入したためにおこったものではないだろうか。自己言及を含む述語は集合の定義には使えないのだ。

自己言及を含む内包的定義は、型不適合で排除できる。素朴集合論を型つきラムダ計算の枠組みで記述出来たら、ラッセルのパラドックスは発生しないので矛盾が起きなくなるのではないだろうかと思うが、それを検証する知識がない。

by tnomura9 | 2019-10-14 08:27 | ラッセルのパラドックス | Comments(0)

述語論理と型付きλ記法

述語論理のモデルの領域を集合 D とする。また、領域 D の冪集合を D* とする。領域 D のアリティ1の述語 P(x) のうち同じ真理集合 {x ∈ D | P(x)} を持つものどうしには同値関係がある。そこで、D* の要素 A が A = {x ∈ D | P(x)}のとき、P(x) = (x ∈ A) を考えると、これは真理集合が A である述語の同値類の代表元になる。

このとき、P(x) の論理演算と D* の要素の集合演算は同型であるから、P(x) の集合と D* は同型である。つまり、述語論理の論理演算は全て、領域 D の冪集合の集合演算と対応している。また、領域 D* の集合演算は領域 D* で閉じている。したがって、領域 Dとこのような述語 P(x) からなる述語論理のモデルは述語論理を充足している。

同様に、アリティ2の述語 P(x, y) は、領域 D の直積 D × D とその冪集合 (D × D)* を考えたとき、

P(x, y) = (x, y) ∈ A ただし、A ∈ (D × D)*

によって領域 D の全てのアリティ2の述語を記述することができる。これもまた、述語論理のモデルとして述語論理を充足している。そうして、この述語 P(x, y) は型付きラムダ記法で記述された関数 P(x,y) :: D × D -> {True, False} に対応している。

言葉足らずになってしまったが、言いたいことは、領域 D があったとき、これに関する型付きラムダ記法によるプログラムは述語論理を充足しているのではないかということだ。述語論理で証明できる数学の定理は全て型付きラムダ記法のプログラムで記述して実験できるかもしれない。

要するに、述語論理的に正しいことは、すべて、型付けられた関数型プログラム言語のプログラムとして調べることができるのではないかということだ。ある数学的な定理が正しいかどうかは、型付き関数型プログラム言語のプログラムで検証できるのではないかという気がする。

上に述べたことが本当に適切かどうかはわからないが、型付き関数言語がかなり数学的な問題についても親和性が高いのではないかという気がする。数学的な理論のモデルを型付き関数言語で記述しながら学習していくという方法もとれるかもしれない。抽象的な数学の理論を具体的なプログラム例として捉えることができたら、随分学習が楽になるのではないだろうか。

ところで、ラッセルのパラドックスの記事は、これで一旦終了したい。何年間かこの問題に素人の立場として取り組んできたのは、集合の学習の最初にラッセルのパラドックスに出会って非常に戸惑ったことがあったからだ。そこで、ラッセルのパラドックスに悩まされないで、集合や論理学を理解できないだろうかと思っていろいろと考えてみた。数学の専門家ではないので、逆に専門家が当たり前として通過するところをいろいろ考えてみたつもりだ。

結論としては述語論理の領域を「自分自身を要素としては含まない集合」にとり、内包記法で集合を定義するときに { x ∈ D | P(x) } という型付き関数 P(x) :: D -> {True, Fasle} を使用すれば、論理学や集合に矛盾はおきないことがわかった(と思う)。確証はできないが、Haskell のような関数型プログラム言語は述語論理のモデルとして使えるような気がするところまできた。

論理学の深いところまで知りたいわけではなく、論理学をどう効率的にいろいろな分野、特に数学の学習に利用できないかというのが目的だったので、これからは、Haskell という関数型プログラム言語の利用法について重点的に色々やってみたい。

by tnomura9 | 2019-05-06 02:56 | ラッセルのパラドックス | Comments(0)

公理的集合論の集合とはどんな集合?

公理的集合論の集合は、公理をもとに集合と定義できるものを演繹していく考え方だ。公理はプログラム言語の文法規則に当たる。プログラム言語ではどのような記号の配列が式であるかを文法規則で判断する。文字列をパーサーに通すことによって、機械的に再帰的に解析され、その文字列がプログラムかどうかが判別される。同様に、公理的集合論においても、ある対象が集合かどうかは再帰的に公理の規則に帰着できるかどうかで判断される。

プログラム言語の再帰的定義の場合、base case がないと、解析が終わらない。公理的集合論の場合はそれは空集合ひとつだけだ。公理的集合論の集合は再帰的に解析していくと最終的には空集合になる。これは、自分自身を要素として含む集合とは性質が異なる。自分自身を要素として含む集合は再帰的な解析が無限に続くため base case に帰着することはないからだ。

したがって、公理的集合論の集合は、自分自身を要素としては含まない集合だ。これは、素朴集合論の場合でも述語論理を充足する。

公理的集合論の集合が述語論理と矛盾しないのはそのためかもしれない。


by tnomura9 | 2019-05-04 15:39 | ラッセルのパラドックス | Comments(0)

集合の分類

任意の集合 A = {a1, a2, ... } はその外延となる対象の集まりと集合 A それ自身という対象から構成されている。これらの対象に述語 P(x) を関数適用することで P(a) の値は T または F の値を取る。

集合 A が P(x) による内包的定義で定義される場合、すなわち、A = {x | P(x)} の場合、集合 A 以外の対象に対しては P(a) の値は全て T だ。しかし P(A) については、P(A) = T の場合と P(A) = F の場合が考えられる。したがって集合 A については、

1. P(A) が F の場合
2. P(A) が T の場合

の2つの場合に分類できる。

P(A) が F の場合は集合は問題なく内包的定義で確定する。P(a) = T となる対象をすべて集め、集合 A は新しい要素としてそれに含まれないのだから集合 A の要素に変動はない。普通に考えられる全ての集合はこの条件を満たしているように思われる。ところが、これらの集合は「自分自身を要素として含まない集合」だから、それら全てを集めた「自分自身を要素として含まない集合の集合」を作ると、これはラッセルのパラドックスを引き起こしてしまう。自分自身を要素として含まない集合は自然な集合であるにもかかわらず、それらの集合全てを集めた集合は、パラドックスを引き起こすのだ。

なぜなら、自分自身を要素として含まない集合の集合を A とすると、A が自分自身を要素として含んでいなければ(すなわち P(A) = F) なら、A は A の要素でなければならないし、その場合 P(A) = T となってしまうのでパラドックスだからだ。

このように P(A) = F となる集合は自然な集合であるにもかかわらず、それら全てを集めた集合は作ることができない。

次に P(A) = T の場合だ。この場合 A ∈ A でなければならない。そうでなければ P(A) = F になってしまうからだ。このとき A = { A, a1, a2, ... } である。この場合は集合 A の要素は安定して存在し、この集合 A を述語論の領域 D と見ても述語論理は充足されるように見える。

しかし、A = {A} のような A ∈ A の最も簡単な集合についても、集合 A を何らかの個体から定義することはできない。A = {{{ A }}} のように無限の合わせ鏡のような姿が見えるだけだ。

さらに、「犬でないものの集合」はやはり、P(A) = T である。犬でないものをすべて集めたとき自分自身も「犬ではない」したがって、「犬でないものの集合」はその要素として自分自身を含んでいると言える。ところが、この「犬でないものの集合」の冪集合を作ると、その要素もまた「犬でないもの」である。これは、「犬でないものの集合」がその要素として「犬でないものの集合の冪集合の要素」を含んでいることになり、集合の濃度の上からもおかしいことになる。このような変な集合は「猫の集合」のような普通の集合の、全体集合を考慮しない補集合には普遍的に見られる。これは、明らかに述語論理を充足しない。

これに加えて、P(A) = T であって A /∈ A の場合もある。「自分自身を要素として含まない集合」を集めて集合を作ると、その集合自身は自分自身の要素として含まれることはできない。しかし、それ故にそれ自身も「自分自身を要素として含まない集合」である。これは明らかにラッセルのパラドックスを引き起こす。

P(A) = T となる集合については、述語論理を適用するためには慎重な考察が必要となる、というか、適用できないと考えておいたほうがいいかもしれない。

このように素朴集合論の定義のように「集合とは対象の集まりという対象である」と考えると、述語 P(x) による内包的定義では、まともな集合よりは、集合といえない集まりのほうが多いことがわかる。このような集合といえないものの集まり(クラス)には述語論理を適用することはできないので、結局、述語論理を適用できるのは、「自分自身を要素として含まない」集合である普通の集合だけになる。

形式的体系の目的の一つは、全ての理論を述語論理学の上に構築することだが、実際には述語論理が適用できる領域は「自分自身を要素として含まない」限られた集合になる。数学的理論に関しては、たまたま、その対象の領域が「自分自身を要素として含まない」健全な集合なので、述語論理が適用できているだけなのではないだろうか。

『語り得ないものについては、沈黙しなければならない。』のである。


by tnomura9 | 2019-05-02 12:06 | ラッセルのパラドックス | Comments(0)

集合と自己言及

対象 a1, a2, ..., を集めて集合 {a1, a2, ... , } を作る。説明の冗長性を避けるため、これを集合 A としよう。すると、対象を集めて集合を作ったときそこには対象の集まり a1, a2, ... と共に集合 A という対象が存在する。述語は対象から2値集合 {T, F} への写像であるが、素朴集合論ではその対象には集合それ自身である A も含まれる。P(a) が真となる対象の集まりを作ったとき、素朴集合論の定義ではそれらの対象以外に集合 A という対象が不可分に存在してしまう。この A も対象の一つだからこれに対しても述語は関数適用され、P(A) の真偽値が問われることになる。これが、素朴集合論における自己言及の正体だ。

この自己言及の存在するシステムでは、内包的定義 {x | P(x)} が集合を定めることができないのはラッセルのパラドックスから明らかだ。すなわち P(x) = ¬ (x ∈ x) という述語で定義される集合を、R = {x | ¬ (x ∈ x)} とすると、

R ∈ R => ¬ (R ∈ R)

と、パラドックスが発生してしまうからだ。これは、集合それ自身という対象に述語を適用することには問題があることを意味している。

そこで、集合を考える対象の全体集合である領域 D を指定し、述語はその領域の要素である集合にのみ適用されると考える。すなわち、内包的定義による集合の定義は、

A = {x ∈ D | P(x) }

であるとする。この場合、領域 D の対象についてのあらゆる述語 P(x) について、矛盾なく内包的定義で集合(Dの部分集合)が定義できる。矛盾を引き起こす述語の自己言及が発生しないからだ。いろいろな数学の理論を素朴集合論で記述しても矛盾が発生しないように見えるのは、述語による集合の内包的定義が暗黙に上のような定義になっているからではないだろうか。

by tnomura9 | 2019-04-30 20:41 | ラッセルのパラドックス | Comments(0)

述語論理と素朴集合論の間に矛盾はない

述語論理と数学の理論をつなぐのはその解釈だ。述語論理の解釈を構成する要素は、「対象領域」、「定数」、「変数」、「関数記号」、「述語記号」だ。しかし、これらの要素のうち根幹になるのは「対象領域」だ。すなわち、述語論理は「対象領域」の性質を記述する言語と言える。その他の要素のうち「定数」と「変数は」対象領域の要素の別名でしかない。また、関数記号はこれを対象に適用することで対象を値として返すから、これも対象の別名どして考えることができる。したがって、述語論理に特異的なものは「述語記号」のみだ。述語記号の性質を明確にすれば、述語論理の本質を明らかにすることができる。

述語記号は基本的に P(x) :: D -> {T, F} 型の関数だ。P(x) を対象領域の要素 a に適用した P(a) は必ず T または F の値を返すので、T の値を返す要素ばかりを集めた対象領域の部分集合を内包的定義で {x ∈ D | P(x)} を定義できる。これは述語 P(x) の真理集合と呼ばれる。述語には無限の表現があり得るが、その真理集合は必ず対象領域の部分集合になる。したがって、同じ真理集合を定義する述語は同値関係にある。また、真理集合は対象領域の部分集合であるから、対象領域の冪集合の要素である。したがって、対象領域の全ての述語の同値類と、真理集合の集合である冪集合は同値関係にある。さらに、述語の論理操作は、真理集合の集合演算に反映されるから。真理集合と述語の同値類とは論理演算について同型でもある。

つまり、対象領域についての述語については、全ての述語を対象領域の真理集合である冪集合と同一視できる。アリティ1の述語は、対象領域の冪集合の要素と同一視できるのだ。対象領域の要素についてのどのような述語の議論も、冪集合と要素の所属関係として捉えることができる。すなわち、命題 P(a) の真偽と a が真理集合 P に所属するかどうか、すなわち、a ∈ P の真偽は一致する。したがって a ∈ P は命題 P(a) である。

述語は引数として複数の変数を取ることができる。たとえば P(x, y) である。この場合 P(x, y) の型は P(x, y) :: D × D -> {T, F} である。これは、Dの直積 D × D について P(x) の場合と同じような議論を行うことができる。すなわち D × D の要素 (a, b) と D × D の冪集合の要素の間の所属関係 (a, b) ∈ P は命題になる。

要するに、述語論理は対象領域を起点として、その冪集合と直積集合という集合の言葉によって余すことなく表現できることがわかる。このように、述語論理と素朴集合論は非常に相性がいい。というより、述語論理は素朴集合論そのもののように見える。少なくともラッセルのパラドックスのようなものは発生しない。これは、内包的定義による集合が必ず冪集合の要素であることを保証されているからだ。すなわち、この議論に現れる述語による内包的定義は {x ∈ D | P(x) } だからだ。集合の内包的定義に公理的集合論の分出公理を採用すれば、述語論理学と素朴集合論の間には矛盾は発生しないように見える。

もちろんこの議論が成り立つのは対照領域が「集合」の場合で冪集合の公理が成立する場合だ。対照領域が「クラス」の場合、述語論理を充足することは保証されない。ラッセルのパラドックスからも矛盾が発生すると考えたほうがいい。

対照領域が「集合」である理論については、素朴集合論は述語論理学に矛盾しないと考えることができるのではないだろうか。

by tnomura9 | 2019-04-26 00:57 | ラッセルのパラドックス | Comments(0)

述語論理のモデル

述語論理は生成規則のある記号列の集まりだ。述語論理の定理や証明も、記号列の文法とその変形規則から導かれる。基本的には、これらの記号列には意味が与えられていない。項や論理式といった記号列は言わば空っぽのコンテナのようなもので、その中に実際の理論の対象を当てはめることで、論理式に意味をもたせることができる。

述語論理はこのような理論の対象のコンテナなので、その理論についての論理的な操作は、述語論理の定理として取り扱うことができる。このような汎用性が述語論理の利点だ。どのような理論でも、述語論理の枠組みに適合するものは、理論の内容を吟味することなく、述語論理の推論や定理を利用できるからだ。

ただし、命題論理の場合と違い、述語論理はそのものの構造がやや複雑だ。逆に言えば、この構造に適合できる対象でないと述語論理が適用できないことになる。述語論理を理論に適用するためには、述語論理そのものの構造に対応するものがその理論にもなければならない。述語論理の構造とはその解釈を考えるときに明らかになる。つまり、議論の対象(個体)の集まりとしての「対象領域」、「解釈」としての「定数」、「変数」、「関数記号」、「述語記号」である。「定数」は対象領域の個々の要素を特定するのに用いられ、「変数」は「対象領域」上の不特定の要素を代表し、「関数記号」は対象領域の要素から他の要素への関数をあらわし、「述語記号」は対象領域から2値集合 {True, False} への写像を表す。これらの構成要素は十分抽象的なので、広い範囲の理論を代表し、その論理演算を担うことができる。

この述語論理の最も基本的な解釈はどのようなものかを考えることは、述語論理の本質を知り、それを活用する助けになるかもしれない。そこで、対象領域 D と述語記号 P のみの非常に簡素な述語論理のモデルを考えてみた。

対象領域 D は単に対象 a1, a2, a3, ... , の集合であると考える。また述語はこれらの対象の1項関数 P1(x), P2(x), P3(x), ... , だけを考えるものとする。このとき P(x) の型は P(x) :: D -> {True, False} である。また、P(x) を D の対象 a に関数適用した P(a) は True または False の値を持つ命題である。また、述語論理の構造には出てこないが、領域 D の冪集合を D* とする。

これらの条件で述語 P(x) については、これを充足する D の要素の集合を内包的定義で {x ∈ D | P(x) } で定義することができる。この内包的定義ももちろん述語論理の構造には現れない。しかし、内包的定義で定義される集合はすべて冪集合 D* の要素であるから、述語記号は内包的定義によって冪集合 D* の要素に対応している。述語記号についての制限はないが、述語記号に対応する集合は D* の要素であるから、述語記号に対応する冪集合 D* が同一の場合、述語記号は同値であると考えられる。したがって、述語記号と対応する冪集合 D* の要素によって類別できる述語記号の同値類を考えることができる。この同値類と冪集合 D* は全単射になるので、述語記号の同値類を冪集合 D* と同一視することができる。

さらに、述語記号に論理演算を適用してできる複合述語記号はすべて、述語記号に対応する領域 D* の要素の集合演算と対応しているから、述語記号の同値類の集合と領域 D* は同型である。したがって、述語論理の述語記号を、冪集合 D* の要素に置き換えても良いことがわかる。このとき、命題 P(a) は a ∈ P で表せる。すなわち、述語論理の最も単純なモデルは、領域 D の集合論であることがわかる。

この述語論理のモデルとしての集合論では、ラッセルのパラドックスは出現しない。なぜなら、この集合論で出現する集合は全て対象領域 D の部分集合であるから、内包的定義によって定義される集合が冪集合 D* の要素以外の集合になることはないからだ。

述語論理学のモデルとしての集合を考える利点は、全称量化子の意味がわかることだ。たとえば、∀x (P(x) -> Q(x)) の意味は x ∈ P -> x ∈ Q、すなわち P ⊂ Q であることがわかる。この例は、述語論理の振る舞いはベン図で全て説明できることを示唆している。ある理論のフレームワークとして述語論理が使えるかどうかは、その理論の述語の真理集合が対象領域の冪集合の要素になるかどうかを見ればいい。

また、この述語論理のモデルには重要な特徴がある。それは対象領域 D には集合を表す個体が存在しないということだ。したがって、このモデルでは対象領域の部分集合を対象として扱うことができない。集合の集合のようなものが扱えないのだ。集合を考える最大のメリットは集合を対象として扱うことができるということなので、これは容認できない。

そこで、対象領域 D の対象が個体とその集合とで構成されている場合を考えてみよう。これは個体とその集合がひとしく対象と考えられる対象領域である。この対象領域では個体の集合とともに、集合の集合も考えることができる。この場合も対象領域 D の冪集合 D* は領域 D についての述語(の同値類)との同型を作ることができ、個体の集合の集合も扱うことができる。しかしながら、この対象領域 D の場合についても集合の集合の集合を含んではいない。対照領域 D の述語(の同値類)の集合は D* と同型であることは保証できるが、この場合でも対照領域の要素として表現できない集合の集合の集合が存在する。集合論を述語論理のフレームワークの中に閉じ込めようとしても、どうしても対照領域の要素として表現できない集合が存在してしまう。述語論理で扱えるのは対象領域の要素である対象だけであるから、それらの集合は述語論理の述語の対象となることはない。

このように、素朴集合論の一部を述語論理の枠組みに閉じ込めることは可能であるが、必ずその枠組みからはずれる集合が発生してしまうことがわかる。

追記

述語論理学の枠組みには、暗黙のうちに対象領域のべき集合が組み込まれていて、そのべき集合の要素は対象領域の中には含まれていない。このため、どのような対象領域を選んでも、それに含まれない対象領域のべき集合の要素が発生してしまう。このため、すべての集合を含む体系を述語論理学のフレームワークに取り込むのことはできないのだ。

by tnomura9 | 2019-04-21 18:48 | ラッセルのパラドックス | Comments(0)

述語論理学では集合をどのように表すか

対象 a, b, ... の集合である領域 D にたいし、述語 P(x) は領域 D から2値集合 {True, False} への写像 P(x) :: D -> {True, False} である。しかし、述語論理学では領域 D の部分集合を表現する項や論理式はない。そこで、述語論理の言語で領域 D の部分集合を表現する方法はないかどうかを考える。

まず、領域 D の要素 a に対してだけ True であるが、他の要素に対しては False である述語 A(x) を考える。この述語による内包的定義で定義される集合は a のみを要素とする集合 {a } である。すなわち、

{x ∈ D | A(x) } = {a}

である。これで、内包的定義で集合を定義できる述語 A(x) を作ることができた。領域 D の部分集合 {a} は述語論理学の言葉では表現できないが、少なくとも内包的定義で集合を定義できる述語 A(x) を述語論理学の言葉で表現できることがわかる。

このようなシングルトン集合ができれば、領域 D の任意の部分集合を内包的定義で定義できる述語を述語論理学の言葉で表現することができる。たとえば集合 {a, b, c} を内包的定義で定義できる述語を P(x) とすると、これは述語論理学の論理式で、

P(x) = A(x) ∨ B(x) ∨ C(x)

と記述することができる。この場合、P(x) については、P(a) = True、P(b) = True、P(c) = True だが、それ以外の要素 n については P(n) = False である。このことは {x ∈ D | P(x) } = {a, b, c} であることを意味している。このように、領域 D についての述語論理の言語で直接に集合を表現する方法はないが、内包的定義によって集合を定義できる「述語」を定義することができることがわかる。

さらに P(a) = True であるからこの命題 P(a) は

a ∈ P (ただし、P は {x ∈ D | P(x)} の略記である)

と同じ意味になる。つまり、領域 D の対象 a が集合 P の要素であるという命題を P(a) で表すことができる。

このように領域 D に関する述語論理の言語で集合を直接的に表現する手段はないが、内包的定義で集合を定義できる述語を記述することはできる。したがって、述語と集合を同一視すれば、領域 D の部分集合は述語 P(x) で表現できることになる。つまり、領域 D に関する述語論理学の言語で集合を記述することができることがわかる。

このようにして、領域 D の述語論理学の言語によって領域 D の部分集合が定義できるようになったので、領域 D の部分集合の振る舞いについては余すところなく述語論理学によって記述できることがわかった。このことは、領域 D の部分集合については述語論理学の定理を安全に適用できるということを意味している。述語論理学の言語は無事に集合をそのフレームワークに取り込むことができるのだ。

ただし、注意しないといけないのは、述語論理で記述できるのはあくまでも述語であって、内包的定義そのものや集合そのものは記述できないということだ。すなわち、述語論理の枠内に記述できるのは、内包的定義で集合を定める述語であって、内包的定義や集合そのものではない。ラッセルのパラドックスの原因は無意識に述語論理の中に内包的定義そのものまで取り込んでしまったところにあるのではないだろうか。述語論理にとっての集合とは、述語を介して投影される映像のようなもので、直接つかむことはできないと考えたほうがいい。

by tnomura9 | 2019-04-17 03:05 | ラッセルのパラドックス | Comments(0)

述語論理の意味

述語論理は一種のプログラム言語だ。

プログラム言語で書いたプログラムはそれだけでは単に記号の列でしかない。字句解析や構文解析でその記号列がプログラムとしての条件を満たしているかどうかは判断することができるが、たとえ、それがプログラムとしての条件を満たしていたとしても、それがインタープリタで実行されたり、コンパイラで実行可能ファイルにならない限り、何もすることができない。

述語論理も同じことが言える。述語論理の推論規則や定理はあくまでも構文論的な記号の構造の分析であり、それが実際の数学的対象に翻訳されない限りは、単なる記号列でしかないのだ。

述語論理を実際の数学やその他の対象に適用するためには、述語論理の解釈が必要なのである。ところで、命題論理については、構文とその解釈の間の関係は単純だ。命題変数には真偽のはっきりした命題であれば何でも当てはめることができる。そのような命題にたいしてはフレームワークとしての命題論理の議論をすべて適用することができる。その意味で命題論理は様々な現実の命題の推論の基礎となることができる。

このように、命題論理の解釈は、真偽のはっきりした命題という抽象性の高いものであるために、ほぼ全ての分野の命題に対し命題論理が論理的推論のバックボーンとなることができる。

述語論理の解釈は、命題論理のそれよりもやや複雑になる。したがって、命題論理よりは適用できる実際の現象の範囲が狭くなることになる。そのかわり、述語論理は命題論理では扱えない対象と述語の関係を扱うことができる。理論の適用範囲と表現力の間にトレードオフがあるのだ。命題論理の解釈には次のようなルールが発生する。

対象領域 (domain)
* 対象変数の動く範囲の集合 D

解釈 (interpretation)
* 定数には D の特定の対象を対応付ける : a, b, c, は特定の U の対象を指す。
* 変数は D の値を動く : x, y, z は U の対象のどれかを指す。
* 関数記号には D 上の関数を対応付ける : f(x), g(x, y), ... など。
* 述語記号には D の述語を対応付ける : P(x), Q(x, y), ... など。

構造 (structure)
* 対象領域 D と解釈 σ の対
* <D, σ>

述語論理の解釈」より改変

簡単に言うと述語論理を適用できる対象は、対象の集合とその関数、述語が存在する構造を持っている必要があるということだ。

そこで、素朴集合論は述語論理の解釈になり得るかどうかを考えてみた。まず対象の集合 D だが、これは特に問題なさそうだ。この対象 D は述語を持っている。すなわち、述語 P(x) を D の対象 a に関数適用すると P(a) は必ず真または偽の値を持つ。ただ、この段階では D には集合という概念はない。そこで、領域 D の部分集合の集合である D の冪集合 D* を考える。しかしながら、冪集合 D" は領域 D についての述語論理では表現できない。つまり、集合の概念は述語論理には馴染みにくいのではないかという疑問が生じる。

述語と集合を関連付けるのは内包的定義だ。すなわち、{x ∈ D | P(x) } で集合を定義する。これは冪集合 D* のどれかの要素と一致する。しかし、この内包的定義も述語論理の解釈には登場しない。単純な推論では、集合を述語論理の枠組みの中で記述することはできないような気がする。

by tnomura9 | 2019-04-14 23:18 | ラッセルのパラドックス | Comments(0)