<   2015年 08月 ( 9 )   > この月の画像一覧

フォンノイマン・ベルナイス・ゲーデル集合論(NBG)

公理的集合論というと教科書には ZFC 集合論しか載っていないが、フォンノイマン・ベルナイス・ゲーデル(NBG)集合論のほうがわかりやすい集合の世界のイメージを作ることができるような気がする。インターネットでも NBG 集合論の解説を見つけるのが難しいし、しっかり理解したわけでもないのだが、直感的には NBG には次のような集合のイメージモデルを当てはめることができる気がする。

まず、NBG 集合論を構成する対象とはどのようなものかを考えてみる。公理的集合論では集合の要素が全て集合になるように、空集合 {} に集合をつくる操作のみを使ってつくる集合、たとば、{{}}、{{}, {{}}}、などのようなものを集合論の要素的な単位と考えるが、数学以外の分野に集合論を活用しようとすると少し技巧的すぎる気がする。

したがって、NBG のモデルとしては、一匹の犬などのような集合ではない対象(個体)を出発点に考える。このような対象は空集合だけではなく複数個存在して良い。

これらの対象は共通の性質でグループをつくることができる。たとえば犬を集めて犬の集まりをつくることができる。 また、この集まりは「x は犬である」という述語を充足する対象の集まりとしても規定される。また、「x は犬である」という述語を充足しない対象の集まりも考えることができる。このため、ある対象をとりあげて「a は犬である」という命題は必ず真か偽の値をとるため、命題の排中律が成立している。

この状態では、P(x) を充足する対象はその集まりを規定する。すなわちP(x) は A = {x| P(x)} という対象の集まり A を定義することができる。犬の集まりといって犬の集合と言わなかったのは訳がある。このような対象の集まりは NBG では集合ではなくクラスになる。

それでは NBG における集合とはなんだろうか。NBG における集合とは別のクラスの要素となることができる対象の集まりだ。上に述べた状態で犬の集まり(クラス)をつくることができたが、これだけでは他のクラスの要素となることはできない。そこで、これが他のクラスの要素となるために、この犬のクラスをあらわす「犬の集合」という対象を最初の対象の集まりの一員として加える。

「犬の集合」とは犬の集まりではないが、犬の集まりの記号となる存在だ。また、この「犬の集合」という対象は他の対象とおなじように「x は犬である」という述語を適用することができる。すなわち「犬の集合」という対象は犬ではないので、この述語の適用は偽の値を返す。「犬の集合」という対象を加えた集合の世界は、したがって、犬の集まりである犬のクラスと犬のクラスをあらわす「犬の集合」という対象という2重の構造が存在することになる。この場合も「x は犬である」という述語は全ての対象について必ず真か偽の値をとるので、排中律は保たれている。

また、この場合も犬でないもののクラス(集まり)はあるので、これをあらわす記号としての「犬でないものの集合」を作って元の対象の集まりのメンバーとしてみる。この「犬でないものの集合」は犬ではないので犬の集合の要素ではない。それでは「犬でないものの集合」の要素になるだろうか。しかし、犬でないものの集合の要素に「犬でないものの集合」が含まれていると、外延性の公理から悪循環が発生してしまうのは以前の記事で述べた。このため「犬でないものの集合」は犬でないもののクラスには含まれない。このため「犬でないものの集合」は集合の世界の要素のメンバーとして加えることはできない。犬でないもののクラスは存在するが犬でないものの集合は存在しない。

最初の対象だけからなる世界は、このような操作によって、犬のクラスと「犬の集合」という対象と犬でないもののクラスで構成されることになる。この状況では、「x は犬である」という述語は「犬の集合(クラス)」を定めることができるし、「x は犬ではない」という述語は「犬の集合」という要素を含む「犬ではないもののクラス」を定める。このため、全てのものは犬であるか犬でないかという排中律も保たれている。また、「犬の集合」という対象を導入したため、これを要素とする「ぽちと「犬の集合」からなる集合」のようなものも定義することができる。

このように、犬の集まりをクラスと考え、犬の集合をこのクラスを代表する記号的な対象と考えることによって、排中律を満たしたまま、「犬の集合」を他の対象と並ぶ「もの」として取り扱うことができる。「犬の集合」は犬のクラス(集まり)ではないが、犬のクラスを代表する記号としての対象である。このようにして排中律を壊さずに作られた「犬の集合」を構成的な集合と呼ぶことにする。また、「犬でないものの集合」のような排中律や正則公理に背くような対象は集合としては認めない。犬でないものの集まり(クラス)はその記号としての「犬でないものの集合」はもたないが、「x は犬ではない」という述語を充足する対象のあつまり(クラス)として定義できる。

NBG ではものの集まりはクラスであり、他のクラスの要素となることができるものを集合としているが、集合をクラスの記号と考えると NBG の集合とクラスの違いがわかる。集合とは、このように構成的な手続きで排中律を侵害しないように作られた記号としての「集合」を意味する。構成的な集合を作るたびに、余分な集合が増えていくが、この余分な集合は排中律を壊さずに存在できる。また、構成的に定義された集合には述語を適用できる。したがって、自分自身を要素しない集合という述語を充足する集合のクラスは存在するが、自分自身を要素としない集合の「集合」は構成的集合としては存在しないため、ラッセルのパラドックスは発生しない。これらの構成的集合の全体である全ての(構成的)集合のクラスが NBG 集合論の世界である。

集合にはものの集まりとしての一面と、他のクラスの要素となる対象としての2重性があるが、上のような構成的な集合を考えると、排中律を侵害することなく二重性を持った集合を記述することができるようになる。NBG の世界はこのような要素と構成的集合からなる世界と考えることができる。

公理的集合論は ZFC が代表的だが、NBG 集合論の方が直感的なイメージを作りやすいのではないかと思う。

追記

公理的集合論の世界といっても、個体と集合の集まりで素朴集合論の構成と見分けがつかない。ただし、集合が構成的集合であるというところが違っている。構成的集合の際立った特徴は2つある。一つは述語の自己言及にたいしては必ず偽となるということだ。つまり、自分自身を要素として含むことはない。このため述語の自己言及によってその要素の構成が変わるということはない。二つ目は正則公理をみたしているということ。つまり構成的集合に集合が含まれていても要素を辿っていけば有限の手続きで必ず集合でない個体に到達するということだ。このことによって悪循環を発生させず集合の内容が確定できる。

この二つの特徴のために、公理的集合論のどの集合 a についても述語 P(x) を a に適用した時 P(a) が真か偽の値を持つという排中律は成立している。つまり、公理的集合論の世界には論理が安全に適用できる。

素朴集合論における最大の困難はラッセルのパラドックスだった。「自分自身を要素として含まない集合」の集まりは存在するように思えるのに、「自分自身を要素として含まない集合の集合」を考えるとパラドックスになってしまう。つまり、「自分自身を要素として含まない集合」を集めた集合は「自分自身を要素としては含まない」ため自分自身を規定する述語を充足してしまう。

公理的集合論では、構成的集合は必ず自己言及に対しては偽の値を返さなければならないので、ラッセルの集合は構成的集合ではない。ラッセルの集合は公理的集合論の構成要素となることはできない。したがって公理的集合論の世界にはラッセルのパラドックスは発生しない。しかし構成的集合は全てラッセルの述語を充足するのにその集まりを考えられないというのはどういうことだという疑問が発生するが、公理的集合論の世界にはそのような集まりは存在する。構成的集合の全ての集まりはそのような集まりだ。しかし、そのような集まりはクラスという用語で表される。

NBG 集合論では、集合や個体などの「もの」の集まりはクラスであると考える。それでは集合とは何かという話になるが、集合は個体と同じ「もの」であるが、ものの集まりであるクラスを指し示す記号である。集合はものの集まりをあらわす記号であって、ものの集まりそのものではない。公理的集合論の世界を観察すると、様々な個体や要素の集まりを見つけることができるが、それをあらわす「集合」は必ずその集まりの外に存在する。任意の集合を集めて集合を作る場合、その集合の要素となっているのは、この記号としての集合であって、その記号としての集合が表すものの集まりそのものではない。

ものの集まりとその記号としての「集合」を分けて考えることによって、「集合」をもたないものの集まりである「真のクラス」が理解出来る。ラッセルの集合は、「自分自身を要素として含まない集合」の集まりであるが、それをあらわす記号としての「集合」を持たないのだ。このような「真のクラス」はそれをあらわす記号としての「集合」を持たないので、「真のクラス」を要素とする集合は作ることができない。

真のクラスの特徴は、その要素を集めた時にそれを表す記号としての「集合」自体が自分自身を規定する述語を充足してしまうことだ。構成的集合は全て自分自身を要素として含むことはできないので、そのような「集合」は作ることができない。この現象は別に無限とは関係がない。図書館のパラドックスでもわかるように、「自分自身に言及しない書籍」の目録はそれ自身が「自分自身に言及しない書籍」でないといけない。しかし、そのような目録をつくるとパラドックスになってしまうため、図書館には確かに「自分自身に言及しない書籍」の集まりがあるのにその集まりを表す目録をつくることができない。

このような真のクラスはラッセルのパラドックスのような特殊な述語に限らない。たとえば、「犬でないものの集合」はそれ自身が犬ではないので自己言及を充足してしまい構成的集合にはなり得ない。すなわち、犬でないものの集まりはあるのに、それを表す記号としての「集合」を作ることはできない。これは記号としての集合に自己言及が起きた時の振る舞いに関係しているからだ。集まりの記号としての「集合」に自己言及が起きた時に偽となる場合はその集合は矛盾を起こさず公理的集合論の世界のメンバーとなることができるが、自己言及で真になる場合はその集合をメンバーに加えることによって公理的集合論の世界に矛盾が発生してしまうからだ。公理的集合論の世界では、「ものの集まり」は自由に存在できるが、その「ものの集まり」を示す記号としての「集合」はいつも存在できるというわけではない。

ラッセルのパラドックスの困難は、「自分自身を要素として含まない集合」の集まりは確かに存在するのに、それを集合と考えるとパラドックスになってしまうという点だったが、ものの集まりとしての「クラス」とそのクラスを示す記号としての「集合」を分けて考えることによって、矛盾なく論理が適用できる集合の世界を構築できる。

内包的定義 A = {x| P(x)} は必ずクラスを定義できるが、P(A) が偽の場合はそのクラスを表す記号としての集合 A が定義され、 P(A) が真となる場合は、クラスを表す記号としての集合 A は定義できない。内包的定義は集合と論理をつなぐための要であるが、論理を集合に変換するために内包的定義が使われた場合その内包的定義が定義するのは実際はクラスである。このクラスを指し示す記号である「集合」という「もの」は内包的定義を適用した「もの」の世界に新しい「もの」を付け加えてしまうため、その性質によっては集合の世界に矛盾を持ち込んでしまう。このため、構成的集合はいつでも定義できるとは限らない。集合はものの集まりをものとして扱うための便利な道具だが、元の世界の論理を破壊しないために扱いに気をつけなければならない代物だ。

このように、ものの集まりである「クラス」とそのクラスを指し示す記号としての「集合」との関係を明らかにすることで、ラッセルのパラドックスは回避され、集合の世界に安全に論理を適用できるようになる。

[PR]
by tnomura9 | 2015-08-30 02:31 | 考えるということ | Comments(0)

集合と論理

箱の中にいろいろな色のボールが入っているとする。また、ボールには自然数が割り振ってあり、重複する数字はないものとする。ただし、色が同じものはあってもいい。たとえば、複数個の赤いボールがあってもいいが、それぞれ異なる数字が書かれている。

これらのボールに対し P(x) =「x は赤いボールである」という述語を適用させてみる。すると、対象としたボール a が赤い時は、P(a) =「a は赤いボールである」という命題は真であり、a が赤いボールではない時はこの命題は偽となる。そこで、述語 P(x) を充足する a すなわち P(a) が真となるボールを集めると、赤いボールの集合ができる。また、P(a) が偽となるボールを集めると、これは赤くないボールを集めた集合になる。また、P(x) は全てのボールについて P(a) が真であるか偽であるかのどちらかであるという排中律を満たす。

これをみると命題 P(a) が必ず真であるか偽であるという排中律の論理と、赤いボールの集合と赤くないボールの集合という集合の世界は相互変換ができるように見える。すなわち、論理の世界の定理は、そのまま集合の世界の定理に置き換えることができ、その逆も可能である。

しかし、集合論では「集合は要素の集まりという物である」と定義される。したがって、「赤いボールの集合」というボールが、これらのボールの中に含まれていなければならないし、また、「赤くないボールの集合」というボールも含まれていなければならない。そうでないと P(x) という述語は全てのボールに適用できるわけではなくなるため、P(a) という命題は必ず真であるか偽であるという排中律が成り立たなくなるからだ。

それでは「赤いボールの集合」というボールは赤いのだろうか、それとも赤くないのだろうか。そもそも、「赤いボールの集合」をあらわすボールが赤いかそうでないかという問い自体が変な問いだが、集合をボールと考える以上それが「赤い」のか「赤くない」のかのどちらかであるかを考えなくてはならない。

そもそも、「赤いボールの集合」をあらわすボールは、赤くも塗れるし、赤くない色でも塗れると考えるのが自然だ。「赤いボールの集合」をあらわすボールが何色であるかどうかを規定する理由はなにもなさそうだからだ。しかし、「赤いボールの集合」をあらわすボールはそれが集合を表しているという理由のために制限がある。それは、外延性の公理から「自分自身を要素として含んではならない」からだ。自分自身を要素として含んでしまうと、外延性の公理を適用した時に悪循環が発生して集合の要素が確定できなくなってしまう理由は以前の記事で述べた。したがって、「赤いボールの集合」をあらわすボールは赤以外のどんな色を塗っても良いが、赤い色だけは塗ることができない。

同様に「赤くないボールの集合」をあらわすボールは、それが自分自身を要素として含まないためには、赤い色を塗られなければならない。しかし、この場合、「赤いボールの集合」に外延性の公理を適用した場合、「赤くないボールの集合」という「赤いボールの集合」の要素の要素に、「赤いボールの集合」という要素が含まれてしまう。これはあきらかに悪循環を引き起こすので、「赤くないボールの集合」という集合のボールは赤い色もその他の色も塗ることはできないということになる。これは矛盾であるので、「赤くないボールの集合」というボールを作ることはできない。

しかしながら、このように「赤くないボールの集合」というボールを箱の中に作れないにもかかわらず、箱の中の「赤くないボール」の集まりは存在する。そうして、箱の中のボールは、赤いものと赤くないものに2分することができる。つまり P(x) = 「x は赤い」という述語に対して箱の中の全てのボールは P(x) を充足するかそうでないかの排中律を満たしている。それでは、「赤くないボールの集合」はどこに存在するのだろうか。それは、箱の外に存在するのだ。「赤くないボールの集合」をあらわすボールは、「赤くないボールの集合には含まれないが、赤いボールの集合にも含まれない。そのようなパラドキシカルなボールは、しかし、箱の外には存在することができる。

一方で「赤くないボールの集合」をあらわすボールに外延性の公理を適用しても、その要素である「赤いボールの集合」の要素には赤いボールしか含まれないので悪循環はおこらない。

色とりどりのボールの「外」に、「赤いボールの集合」という概念が存在する場合、論理と集合の対応は整合的である。しかし、「集合は要素の集まりという物である」と定義して、集合という概念を色とりどりのボールの「一員」と考えた時に、上で考えたような困難が発生してしまう。集合の概念はその要素の外で考えるべき物であるのに、それをその要素の一員として取り扱うために、「自分自身を要素として含まない集合は、自分自身を要素として含むとも含まないとも言えない」というラッセルのパラドックスが発生してしまう。

要素とその集合を同列に考えるやり方は、公理的集合論で順序数を作る時に必須の方法となっているので、このような要素と集合の混在を避ける方法はないのだろうが、そのためにクラスという集合でない物を考えなくてはならなくなってしまう。何か無理をしているような印象はぬぐいきれない。もっと素直に論理と集合の対応関係を記述する方法はないものだろうかと考えてしまう。

[PR]
by tnomura9 | 2015-08-29 07:10 | Comments(0)

竹内外史著 集合とはなにか

講談社ブルーバックスの 竹内外史著『集合とは何か』を読み返したら、前回の記事で論じた構成的な集合の作り方はゲーデルがすでにきちんと理論化していたことがわかった。この本は以前にも読んでいたはずなのに理解できていなかったのだ。

そのほかにも今回読み返してみたら、公理的集合論の世界は全てが集合でできていて、空集合 {} から始まって、要素を集めて新しい集合を作るというやり方で、次々に新しい集合を作り上げたものの総体だということがわかった。ちょっと技巧的だが、それらの集合の一つを自然数の数に割り当てることができる。このやりかたで、自然数から始まって複素数に至るまで全ての数をその体系の中に含むことができる。

また、正則性の公理なども、集合を次々に解体して樹形図を作ることができることだと説明されるとよくわかるが、正則性の公理そのものを示されても何のことを言っているのかわからない。

やはり、素人には記号でものを考えるのは難しい。記号の背後にあるモデルやイメージを解説してもらわないと理解できないと思う。逆に言うと、そういうイメージやモデルを先に示してもらえば、難解な記号の理解が意外にたやすくできるのではないだろうか。

数学の記号は数学的対象を表現する的確な方法だが、対象のどのようなものにも適合する一般性のために、かえって数学的対象のわかりやすいイメージを作るのを邪魔しているのではないかと思った。数式を使わない曖昧な説明では意図が伝わらないが、数学教育では、まずモデルを示して、それから公理や記号がどのようにそれに関わっていくのかという逆方向の教え方のほうがわかりやすいのではないだろうか。

しかし、この『集合とは何か』という本は集合論についていままで疑問に思っていたことにきちんと答えてくれている気がする。また、ブルーバックスだというのもうれしい。簡単に理解できる内容ではないが、じっくり時間をかけて読みたい本だ。

[PR]
by tnomura9 | 2015-08-24 18:46 | 考えるということ | Comments(0)

ghci でファイルの行を逆順にする。

ファイルの行を逆順にしたいときはよくある。ブログの記事リストは新しい順に表示されるが、過去記事のリストを作るときは古い方から表示した方が読みやすい。簡単な操作だが、プログラムをいちいち組むのは面倒だ。そこで、ghci でインタラクティブにやれないかどうかを考えてみた。

最初にghciからシェルコマンドが使えることを確かめる。本題と関係ないが、グリコのおまけは箱の上に乗っているので。

Prelude> import System.Process
Prelude System.Process> system "cat let_it_be.txt"
When I find myself in times of trouble,
Mother Mary comes to me,
Speaking words of wisdom,
Let it be.
And in the hour of darkness,
She is standing right in front of me,
Speaking words of wisdom,
Let it be.
ExitSuccess

これからが本題。ファイルを読み込む関数は readFile だ。

Prelude System.Process> readFile "let_it_be.txt"
"When I find myself in times of trouble,\nMother Mary comes to me,\nSpeaking words of wisdom,\nLet it be.\nAnd in the hour of darkness,\nShe is standing right in front of me, \nSpeaking words of wisdom,\nLet it be.\n"

一続きの文字列を変換して行のリストにするには lines を使う。readFile の出力は IO モナドなので >>= でパイプして print 関数で表示するなどの工夫が必要だ。lines は IO モナドの関数ではない純粋関数だが print と . で関数の合成を行うことで使うことができる。

Prelude System.Process> readFile "let_it_be.txt" >>= print . lines
["When I find myself in times of trouble,","Mother Mary comes to me,","Speaking words of wisdom,","Let it be.","And in the hour of darkness,","She is standing right in front of me, ","Speaking words of wisdom,","Let it be."]

次に reverse 関数でリストを逆順にする。

Prelude System.Process> readFile "let_it_be.txt" >>= print . reverse . lines
["Let it be.","Speaking words of wisdom,","She is standing right in front of me, ","And in the hour of darkness,","Let it be.","Speaking words of wisdom,","Mother Mary comes to me,","When I find myself in times of trouble,"]

unlines 関数でリストを文字列に変換

Prelude System.Process> readFile "let_it_be.txt" >>= print . unlines . reverse . lines
"Let it be.\nSpeaking words of wisdom,\nShe is standing right in front of me, \nAnd in the hour of darkness,\nLet it be.\nSpeaking words of wisdom,\nMother Mary comes to me,\nWhen I find myself in times of trouble,\n"

仕上げは writeFile でファイルに書き戻す。

Prelude System.Process> readFile "let_it_be.txt" >>= (writeFile "reversed.txt") . unlines . reverse . lines
Prelude System.Process>

ファイル reversed.txt が作成されているかどうか確認する。

Prelude System.Process> system "cat reversed.txt"
Let it be.
Speaking words of wisdom,
She is standing right in front of me,
And in the hour of darkness,
Let it be.
Speaking words of wisdom,
Mother Mary comes to me,
When I find myself in times of trouble,
ExitSuccess

大成功。

[PR]
by tnomura9 | 2015-08-18 00:28 | Haskell | Comments(2)

System.Random 記事リスト

今年の1月に始めた Haskell の標準モジュール の System.Random のソース解読を中断していたら、すっかり忘れてしまっていたので記事リストを作ってみた。もう一回読み直して再挑戦だ。

System.Random 記事リスト

Haskell で乱数[ 2015-01-03 12:42 ]
System.Random (1)[ 2015-01-04 00:30 ]
System.Random (2) Haddock[ 2015-01-04 15:01 ]
System.Random (3) Haddock[ 2015-01-05 21:04 ]
System.Random (4) Haddock[ 2015-01-11 17:53 ]
System.Random (5) Haddock[ 2015-01-12 15:06 ]
System.Random (6) Haddock[ 2015-01-12 18:33 ]
System.Random (7) Haddock[ 2015-02-01 12:06 ]
System.Random (8) Haddock[ 2015-02-03 12:00 ]
System.Random (9) Haddock[ 2015-02-08 23:08 ]


[PR]
by tnomura9 | 2015-08-16 10:50 | Haskell 記事リスト | Comments(0)

実無限と可能無限

ラッセルのパラドックスの魅力は、数学の根本であるはずの集合論に紛れもない矛盾が潜んでいるという神秘性だろう。この世界のすべての論理を支えている数学に、ラッセルのパラドックスという矛盾が潜んでいて、しかもその矛盾を認めてしまえば、壮大な数学の伽藍が一挙に無意味なものになってしまう。また、これは、集合は「自分自身を要素として含んでいるか」「自分自身を要素として含まないか」のいずれかであるという排中律を根幹から否定してしまため、論理の土台である排中律すら否定しなくてはならなくなる。なんとも破壊力のある厄介な謎だ。

ラッセルのパラドックスの発生するメカニズムについては、このブログで言葉を換え何度も記述してきたので繰り返さないが、一言で言うと、「ものの集まりは集合という『もの』である」という集合の定義と「述語を充足するものの集まりは集合を規定する」という内包公理のあいだの微妙なずれから発生しているのだ。

ラッセルのパラドックスの推論には一見何の瑕疵もないがパラドックスを引き起こしてしまう。すなわち、「自分自身を要素として含まない集合」の集合はそれ自身が自分自身を要素としていなければ、「自分自身を要素として含まない集合」という述語を満たすので、自分自身を要素として含んでいなければならないし、自分自身を要素として含んでいると仮定してもやはりパラドックスになってしまう。

これは、ものの集まりはどんな場合でも集合であるし、述語を充足するものの集まりは必ず集合であるという大原則が森羅万象に当てはまると仮定した上での推論だからだ。すなわち、無限のものの集まりに対し、どのような場合にでもこの2つの根本原理は成立すると仮定しての推論である。しかし、残念ながら、この推論からはパラドックスが演繹されてしまう。

すべてのものに共通する原理から、すべてのものに適用される定理を演繹するというのは数学ではよく取られる手法だ。数学の目的は個々の事例における特殊な結論ではなくて、すべての事例に適用される一般的な定理を求めることだからだ。しかし、それが正当な推論によってパラドックスを引き起こす場合は、共通する原理のほうを疑わなければならない。

そうは言っても「ものの集まりを集合という『もの』である」と考える集合の定義は、これを疑ってしまうと集合について全く議論できなくなるし、「述語を充足するものの集まりは集合を規定する」という内包公理は、論理の根幹である排中律と表裏一体の公理である。この二つを疑う理由は全くないように思われるので、それでは論理のほうにパラドックスが潜むのかという話になって、論理には人知の及ばない深淵があるというような神秘的な感銘を受けてしまう。

すべてのものに潜む性質から、推論によってすべてのものに適用される定理を求めるというのは、抽象的なアプローチだ。個々の事例の瑣末な性質を捨象し、本質的な性質について論考することによって得られた結果は、すべてのものに適用できる。すべての事象に適合する原理はすなわち真理である。これが、ギリシャの哲学者たちによって発明され、現代の文明を支える根幹にもなっている。これは、また、すべてのものを一括りにして考えるトップダウンの考え方でもある。

しかし、この抽象的なトップダウンの考え方がうまくいかないときは、考え方の方向性を変えてみる必要がある。つまり、構成的なボトムアップの検討をしてみることだ。抽象的な考え方の真逆をいくのだ。

ラッセルの推論はすべての要素や集合に共通する2つの公理から出発した。しかし、構成的な推論では、これらの原理が個々の事例にどのように現れるかをまず調べる。

最初に、構成論的な立場では集合を構成する大元は集合ではなく犬や猫などの個体であると考える。数学的な対象である数なども集合ではないものは個体である。集合はこれらの原初的な個体の幾つかを集めて作るが、集合論ではその集合もやはり個体と考える。この集合という個体は、最初に考えた要素の個体の集まりにはなかったものだ。それらの要素の集まりを抽象して集合という個体として新たに作り出されたものだ。しかし、集合論の世界では、この新しく作られた集合という個体を元々の要素の集まりの一員として加え、それらの要素と等しく個体として考える。

もともとの要素の集まりに集合という個体を加えることで、集合論の扱う個体の範囲は広がるが、新しく増えた集合という個体を含めてさらに新しい集合という個体を作り出すことができる。したがって、集合論の扱う個体とは、このような操作を無限に続けていって次々に生成される個体の世界なのだ。数学ではこのような無限の生成過程で生じる個体すべてを個体の全体として抽象化して考えるが、構成的な立場からは、それは終わることのない無限の『生成過程』なのだ。抽象的な視点からは、それらの生成過程の総体を考えるが、構成的な視点からは、それらの生成過程の切断面を考える。抽象的な視点が総合ならば、構成的な視点は分析である。

抽象的な視点からは、すべての個体は述語を充足するか充足しないかのどちらかであり、すべての集合は、自分自身を要素として含むか、要素として含まないかのどちらかであると捉える。しかし、構成的な視点から集合を捉えるとその2つの状態では割り切れない事態が起こり得ることがわかる。

たとえば、構成的な視点から集合の世界をとらえるときの初期条件である要素だけの集まりが存在する状態を考えてみよう。その状態で、犬を集めて犬の集合を考える。「犬の集合」という個体は初期条件には存在していなかったが、初期条件の要素の中から「犬である」という述語を満たすものを集めると「犬の集合」ができあがる。犬の集合を生成した過程を考えると、当然犬の集合自身はその要素には含まれない。しかし、犬の集合も個体のひとつなので「犬である」という述語が適用される。この場合犬の集合はそれ自身には含まれないので、犬の集合の要素は確定する。こうして、初期条件の要素の集まりに犬の集合という個体のメンバーが加わる。また、新しい個体の集まりのメンバーにはすべて「犬である」という述語や「犬ではない」という述語が適用され、真か偽の値が得られる。すなわち、排中律がそれらすべての個体について適用できる。

そこで、こんどはそれらの個体について、「犬でないもの」の集合を作ってみよう。そうすると、先ほど作られた犬の集合の要素ではない個体を集めて「犬ではないものの集合」を作ることができる。面白いことに「犬の集合」は犬ではないので「犬ではないものの集合」の要素となる。この場合も「犬ではないものの集合」という新しい個体が出現する。したがって、この個体にも「犬ではない」という述語が適用され、「犬ではないものの集合」は「犬ではない」ことがわかる。これは、「犬の集合」の場合と違って「犬ではないものの集合」自身がそれを規定する述語である「犬ではないもの」を充足する。しかし、その生成過程をみるとわかるように「犬ではないものの集合」それ自体はその要素としては含まれていない。しかしながら、この集合は自分自身を要素としては含んでいないにもかかわらず「犬ではないもの」という述語を充足している。

これが、集合の定義と内包公理の微妙なずれの正体である。集合の世界を構成的に調べると、自分自身を要素として含まないにもかかわらず、自分を規定する述語を自分自身が充足してしまうという事例が発生することがわかる。

しかし、この場合にも個体は述語を充足するか充足しないかのどちらかであるという排中律は成立している。つまり、「犬の集合」と「犬でないものの集合」とその他の要素的な個体からなる世界では、述語「犬である」も述語「犬ではない」も必ず真か偽の値をとる。

ただし、集合の世界全体を考えた時にはこれでは十分ではない。つまり「犬でないものの集合」という新しい「犬でないもの」という個体がある限りは、暫定的な「犬でないものの集合」は内包的定義による「犬でないものの集合」にはなりえない。そこで、暫定的な「犬でないものの集合」をふくむ新しい「犬でないもの」を集めた集合を考えなければならない。そこでそのような集合を作ってみると、その新しい集合自身が「犬でないもの」という述語を充足してしまう。したがって、この操作を無限に繰り返しても「犬でないもの」すべてを集めた集合を作ることはできないのだ。これを無理にそのような集合があると考えるとラッセルのパラドックスが発生してしまう。

このように、集合の世界全体をとらえる抽象的なアプローチでは見落とされる集合の構造は、構成的なアプローチを取ることで浮き彫りにすることができる。構成的なアプローチを取ることで、内包的定義では集合を定義することができない場合があることをはっきりと知ることができる。また、構成的なアプローチは集合の世界を完成された個体の世界と捉えず、常に個体が生成され続ける動的な世界と捉えることで、その無限の生成過程の断面では排中律が問題なく適用できることを知ることができる。

ラッセルの推論のように集合の世界を静的に捉えるやり方は、実無限の視点だ。また、構成的に集合の世界を組み立てていくやり方は可能無限の立場だ。実無限の視点からはパラドックスと捉えられる現象が、可能無限の立場からはパラドックスではないが、無限に生成される運動として捉えることができる。しかし、どちらも白か黒かの決着がつけられないという意味では一致している。

無限とはこのように本質的には動的な生成現象なのではないだろうか。これを実無限の立場からみるとパラドックスになり、可能無限からみると無限の運動に見える。アキレスと亀のパラドックスで有名なゼノンの一連のパラドックスは、この無限の運動の不可思議さを浮き彫りにしているのだろう。

[PR]
by tnomura9 | 2015-08-14 08:44 | 考えるということ | Comments(0)

年号西暦変換

年号を西暦に変換するプログラムを作ってみた。明治、大正、昭和、平成の違いは case ~ of を使ったパターンマッチで処理した。また、年の文字列を数値に変換するのには read 関数を使った。ちょっと使っていないとこんな簡単なコツも忘れてしまう。

Prelude> :set editor vi
Prelude> :e fromNengo.hs
Ok, modules loaded: none.
Prelude> :l fromNengo.hs
[1 of 1] Compiling Main ( fromNengo.hs, interpreted )
Ok, modules loaded: Main.
*Main> fromNengo "h27"
2015
*Main> fromNengo "t12"
1923


fromNengo のソースは次のようになる。


fromNengo :: String -> Integer
fromNengo xs =
  case (xs) of
    ('m':year) -> 1867 + (read year :: Integer)
    ('t':year) -> 1911 + (read year :: Integer)
    ('s':year) -> 1925 + (read year :: Integer)
    ('h':year) -> 1988 + (read year :: Integer)


fromNego を ghc でコンパイルしてターミナルから実行できるようにしたくなったので。fromNengo.hs のソースファイルを次のように変更した。


import System.Environment

main = do
  nengo <- getArgs
  print $ fromNengo $ head nengo

fromNengo :: String -> Integer
fromNengo xs =
  case (xs) of
    ('m':year) -> 1867 + (read year :: Integer)
    ('t':year) -> 1911 + (read year :: Integer)
    ('s':year) -> 1925 + (read year :: Integer)
    ('h':year) -> 1988 + (read year :: Integer)


ソースファイルのコンパイルは次のようになる


$ ghc -o fromNengo fromNengo.hs
$ ./fromNengo t12
1923



[PR]
by tnomura9 | 2015-08-09 13:41 | Haskell | Comments(0)

Haskell でパスワードを作る

最近ネットのサービスを利用することが多くなったが、そこで一番困るのはパスワードをどうするかだ。ひとつのパスワードを使いまわすのは危険だし、かといって、ランダムなパスワードを考えるのは大変だ。そこでパスワードを Haskell で作れないか考えてみた。

ソースファイルを作るのが面倒臭かったので ghci で対話的に作ってみた。まず、乱数を使うので System.Random モジュールをインポートする。

Prelude> :m System.Random
Prelude System.Random>

パスワードに使用する文字のリスト chars を作成した。英小文字、英大文字、数字からなっている。

Prelude System.Random> let chars = ['a'..'z'] ++ ['A'..'Z'] ++ ['0'..'9']
Prelude System.Random> chars
"abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ0123456789"

このリストのどの文字を使用するかは、chars に添字を指定してやればいい。

Prelude System.Random> chars !! 5
'f'

chars に含まれる文字数を調べるのには length 関数を使えばいい。

Prelude System.Random> length chars
62

System.Random モジュールで乱数を発生するためにはシードとなる StdGen 型のデータが必要だ。これは mkStdGen 関数で作成できる。mkStdGen 関数は Int を引数に取り StdGen 型の乱数のシードを作る。

Prelude System.Random> let seed = mkStdGen 7
Prelude System.Random> seed
8 1

0 .. 61 までの数の乱数のリストを作るには randomRs 関数を使う。randomRs 関数の引数は整数の範囲を示すペア (0, 61) と乱数のシードだ。発生する乱数リストは無限リストなので、take 関数で適当に切り取る。

Prelude System.Random> take 5 $ randomRs (0, 61) seed
[25,12,33,38,20]

この乱数のリストの数字を添字に chars の文字を取り出せば、目指すパスワードが作れるはずだ。

Prelude System.Random> take 8 $ map (chars !!) $ randomRs (0, 61) seed
"zmHMuJ2n"

このパスワードは mkStdGen の引数 7 から簡単に取り出せるので覚えやすいが、破られやすい。その場合は、乱数リストの先頭の何文字かを読み捨てて取り出せばいい。

Prelude System.Random> take 8 $ drop 66 $ map (chars !!) $ randomRs (0, 61) seed
"XCUb6yu5"

久しぶりに Haskell でプログラムを作ったが、小さいプログラムを Haskell で作るのはやっぱり楽しい。


[PR]
by tnomura9 | 2015-08-05 21:11 | Haskell | Comments(0)

自己言及は矛盾ではない

ラッセルのパラドックスは集合を定義する述語の自己言及によって起きる。つまり「自分自身を要素として含まない集合」という述語をもとに内包公理で集合 R を作った時に、R にこの述語を適用すると、R が R の要素であれば、R は R を含まないし、R が R の要素でなければ、R は R を要素として含むというパラドックスになってしまう。

公理的集合論の分出公理はこのような述語の自己言及を防ぐための工夫で、これで内包公理を弱めることによって一応ラッセルのパラドックスは起きなくなったわけだが、はたして、述語の自己言及は矛盾なのだろうか。

この記事では、素朴集合論の構成を考えることで、述語の自己言及という不可解なものを自然に取り入れることができ、しかも、それは矛盾を引き起こすものではないことを主張したいと思う。内容は今までの記事と同じだが、こういう見方をすれば素朴集合論に矛盾が含まれていると考える必要はないのではないかという主張だ。

まず素朴集合論の公理として、「集合に分解できない個体としての要素が存在する」を取り入れる。集合論の特徴は、このような要素の集まりも「集合」という個体として扱うが、実世界を眺めても、集合ではない個体としての要素があると考えたほうが自然だ。

2番目の公理としては「個体を集めて集合という個体と考えることができる」を採用する。これは生成的な定義で、それまでにあった個体を集めて集合という新しい個体を形成できる。つまり、集合とは個体の集まりから作られた新しい個体であるというところがミソだ。

第3の公理は排中律の公理で、「述語は個体に適用して真か偽の値を得ることができる。」を採用する。また、内包公理の代わりに、第4の公理である「述語を充足する要素だけの集合を作ることができる。」を取り入りれる。これは内包公理のように、「述語を充足する要素全てを集めたものは集合を定義する」とは言っていない。

第5の公理は外延性の公理だ。これは「集合が等しいと考えられるのはその要素全てが一致する場合に限る」というもので素朴集合論でも採用されているものと同じだ。

自己言及が矛盾ではないことを主張するのには、この5つの公理で十分だ。素朴集合論の世界の土台はこの5つの公理で構成されるものの全てだと考えるのだ。これらの公理の根幹は、素朴集合の世界はその構築の基礎はあくまでも集合に分解できない要素という個体であるということだ。集合はそれらの要素から概念という個体として組み立てられ、また、それらの要素と等しく個体として扱うことができるが、しかし、そのような集合の根幹は要素でなくてはならない。これが、明確にされていれば、述語の自己言及のような不可解なものも許容されるのがわかる。

素朴集合論をこのような公理で捉えた時に、述語の自己言及はどのように捉えることができるだろうか。そこで、ある述語 P(x) を充足する要素全てを集めた集合 P を考える。まず、これがそれまでの集合の構成要素にはなかった新しい集合であることを示そう。集合の一意性を示すためには、その要素がほかの集合と一致していないことを示す必要が有る。そのような場合外延性の公理から、集合 P はその要素として自分自身を含んでいないことがわかる。それは、集合 P が自分自身を要素として含んでいた場合、その要素としての P の一意性を確かめるために外延性の公理を使った時に、無限の再帰が起きてしまって、集合 P を確定することができなくなるからだ。

さて、集合 P はその要素に含まれないので、これは、その要素が確定していることを外延性公理で確かめることができる。したがって、集合 P はそれまでの集合の構造には含まれていなかった新しい個体だが、集合の定義に合致しているため、これに対しても述語を適用することができる。そして、排中律の公理から述語 P(x) を P に適用すると真か偽の値が得られる。P が P(x) を充足しない場合はこれは通常の内包公理による集合の定義となる。しかし、P が P(x) を充足する場合、P は自分自身を要素として含まないにもかかわらず、自分自身を規定する述語 P(x) を充足する集合になる。素朴集合論の内包公理ではこのような場合ラッセルのパラドックスが発生してしまうが、上に述べた公理からは新しく生成された P という集合に P(x) が適用されることは禁止されない。

つまり、術語 P(x) を充足すると思われる当面全ての要素を集めて集合 P を作ったとすると、その集合はそれまでの集合や要素とは異なる新しい集合 P という個体であるということだ。これは集合の世界全てを最初から考えるのではなくて、集合以外の要素だけからなる初期の状態から集合の定義を使って新たな集合という個体を生成していく過程の過渡的な切断面を捉えているためだ。したがって、その集合を内包公理で生成するための術語 P(x) をその集合が充足したとしても矛盾ではない。集合 P が生成される前の構造の中で内包公理によって新しい集合 P が生成された後で、それに対し P(x) を適用することは可能である。たとえば、当面考えられる全ての「自分自身を要素として含まない集合」をあつめて集合 R を作った時、その R が「自分自身を要素として含まない集合」という述語を充足しても問題ない。

P(x) によって P が生成された時に、新しい集合 P が生成されるといったが、実は、P の部分集合はすべてそのような集合になる。「個体を集めて集合という個体と考えることができる」という集合の定義が生成的な定義であるために、述語 P(x) で集合を作ると同時に、その要素と異なる新しい集合が次々に生成されてしまうのだ。述語の自己言及は一回だけ起きるわけではなく、このような集合の生成の度に連綿と行われる。述語の自己言及をこのような過程の一断面と考えると、自己言及自身に矛盾があるわけではないことがわかる。ラッセルのパラドックスはこのような自己言及が無限に終わらない集合の生成過程を表していたのだ。このような要素の集まりは集合ではなくクラスになってしまう。集合は述語を充足する要素はすべてその集合の要素であるが、クラスを生成する過程で現れる集合は常に自分自身を要素として含まないにもかかわらず、述語を充足してしまうからだ。

内包公理による集合の定義は静的な状態であると考えるとラッセルのパラドックスが起きてしまうが、述語の自己言及が動的に行われ、次々に述語を満たす要素を生成していく過程であると理解すると、述語による内包的定義が集合を定義せずクラスの要素が無限に増大していく様子をイメージすることができる。また、この考え方の利点は、クラスのどの要素をとっても述語を適用した時に真か偽の値をとるという排中律が成立していることだ。ラッセルのパラドックスは排中律に矛盾があるような結果になったが、クラスを動的にとらえるとどの時点でも排中律は破られない。

このように述語の自己言及を集合が次々に生成される過程に生じる現象だととらえることで、ラッセルのパラドックスを回避できるだけでなく、自分自身を要素として含まないにもかかわらず自分自身の述語を充足してしまう集合からなるクラスの性質を明確にできる。このため、素朴集合論に矛盾が潜んでいると考えることなく、ラッセルのパラドックスのような現象を説明できる。

[PR]
by tnomura9 | 2015-08-01 07:36 | 考えるということ | Comments(0)