tnomuraのブログ

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

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

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 は自分の髭は剃るとも、そらないとも言えないのだ。しかし、床屋が村人でなければ、問題なく「自分の髭をそらない人」全員の髭を剃ることができる。

素朴集合論におけるラッセルのパラドックスの回避

１．集合とはものの集まりである

「集合とはものの集まりである」という定義から、様々な集合が生成される。

複数の個体があったとき、それを集めたものは集合であるから仮にこれを A とする。このとき、A の要素の一部を集めたものは A の部分集合であり、A の部分集合を全て集めたものは A の冪集合 2^A である。

さらに、２つの集合 A と B があったとき、A の要素 a と B の要素 b のペアを集めたものは A と B の直積 A × B である。また、A の要素 a に b の要素を対応させたものは A から B への写像であり、これは A × B の部分集合と同一視できる。

また、Aと B という２つの集合から A ∩ B と A ∪ B という２つの集合を作ることができる。あきらかに、この２つの２項演算は集合 A の冪集合である 2^A について閉じている。それに加えて、Aの冪集合について言えば上の２つ以外に ¬ 演算子（補集合）についても閉じている。

このように、個体から様々な集合が上の公理から生成され。それらを組み合わせることで、さらに多くの集合を生成することができる。上の説明では複数の個体を仮定したが、ただ１個の個体からでも無限の集合の生成が可能だ。たとえば、公理的集合論の集合の世界では、最初にたった１個の個体である空集合 { } から無限の集合を作り出し、その中に整数や実数や関数を収めることができる。

このように、「ものの集まりが集合である」という公理から無限の集合が作り出され、それらのなかに、集合の演算や写像など基本的な集合の性質を定義することができる。しかし、これらの集合は全て外延的定義による集合である。

ラッセルのパラドックスによると、素朴集合論には矛盾が存在するということだが、はたして、これらの外延的に定義された集合の体系に矛盾が存在するのだろうかという疑問が湧く。このような外延的定義の集合には矛盾はなく、ラッセルのパラドックスはこのような外延的に定義された集合の体系に不適切な内包的定義を導入したために起きたのではないかという疑問だ。

２．外延的集合による述語の定義

興味深いことに上の外延的集合には、外延的集合の規則で内包的定義を導入できる。

集合 A の冪集合を B とし、A と B の直積から２値集合 {True, False} への写像 ψ(x, y) :: A × B -> {True, False} を作ることができる。この関数は集合 A の要素が B の要素に含まれているとき True, そうでないとき False の値を返すように定義することができる。この関数は 集合 A と集合 B の全ての要素 a ∈ A と b ∈ B について a ∈ b であるかどうかを完全に記述できる。

このとき ψ(x, y) の y を b に固定した関数 ψ(x, b) は A の全ての要素についてそれが b に所属しているかどうかを判別するので、集合 A についての述語 P(x) = ψ(x, b) と考えることができる。この述語 P(x) による内包的定義は {x | P(x)} = b となるから A の部分集合 b を定めることができる。一般的な述語 P(x) についても、P(x) は任意の A の要素に適用することで True, False の値を返すので、そのふるまいは、上に定義した ψ(x, b) のいずれかと一致する。すなわち、集合 A についての全ての述語は ψ(x, b) で表すことができる。

述語についての上のような定義は、外延的定義の集合の規則で導出されているところがポイントだ。

３．ラッセルのパラドックス

述語をこのようなものとして定義したときラッセルの集合はどのように定義できるだろうか。ψ(x, y) には集合 A の全ての要素の全ての A の部分集合に対する所属関係が記述できる。しかし、これは集合 A の要素と集合 A の部分集合との対応関係であり、本来は P(x) = x /∈ x のような述語は発生しない。

そこで、所属関係の自己言及を実現するために別の評価関数 φ(x, y) :: A × A -> {True, False} を考える。A の任意の２つの要素の所属関係が φ(x,y) = True のとき x ∈ y であると考えるのだ。これは A の要素と A の部分集合の所属関係ではなく、A の任意の要素間に導入した所属関係である。この場合、 x ∈ y の右項の y は A の要素ではあるが、それは集合をあらわし、x を要素として含んでいる。評価関数をこのように定義すれば、 φ(a, a) に True あるいは False の値を与えることができ、集合 a の要素が、a が代表する集合 A の部分集合に属しているという自己言及が実現できる。

この評価関数 φ(x, y) のもとで、 y を集合 A の要素 a に固定したときの φ(x, a) は任意の A の要素 x が b に属しているかどうかを示す述語になる。なぜなら、φ(x, b) は任意の A の要素 x が b に所属しているかどうかを判別するからだ。このように φ(x, a) もまた集合 A の述語になる。したがって、この述語を用いた内包的定義 {x | φ(x, a)} は A の部分集合を定める。また、明らかに、

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

である。

このように定義された評価関数 ψ(x, y) をもちいて、述語 P(x) = x /∈ x となるラッセルの述語が次のように定義できる。

R(x) = ¬φ(x, x)

この R(x) は集合 A の任意の要素について、True または False を返すため、集合 A の述語である。そこでこの述語によって内包的に定義できる集合を R とすると、R は次のようになる。

R = {x | R(x)} = {x | ¬φ(x, x)}

この集合の述語 R(x) の値は A の要素の x について、ψ(x, x) の値を反転させたものになる。これは φ(x, a) で表されるどの述語とも振る舞いが異なる。なぜなら A の集合の要素のどの a についても R(a) /= ψ(a, a) だからである。したがって、R(x) の内包的定義で定義される A の部分集合を表す集合は φ(x, a) で表される述語では定義できない。a = {x | φ(x, a)} であるから、結局、集合 R を表す要素は集合 A の要素の中に見つけることができないことになる。定義される集合 R = { x | x /∈ x} は A の部分集合としては存在するが、それを代表する A の要素 a を見つけることができないのだ。R は集合 A の要素としては認められないのだ。

評価関数 φ(x, y) は集合 A の要素と要素の間の所属関係を記述していた。したがって、引数の x と y は集合 A の要素である必要がある。ところが、ψ(R, R) を考えるとき R は集合 A の要素ではないので、ψ(R, R) の値を求めるルールはない。すなわち、R ∈ R は無意味な論理式になる。しかし、P(x) は A の述語として集合を内包的に定義でき、R は A の冪集合 B の要素としては存在し、R(x) に相当する述語は ψ(x, b) の中に存在する。したがって、R(x) という述語自体に矛盾があるということはできない。R ∈ R かどうかという問が無意味であるだけである。

内包的定義の述語 P(x) は外延的に定義された集合から、評価関数 ψ(x, y) :: A × B -> {True, False} によって定義できる。この方法で定義された述語には矛盾は存在しない。しかし、集合 a の要素感の所属関係を記述した関数 φ(x, y) から導出された述語では、A の要素で代表できない A の部分集合が作られてしまう。これは、単に ψ(x, y) が A の全ての部分集合を記述するためには表現力が不足していることを示しているだけだ。一方 ψ(x, y) を用いて定義された述語の有益な点は要素と集合の所属関係について自然な階型が導入され、ラッセルの述語によるパラドックスを回避できることである。このように内包的定義の述語を ψ(x, y) から導出したとき素朴集合論になおも矛盾があるといえるのだろうか。

４．ラッセルのパラドックスの発生しない素朴集合論

以上の議論をまとめると次のようになる。

集合とはものの集まりであるという定義から次のようなことが言える（あるいは公理とすることができる）。

１．要素 a とその集合 A。要素と集合の関係 a ∈ A

２．集合 A の部分集合とその集合であるべき集合の存在

３．集合 A のべき集合を B とするとき、集合 A の要素と集合 A の部分集合との所属関係を全て表す評価関数 ψ(x,y) :: A × B -> {True, False} が存在する。

４．集合 A の述語 P(x) :: A -> {True, False} と集合 A の部分集合 B の内包的定義 B = {x | P(x) } = {x | ψ(x, B) }

５．述語 P(x) の真理集合は A の部分集合であるから、述語の論理演算はべき集合の要素の集合演算に対応する。この条件で論理演算は無矛盾である。

この５つの条件のもとではラッセルのパラドックスは発生しない。

素朴集合論の上で理論を組み立てるときは、集合 A 、集合 A の述語 P(x)、集合 A のべき集合 B、評価関数 ψ(x, y) :: A × B -> {True, False} が単位となる。この単位のもとでは論理は無矛盾である。実際の数学的対象の理論を組み立てるときはこの単位を複数個利用し、異なる集合間の関係はそれらの直積集合について同様の単位を組み立てる。こうして組み立てられた理論は無矛盾であるといえるのではないだろうか。

また、この方法の利点のひとつは、クラスを明確に定義できるところだ。数学理論の対象を集めた領域 A を作り、領域 A の要素間の所属関係で集合を代表させたとき、A × A の対照表の中に現れることのできるものが所謂集合で、その所属関係のもとでは対照表の中に表現できない領域 A の部分集合がクラスなのである。

５．まとめ

ラッセルのパラドックスの発生原因は、素朴集合論の世界を対象とその所属関係のネットワークとして捉えようとしたためである。対象とか所属関係とかは無定義用語なので、これだけで矛盾が起きるのは不思議な感じがする。しかし、このモデルでは対象間の所属関係を表す評価関数 ψ(x, y) :: A × A -> {True, False} の対照表は正方行列になってしまう。このときに集合 A の要素 a を集合として定める述語 P(x) は P(x) = ψ(x, a) となり、このときこの述語を用いた内包的定義で a = {x | P(x)} = {x | ψ(x, a)} となるが、A の要素だけでは全ての A の部分集合を代表することはできない。R(x) = not ψ(x,x) は A の述語であるがこれによって定められる集合 R = {x | R(x)} は A のどの要素もこれを代表することができないことが対角線論法から証明できる。

この困難は、対象の集合 A の冪集合を B とし評価関数の型を ψ(x, y) :: A × B -> {True, False} とすることで解決できる。この場合 ψ(x,y) の対照表は非対称で対角線論法は成立しない。集合 A の述語 P(x) は全て ψ(x, b) で定義することができるため、内包的定義で定義できない A の部分集合はない。P(x) についての全ての論理演算は冪集合 B の集合演算に対応させることができる。素朴集合論にこのような評価関数 ψ(x, y) と述語 P(x) = ψ(x, b) を導入すれば、A の全ての要素に True または False 関数を返す述語 P(x) でありながら、集合 A の部分集合を内包的定義で定義できないということは起こらない。

素朴集合論の公理のアイディア

前回提案した素朴集合論の公理のアイディアについて整理してみた。おおよそ次のようなものだ。細かい定義は省いている。

集合はものの集まりだ。集合 A が存在するとき述語 P(x) は A -> {True, False} 型の関数で、A の全ての要素について P(x) は True または False の値をとる。これは排中律が成立することを示している。また、P(x) により内包的定義で A の部分集合 {x | P(x)} を定めることができる。

集合 A のべき集合が存在する。有限集合の時はべき集合の存在は明らかだが、無限集合にも対応するためこれを公理とする。集合 A のべき集合を B とするとき評価関数 ψ(x, y) :: A × B -> {True, False} は任意の A の要素と B の要素（Aの部分集合）の間の所属関係をすべて記述することができる。また、B の要素を固定した ψ(x, b) は A の述語であり、b = {x | ψ(x, b) } である。なぜなら ψ(x, b) が True となるのは x ∈ b の時だからだ。

ψ(x, y) の性質から、集合 A の全ての P(x) の振る舞いは、ψ(x, b) のどれかと一致している。述語 ψ(x, b) すべての集合を C とすると、これに命題演算子を適用したものたとえば ψ(x, b) ∧ ψ(x, c) はやはり A -> {True, False} 型の関数であるので、論理演算は C に対して閉じている。また、B が冪集合であるという性質から、B の集合演算の値は全て B の要素であるから、集合演算は B について閉じている。このとき明らかに C から B への写像で全単射で準同型なものが存在する。つまり、述語についての論理的な考察は集合の性質として読み替えることができる。

このような前提の下で、集合 A の全ての述語 P(x) は排中律を満たし、すべての論理演算について閉じている。

述語をこのように集合 A から {True, False} への関数であると定義するとき、素朴集合論には矛盾はみられない。ただし、述語とは、すべての集合に適用される汎用的な関数というより、特定の集合の部分集合だけを決定すると考えなくてはならない。複数の集合（圏論でいう対照）から構成される理論については、それぞれの集合についての述語が存在し、すべての集合に汎用的に適用できる述語はないと考えるべきである。

集合 A の要素を引数にとる述語が内包的定義で定義できるのは集合 A の部分集合だけだと割り切るということだ。

ラッセルのパラドックスではすべての集合の集合 A を考え、これらの相互関係が ψ(x,x) :: A × A -> {True, False} で表すことができると仮定しているが、A のべき集合 B の濃度は A のそれよりも大きいため A × A に基づく ψ(x,b) では、すべての A の部分集合を表すことができない。そのため対角線論法でラッセルのパラドックスが発生する。しかし、A のべき集合を B とし、ψ(x,y) :: A × B -> {True, False} を仮定したら、ψ(x,b) は全ての A の部分集合を表すことができる。

しかし、このさい r = {x | x /∈ x} は A の部分集合ではあるが、対角線論法から r は A × A -> {True, False} 型の関数では定義できない。しかし、B の要素ではあるのでパラドックスは生じない。また、r /∈ A ではないので、ψ(r, r) は ψ(x,y) :: A × B -> {True, False} の関数では定義されず（（r, r) ∈ B × B ）、r が r に含まれるかどうかという議論は無意味だということが分かる。

冪集合にしても、直積集合にしても、内包的定義可能な述語の定義にしても、いずれも公理的集合論の公理から導出できるものばかりだ。したがって、提案した素朴集合論の公理に関するアイディアは、公理的集合論のモデル（部分的な）であると言えるのではないかと思う。いずれにしても、ラッセルのパラドックスでは素朴集合論の致命的な矛盾の指摘にはならないような気がする。

矛盾のない素朴集合論の公理

素朴集合論もこんな公理にしたら矛盾が生じないのではないかというのを考えてみた。ただの思いつきなので、SFみたいなものだ。

１．ものの集まりを集合と呼ぶ。また、要素 a が集合 A に含まれているとき、a ∈ A で表す。

２．集合 A の要素がすべて集合Bの要素であるとき A ⊂ B である。

３．集合の部分集合の全てからなる冪集合が存在する。冪集合の要素間には集合演算が適用され、冪集合は集合演算について閉じている。集合演算の中には補集合も含まれる。

４．集合 A と 集合 B の直積 A × B が存在する。

５．集合 A と 集合 B のあいだに写像を定義できる。

６．集合 A とその冪集合 B があるとき、関数 ψ(x,y) :: A × B -> {0, 1} が存在し、集合 A の要素と集合 B の要素との所属関係を全て記述する。このとき、B の要素 b に対し ψ(x, b) は b を定める述語である。すなわち、b = {x | ψ(x, b) = 1} である。

７．述語の集合には、述語論理が適用できる。このとき冪集合の集合演算と、述語の述語論理は同値である。

要するに、集合の内包的定義を、冪集合の要素に限定しただけだが、r = {x | x /∈ x} としたとき、ψ(r, r) は意味を持たないのでラッセルのパラドックスは発生しない。また、論理法則を冪集合に限定したので、命題の否定を含む全ての述語に対する論理演算が冪集合上の集合演算に変換できる。

ここで、なぜこのような公理を考えたか論理の視点から説明する。

論理学の根幹は命題である。命題は必ず真または偽の値を取る。述語 P(x) を要素 a に適用したとき P(a) は命題となり、真または偽の値をとる。したがって、a が属している集合を A とすると述語 P(x) :: A -> {0, 1} は集合 A から {0, 1} への写像である。このとき、P(x) により内包的定義で集合を定めることができる。集合 b が P(x) による内包的定義で定まる場合、b = {x | x ∈ A, P(x)} である。このとき、b は A の部分集合である。なぜなら、P(x) を適用する要素は A の要素であるからだ。すなわち、b は P(x) = 1 となる x を集めた集合になり、それは A の部分集合である。

ところで、A の冪集合を B とすると、直積 A × B を考えたとき ψ(x,y) :: A × B -> {0, 1} は A の要素のB の要素であるAの部分集合に対する所属関係を全て記述できる。このとき、y = b に固定した ψ(x, b) :: A -> {0, 1} は集合 A の要素についての述語である。そうしてこの述語によって定義できる集合は b と一致する。すなわち b = {x | ψ(x, b)} である。なぜなら、このようにして集められた A の要素 x は全て b の要素であるからである。すなわち、ψ(x,b) = 1 は x ∈ b であることを意味しているからだ。

任意の述語は P(x) :: A -> {0, 1} 型の関数だから ψ(x, b) のどれかと一致する。なぜなら、ψ(x, b) :: A -> {0, 1} は全ての起こり得る述語を尽くしているからだ。すなわち、冪集合では全ての可能な A の部分集合を尽くしているので、それを内包的に定義する関数 ψ(x,b) も起こり得る述語の全てを尽くしている。すなわち、冪集合 B と述語の集合 { ψ(x,b) } の対応関係は全単射である。

冪集合は明らかに補集合を含む集合演算について閉じている。また、述語の集合は論理演算について閉じている。さらに、冪集合の演算は、述語の論理演算と同型である。この意味で論理と集合が同型であることがわかる。論理演算の結果は集合演算の結果として解釈することができる。

きちんと説明しようとするとかえってわかりにくくなったが、要するに、述語とは A -> {0, 1} 型の関数であり、集合 A の述語についての論理演算は、すべて冪集合 B の要素に対応していると言いたかったのだ。論理は集合なのだ。

要するに言いたいことは、集合 A があきらかな集合であれば、集合 A の要素についての述語 P(x) は必ず内包的定義 {x | P(x)} で A の部分集合を定めることができ、P(x) についての論理演算は、A の部分集合についての集合演算と同型であるということだ。この条件では述語についてのパラドックスは一切存在しない。素朴集合論のモデル次第では、素朴集合論には矛盾はないかもしれない。

ラッセルのパラドックスでは全ての集合の集合 A について、暗にψ(x,y) :: A × A -> {0, 1} を採用したためにパラドックスがおきたのだ。実際には A の冪集合を B として ψ(x,y) :: A ×B -> {0, 1} を採用していればパラドックスは発生しなかった。

述語とは何か

素朴集合論で最も重要なのは述語 P(x) である。P(x) を充足する要素を集めたものが集合になるという内包原理は、集合を外延的定義ではなく、述語で定義することを可能にする。すなわち、

{x | P(x) = true}

が集合を定めると言えることで、集合の問題を述語の問題として抽象化できるからだ。このような述語と集合の１対１の関係はしかし、ラッセルのパラドックスで否定されてしまった。しかし、それは述語のあり方に対する洞察の違いからきているような気がする。

これを論証するのに、まずA = {a, b, c} という３個の要素しか含まない有限集合について見てみよう。この有限集合が与えられたとき、この集合の部分集合からなる冪集合 2^A を考えることができる。すなわち、

2^A = { {a, b, c}, {a,b}, {a, c}, {b, c}, {a}, {b}, {c}, {} }

要素数３の集合の冪集合は 2^3 = 8 個になる。ここで、直積 A × 2^A から２値集合 {0, 1} への写像 ψ(x, y) を考える。この関数は A の要素 x が 2^A の要素 y に含まれているとき 1, 含まれていないとき 0 をとる。このとき A の要素を列に、2^A の要素を行にとった対象表を作ると次のようになる。

**a b c

p 0 0 0

q 0 0 1
r 0 1 0
s 0 1 1
t 1 0 0
u 1 0 1
v 1 1 0
w 1 1 1

このとき 2^A の要素の一つを固定した関数 g(x) = ψ(x, p) :: A -> {0, 1} は A の述語になる。すなわち、g(a) は１または０の値を取り、

{x | g(x) = 1}

は A の部分集合を定める。この例の場合は g(a) = 0, g(b) = 0, g(c) = 0 だから空集合 { } でこれは対照表の p と一致する。このように A と 2^A の間で関数 ψ(x, y) が定められているとき、関数 ψ(x, p) は集合 p と１対 1 対応している。すなわち、ψ(x, p) は A の述語である。また、述語 P(x) がどのように表現されていても、そのふるまいは上の対照表のどれかの行に一致する。したがって、ψ(x, y) の y を固定した関数 ψ(x, m) は A の述語の全てを尽くしている。したがって、これを述語の定義としても構わない。

ところで、述語の定義を ψ(x, m) としたときの述語とラッセルのパラドックスの関係はどうなるだろうか。

それを見るために上の対象表の一部を A の要素に変更したものを作ってみる。最初の３行を a b c に変更してみよう。

**a b c

a 0 0 0

b 0 0 1
c 0 1 0
s 0 1 1
t 1 0 0
u 1 0 1
v 1 1 0
w 1 1 1

a b c の部分だけを取り出すと次のようになる。

**a b c

a 0 0 0

b 0 0 1
c 0 1 0

この対照表では、「自分自身を要素として含む集合」や「自分自身を要素として含まない集合」が存在する。この対象表では、a b c 全てが「自分自身を要素として含まない集合」である。そこで述語 P(x) を「自分自身を要素として含まない」と定義する。すると、

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

であり述語 ψ(x, R) の振る舞いは対照表の行の 1 1 1 として現れる。これは対照表の w と一致しているので R = w である。つまり、「自分自身を要素として含まない集合」という述語は A の立派な述語であって、A の部分集合を定める。ところが、ラッセルのパラドックスではさらに R が R に属するかどうかを議論している。すなわち P(w) の値を問うている。しかし、ψ(w, w) は上の対照表には現れてこない。w は A の要素ではないからだ。したがって R が R に属するかどうかという問題提起が無意味なのだ。

したがって、述語の定義を上で述べた定義にする限りそれは集合 A の要素にのみ適用されなければ意味がないことがわかる。これは、公理的集合論の公理（分出公理）として取り上げてある。

ラッセルのパラドックスは述語 P(x) の定義に制限がないため発生したのだ。述語本来の意味は、集合 A の部分集合は述語による内包的定義ができると考えるべきである。ラッセルのパラドックスはこうして、公理的集合論の内包的定義の公理(分出公理）によって防ぐことができることがわかる。

また、冪集合については述語で定義できる集合の全てを尽くしている。さらに、冪集合は集合演算について閉じている。したがって、冪集合においては論理学の定理が全て成立することがわかる。適切な述語には論理は心配なしに適用できるのだ。

ところで、ラッセルのパラドックスで、P(w) がなぜいけないのかと言うと、それは P(x) :: A -> {0, 1} という述語を P(w) のように 2^A のデータ型に適用して、型エラーを起こしてしまったためだ。述語を型付き関数としてとらえることで、パラドックスは回避できる。ラッセルのパラドックスは型なしプログラム言語でランタイムエラーを起こしたのだ。Haskell のような型付きプログラム言語は、素朴集合を安全に使うためのモデルになっているのかもしれない。

ラッセルのパラドックスのどこがいけないか

ラッセルのパラドックスの論証は次のようになる。

集合は自分自身を要素として含まない（x /∈ x）か、自分自身を要素として含む（x ∈ x）かのどちらかであるはずだ。そこで自分自身を要素として含まない集合を集めた集合 R = {x | x /∈ x} を考える。この集合も自分自身を要素として含むか、または、含まないかのどちらかであるはずだ。そこで R ∈ R とするとこれは R の性質から R /∈ R でなければならない。また、R /∈ R であるとすると、Rの述語を満たすので R ∈ R でなければならない。結局 R は自分自身を要素として含むとも、含まないとも言えない。ゆえに素朴集合論には致命的な矛盾がある。

なかなか反論できないが、上の議論だけでは素朴集合論のどこが悪いのかがわからない。しかし、対角線論法を調べているうちに問題点が分かった気がするので書いてみる。要点は次のようなものだ。

仮定：すべての集合を集めた集合をAとする。Aの要素間には所属関係があり、評価関数 ψ(x,y) :: A × A -> {0, 1} で所属関係を表すことができる。ψ(x,y) は A の全ての要素間に定義できるので、A の各要素（集合）の外延を決定できる。A の要素であるある集合 a の外延は内包的定義で a = {x | ψ(a, x) = 1} で定義でき、ψ(a, x) は集合 a を決定する述語である。

結論：以上の仮定の下で、対角線論法により ψ(a, x) では記述できない述語 ￢ψ(x,x) が存在する。したがって、 A の要素では代表できない A の部分集合がある。すなわち、素朴集合論に矛盾が存在するのではなく、集合 A の要素では代表できない A の部分集合がある。（素朴集合論に矛盾があるというわけではなく、集合 A の要素では代表できない A の部分集合があるということだ）

素朴集合論に矛盾があるというよりは、すべての集合を集めた集合ができるという仮定に誤りがある。素朴集合論の集合は次々に生成されていく生成的な過程であり、これがすべてという境界を引くことができないのだ。

以下の議論は本質的に冒頭の論理と同じことだが、集合 A で記述できる集合とは何かということを明示している。

それでは、議論に入る。問題点をはっきりさせるためにすべての要素が集合であるような集合 A を考えてみよう。このとき、この集合 A の任意の２つの要素の間に所属関係の有無があるはずだ。そこで、評価関数 ψ(x,y) :: A × A -> {1,0} を次のように定義しよう。すなわち、x ∋ y なら ψ(x,y) = 1, x /∋ y なら、ψ(x,y) = 0 である。このとき x = a に固定したときの ψ(a, x) は A -> {0,1} 型の関数で、ψ(a,x) は x が a の要素であるとき 1、そうでないとき 0 の値をを取る。これは A の要素のどの要素が a に所属しているかを判別する関数になる。すなわち、要素 b について ψ(a,b) = 1 なら b ∈ aである。これはまた、集合 a を定める内包的定義を提供する。つまり a = {x | ψ(a,x) = 1} である。

ここで、not :: {1, 0} -> {1,0} 関数を次のように定義する。すなわち、not(1) = 0, not(0) = 1 である。このビット反転関数を ψ(a,x) に適用した、not( ψ(a,x)) 関数もまた、集合の内包的定義の述語となる。つまり、{x | not(ψ(a,x)) = 1} は a に含まれない A の要素を集めた A の部分集合である。

ここで、ψ(x,y) の対角線成分からなる関数、ψ(x,x) :: A -> {0, 1} を考える。この述語によって定義される集合を R' = {x | ψ(x,x) = 1} とすると、R' は「自分自身を要素として含む集合の集合」である。仮定から、A の要素 a の外延は a = {x | ψ(a,x) = 1} という内包的定義で規定されるから、R' と一致する a があるはずである。すなわち R' = a。この時全ての x ∈ A について ψ(x,x) = ψ(a, x) である。特に (a, a) について ψ(a,a) = ψ(a,a) となる。

また、not 関数と ψ(x,x) の合成 not(ψ(x,x)) :: A -> {0, 1} は A -> {0,1} 型の関数であるので、これは A の部分集合を定める述語である。これは R = {x | not(ψ(x,x)) = 1} という集合を定める。この集合は「自分自身を要素として含まない集合の集合」であるここで、R が A の要素の1つ r と一致すると考えると、全ての x ∈ Aについて、ψ(r, x) = not(x,x) である。特に (r,r) についてみると、ψ(r, r) = not(r, r) となり矛盾する。したがって、R は ψ(a, x) の形で表される集合の述語のどれとも一致することはない。また、R = r となる r が存在したとすると、ψ(r,r) = not(ψ(r,r)) だから R が R の要素であれば、RはRの要素ではないというパラドックスに陥ってしまう。

これは不思議な話である、特性関数から not(ψ(x,x)) という述語で定義できる集合 {x | not(ψ(x,x)) = 1} は確かに A の部分集合として存在できるのに、ψ(a, x) の中には同等の述語を見つけることができないのである。しかし、これは ∈ という演算子に矛盾が存在するのを示しているというわけではない。単に ψ(a, x) という述語では定義できない集合 A の部分集合があることを示しているに過ぎない。ψ(x, y) を A×A -> {0,1} という型で定義したので ψ(x,y) では表現できない集合が発生してしまっただけで、ψ(x,y) :: B × A -> {0, 1} という非対称な直積集合に定義したら、対角線というものがなくなるので、A の部分集合は完全にψ(x,y) で記述することができる。

無限に大小はないだろうという批判もあるかもしれないが、無限は数ではない。自然数は無限集合だが、だれも無限大を捉えることはできない。どんな大きな自然数 n を持ってきてもそれより大きい n + 1 があるので無限だと言っているに過ぎない。自然数のある一部分を切り取ったとき、それよりも大きい数があるから無限大になると言っているだけだ。捕まえることができるのは常に有限の値だ。

同様に有限集合とその冪集合の要素数の対を作ってみると、(1,1), (2, 4), (3, 8), ...., と集合の要素数をどんどん増やしていくと、冪集合の要素もどんどん大きくなっていく、しかし、どの時点で切り取っても集合の要素数より、冪集合の要素数のほうが大きいのだ。有限集合の要素をどんなに大きくしても、もっと大きくできるというのが無限集合だ。しかし、その過程で常に集合の要素より冪集合の要素のほうが大きいのなら、無限集合についても集合の要素数より冪集合の要素数が多いと言える。したがって、無限集合 A であっても、その冪集合のほうが要素数が多い（A の要素と全単射できない A の冪集合の要素がある）ということはできるのだ。

このようにラッセルのパラドックスは ∈ 演算子に矛盾があったわけではなく ψ(x,y) :: A × A -> {0, 1} という対称的な直積集合の関数 ψ(x,x) ですべての A の部分集合が記述できると暗に仮定したところが問題だったのだ。

ラッセルのパラドックスは素朴集合論に致命的な矛盾が存在することを示したわけではなく、暗に仮定した集合の表現法が集合全体を表現するのに不十分であるということを論証しただけだ。