述語論理の意味論

命題論理学の場合原子命題 A は真値か偽値を持つという意味論が分かりやすいので、命題論理の仕組みをイメージするのが容易い。原子命題を論理記号で結合した複合命題の真偽値は真理値表を作成すれば簡単に調べる事ができる。

しかし、このような命題論理学の応用範囲は論理回路の設計以外には比較的限られている。実用上論理的な推論の道具となるのは述語論理だ。したがって、述語論理の意味論を考えることは、論理についての理解を容易にするはずだ。そう思って論理学の教科書をのぞいみたがお手上げだった。

論理学を集合のイメージでとらえる事ができれば便利だと思ったが、論理の仕組みはそう簡単ではないようだ。素朴集合の世界を「帰属関係の定義された個体の集合」と考えると、そのような個体の集合である個体領域 D には述語論理が構築できない。D は述語論理のモデルにはならない。そうであれば、個体領域 D を拡張して述語論理のモデルになるようにすれば、素朴集合論の簡潔な集合のイメージを利用できて、論理も適用できると考えたが、そう簡単にはいかないようだ。

直感的な発想だけにたよらず、真面目に勉強しなくては。

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

ラッセルのパラドックスとは何か

「自分自身を要素として含まない集合の集合」を考えるとパラドックスになってしまうというラッセルのパラドックスには長年悩まされ続けてきた。数学の根底は集合の考え方と論理にあると思って論理学や集合を学び始めると最初のところにパラドックスが紹介してあり、足元から土台が崩れてしまう。

不満の理由はふたつあった。一つは集合を物の集まりという物と考える素朴集合論ではパラドックスが発生する理由が分からなかったこと。もう一つは公理的集合論では集合とは何かという視覚的なイメージが作れなかったことだ。

前回の「論理と集合」という記事でその不満がほぼ解決されたと思うが、宣伝のため、簡単にその要点をまとめてみた。

第1は、ラッセルのパラドックスは、素朴集合論の世界を「所属関係が定義された対象の集合」という対象のネットワークと考えるとらえ方が、その発生原因であるということだ。自分自身を要素として含まない集合の集合というような述語は、素朴集合の世界をこのような対象の所属関係によるネットワークでとらえることによる副産物である。つまり、「所属関係が定義された対象の集合」では表現力が不足して、その対象の集合の全ての部分集合を表現できないのだ。

第2は、論理は、数学的対象のうちそのべき集合が全て扱えるものにだけ適用されるということだ。論理とは集合演算の別名なのだ。ある数学的対象の集合のべき集合が完全に記述できないような体系には集合演算は適用できず論理は適用できない。素朴集合論を「所属関係が定義された対象の集合」ととらえる限り、そのネットワークでは対象の集合の部分集合を部分的にしか表現できないので、論理を適用することはできない。

第3はこのような見方によって「クラス」の定義が明確になる。「クラス」とは集合の世界を「所属関係が定義された対象の集合」のようなネットワークでとらえたときに、そのネットワークでは表現できなかった部分集合をさす。素朴集合論に論理を適用する場合、「所属関係が定義された対象の集合」に現れる「集合」に加えてそこに現れることのできなかった部分集合である「クラス」を合わせた「広義のクラス」に対して適用させなければならない。

集合、クラス、論理をこのようにとらえると随分視界がすっきりする。

たとえば、「自分自身を要素として含む集合」や「自分自身を要素として含まない集合」は「所属関係の定義された対象の集合」の中に存在し、対象はそのどれかであるはずなのに「自分自身を要素として含まない集合の集合」がパラドックスになるという不満に対しては、「所属関係の定義された対象の集合」というネットワークの要素である対象としてはそのような集合は存在しないが、そのようなネットワークの外に「クラス」として存在すると考えることができる。なぜなら、そのようなネットワークでは、そのネットワークの対象の集合の部分集合全てを表現することはできないからだ。「自分自身を要素としない集合の集合」は確かにネットワークに現れる対象の部分集合だが、それを対象のネットワークの内部で表現することはできない。

くわしい議論については前回の記事の「論理と集合」やその関連リンクに紹介している。

追記

ラッセルのパラドックスの深刻さは、論理と集合が表裏一体のものであるという直観が見事に裏切られたことにある。素朴集合論には論理を適用できないことが分かったのだ。しかし、それは、素朴集合の考え方の中に暗黙のうちに集合の全体を「帰属関係の定義された対象の集合」で表せるという前提があるからに過ぎない。{a, b, c} というような対象が3個しかない体系でも a, b, c の帰属関係では {a, b, c} の全ての部分集合を表すことはできない。論理と集合の間の齟齬は、集合の世界を「帰属関係の定義された対象の集合」で表現しようとしたことによる副次的な現象なのだ。集合を表す記号表現を {a, b, c} の内に求めなければ、論理と集合の関係は直観通り整合的なものになる。{a, b, c} の冪集合に全単射な対象の集合 {h, i, j, k, l, m, n, o} を考えると、{a, b, c} の全ての集合についての集合演算と論理が {h, i, j, k, l, m, n, o} の上で成り立つからだ。このように、論理と集合の間の関係は、集合を記号表現、集合の外延を記号内容と考える記号論的な観点から解きほぐすことができる。

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

論理と集合

論理とは集合演算のことだ。従って、ある数学的対象について、その全ての部分集合を表現できない理論では、その数学的対象に論理を適用することができない。

素朴集合論の場合、集合の世界を「帰属関係の定義された対象の集合」と定義したために、その対象の集まりの全ての部分集合の一部分しか表現することができない。このため、素朴集合論には論理を適用することができない。前回の記事で述べたように、素朴集合論にラッセルのパラドックスが発生したのは、「帰属関係の定義された対象の集合」では、その対象の集合の全ての部分集合を表現できないからだ。

一方で自然数の集合について考えてみる。自然数の集合の冪集合は0以上1未満の実数と全単射を作ることができる。従って、自然数の集合についての集合演算は実数の上で全て記述することができる。このような場合、自然数の集合には論理が適用できるのだ。つまり、自然数は奇数かまたは偶数であるという論理的な推論は、自然数の集合を N、奇数の集合を O、偶数の集合を E としたとき、

N = O ∪ E かつ O ∩ E = ∅

のように集合の言葉で表現することができる。また、数学的帰納法についても、述語 P(x) について

P = {x | P(x)}

とすると、

1 ∈ P かつ (k ∈ P ならば k+1 ∈ P)

であるとき、ペアノの公理から、

1 ∈ N かつ (k ∈ N ならば k+1 ∈ N)

なので

1 ∈ N ならば 1 ∈ P

である。また k が 1 以外の自然数のときは、k ∈ N のときは 1 から始めて k に至るまでの数がみな N の要素であることがわかるが、同様に 1 から k までの数が P の要素であることもわかるので、

k ∈ N ならば k ∈ P

したがって、

N ⊂ P

となる。また、明らかに P ⊂ N なので、結局

N = P

となり述語 P(x) を充足する自然数の集合は全ての自然数の集合であることが分かる。

このように自然数の集合については、その冪集合の存在が保証されているので、論理を集合の関係として論じることができる。ところが、「帰属関係の定義された対象の集合」ではその集合の冪集合を全ては表現できないためその全ての集合演算を論理として記述することができない。

ある数学的対象に論理と集合を適用させたいと考える場合は、最低その対象の部分集合の全て、すなわち冪集合が存在することが必要条件なのだ。素朴集合論のラッセルのパラドックスを回避するために、集合に様々な公理による規則を適用することによって、数学的対象に集合と論理を共存させようと試みられているが、もっと単純に、その数学的対象をその全ての部分集合を表現できるような体系に構築するというアプローチも考えることができるのではないだろうか。

たとえば反復的集合観という考えが ZFC 集合論のモデルになるらしい。詳しくは「反復的集合観と公理的集合論」というページに紹介してあるが、要するに、空集合から初めて、その段階的にその集合のべき集合の要素を付け加えて集合を増やしていく方法だ。この手続を引用すると次のようになる。

  • 段階0: 何もない。
  • 段階1: 段階0までの集合を要素とするあらゆる集合を考えて、それらを追加する。
  • 段階2: 段階1までの集合を要素とするあらゆる集合を考えて、それらを追加する。
  • 以下同様。

  • この方法なら、どの段階の集合の要素も、前の段階の集合の全ての部分集合を表現することができる。言葉を変えると前の段階の集合を論理的に扱うことができる。他の数学的対象も同じようなやり方で論理化できるのではないだろうか。

    ラッセルのパラドックスを回避するために集合とは何かという議論が変に難しくなってしまっているが、ラッセルのパラドックスの発生原因が集合の世界を「帰属関係の定義された対象の集まり」と定義する方法の不完全さによる副産物であると考えると、集合を素朴に捉えながら同時に論理的にも扱いやすいように説明できるのではないだろうか。

    このブログ内の関連記事



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

    ラッセルの集合(クラス)の存在証明

    素朴集合論の世界を「帰属関係の定義された対象のあつまり」と捉える方法では、ラッセルのパラドックスによって「自分自身を要素として含まない集合の集合」が矛盾を起こすことを示す。

    いま、「帰属関係の定義された対象」a, b, c, ..., が無限に存在するとする。そこで、a, b, c, ..., を縦横に並べて行の対象が列の対象を要素として含まないときに 0, 行の対象が列の対象を要素として含むときに1となるような演算表を考える。すると、この演算表の行に現れる数列、たとえば 0, 1, 1, .., などは対象 a, b, c, ... の集合の部分集合を表している。すなわち、各行の a, b, c, ..., の外延である a, b, c, の集まりは、演算表の行の数列で表されることが分かる。

    このとき、演算表の対角線部分はある対象が自分自身を要素として含むか含まないかを表す。対角線部分の数が 0 であればそれは対応する対象が自分自身を要素として含まないことを示し、1 であれば対応する対象が自分自身を要素として含むことを示す。そこで、対角線部分が0であれば1、1であれば0となるような数列を考えると、これは a, b, c, ..., の集まりの部分集合である。また、これは「自分自身を要素として含まない集合の集合」を表している。しかし、この集合は演算表の中に現れることはない。それは、対角線部分で演算表のどの行の集合とも異なるからだ。

    このことをラッセルのパラドックス風に表現することもできる。そのような集合に対応する対象を r とする。この r の対角線部分の値は 0 とも 1 とも言うことができない。なぜならば、r の対角線部分が 0 であれば、r は自分自身を要素として含まない集合であるので、r に含まれるすなわち r の対角線部分は 1 でなければならないので矛盾するし、r の対角線部分が 1 であると仮定してもやはり矛盾するからである。従って、このような r は演算表に現れる事はできない。

    以上の議論は、しかし、自分自身を要素として含まない集合の集合が存在しないことを意味しない。なぜなら、対角線部分を反転させてできる数列は明らかに a, b, c, ... の部分集合を表しているからだ。ただし、この部分集合は「帰属関係を定義された対象の集まり」の中に含まれることはない。すなわち、a, b, c, ... からなる集合全てを表現するには「帰属関係を定義された対象の集まり」では表現力が不足していることを示している。「自分自身を要素として含まない集合の集合」はこのような対象の内部には見つけられないが、このような対象の集まりの外部には表現可能なのである。

    実際、a, b, c, ... の一つの部分集合は 0.0101.. のような0以上1未満の2進数の無限小数との全単射を作ることができる。この全単射関係によって a, b, c, ... の全ての部分集合の集合演算を0以上1未満の実数軸の上で考えることができる。ただし、上に述べた演算表ではその全てを表現することができない。ラッセルのパラドックスはこの穴ぼこだらけの演算表に現れた現象を示しているにすぎないのだ。

    このような演算表に現れない a, b, c, ... の部分集合を集合ではなくクラスと呼ぶことにすると、演算表上の部分集合と演算表には現れない部分集合であるクラスとで a, b, c, ... の全ての部分集合をカバーすることができるため、集合の世界に矛盾なく論理を導入することができる。「帰属関係の定義された対象のあつまり」は表現力の不足から論理が構築できないが、集合というものの集まりをクラスにまで拡張することで全ての集合演算を行うことができる。

    集合の世界に論理を持ち込むには、集合とクラスをあわせた広義のクラスが必要なのだ。

    追記

    「自分自身を要素として含む集合」や「自分自身を要素として含まない集合」は集合本来の概念とは異なるのではないだろうか。それは集合の世界を「帰属関係の定義された対象の集まり」という対象のネットワークで表現した方法による副産物のような気がする。そのため、上で議論したような表現力の不足する集合の世界が生まれてしまったのではないだろうか。だから、公理的集合論のような複雑な規則で縛られた公理体系よりもっとシンプルで論理とも相性の良い集合論があるような気がする。単なる直感的な印象だが。

    追記その2

    集合 a, b, c, ... の全ての部分集合を表すのに「帰属関係の定義された対象の集まり」では表現力不足であることは分かったが、それではそのような集合のネットワークから漏れた a, b, c, ... の部分集合は一体どれほどあるのだろうか。これは a, b, c, ... の部分集合が0以上1未満の実数と全単射で対応することを利用すると分かる。a, b, c, ... の外延に対応する a, b, c, ... の部分集合をそれぞれ 0 以上 1 未満の実数に対応させると、それは小さい方から整列させることができる。もちろん、a, b, c, ... は無限にあるのでこの操作は無限に終わらない。しかし無限に整列操作が行われていてもその整列された無限集合の隣り合う2つの実数は異なる実数である。ところが、実数の性質から相異なる2つの実数の間にはその2つの実数と異なる実数が存在する。つまり、「帰属関係の定義された対象のあつまり」で表現できない a, b, c, ... の部分集合は無限に存在することがわかる。

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

    集合の表現力とラッセルのパラドックス

    集合 a, b, c を集めた集合の集合 A = {a, b, c} を考えてみる。素朴集合論では集合の世界は「帰属関係の定義された対象の集まり」と考えるから、a, b, c の間には帰属関係があると考える。たとえば、a = {}, b = {a}, c = {b} であるとする。この場合の a, b, c の帰属関係を演算表にすると次のようになる。

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

    ところで、A = {a, b, c} の全ての部分集合を集めた A のべき集合 B は、B = {{}, {a}, {b}, {c}, {a, b}, {a, c}, {b, c}, {a, b, c}} である。したがって、A = {a, b, c} に帰属関係を定義することによっては、A において発生可能な集合全てを表現するには圧倒的に表現力が不足してしまうのだ。したがって、集合 A は集合演算に対して閉じていない。たとえば b ∩ c = {a, b} であるが、この集合は上の演算表には現れない。

    集合についての集合演算とは集合の論理であるから、上の例は、集合 A の要素には論理を適用することができないことを意味している。集合 A に論理を適用するためには、その冪集合 B を作り、B の要素のうち A に現れないものは集合ではなくクラスとして取り扱う事によって、集合Aの表現不足を補わなくてはならない。

    例えば上の演算表の対角線部分は、a, b, c が自分自身を要素として含むかどうかを示している。上の演算表では対角線部分は全て0だから、a, b, c は全て自分自身を要素として含まない集合である。従って、この「自分自身を要素として含まない集合」の集合は {a, b, c} であるが、上の演算表では {a, b, c} を表現することはできない。これをクラスとして集合ではない集合として取り扱うのだ。

    「集合とは帰属関係の定義された対象である」という素朴集合論の定義では、このように集合についての表現力が不足している。したがって、素朴集合論の世界に論理を適用することはできないのである。素朴集合論の世界に論理を適用できるようにするためには、その冪集合を考え、素朴集合論の世界に現れない冪集合の要素はクラスとして補う事によって、論理を適用させなければならない。

    この方法なら、「自分自身を要素として含まない集合の集合」は存在しないが、「自分自身を要素として含まない集合のクラス」は存在しそれは {a, b, c} であるということができる。

    素朴集合論に現れるラッセルのパラドックスのような矛盾は、集合の世界を「帰属関係の定義された対象の集まり」と定義することによる本質的な表現力不足が原因だったのだ。

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

    冪集合と論理

    ある集合の部分集合を全て集めたものがその集合の冪集合だ。例えば A = {a, b, c} の全ての部分集合の集合 B は、B = {{}, {a}, {b}, {c}, {a, b}, {a, c}, {b, c}, {a, b, c}} である。

    あたりまえのことだが、この冪集合は集合演算について閉じている。B の任意の2つの要素の和集合は A の部分集合なので和集合の演算は B について閉じている。同様のことが、共通部分や、差集合や、補集合についても言うことができる。

    このように冪集合は集合の演算に親和性が高い。また、同時に冪集合の要素は論理とも整合性がある。論理とは表現を変えた集合演算であるので、集合演算について閉じている冪集合については、常に破綻なく論理を適用することができる。冪集合は集合の考え方と論理との理想的なペアを体現している。

    上の例では有限集合の冪集合について考えたが、無限集合についてもその冪集合は有限集合と同じように論理演算について閉じている。

    したがって、数学のある分野について、それを記述する冪集合を考えることができれば、その数学的対象は論理的に考察できることが保証される。

    ところが、集合の考え方にはもう一つの特徴がある。それは、集合を一つの対象と考えて集合の集合を考えることができるということだ。残念ながら、冪集合には集合の集合は存在しない。

    集合の集合を考えるためには「帰属関係の導入された対象の集まり」を考える必要がある。しかし、これは本質的にラッセルのパラドックスを抱えているので、論理とのすり合わせができない。

    この「帰属関係の導入された対象の集まり」を冪集合に変換することができれば、論理と破綻なく整合性があり、かつ、集合の集合のような高階の集合も扱える集合論を構築できる。.... 筈だ。

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

    集合 論理 クラス

    素朴集合論の世界は「帰属関係が導入された対象の集まり」としてモデル化できる。しかし、このモデルには残念ながら論理は適用できない。ここでいう論理とは、排中律(補集合)を含む集合演算のことである。

    素朴集合のモデルである「帰属関係が導入された対象の集まり」では、帰属関係から、対象にその外延という対象の集まりを定義できるが、対象の集まりの部分集合を全て表現するためには対象の数が足りない。これは対象の集まりが有限のときは自明である。N個の対象に対し、その冪集合の要素は2^N個あるからだ。

    たとえば {a, b, c} という集合の部分集合を全て挙げると次のようになる。

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

    この演算表の各行の数列は、その対象が各列の対象を要素として含んでいるかどうかを表している。たとえば、対象 c では 0 1 0 だから、c は対象 b だけを要素として含んでいる。すなわち c = {b} である。

    {a, b c} の考え得る全ての部分集合は各行の a, b, ..., h という対象で表されている。たとえば {a, b, c} の対象全てを要素とする対象は h である。

    ところが、この演算表の行に現れる対象は {a, b, c} の中には現れないものがある。すなわち、c, d, ..., h は {a, b, c} の中には現れない。素朴集合の世界を「帰属関係を導入された対象の集まり」と捉えると、上の演算表で言えば、{a, b, c} の素朴集合の世界は次のような対称な演算表で表される。これには c, d, ..., h は含まれない。

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

    この場合 a = {}, b = {a}, c = {b} だが、素朴集合の世界を「帰属関係の定義された対象の集まり」で表す対称な演算表はこれに限らない。次のようなものでもいいのだ。

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

    この場合は a = {a, c}, b = {b, c}, c = {a} である。どのような対称な演算表にするかは、どのような集合を扱いたいかによって選択すればいいのだ。

    ただ、対称な演算表は {a, b, c} の全ての部分集合を表す事ができないので、この演算表では集合演算を定義できない。たとえば上の演算表で言えば a ∩ b = {c} であるが {c} を表す対象はこの演算表には存在しない。

    しかし {a, b, c} に加えて d, e, .., h という対象を加えると {a, b, c} の全ての部分集合について集合演算を定義することができる。上の演算では a ∩ b は存在しなかったが、拡張された対象では a ∩ b = e となる。ただし e は {a, b, c} には含まれないので e を集合と呼ぶわけにはいかない。e は集合ではないが集合に準じるものなのでクラスと呼ばれる。

    論理とは集合演算のことである。しかし集合の世界を「帰属関係の導入された対象の集まり」と定義すると、その定義の表現力不足から集合演算を適用できない場合がでてくる。この困難は集合に加えてクラスという拡張を行い、集合演算はクラスをふくむ対象の集まりに適用することで論理(集合演算)との整合性をもたせることができる。集合とクラスを含めて広義のクラスという対象と考えると広義のクラスの集まりには論理(集合演算)を定義できるのだ。

    例えば集合の演算表が次のような場合、

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

    自分を要素として含まない集合の集合は 0, 0, 1 であってこの対照な演算表による集合の世界には現れないがクラスの世界では e = {c} として表現できる。

    素朴集合論の世界を「帰属関係の導入された対象の集まり」として定義すると、それに論理(集合演算)を適用するためには、それをクラスの世界に拡張する必要があるのだ。

    ここで述べたのは有限集合についての議論だったが、無限集合についても基本的には成り立ちそうなのは、無限の対称な演算表についても対角線論法によってラッセルのパラドックスが発生することからも分かる。

    素朴集合論の最大の困難はその世界に論理が適用できないということだった。しかし素朴集合論の世界を広義のクラスに拡張すればそこには論理(集合演算)が適用できることが分かる。

    [PR]
    # by tnomura9 | 2017-07-04 06:25 | ラッセルのパラドックス | Comments(0)

    実数と自然数の冪集合

    素朴集合論の世界を「帰属関係の定義された対照の集まり」と考えると、不動点定理からラッセルのパラドックスが発生することを前回の記事で述べた。したがって、このモデルでは対象の全ての帰属関係を表現できないので、集合の演算を定義できない。集合の演算が定義できない集合が発生してしまうからだ。

    しかしながら、「帰属関係の定義された対象の集まり」というモデルは、集合の集合のようなものもうまく表現できるので捨てがたいものがある。また、自分自身を要素として含む集合や、自分自身を要素として含まない集合のようなものの対角線部分の値として表現できる。なんとかこれに集合の演算を導入できないものだろうかと考えてみた。

    たとえば、集合 {a, b, c} の全ての部分集合を集めると次のようになる。

    ** a b c
    0 0 0 0
    1 1 0 0
    2 0 1 0
    3 1 1 0
    4 0 0 1
    5 1 0 1
    6 0 1 1
    7 1 1 1

    各行の 0 1 0 などの数列はそれぞれ {a, b, c} の部分集合をあらわしている。たとえば 0 1 0 は対象 b だけが含まれるので {b} である。また、6行目の 0 1 1 は対象 b, c が含まれるので {b, c} である。これらの部分集合を対象 a, b, c の外延として考えると次のような対照な演算表を作ることができる。

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

    ただし、{a, b, c} の部分集合は8個あるのに、この演算表ではそのうちの3個しか a, b, c という対照の外延として表現できないのでこの演算表では全ての {a, b, c} の部分集合を表すことはできない。したがって、この演算表の対角線部分を反転させた、0 0 1 すなわち {c} はこの演算表にはどうしても現れない。対角線部分で a, b, c のどの外延とも一致しないからだ。また、この集合はあきらかに「自分自身を要素として含まない集合の集合」である。

    ここで、上の演算表とは異なるつぎのような演算表も考えてみる。

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

    この場合は対角線を反転させた部分集合は 1 0 0 すなわち {a} である。これは、この演算表における「自分自身を要素として含まない集合の集合」であるが、先程の演算表の {c} とは異なっている。つまり、「自分自身を要素として含まない集合の集合」とは {a, b, c} の特定の部分集合ではなく、演算表の内容によって変化する。「自分自身を要素として含まない集合の集合」という定義は演算表に依存し、特定の集合を定義するものではないのだ。このようなモデルに集合演算が定義できないのは明らかだ。

    ところで、最初に挙げた 3 列 8 行の演算表を眺めてみよう。演算表の縦の自然数 0 .. 7 は {a, b, c} の部分集合と全単射で対応しているのは明らかだ。したがって、{a, b, c} の集合演算は {0, 1, .. , 7} の中で完全に定義できる。例えば {a, b} ∩ {b, c} = {b} は 3 ∩ 6 = 2 と表現できる。

    このように、{a, b, c} の部分集合を a, b, c で表すことはその一部分しか表現できないが、{a, b, c} の部分集合を 0 .. 7 に全単射で対応付けることによってその集合演算を過不足なく表現することができる。

    同じようなことが自然数の部分集合についてもできないだろうか。

    たとえば自然数 1, 2, ... に対してその自然数が要素として含まれていれば 1 含まれていなければ 0 となるような無限数列 0 1 0 1 1 ... のようなものを考えてみる。そうしてこれを2進数の小数に対応づけてみる。すると 0 1 0 1 1 ... は 0.01011 ... のような無限少数に対応する。この方法をつかうと自然数の部分集合はこの無限小数の一つと全単射で対応することが分かる。この無限小数の小数点下を調べれば、自然数の部分集合にどの自然数が含まれているかを知ることができるし、自然数の部分集合が異なっていれば、それに対応する無限少数も異なるからである。

    つまり、自然数の部分集合は0以上1未満の全ての実数に全単射で対応していることが分かる。従って自然数と0以上1未満の実数との対照表を作れば、自然数の全ての部分集合の演算を実数の演算として表現することができる。

    それでは、そのような演算表に「自分自身を要素として含まない集合の集合」は表現できるのだろうか。残念ながらこれはできない。演算表の各行は 0以上1未満の数なのでその中には自然数は1つも含まれていないからだ。

    このように、「帰属関係の定義された対象のあつまり」としての対象的な演算表では全ての部分集合を表現できないし、対象の全ての部分集合と実数との対照表を作っても今度は、自分自身を要素として含まない集合などの情報が抜け落ちてしまう。素朴集合論の定義で集合の世界を閉じ込めようとしてもなかなか悩ましい問題がある。

    素朴集合論の世界に論理を導入しようとしても、帰属関係による演算表では全ての部分集合を表現できないし、対象の全ての部分集合を実数に閉じ込めると、論理との整合性は取れるが、今度は「自分自身を要素とする集合の集合」というような情報が抜け落ちてしまう。集合と論理の関係を取り持つのはなかなか難しい。



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

    帰属関係と素朴集合論

    前回の記事は、「集合とは対象の集まりという対象である」という定義から素朴集合論の世界を眺めてみたが、今回はもう一つ別の観点から素朴集合論の世界を眺めてみたい。それは対象と対象の帰属関係という観点から素朴集合の世界を考える方法だ。

    集合の世界の対象の間には帰属関係という二項関係が存在する。a ∈ B は対象 a が集合 B に属するという帰属関係を表している。しかし、素朴集合論の世界では集合も一つの対象として扱われるからこの帰属関係は a ∈ b というような対象と対象の間の二項関係と考えることができる。従って素朴集合の世界は対象と対象の間に帰属関係が存在するような対象の集まりと考えられる。

    対象 a は b に属するか、属さないかのどちらかなので、帰属関係は2変数関数で {0, 1} の2値をとると考えられる。すなわち、∈ :: {a, b, c, ... } x {a, b, c, ... } -> {0, 1} という型の関数である。この2変数関数の値は次のような演算表で計算することができる。記述を簡単にするために対象が {a, b, c} であるような集まりを考える。

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

    このとき帰属関係を表す関数を ψとおくと。ψ(a, a) = 0, ψ(a, b) = 0, ψ(a, c) = 0, ψ(b, a) = 1, ... となる。この表で行の対象が列の対象を含んでいるときに 1, 含んでいないときに 0 であるとすると、a の行の数列 0 0 0 は一つの集合を表す、すなわち a = {} である。また、b = {a} であることも分かる。

    ここで、この行の対象を固定すると g(x) = ψ(a, x) という対象の1変数の関数を考えることができる。このとき、g(a) = ψ(a, a) = 0, g(b) = ψ(a, b) = 0, g(c) = ψ(a, c) = 0 である。すなわち g(x) は集合 a がどの対象を含んでいるかを示しているのでこれを ga(x) と書くことにする。同様に gb(x) = ψ(b, x), gc(x) = ψ(c, x) も考えることができる。ga(x) = ψ(a, x) のとき a は ga(x) のインデックスであるという。ga(x) が集合を表しているとして、a はその集合のラベルになっているからだ。

    さらに対角関数というものも考える ⊿(x) = ψ(x, x) だ。これは上の演算表の対角成分を表すから、⊿(a) = 0, ⊿(b) = 0, ⊿(c) = 0 である。

    最後にこの⊿関数と適当な関数 f(x) を使って関数 h(x) を定義する例えば f(0) = 0, f(1) = 1 を使うことにすると、h(x) = f(⊿(x)) = f(ψ(x,x)) だから、h(a) = f(ψ(a,a)) = f(0) = 0。同様に h(b) = 0, h(c) = 0 になる。このとき、h(x) の振る舞いをみると h(x) = ga(x) になることが分かる。

    同様に j(0) = 1, j(1) = 0 を使って i(x) = j(⊿(x)) と定義すると i(a) = 1, i(b) = 1, i(c) = 1 となって演算表から作った ga(x), gb(x), gc(x) のどれとも一致しない。

    ところで、素朴集合論の世界で対象が全て集合であるものを考える。このとき、全ての対象は他の対象との間の帰属関係があるのでこれを ψ(x, y) とする。ここで f(0) = 1, f(1) = 0 という関数をつかって g0(x) = f(⊿(x)) = f(ψ(x,x)) という関数を定義する。g0 は対象についての1変数関数であるから、インデックスとなる対象 a0 を持っているはずである。すなわち g0(x) = ψ(a0, x) である。このとき次の等式が成立する。

    f(ψ(a0, a0)) = g0(a0) = ψ(a0,a0)

    これは、ψ(a0, a0) が 関数 f の不動点となり、f を関数適用しても値が変化しないことを示している。

    ところが、ψ(a0, a0) は 1 か 0 の値をとるが、f(1) = 0, f(0) = 1 のはずなのでこれは上の結論と矛盾する。なにが行けなかったのかというと、対象の1変数関数に全てインデックスが存在するという仮定が間違っていたのだ。上の具体例でも i(x) と同じ振る舞いをする ga(x), gb(x), gc(x) は存在しない。

    実際集合 {a, b, c} とその冪集合との対応表は次のように対称行列にはならない。

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

    素朴集合論の世界が帰属関係という対称な演算表で表現できる場合、不動点定理は成立しなくてはならない。従って素朴集合論の世界はこのような対称的な演算表では表現できない事がわかる。対象の集合とその冪集合とのボタンの掛け違いは対象の数を無限に増やしたとしても解消できないのだ。

    素朴集合論の世界のモデルを対称な演算表ではなく上のような縦長の表を使って構築したとき、論理との整合性を取っていけるのかどうかは興味のあるところだ。




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

    ラッセルのパラドックスと素朴集合論の世界

    素朴集合論の定義では「集合とは物のあつまりという物である」として集合を一種の物として扱う。そこで、物としての集合を集めて A としてみる。Aの要素である集合はなにかの物の集まりを代表しているが、それは、他でもない A の部分集合である。これが、素朴集合論の世界である。

    有限集合の場合について言えば、N個の物の集合Aがあるとき、その部分集合の数は2^N個ある。したがってA の要素でAの部分集合を代表させようとすると個数が必ず不足するので、Aの部分集合の一部しかAの要素で代表させることはできない。

    例えば {a, b, c} の部分集合は {}, {a}, {b}, {c}, {a, b}, {a, c}, {b, c}, {a, b, c} の8個だ。これらは次のような表に表すこともできる。各行は {a, b, c} の部分集合で、列の 1 と 0 はその列の要素が部分集合に含まれているかどうかを表す。

    ** a b c
    0 0 0 0
    1 1 0 0
    2 0 1 0
    3 0 0 1
    4 1 1 0
    5 1 0 1
    6 0 1 1
    7 1 1 1

    これらの集合を {a, b, c} の要素に対応させると次のような正方行列になる。

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

    a, b, c に対応させる集合はなんでもいいので、

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

    のようなものも考えられる。いずれにせよ {a, b, c} で代表できる部分集合は8個あるうちの、上のような正方行列に収まる3個しかない。{a, b, c} の部分集合を a, b, c で代表させようとしても正方行列の窓から見える3個の部分集合しか扱えないのだ。

    これは物の集合の要素数がどのように大きくなっても変わらない。「集合とは物の集まりという物である」という素朴集合論の集合の定義では、集合を表す「もの」の数をどのように大きくとっても、その冪集合の一部分としか対応させることができないのだ。

    このような状況で、「自分自身を要素として含まない集合の集合」のような自己言及的な定義で集合を定義しようとすると、その集合はうえに述べた正方行列の対応表に載せることができない。対応表の集合をどのように選んでもその集合は対応表の外にしか見つけられないからだ。

    たとえば、対応表が

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

    の場合「自分自身を要素として含まない集合の集合」は対角線部分を反転させた 1 1 0 すなわち {a, b} になるがこれはどの行の集合とも対角線で異なっている。このような集合はどのような場合も正規行列の対照表からははずれることになる。これが対角線論法の本質なのだ。

    集合を物として表現したとき、必然的にその物をふくむ冪集合が発生するが、その量は常に集合の物全体よりは大きいのだ。この関係は集合を1個の「もの」と考える素朴集合論では必ず発生する現象だ。そうして、それは不可解なラッセルのパラドックスが発生する母体になっている。

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