tnomuraのブログ

公理的集合論のモデル

前回素朴集合論の2種類のモデルについて述べたが、ついでに公理的集合論のモデルについて述べてみる。公理的集合論の公理からどんな集合が発生するかということだ。

まず、空集合の公理から {} は集合である。次に、対の公理から {{}, {}} は集合である。また外延性の公理から {{}, {}} = {{}} である。さらに対の公理から、{{{}}, {{}}} は集合である。これに外延性の公理を適用すると、{{{}}} は集合である。したがって、{}, {{}}, {{{}}}, ... は集合である。これで、空集合に玉ねぎの皮をかぶせていったものは全て集合であることが分かる。

対の公理から {{}, {{}}} は集合である。また、{{{}}, {{{}}}} は集合である。さらに対の公理から {{{}, {{}}}, {{{}}, {{{}}}}} は集合である。これに和集合の公理を適用すると、{{}, {{}}, {{{}}}} は集合である。このことから、任意の集合を集めた {{}, {{}}, {{{}}}, ... } は集合であることが分かる。ただし、ここまでの公理の適用で生成される集合は有限集合である。

無限公理から {{}, {{}}, {{}, {{}}}, {{{}}, {{{}}}}, ... } は集合である。すなわち、無限の要素を含む集合が存在する。

これで、無限の要素、任意の有限要素の集合、無限要素の集合が公理から演繹された。

面倒くさくなったのでこれでやめるが、要するに公理的集合論の公理から演繹される集合の世界は {{}, {{}}, {{{}}}} のような玉ねぎの皮だけでできた世界なのだ。玉ねぎの皮だけだけれど公理から外れた集合はひとつもない。また、その中には、無限の要素や、有限要素の集合や、無限集合が多数含まれており、それぞれに勝手に 0, 1, 2, 3, ... などの自然数や、{1, 2, 3} などの集合を割り振って普通の数学の世界を構築することができる。

何が集合かというと、公理から演繹されるものだけが、集合なのである。公理的集合論で厳密化された集合とはこのような集合をいう。現実の数学理論は、この公理的集合論の構造を利用して構築することになる。

素朴集合論では定義できなかった厳密な集合とは、このような玉ねぎの皮のことだったのだ。

素朴集合論のモデル その２

前回の素朴集合論のモデルは、集合も個体もすべて等しく対象として扱い、集合は対象間の所属関係から導くやり方だったが、別のモデルも考えることができる。

領域 D が対象 a0, a1, ... , an, ... の集合であるとする。このとき、領域 D に対し領域 D の部分集合の集合である冪集合 D* を考える。すると、領域 D の要素の部分集合は全て、冪集合 D* の要素として表すことができる。つまり、領域 D の要素の集まりである集合という対象を領域 D の冪集合の要素として表すのである。

前回のモデルでは、集合も個体もすべて領域 D の対象であり、述語 P(x) は等しくそれらの対象に適用された。しかし、今度のモデルでは、領域 D の対象の名前空間は領域 D の要素として存在するが、対象の集合の名前空間は冪集合 D* の要素として表現され、対象と集合の名前空間は別になる。したがって、領域 D の要素に対する述語、すなわち、領域 D の要素に対し０または１を返す関数 P(x) について、内包的定義で集合を定める場合、内包的定義は次のようになる。

{x ∈ D | P(x)}

つまり、述語は領域 D の要素に適用されるが、述語を用いた内包的定義で定義される集合は、冪集合 D* の要素となる。これは、ラッセルの階型理論に似ていると思うが、階形理論を勉強していないのではっきりしたことは分からない。

このような集合の内包的定義の利点は、領域 D の全ての部分集合を内包的定義で定義できるということである。前回述べたような、領域 D の対象で集合も個体も等しく表現するような方法では、領域 D の述語の中にその内法的定義による D の部分集合が D の対象として表現できないものが存在したが、今回のモデルの内包的定義ではそのようなことはない。

領域 D の述語は全て冪集合 D* の要素と対応するため、述語 P(x) による内包的定義は冪集合 D* の要素と同型である。したがって、述語 P(x) についての論理演算、たとえば P(x) ∧ Q(x) や ¬ P(x) のようなものは全て冪集合 D* の集合演算に対応する。また、領域の要素とその集合の名前空間が違うので R(x) = ¬ (x ∈ x) のような自己言及する述語は発生せず、ラッセルのパラドックスは発生しない。

領域 D の集合の集合のようなものを考えたいときは冪集合 D* の冪集合 D** を考えることで、その要素で集合の集合を表すことができる。またDの要素とDの集合のペアについて考えたいときは D と D* の直積集合 D × D* を新しい領域として考え、その冪集合は直積集合の要素の集合を表すことができる。さらに、D と D* を等しく対象として考えたいときは D と D* の和集合を領域として考えればよい。

このやり方は Haskell のような型付づけられた関数型のプログラミング言語に似ている。このモデルでどのような数学理論が構築できるかはわからないが、パラドックスが発生しない（ようにみえる）点で魅力的なモデルだ。ただ、構成が均一ではなく複雑になるのが難点だが。

素朴集合論のモデル

いままでのこのブログでの、ラッセルのパラドックスについての議論のまとめとして、素朴集合論の世界を表すモデルを作ってみた。それは次のようになる。

対象 a0, a1, ... , an, ... の集まりを領域 D とする。この対象は個体も集合も含んでいる。領域 D の対象の間に所属関係 ∋ を導入する。すなわち、領域 D の任意の対象の a, b の間に a ∋ b の関係があり、このとき、集合 a は b を要素として含んでいる。この場合個体も空集合も他の要素を要素として含まないが、空集合は自分自身を含めてほかの全ての集合の要素となるので、空集合と個体を区別することができる。すなわち、空集合は自分自身のみを要素とする集合だ。したがって、外延公理で集合の同等性を判別するときも、空集合は自分自身のみを要素として含むので、個体と区別できる。

ここでこの所属関係を表す評価関数 ψ(x, y) を考える。 ψ :: D × D -> {0, 1} 型の関数で、a ∈ b のとき ψ(a, b) = 1, ¬( a ∈ b) のとき ψ(a, b) = 0 であるとする。あきらかに、ψ(x, y) は領域 D の全ての対象間の所属関係を記述することができる。

このとき、ψ の第１引数を固定して得られる１変数関数 P(x) = ψ(a, x) は領域 D の全ての対象について 0 または 1 の値を返すので、領域 D における述語である。また、このことから P(x) = 1 となる対象を集めた集合は対象 a の外延と一致する。すなわち、

a = {x | P(x) } = {x | ψ(a, x)}である。

このように、領域 D には、所属関係、集合、空集合、述語を導入できる。

しかし、残念ながら領域 D の対象は領域 D の全ての述語に対応することはできない。ここでいう述語とは領域 D の任意の要素に対し０ または 1 を返す関数である。つまり、領域 D の対象について 0 または 1 を返す関数 P(x) のうち、内包的定義 {x | P(x) = 1} で表す対象の集まりを外延とする領域 D 内の対象を見つけられないものがある。

たとえば、ラッセルの述語 R(x) はその例である。R(x) を次のように定義する。

R(x) = ¬ ψ(x,x)

これは領域 D の任意の対象について 0 または 1 の値を返すから領域 D の述語である。したがって、R = {x | R(x)} は、領域 D の部分集合を特定することができる。それにもかかわらず、R と外延が一致する領域 D の対象 r は存在しない。なぜなら、そのような r が存在したとすると、

r = {x | ψ(r, x)}

となるはずなので、

ψ(r, x) = R(x) = ¬ ψ(x, x)

であるが、x = r のとき、

ψ(r, r) = R(r) = ¬ ψ(r, r)

となって矛盾するからだ。すなわち、述語 R(x) で定められる領域 D の対象の集まりは特定できるにもかかわらず、その集まりを外延とする領域 D の対象を見つけることができない。すなわち、領域 D の対象だけでは、領域 D の全ての部分集合を表すことはできないのだ。したがって、素朴集合論は矛盾するという表現よりも、素朴集合論は不完全であると表現するほうが適切であるということがわかる。

なにかの理論を素朴集合論で構築したい場合、このような領域 D の不完全性を頭に入れて論理を組み立てていけば、素朴集合論による直感的なイメージを活したまま、実効性のある理論を構成していくことができる。

実際、数学理論を学習する際に公理的集合論にまで遡ることはない。実際には素朴集合論が用いられているのに、素朴集合論には矛盾があると説明されるのは、学習者にとっては納得できない印象を残してしまう。領域 D のような素朴集合論のモデルがあれば、どのような集合のどのような述語が危険で、どのような述語は安全かがはっきりするので便利ではないだろうか。

クラスについて

上で述べた述語 R(x) のように領域 D の対象の外延としては表せない領域 D の部分集合はクラスである。述語 P(x) により内包的に定義される領域 D の部分集合のうち領域 D の対象の外延として表現できる集合は「集合」であり、領域 D の対象の外延として表現できない領域 D の部分集合を「クラス」とすることにすれば、領域 D の部分集合は全て集合またはクラスとして述語で表現することができる。この場合は領域 D の述語（領域 D の要素への適用に対し０または１を返す関数）全てに対し、領域 D の部分集合を集合またはクラスとして定めることができる。

領域 D の部分集合が集合になるかクラスになるかは、評価関数 ψ(x, y) の性質による。ψ(x, y) は扱おうとしている理論によって異なってくるので、領域 D の部分集合が集合かクラスかは、その理論によって変わってくる。例えば、ψ(x, y) を定める対象間の所属関係 ∋ にはとくに制限はないので、a ∋ a のような自分自身を要素として含むこともできる。また、集合は自分自身を要素としては含まないと規定される対象間の所属関係を定めることもできる。当然、前者と後者の評価関数 ψ(x, y) は異なっており、何が集合で、何がクラスであるかも違ってくる。

集合という対象を創り出す集合の定義

集合とは対象の集まり（という対象）であるという素朴集合論の集合の定義は、対象を集めることによってそれまでになかった集合と言う対象を創り出す。外延的定義であれ、内包的定義であれ、この定義によって、対象の集まりである集合 {a1, a2, a3, ..., an} という対象が出現する。

例えば a1, a2, ... , an という対象があったとする。そのうち a2, a3, を取って A という集合を作ったとする。

A = {a1, a2}

このとき、今までには a1, a2, ... , an という対象しかなかったのに、その対象の中に {a2, a3} という対象が新たに仲間入りすることになる。すなわち、対象の世界が a1, a2, ... , an から a1, a2, ... , an, {a2, a3} に変化する。新しい対象の発生は、集合が定義されるたびにおきるので、集合の定義に伴って、対象の世界のメンバーはどんどん増殖していくことになる。

集合の定義が外延的に行われる限り、ラッセルのパラドックスのような不都合は生じない。集合の定義は完全に対象に依存しているからだ。

問題は、集合の定義が内包的に行われる場合だ。述語 P(x) は対象に関数適用することによって真または偽の値をとる関数である。したがって、P(x) が真の値を取る対象のみを集めるとそれは集合を定義するのは当然と思われる。a1, a2, ... , an にそれぞれ P(x) を適用することで、P(a2) と P(a3) のみが真だったとしよう。そこで、外延的に a2 と a3 からなる集合

{x | P(x)} = {a2, a3}

を作る。当然対象の世界は a1, a2, ... , an と {a2, a3} という対象から構成されることになる。しかし、ここに問題が発生する。

なぜなら、内包的定義は外延的定義と異なって、集合を定義するのに、対象の世界の全ての対象に述語 P(x) を適用する必要があるからだ。つまり、対象の世界の対象が a1, a2, ..., a3, {a2,a3} であるからには、P({a2, a3}) の値も検討しない限り内包的定義で、集合を定めることができない。

P({a2, a3}) が偽のときは問題はなさそうだこの場合は {x | P(x)} = {a2, a3} が確定する。

問題は P({a2, a3}) が真の時だ。この場合は当然、

{x | P(x)} = {a2, a3, {a2,a3}}

と考えなくてはならない。ところで {a2, a3, {a2, a3}} は {a2, a3} とも異なる新しい対象である。したがって対象の世界は a1, a2, ... , an, {a2, a3}, {a2, a3, {a2, a3}} と対象のメンバーが増えることになるそこで、今度は P({a2, a3, {a2, a3}}) についても検討しなくてはならない ... 。

この操作は P(x) が偽になるときに終了するが、ずっと真であるとこの手続きは無限に終了せず、述語 P(x) の内包的定義で定義できる集合は確定できないことになる。

ラッセルの集合の述語 R(x) は「自分自身を要素として含まない集合」である。ここで、自分自身を要素として含まない集合が b1, b2 しかなかったとする。すると、

{x | R(x)} = {b1, b2} = R1

と考えられるが、まだ R(x) が適用されていない対象 R1 = {b1, b2} が存在する。R1 は b1, b2 とは異なっているように見えるので R1 は R1 の要素ではない。この場合 R(R1) は真である。したがって、

{x | R(x)} = {b1, b2, {b1,b2}}

としなければならない。上の例と同じような理由でこの操作は無限に終わらないから R(x) による内包的定義では集合を確定することができない。

それでは R1 が R1 の要素である場合は考えられないだろうか。この場合はたとえば b1 = R1 の場合が考えられる。すなわち、

R1 = {R1, b2}

である。この場合は R(R1) が偽となるから、集合は確定する。すなわち、

{x | R(x)} = R1 = {R1, b2}

である。しかし、この場合は R1 は自分自身を要素として含むため、{x | R(x)} の要素としては不適格になるので

{x | R(x)} = {R1, b2}

はありえない。すなわち、どの段階でも R1 が自分自身の要素となることはありえない。したがって、{x | R(x)} は自分自身を要素として含まない集合を次々に創り出して取り込んでいくが、永久に集合としては確定できない対象の集まりとなる。

述語に自己言及を許可すると、内包的定義では集合を定義できないことがあることが分かる。これを避けて内包的定義で必ず集合を定義するためには、内包的定義を次のように定義する必要がある。

{x ∈ D | P(x)}

これは領域 D の要素について、述語P(x) で集合を定義することができることを示している。この内包的定義で定義できる集合は、領域 D の部分集合のみである。すなわち、領域 D のべき集合 D* を考えるとき、内包的定義で定義できる集合は必ず D* の要素となる。内包的定義が領域 D にも D* にも含まれない新しい集合を定義することはない。これは、公理的集合論の分出公理と同じものであるが、非常に安全な内包的定義だ。また、P(x) についての全ての論理演算の真理集合は D* で完結している。つまり、論理的にも安全な述語を提供することになる。

領域 D とDのべき集合 D* および内包的定義 {x ∈ D | P(x)} は様々な数学的対象に素朴集合論を適用するときの強力な武器となるような気がする。

ところで、内包的定義で述語の自己言及を許すと、上で述べたような無限の再帰が発生してしまう。しかし、このような述語の自己言及は全く捨て去るべきものではなく、プログラムにループや、関数の再帰的定義を導入するための必須の仕組みでもある。述語の自己言及を積極的に活用する方法も考えることができるのではないだろうか。

集合の内包

集合を定義するのに、要素となる対象を列挙する方法が外延である。{a1, a2, ... , an } のように要素となる対象を列挙する。これに対し述語 P(x) を充足する対象を全て集めるという定義方法が内包で、{x | P(x)} のように記述する。述語 P(x) は任意の対象について真または偽の値をとるので内包によって集合が定まるのは当然のように思われる。そこで、これが集合 P* を定めるとすると、

P* = {x | P(x)}

となる。これは次の論理式と同値である。

x ∈ P* ⇔ P(x)

ここで、述語 R(x) をつぎのように定義する。

R(x) = ￢ (x ∈ x)

するとこの述語で内包的に定義される集合 R* は次のようになる。

R* = {x | R(x)} = {x | ￢(x ∈ x)}

これは次の論理式と同値である。

x ∈ R* ⇔ ￢(x ∈ x)

ところで R* 自身も対象の一つなので R(R*) も真か偽の値を持つはずである。そこで上の x に R* を代入すると、

R* ∈ R* ⇔ ￢(R* ∈ R*)

となって矛盾してしまう。つまり、内包で集合を定義しようとすると対象 R* に対し R(R*) が真であるしても偽であるとしても矛盾する述語 R が発生してしまうのだ。

集合とは対象の集まりという対象であるという素朴集合の定義と、述語 P(x) を対象 a に適用した命題 P(a) は必ず真または偽のどちらかの値を取るという排中律という単純な条件からパラドックス（矛盾）が発生してしまうので深刻だ。

これは、対象を集めた集合という対象の在り方から発生しているのだ。集合の外延は対象を集めてできる。対象 a1, a2, ... , an を集めて A という集合が作られたとする。当然、外延の中に A は含まれていない。なぜなら、最初にあったのは対象の集まりのみで、それを集めて集合 A という概念が作られたからだ。この概念もまた対象であると考えると、概念の集合のようなものも考えられるので非常に便利だ。集合 A という概念としての対象 A は A の外延 {a1, a2, ... , an} の中には含まれないが、集合 A の外延的定義の性質から考えると当然だ。

ところが集合 A を内包的に定義するときは様子が少々変わってくる。集合 A を述語 P(x) によって内包的に定義する場合も基本的には外延と同じだ。対称 a1, a2, ... , an, ... に述語 P(x) を関数適用してその値で集合 A の外延を作り上げていくからだ。アルゴリズム的には外延の場合と同じと考えてよい。そうして、全ての対象について P(x) の適用を行った後集合 A が出来上がる。すなわち、

A = {x | P(x)}

である。ところが、A は述語 P(x) を対象に適用したときは対象として存在しなかったが、A を定義したとたんに A という対象が発生してしまう。A を外延的に定義したときはそれで問題はなかったが、内包的定義を行うときは、述語 P(x) は A という対象にも適用されなければならない。なぜなら、すべての対象に対して P(x) が適用されることで内包的定義が完了するからだ。すなわち P(A) という自己言及の真偽が問題にされることになる。

対象の集まりは集合という対象であるとする素朴集合論の集合の定義は、このように生成的な定義になる。対象を集めることで対象にはなかった新しい対象を生成してしまうからだ。

全ての対象について「自分自身を要素として含まない集合」を集めて A という集合を作った時、A は自分自身を要素としては含んでいない、なぜなら、対称の中に A という対象はなかったからだ。しかし、それ故に A は自分自身を要素として含まない集合になってしまう。また、この A という対象を A の外延と合わせて A' という対象を作ったとしても、A' はやはり、自分自身を要素としては含んでいないが、それ故に自分自身を要素として含まない集合になってしまう。

このような集合 A の要素は「自分自身を要素として含まない集合」であるが、A自身は A の要素としては含まれていない。しかしそれ故に自らも「自分自身を要素として含まない集合だ」。大切なのは集合 A は自分自身を要素として含まないが、自分自身が自身の述語を充足するという構造で安定して存在できるということだ。しかし、どのような場合も A は自身の要素ではないので、「自分自身を要素として含まない集合全ての集合」を考えるとそういう集合自身は自身に含まれるとも含まれないとも言えないというラッセルのパラドックスになってしまう。

このような自己言及による困難は、集合とは対象の集まりという対象であるという素朴集合論の定義の意図をはなれて、複雑な様相を呈してくる。実は外延的に定義された場合も同じ困難は生じるのだ。対象を外延として集めて集合を作ると同時に新しい対象であるその集合が出現するからだ。これは、ひとえに素朴集合論の集合の定義が「生成的な」定義であるためである。

集合の内包的定義が新しい対象を生成しない方法は、内包的定義によって常に「既存の集合」しか現れないようにすることだ。つまり、集合の内包的な定義を次のようにすることだ。

{x ∈ D | P(x)}

このようにして定義された集合は、集合それ自身という新しい対象は作らない。この定義で作られた集合は全て領域 D の部分集合だからだ。対象の集まりは集合という対象であるという素朴集合論の定義と、このような新しい対象を作り出さない内包的定義を武器にいろいろな数学の理論を記述することができるかどうかを調べるのは管理人の能力を超えているが、おそらく可能なのではないかという感じがする。

具体的には、次のような道具立てが利用できるのではないだろうか。領域 D という集合、D のべき集合 D*、D* の要素を定める内包的定義 {x ∈ D | P(x)}、P(x) の論理演算の場としての D*。このシンプルな道具で、いろいろな数学理論が記述できることを示すことができれば、面白いと思う。（多分、管理人にはできない。）

実数は自然数よりどれくらい多いか

自然数全てと０から１までの２進数を対応付けた対照表を考えると、たとえば次のようになる。

1 : 0.100101...

2 : 0.001010...

3 : 0.010010...

4 : 0.000100...

5 : 0.110101...

6 : 0.001000...

.....

この対照表の小数点下の対角線部分を取り出すと次のようになる。

0.100100...

これを反転させてできる次の実数は上の対照表には現れない。

0.011011...

これがカントールの対角線論法である。しかし、この論法では自然数に対応付けられない実数が一つしか示されていない。他にはないのだろうか。そこで上の対照表の１と２を入れ替えてみる。

2 : 0.001010...

1 : 0.100101...

3 : 0.010010...

4 : 0.000100...

5 : 0.110101...

6 : 0.001000...

.....

こうしてできた新しい対照表は自然数全てに対応付けられた実数の対照表である。順番を入れ替えただけだから上の対照表と内容は変わらない。このとき、新しい対照表の対角線部分を取り出してみる。

0.000100...

これは最初の対照表の対角線部分と異なっている。これを反転させると

0.111011...

になるが、これもまた自然数と実数の対照表には現れていない数だ。したがって、この数は対照表に現れない２番めの実数になる。ところで、行を交換するときどの２組を選ぶかという組み合わせは ∞C2 個あることになる。行を交換したとき対角線部分の２箇所が変更になるからそれらが同じになる確率が1/4だったとしてもまだ、∞C2*3/4 個の対照表に現れない実数が存在することになる。したがって、自然数に対応付けられていない実数の数は無限にあることがわかる。

ただし、これは自然数と実数の対応付けが冒頭の対照表で終わっていると考えた場合である。その後に上の方法で見つけられた対応付けられていない実数は、ヒルベルトの無限ホテルの方法で新たに自然数との全単射に繰り込むことができる。部屋数が無限にあるホテルが満室であったとき、新しい客が来た場合、元の客を一つずつ後ろの番号の部屋へ移動してもらえば１号室を開けて新しい客を受けつけることができる。したがって、元々の対照表に含まれない実数を見つけることができたとしても、それを対照表の先頭に置いて新しい対照表を作ることができる。

しかしながら、この段階でも新しい対照表を作成し対応付が終わったと宣言した途端に、それに含まれない無限の実数が存在していることがわかる。まるで、蜃気楼を追いかけても常に遠くに蜃気楼があるようなものだ。

ただし、対応付けを変えて作った新しい対照表は、もとの対照表とは対応付けのルールが異なる。もとの対照表では、自然数 n と実数 a が a = f(n) という全単射の関数で対応付けられていたとすると、新しい対照表では、その関数では全単射が作れず新しい f1(x) という関数が必要になる。このとき自然数 N から実数への f(x) の像を f(N) とすると、

f(N) ⊂ f1(N)

である。対角線論法で新しい実数を発見するたびに対照表を改定していくと次のような無限の包含関係が発生する。

f(N) ⊂ f1(N) ⊂ f2(N) ⊂ ....

f(x) も f1(x) も全単射の関数のはずなのに自然数の像 f(N) の値域が異なっているのは変な感じだ。

このように、自然数の全単射による像は実数の集合のなかにどんどん広げていくことができる。しかし、その場合でも常にその像に含まれない実数の要素は無限に発見できる。

おかしな話だが、その原因は f(x) という全単射の関数にあるような気がする。集合 A と集合 B の要素が全単射の関数 f(x) によって１対１に対応付けられているとする。このとき f(x) が全単射であることは、集合 B の全ての要素を検査してそれが１対１の対応関係であるということを検証しなければならない。集合 B が有限集合のときは B の要素を全て数え上げることができるのでそれは可能だが、集合 B が無限集合のときは問題が生じる。無限集合 B の要素を数え上げきることができないからだ。

そこで、集合 B が無限集合の場合は f(x) が全単射であるかどうかを別の方法で調べることになる。無作為に取り出した集合 B のどの要素についてもその原像である集合 A の要素が唯ひとつ見つかれば f(x) は全単射であると考えることにするのだ。

この新しい f(x) の評価方法は集合 B が有限集合の場合も働くので、集合 B の要素を全て調べ上げる方法の拡張版だとも言える。しかし、B が無限集合のときに、任意にBの要素 b を取り出しその原像の a ∈ A がただひとつであることが確認できたとしよう。だからといって B の要素全てについて f(x) が全単射であると無邪気に言ってもいいのだろうか。任意の B の要素を検証することは無限に続けることができる。しかし、その検証はどの段階でも、検証していない B の要素が存在している。無限集合の場合は全単射の全という部分については、注意が必要なのである。

関数 f(x) が全単射であるというのは、集合が有限集合のときのみに検証できることではないのだろうか。言い換えると f(x) の全単射性は有限集合同士の写像でしか検証できないということだ。集合が無限集合の場合は、有限集合に対し全単射である関数 f(x) を無限集合に流用しているだけなのだ。有限集合に置ける全単射の意味が無限集合にも適用できるというのは、一種の幻想なのである。

無限集合に適用されている全単射の関数は、あくまでも有限集合では全単射であるという意味であると考えたほうが良いのではないだろうか。満室の無限ホテルの場合も、新しい客が来たときには、１号室の客に一旦出てもらい新しい客を入れる。次に２号室の客に出てもらい１号室の客を２号室に入れる... というアルゴリズムを無限に行うことになる。しかし、この作業が完了することを保証するものは何もないのだ。

これは数列の極限値を求める微分積分での議論に似ている。⊿x を順に０に近づけていくような数列を考えると(f(x+⊿x) - f(x))/ ⊿x はある一定値 a にどんどん近づいていく。しかし、⊿x が０になるという議論はありえない。同じように、無限ホテルでも無限号室の議論はできないのだ。微分積分の場合は ⊿x の議論は⊿x が０に近づく仮定の断面の１時点について論理が適用される。無限ホテルの場合も、無限号室へ客の入れ替えが行われる過程の断面での議論の推論によって無限集合の性質を述べている。

自然数と偶数が全単射するという実無限の議論についても、その対応関係を無限大まで追いかけることはできない。f(x) = 2x という有限集合の関数を用いて無限の過程を推定することによって自然数と偶数の全単射があると結論づけている。しかし、そこには有限集合ほどの明白さはない。そのアルゴリズムが完遂されることは絶対にないからだ。

このことは、自然数と実数の対応を示す対照表についても言うことができる。対角線成分の無限遠の値を知ることは不可能なのである。しかし、有限のわかる範囲内では、対角線成分を反転させてできる実数は対照表に現れることはできないので、無限遠でも同じ事情であると推測できるのだ。

ラッセルの集合でも同じことが言える。有限個の「自分自身を要素として含まない集合」を集めた集合は、自分自身を要素としては含まないが「自分自身を要素として含まない集合」という述語を満たしてしまう。この事情は、無限個の「自分自身を要素として含まない集合」を集めた集合にも適用されるだろうと推測できる。それゆえ、そのようなラッセルの集合は「自分自身を要素としては含まない」が「自分自身を要素として含まない集合」という述語を満たしてしまうのだ。つまり、述語を充足するが、述語を充足する集合の要素ではないという事態が発生し。述語を充足する要素の集合は「集合」であるという、内包公理は否定される。

このように無限集合の振る舞いを直接的に調べる方法はない。有限集合の性質の拡張として推論することができるだけである。したがって、無限集合の振る舞いについて考察するときは、必ずその有限集合におけるアルゴリズムの等価物として考えることが必要になってくるのだ。

論理と集合

論理と集合は同型であると考えるのは自然な発想だ。素朴集合論の述語を充足する要素は集合を定義するという内包公理はそれを示している。しかし、それはラッセルのパラドックスによって否定的に証明された。ラッセルのパラドックスの意義は、排中律を満たす述語であっても、集合を定義できないことがあることを証明したことだ。

このように、論理学を集合と同型とみなすことはできないのだ。

公理的集合論は、論理学の中に集合を取り込もうとする試みで、コンピュータのビット操作に比すことができる集合だけの構造を作り上げることによって、論理と集合に整合性を持たせようとしたと思われる。これはある程度成功した。全ての数学的対象が、公理的集合論の世界の中に構築できるからだ。

これは、論理を基礎に数学を組み立てたいという意図のもとに工夫が行われたからだ。

しかし、公理的集合論ではなぜ、論理学と集合が同型とみなすことができないのかという問いには答えてくれない。ものの集まりを集合とするというシンプルな定義が、どうして論理となじまないのかの説明がないのである。

例えば「犬の集合」について考えてみよう。「ｘは犬である」という述語を満たす集合は想像することができる。しかし、この集合が論理と整合性を保つためには「xは犬ではない」という述語も集合を定めなくてはならない。そうして「犬でないもの全てを集めた集合」を考えると、この集合自体は何に含まれるのかという疑問が起きる。

これは、やはり「ｘは犬ではない」という述語を充足するのでそれ自身に属すると考えてもいいが、述語によって要素を集めたものが集合になるという過程を考えたときに集合が出来上がる前に「犬でないものの集合」がそれ自身の要素であったと考えるのは不合理だ。犬ではないものを集めた結果として「ｘは犬ではない」という述語を満たす集合が出現したと考えるべきなのである。すなわち、「ｘは犬ではない」という述語は排中律を満たしているにもかかわらず集合を定義できない。全ての犬でないものの集合を作ったとしても、その要素として含まれないその集合自身が存在するからだ。

どこがいけないのか。それは論理の適用法が誤っているからだ。論理は集合の部分集合に適用されたとき、真理集合としての部分集合と論理の述語の論理演算は同型になる。それはベン図で全体集合のないベン図を描いたとき補集合が表示できないが、全体集合を考えることで補集合が表示できることからもわかる。論理は集合の部分集合に適用すべき構造だということだ。そのやり方なら論理と集合は同型だし矛盾も生じない。ラッセルのパラドックスは全ての根幹を論理に求めたところに問題があったのではないだろうか。

公理的集合論とCPU

集合をものの集まりと定義する素朴集合論ではラッセルのパラドックスにより矛盾がみつかったので、公理的集合論で矛盾しない集合論を組み立てたと言われているが、公理的集合論の公理を見ても、ものの集まりがどこにも出てこないように見える。

公理的集合論の公理に従って、いろいろな集合を演繹してみても、見えてくるのは空集合を起点として演繹されていく集合ばかりの世界だ。このようなものがどうして数学の基礎になるのだろうかと不満が募る。

しかし、これは公理的集合論が論理を元に数学を組み立てようとしている試みだということに気づいてから納得できるような気がしてきた。記号論理学では論理は単なる記号とその記号の変形規則だ。この記号の変形規則である論理で集合を構築しようとしたのだ。一旦記号論理で集合が記述できれば、その集合を使って他の数学的対照が記述できるようになる。これは、コンピュータのCPUに似ている。

コンピュータのCPUはメモリーと論理回路から構成されているが、ビット列を入力し処理されたビット列を出力することしかしていない。このビット列に意味を持たせてインタネットにアクセスしたり、画像を表示したりするのはプログラミングの仕事だ。

公理的集合論がやっているのはこのCPUと同じ仕事なのだ。空集合を起点として集合だけの世界を構築しているが、その世界にものの集まりとしての集合や、自然数や、実数などを作り込んでいける。したがって、公理的集合論から {} や {{}, {{}}} など波括弧だけの奇妙な集合しか見えてこなくても構わないのだ。CPUはビット列しか操作できないが実世界のシミュレーションができるように、公理的集合論の奇妙なカッコだらけの世界にも数学が構築できるのである。

このことに思いが至ったら、公理的集合論の公理に対する抵抗感が随分減った。また、他の数学が公理的集合論に全く言及しないでも論理を組み立てていける理由もわかった。それらは、公理的集合論を基盤とした高レベルのプログラム言語だからだ。Haskell でプログラムを組み立てるとき、機械語のプログラムは全く気にしなくてもプログラムできる。

ただ、このような便利なCPUだが、いつもうまく働くわけではない。無限ループを作るプログラムに対しては無力なのだ。同じように公理的集合論であってもゲーデル文にたいしてはうまく働かない。無限ループのプログラムをプログラム言語で書けるのと同じように、公理的集合論においてもゲーデル文が論理的に演繹できるにもかかわらず不都合が起きてしまう。

公理的集合論とCPUのアナロジーが適切かどうかはわからないが、こう考えると自分の無矛盾性を自分自身の体系では証明できないというゲーデルの不完全性定理も、人間は真理に到達できないことが証明されたなどと深刻に考える必要はなく、CPUで無限ループは処理できないのと同じこどだとちょっと安心できるのではないだろうか。

嘘つきのパラドックスと対角線論法

自己言及のパラドックスの一つに嘘つきのパラドックスがある。

「私は嘘つきだ」とある人が言ったとすると、その人は嘘つきとも本当つきとも言えないというパラドックスだ。ここで、嘘つきは必ずうそを言うとし、本当つきは必ず本当のことを言うとする。このとき、この人が嘘つきであれば「私は嘘つきだ」という言明は嘘であるから、この人は本当つきだということになって矛盾する。また、このひとが本当つきだったとすると、「私は嘘つきだ」という言明は本当なので、この人は嘘つきだということになってしまいやはり矛盾する。結局この人は嘘つきとも本当つきとも言えないということになりパラドックスであるというものだ。

じつは、この嘘つきのパラドックスにも、対角線論法が潜んでいるのだ。

いま、本当つき h と嘘つき l しかいない世界を考える。その世界（集合）を A とおくと A = {h, l} である。このとき x が y についてどう評価するかという関数を Φ(x, y) :: A × A -> {1, 0} で表す。この時 Φ(x, y) = 1 なら y は x のことを本当つきだと言明し、Φ(x, y) = 0 なら y は x のことを嘘つきだと言明するとする。そうすると Φ(x, x) :: A -> {0, 1} は x が自分について本当つきか、嘘つきかを言明することを表す。

この関数 Φ(x, y) については次のように変数と値の対照表を作ることができる。

.. h l (x)

h 1 0

l 0 1

(y)

この対照表では 列の h と l は Φ(x, y) の x に与える値を表し h は本当つき、l は嘘つきである。また、行の h と l は Φ(x, y) の y に与える値を表す。この表では Φ(l, h) = 0 であるが (h 行 l 列）本当つき h は 嘘つき l が嘘つきであると言明していることを示している。この時 y を h に固定した Φ(x, h) は集合 A = {h, l} の述語となり、本当つきが集合 A の要素についてどのように言明するかを表している。

こういう正方行列の対照表には対角線論法を使うことができる。上の対照表の対角線部分は Φ(h, h) = 1, Φ(l, l) = 1 であり、本当つきは自分のことを本当つきだというし、嘘つきも自分のことは本当つきだという。ここで、対角線部分の Φ(x,x) の値を反転する関数 P(x) = ￢Φ(x, x) を考える。これは h と l のどちらにも定義でき、P(h) = 0, P(l) = 0 であり、P(x) はある人が本当つきと嘘つきに対しどちらも嘘つきであるという言明をしていることを示している。重要なのはこの述語が Φ(x, y) と論理記号のみから導出されているということだ。対照表の値に対する論理演算が認められている場合は、ルール通りに導出された正当な述語だ。

しかし、明らかに h と l のどちらに対しても嘘つきであると言明する集合 A のメンバーはいない。対照表は本当つきと嘘つきのあらゆる可能性に対応しているにも関わらず、P(x)の振る舞いと同じ対照表の行はないからだ。対角線でどの行とも値が異なってしまう。したがって、もしそういう言明が可能な人 r がいるとしたら、それは集合 A のメンバー以外の人である。その場合にもその r について r が自己言及する Φ(r, r) は定義されていない。r は A = {h, l} のメンバーではないので本当つきでも嘘つきでもないからだ。すなわち、自分のことを嘘つきだと呼べる人は集合 A の中には存在しないことが分かる。「私は嘘つきだ」という言明ができる人は本当つきも嘘つきも集合 A の中には誰もいないのだ。

また、集合 A = {h, l} と Φ(x, y) の世界では、無制限に Φ(x, y) に論理操作を行うと、パラドキシカルな述語を発生してしまうことがわかる。世界が嘘つきと本当つきの排中律で記述できたとしても、無制限な論理の適用はパラドキシカルな述語を発生させてしまう。

対角線論法は要素数が有限であれ、無限であれ、正方行列の対照表から、その表に含まれない行を作り出すテクニックだ。対照表が正方行列でないときは対角線は全ての対照表の行に適用されるという保証がないので対角線論法が使えない。無限の自然数と無限の実数の全単射ができないと言っても、実数の小数点化の桁数と、実数に対応する自然数の個数が等しくなければ対角線論法は使えない。暗黙の正方行列が仮定されているのだ。無限に濃度差があるのであれば、対照表は必ずしも正方行列である必要はないはずだ。その場合は非対称の演算表も考えらえるが、そのような演算表では対角線論法は成立しない。

有限集合のラッセルのパラドックス

ラッセルのパラドックスはその発生原因が無限集合にあるのではない。有限集合にも発生するのだ。この意味で、床屋のパラドックスは村人の集合が有限集合であるが、ラッセルのパラドックスと全く同じ論理構造であると考えて良い。それを、有限集合 A = {a, b, c} で論じてみる。

対照 a, b ,c があるとき、この対照の集まりを集合 A とする。すなわち、

A = {a, b, c}

A の要素の一部からなる集合は A の部分集合である。たとえば、{}, {a}, {a,b} などは A の部分集合である。この部分集合を全て集めたものは A の冪集合である。これを B とすると次のようになる。

B = {{}, {a}, {b}, {c}, {a, b}, {a, c}, {b, c}, {a, b, c}}

集合 A の要素 a と A の部分集合の間には所属関係がある。すなわち a ∈ {a, c}, b /∈ {a, c} などである。

そこで、集合 A の要素と A の冪集合 B の要素間の所属関係を表にすると次のようになる。表の列の a と 行の {a, b} の交点の 1 はa ∈ {a, b} であることを表し、b と {a, c} の交点の 0 は b /∈ {a, c} であることを表している。

............ a b c

{}.......... 0 0 0

{a}........ 1 0 0

{b}........ 0 1 0

{c}........ 0 0 1

{a,b}..... 1 1 0

{a,c}..... 1 0 1

{b,c}..... 0 1 1

{a,b,c}.. 1 1 1

ここで、集合 A と 集合 B の要素から作られたペア、たとえば (a, {b,c}) のようなペアを全て集めたものは A と B の直積であり A × B で表す。これは次のような集合である。

A × B = {

(a, {}), (b, {}), (c, {}),

(a, {a}), (b, {a}), (c, {c}),

....

(a, {a,b,c}), (b, {a,b,c}), (c, {a,b,c})

}

そこで、A × B から {0, 1} への関数 ψ(x, y) :: A × B -> {0, 1} を考えると上の A と B の対照表を表すことができる。たとえば ψ(a, {a, b}) = 1, ψ(b, {a, c}) = 0 である。このとき y の値を固定して得られる関数 P(x) = ψ(x, {a, b}) は x に A の要素を代入すると０または１の値を返す。P(x) は A の全ての要素について 0 または 1 の値を返す。すなわち、P(a) = 1, P(b) = 1, P(c) = 0 である。これは P(x) が集合 A の要素について述語であることを示している。ここで P(x) に A の要素を代入したとき P(x) = 1 になる要素を全て集めるとそれは A の部分集合を定めるすなわち

{x | P(x)} = {a, b}

である。すなわち、述語 P(x) は内包的定義により集合 A の部分集合を定める。したがって、 A の冪集合の要素 b について ψ(x, b) は集合 A の述語で、A の部分集合 b を定める。すなわち、

{x | ψ(x, b)} = b

である。A と B の対照表から ψ(x, b) という形式の述語は集合 A の全ての部分集合を定める述語を作り出すことができることがわかる。したがって、集合 A の述語は ψ(x, b) で定義することができる。

さて、集合 A の述語で P(x) = x /∈ x というラッセルの集合の述語は定義できるのだろうか。たしかに、ψ(x, {a, b}) = 1 のとき x ∈ {a, b} であるが、x は集合 A の要素であり、{a, b} は A の冪集合 B の要素であるから、ψ(x, b) の述語では P(x) = x /∈ x のような自己言及を伴う述語を表現できない。

そこで ψ(x, y) とは別の φ(x, y) :: A × A -> {0, 1} という評価関数を考える。そうして、φ(x, y) = 1 のとき x ∈ y と考える。このようにすれば次の表のように集合 A の任意の２つの要素の間の所属関係を φ(x, y) で表現できる。

..... a b c

a... 1 0 0

b... 0 1 0

c... 1 1 0

この対照表を用いれば、x ∈ x のような自己言及を表現できる。このとき、φ(x, y) と ψ(x, y) は引数の型が全く異なっていることに注意が必要だ。

さて、φ(x, a) はどのような関数だろうか。これは x ∈ a のときに 1, x /∈ a のときに 0 であることに注目すると Q(x) = φ(x, a) が集合 A の述語であることがわかる。このとき {x | Q(x)} はどのような集合を内包的に定義するだろうか。上の対照表から、Q(a) = 1, Q(b) = 0, Q(c) = 0 であるから、

{x | Q(x)} = {x | φ(x, a)} = {a}

であることがわかる。φ(x, y) からみちびかれる述語は ψ(x, y) から導かれる述語とはタイプが異なるが、A の全ての要素について Q(x) = 1 または 0 を返すという述語の性質を持っているため、A の部分集合を定めることができる。

そこで、ラッセルの集合の述語 R(x) をφ(x, y) で表現すると、R(x) = ¬φ(x,x) と定義できる。R(x) は A の述語である。すなわち R(a) = 0, R(b) = 0, R(c) = 1 のように集合 A の全ての要素について 1 または 0 の値を返すからだ。このとき、

{x | R(x)} = {c}

であることがわかる。R に A の要素 a, b, c 含まれているかどうかを対照表にしてみると、次のようになる

...... a b c

R.... 0 0 1

ところがこれは上の対照表の中には現れることはない。なぜなら、R(x) = ¬φ(x,x) という定義は対照表の対角線部分の値を反転させたものだから R は 対照表のどの対角線部分とも異なっているからだ。すなわち、R は集合 A の要素ではない。しかし、これは A の部分集合なので冪集合 B の要素としては存在する。R(x) は A の述語であり A の部分集合を内包的に定義できるが、A × A の対照表に現れることができない。したがって、

R ∈ R

という論理式は意味を持たない。R という要素は A = {a, b, c} の要素ではないからだ。このことによって R ∈ R ならば、R /∈ R であるというパラドックスは発生しないことがわかる。ラッセルの集合がパラドックスを引き起こすように見えたのは、集合 A の部分集合を、集合 A の要素間の所属関係で全て表すことができると考えた仮定が誤っていたからだ。

この例では集合 A の要素は a, b, c の３つだけであったが、集合 A が無限集合であったとしても同じことが言える、集合 A の要素が無限にあったとしても、部分集合を集合 A の要素間の所属関係のみによって表そうとすると φ(x, y) :: A × A -> {0, 1} のような正方対照表をもつ関数から述語を導くことになり、その対照表には載せられない部分集合が導かれてしまうからだ。

このように、集合 A の述語を作る方法は、ψ(x, y) :: A × B -> {0, 1} という関数から導く方法と、集合 A の要素間の所属関係に注目した φ(x, y) :: A × A -> {0, 1} から導く方法との２種類があることがわかる。このうち ψ(x, y) を用いたものは A の全ての冪集合を定義できるが、φ(x, y) を用いたものから導かれた述語には、A の要素として A の部分集合を定義できないものがある。

これは、ラッセルのパラドックスは、集合 A の部分集合を表す要素を、その要素間の所属関係のみからは導くことができない場合があることを示している。しかし、φ(x, y) :: A × A -> {0, 1} の代わりに ψ(x,y) :: A × B -> {0, 1} を用いれば、集合 A の全ての部分集合を表現できる述語が定義できる。この場合、素朴集合論には部分集合を必ず定義できる述語が存在し、矛盾は発生しない。

この観点から床屋のパラドックスを眺めるとその意味がわかる。村人が互いに髭を剃るかそらないか（自分自身を含めて）の対照表を作ることができるが、その対照表の行には「床屋にひげを剃られる、自分自身の髭を剃らない人の集合」を求めることはできない。そのような集合を表す数列は、対照表の全ての行と対角線部分で異なるからだ。したがって、「自分自身のひげを剃らない人のひげを剃る床屋」という要素は、村人の集合の中には見つけられない。しかし、このような床屋を村人の外に求めれば、「床屋にひげを剃られる、自分自身のひげを剃らない」村人の集合を求めることができる。この議論は、村人の集合が有限集合であるにもかかわらず、本質的にラッセルのパラドックスと同じ論理構造なのだ。

追記

集合の所属関係と違い、髭を剃るという２項関係は却って話がわかりにくくなるが、村人 x の髭を村人 y が剃るという関係を φ(x, y) で表し、y が x の髭を剃るとき φ(x, y) = 1、そうでないとき φ(x, y) = 0 であるとする。このとき φ(x, x) は村人 x が自分自身の髭を剃るかどうかを表している。村人 b が「自分自身の髭を剃らない人の髭を剃る」とすると、φ(x, b) は φ(x, x) が 1 のときは 0、0 のときは 1 にならなければならないが、φ(b, b) についてはパラドックスが発生してしまう。つまり、b は自分の髭は剃るとも、そらないとも言えないのだ。しかし、床屋が村人でなければ、問題なく「自分の髭をそらない人」全員の髭を剃ることができる。