tnomuraのブログ

集合の生成とゲーデルの不完全性定理

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

複数の個体があったとき、それを集めたものは集合であるから仮にこれを 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 のような述語は発生しない。しかし自分自身を要素とするという状況を発生するために、集合 B の要素の一部を集合 A の要素と同一視することにする。そうすることで ψ(a, a) に True あるいは False の値を与えることができる。このとき R = { x | x /∈ x} は A の部分集合として存在する。しかし、対角線論法からこの R は A の要素としては存在しないため、P(R) = R /∈ R は型エラーとなり、True の値も False の値も取ることはできない。しかし、R は B の要素としては存在しているので矛盾ということはできない。R ∈ R かどうかという問が無意味であるだけである。

内包的定義の述語 P(x) は外延的に定義された集合から定義できる。この方法の有益な点はラッセルの述語のどこがいけなかったかを自然に明らかにすることができるところだ。このように内包的定義の述語を外延的集合から定義したとき、素朴集合論になおも矛盾があるといえるのだろうか。

述語P(x)は外延的集合で定義できるものに限る必要があるのではないだろうか。べき集合から導出される述語の定義では、述語 P(x) はべき集合の要素に対応し、その論理演算はべき集合の集合演算に対応する。さらに、冪集合は集合演算について閉じているので、述語に関する論理演算で矛盾は発生しない。論理演算と集合演算は同型である。

言い換えると、述語による論理はべき集合にのみ適用すべきだということだ。べき集合に適用される集合演算はそのまま論理を反映しているし、べき集合に対し集合演算は閉じているので、論理的矛盾も発生しない。

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

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

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

この観点からゲーデルの第１不完全性定理の意味が類推できるような気がするので少し述べてみる。まず証明可能な論理式かその否定が証明可能な論理式を集めた集合 A を考えてみる。さらに A の要素 a を A の要素の b に関数適用した ab も集合 A の要素として演繹できることがわかっているとする。

そこで、A の任意の要素 x, y について、xy が証明可能ならば True を、その否定が証明可能ならば False を値として返す関数 ψ(x,y) :: A × A -> {True, False} を考えると、A の要素全てを横と縦に並べた対照表をつくることができる。すなわち、ψ(x,y) = xy = True のときは対照表の x 行 y 列の値が True である。これは y に x を関数適用してできる論理式 xy が証明可能であることを示している。

このとき y を固定して y = b とすると、ψ(x, b) は x を b に関数適用したとき証明可能か否定の証明が可能かを表す。これを P(x) = ψ(x, b) と置くと、P(x) は x を b に関数適用すると証明可能であるという述語になる。したがって {x | P(x)} は b に関数適用すると証明可能な論理式の集合になる。

ここで、ψ(x,x) という関数を考える。これは xx が証明可能なとき True となり、Q(x) = ψ(x,x) は集合 A の述語である。そこで G(x) = not ψ(x,x) という述語を考える。これは xx の否定が証明可能なとき、G(x) は True となる。そこで、G = {x | G(x)} と置くと G は A の部分集合である。したがって、A のある要素 g があり G = {x | G(x)} = {x | ψ(x, g)} となるはずである。このとき、任意の x について G(x) = ψ(x,g) となるのは明らかだ。ところが x = g のとき G(g) = ψ(g, g) = not ψ(g, g) となり、G(g) に True を割り当てても False を割り当てても矛盾が起きてしまう。g は公理から演繹可能な論理式なので、ψ(g, g) = not ψ(g, g) が成立するのは公理系が矛盾しているときだ。矛盾していないのであれば、G(g) は True とも False とも言えないので、gg は証明可能ともその否定が証明可能ともいうことができない。このような困難は、形式的体系で gg のような自己言及が可能な場合におきる。自己言及が可能でない体系では G(g) のような論理式は発生しない。

ゲーデルの不完全性定理では G(g) がその体系から演繹できてしまうところが、ラッセルのパラドックスの場合と異なるが、評価関数に ψ(x,y) :: A × A -> {True, False} 型の関数が用いられるときの、自己言及による困難を示している。

この議論はあくまでも、集合とその冪集合の性質からの類推なので、著者がゲーデルの定理を理解して言っているのではないので断っておく。しかし、集合論や論理学のいろいろな不可解な振る舞いは、述語を 評価関数 ψ(x,y) :: A × B -> {True, False} から導出できるものとして捉えることでその理由を明らかにすることができるような気がする。

集合を利用して理論を組み立てる際には、要素の集合 A とその冪集合 B、集合 A の評価関数 ψ(x, y) :: A × B -> {True, False}、A の部分集合を定める述語 P(x) = ψ(x, b) に注目してその意味を考えていくと安全な体系が構築できるような気がする。

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

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

集合はものの集まりだ。集合 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 の部分集合が記述できると暗に仮定したところが問題だったのだ。

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

構成的集合

実は構成的集合あるいは、構成可能集合の厳密な意味を筆者は知らない。あまり、こういう問題に深入りすべきではないとは思うが、こうであればいいなという希望として述べている。それで、ここでは、構成的集合とはすでにあるものから段階的に定義していく集合という意味で使う。

まず集合ではない要素を集めた集合 A = {a, b, c} を考える。これは普通の意味での集合だ。さらに、この集合をもとにして冪集合 2^A = {{a,b,c}, {a,b}, {a,c}, {b,c}, {a}, {b},{c},{}} を考える。これらの A と 2^A は圏論の用語を借りて対象と呼ぶことにする。また、Aの要素と2^A の要素の間には要素としての所属関係がある。すなわち A の要素 a が 2^A の要素 b に含まれていれば、a ∈ b である。この所属関係について A の要素と 2^A の要素との間の評価関数を ψ(x,y) を次のように作ることができる。すなわち、 2^A の要素 x が A の要素 y を要素として含んでいれば ψ(x,y) = 1 、そうでなければ ψ(x,y) = 0 である。

この評価関数 ψ(x, y) について A と 2^A の要素間の対象表を作ることができる。

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

{a,b,c}: 1 1 1

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

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

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

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

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

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

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

この対象表の中には「自分自身を要素として含む集合」は発生しない。A と 2^A は異なる対象だからだ。さて、ここで A の要素と 2^A の要素の間の写像 f :: A -> 2^A を考えてみる。そうして、2^A の要素の中で X = {x ∈ A | x /∈ f(x)} を考えてみる。ここで x ∈ X ならば、x /∈ X というパラドックスが発生するだろうか。こたえは、否である。上の対象表は正方行列ではないので対角成分は発生しない。集合 X は 2^A の要素としていつでも存在可能だ。

たとえば f(a) = {a,b}, f(b) = {a,c}, f(c) = {b, c} の場合の x と f(y) の間の所属関係の対象表を作ってみる。

.......a b c

f(a) : 1 1 0

f(b) : 1 0 1

f(c) : 0 1 1

このとき a ∈ f(a), b /∈ f(b), c ∈ f(c) だから X = {b} であり a b c との所属関係を表す数列は 0 1 0 である。これは f に関する対象表の対角線部分の数列をビット反転したもので、この対象表のどの行とも対角線との交点部分が異なるから、この数列は対象表には存在しない。しかし、あきらかに、これは 2^A の要素で {b} である。集合 X はどのようにも定義できないパラドキシカルな集合というわけではない。

これは、A の要素と 2^A の要素との所属関係が正方行列ではないので、対角線論法が適用できないためだ。しかし、A の要素と 2^A の要素が全単射していると仮定すると、その対象表は正方行列になるために対角線論法が成立してしまう。対角線論ぽいことについて言うなら f :: A -> 2^A の値の中には確かに X は存在しない。f に関する所属関係の対象表は正方行列だからだ。

このように、対象の集合 A とその冪集合 2^A のタイプ（型）を分けて考えると、対角線論法が A と 2^A の間の写像の限定的な条件のもとで発生し、パラドックスなどではないことがわかる。

これはほんの一例だが、Haskell 風の型付き集合の取扱をすることによって、対角線論法をパラドックスとして捉えなくても済むのではないかと思う。型付きデータの構成的集合が、素朴集合論のラッセルのパラドックスの解決になるのかどうかはわからないが、少なくとも Haskell でプログラムを作成するときは、ラッセルのパラドックスの呪縛から逃れることができるのではないかと思う。

実無限と構成的集合

自然数は無限に存在する。自然数の全体を数えきることはできない。しかし、どの自然数も共通の性質、すなわち、ペアノの公理を満たしている。このため、どのような大きな自然数であってもそれが自然数であるかをペアノの公理に照らして判断できる。このような数を、たとえその全体がつかめなくても、自然数の集合としてまとめることは有益だし、問題がないように思われる。

しかし、全ての集合をまとめて「全ての集合の集合」を考える場合は問題が生じる。カントールの定理によって、集合の濃度より冪集合の濃度のほうが大きく、両者の間の全単射は存在しないからだ。たとえば A = {a, b, c} のときその冪集合 2^A は 2^A = {[a,b,c],[a,b], [a, c], [a], [b, c], [b], [c], []} となる。A の要素で冪集合の要素を表そうとしても A の要素数が３であるのに対し、2^A の要素数は８であるので、到底 A の要素でその全てを代表させることはできない。無理に代表させることができると仮定すると、対角線論法で矛盾が導かれる。カントールは無限集合においても、同じ推論ができることをやはり対角線論法で証明している。

「全ての集合の集合」を考えた場合、「全ての集合の集合」の冪集合の要素も「全ての集合の集合の」要素として含まれていなければならないが、それはカントールの定理から不可能だ。このため、「全ての集合の集合」を考えるとラッセルのパラドックスが発生してしまうのだ。すなわち、全ての集合を集めて「全ての集合の集合」とするというくくり方に問題がある。A = {a, b,c} でできないことが、無限集合 X ならできると考えることがおかしいのだ。

この問題は無限の要素を持つ集合を安易に集合としてくくってしまう実無限の考え方に問題があるのではないだろうか。

自然数の集合にしても、その要素の全体を数えきってしまうことは不可能だ、自然数の集合の要素は無限に増やしていくことはできるが、それはペアノの公理によって構成的に要素が生成されていくからだ。構成的集合の無限は「可能無限」だ。これを自然数の集合という無限集合（実無限）として捉えることは可能だが、それは、便宜的にそういう捉え方ができるということでしかない。

たとえば、自然数を次のように後者が順次作られていく過程であると捉える可能無限の立場からは、自然数と偶数の全単射は存在しない。

1, 2, 3, 4, ...

なぜなら、この要素の増加のどの段階で止めても自然数と偶数の全単射は存在しない。ところが、偶数を 0, 2, 4, 6, というふうに２つずつ増加する生成過程であるという見方（公理）をすると、自然数の集合と偶数の集合は構成的にも全単射させることができる。

0, 4, 6, 8, ...

1, 2, 3, 4, ...

この方法なら偶数と自然数の生成段階のどの時点であっても両者は全単射している。自然数と全単射させることができる偶数の集合はこのような集合であって、自然数の部分集合である偶数ではない。自然数がその部分集合である偶数との全単射があるように見えるのはこのような構成的な無限集合（可能無限）を無限の要素を集めた無限集合（実無限）としてくくってしまうためだ。自然数の部分集合としての偶数と、構成的に生成される偶数の集合を同一視してしまう実無限の考え方は危険なのである。

同じようなことが「全ての集合の集合」についても言える。有限集合について言えば、A = {1, 2, 3} の部分集合は 1 0 1 のような数列で表すことができる。これは対応する要素が含まれているときは 1 、含まれていないときは 0 で表している。すなわち、1 0 1 -> {1,3} だ。このような {1,2,3} の集合はつぎのように８個ある。

1 2 3

------

0 0 0

1 0 0

0 1 0

1 1 0

0 0 1

1 0 1

0 1 1

1 1 1

このうち任意の３個を取り上げて {1, 2, 3} の要素と対応させた対照表を作ると次のようになる。

* | 1 2 3

1 | 1 0 0

2 | 1 0 1

3 | 0 1 1

この対照表について、対角線成分は 1 0 1 となる。これは {1, 2, 3} の部分集合 {1, 3} を表している。これをビット反転させたものが 0 1 0 でこれは {2} を表すがこの集合は上の対照表には現れない。なぜなら、対角線部分でどの行とも異なるからだ。対角線論法は有限集合にも適用できる。

ここで、有限集合を構成的に {1,2,3,4}, {1,2,3,4,5} と増やしてみても正方形の対照表で全ての部分集合が表せないということは変わりなく、対角線論法も成立している。そうして、自然数の集合を無限に増やしていってもどの段階でもこれらの性質は一貫して存在している。そうして、無限の集合を数え尽くしたと考えたとき、カントールの定理になる。

全ての集合の集合について考察するときもこのような構成的な方法を用いると、ラッセルのパラドックスがどのようなものか考えることができる。推論は全く上と同じようなものになる。集合 {a, b, c} について各要素で作ることのできる集合を考えると次のような表ができる。

a b c

------

0 0 0

1 0 0

0 1 0

1 1 0

0 0 1

1 0 1

0 1 1

1 1 1

このうちの３つだけを取り上げて a, b, c と対応させると次のような対照表ができる。

* | a b c

a | 1 0 0

b | 1 0 1

c | 0 1 1

この対照表については当然対角線論法とラッセルのパラドックスが発生する。そこで、残りの集合を表す、d, e, f, g, h という要素を作り {a, b, c} に追加する。すると {a, b, c, d, e, f, g} の部分集合を作ることができる。

a b c d e f g h

----------------

0 0 0 0 0 0 0 0

1 0 0 0 0 0 0 0

0 1 0 0 0 0 0 0

...

ここで構成される集合は 256 個あるので、そのうちの８個を取り出し対照表を作るとその対照表にも対角線論法とラッセルのパラドックスが発生する。しかし、それは２５６個ある集合を８個の要素で代表させようとしたために起きる現象だ。そこで、... という具合に構成的に段階的に集合を作り出していくのが構成的集合だ。

要素数が爆発的に増加するのでこれくらいでやめるが、構成的方法のどの段階でも正方対照表では可能な集合の全てを表すことができず、その対照表の中でラッセルのパラドックスが発生する。これは、構成的方法を無限に続けていったとしてもどの段階でも正方対照表で全ての集合を表すことができないからである。すなわち、正方対照表では可能な全ての集合を表すことはできず、無理にそれを仮定するとラッセルのパラドックスになるためだ。

構成的集合の利点は、このようにどのような集合が領域に含まれることができて、どのような集合は領域の要素で代表することができないかを明確にできることだ。全ての集合の集合が存在するという実無限からの安易なくくり方を認めると、ラッセルのパラドックスがなぜ発生するのか。どのようにすれば回避できるのかが見えなくなる。

このように領域 {a, b, c, ... } の要素で領域の集合を「全て」代表させようとするとラッセルのパラドックスが発生するが、領域の要素で代表させることのできる領域の要素の集合を明示的に示せば、対照表にラッセルのパラドックスが存在しても、目的とする理論を集合で構築することができる。

さいわいなことに、多くの数学的理論や、コンピュータのプログラムは構成的に集合を定義しているように見える。これが、素朴集合論にラッセルのパラドックスという重要な欠陥があるにもかかわらず、一般の数学理論が素朴集合を用いて矛盾なく理論を構築できている理由だろう。

自然数の集合という無限集合があると考える実無限の考え方は、概念を簡潔にして問題の見通しを良くすることがあるが、ときに構成的集合（可能無限）の視点からはその問題がどう見えるのかも考える必要がある。

カントールの定理と背理法

集合 X とそのべき集合 2^X との間に全単射が存在しないことを証明したカントールの定理は背理法による証明が用いられている。

集合 X からその冪集合 2^X への写像 φ : X -> 2^X において、つぎのような集合 Y = { x ∈ X : x /∈ φ(x) } に対応する x ∈ X は存在しない。なぜなら、x /∈Y ならば x ∈ Y でなければならないし、x /∈ Y ならば x ∈ Y にならなければならなくなるのでパラドックスが生じるからだ。

確かに X から 2^X への全単射があると仮定すると矛盾が生じるので、そのような全単射はないと結論付けられるが、背理法の問題点はこの全単射の全体像が見えないということだ。

たとえば、集合 X = {a, b, c} とそれ自身のべき集合と全単射していると仮定する。そうして a に対する X の集合を a' で表すようにすると {a, b, c} と a', b', c' との間に次のような対照表を作ることができるはずだ。

** a b c

a' 1 0 0

b' 1 0 1

c' 1 1 0

この対照表の行はどの集合が列のどの要素を要素として含んでいるかを表している。たとえば a' は a を要素として含んでいるが、b, c は含んでいない。すなわち a -> a' = {a} である。

ここで対照表の対角線分は写像で a が対応する a' に含まれているかどうかを表している。上の例では a ∈ a'、b /∈ b', c /∈ c' である。カントールの定理に現れる集合 Y があったとすると a /∈ Y, b ∈ Y, c ∈ Y である。これは a は含まれず、ｂ は含まれ、c は含まれるということだから Y 0 1 1 となるような数列が行に現れるはずだ。ところで 0 1 1 という数列は対角成分を反転させてできている。したがって、a', b', c' のどの行とも一致しないので Y はこの対照表には表れない。

また、仮に Y が b' と一致していたとしよう。すると (b', b) の値は１にならなければならないはずだが、もとの表から (b', b) は０ であるはずだから矛盾する。なぜなら (b', b) = 0 だからこそ b ∈ Y なのだが、この場合 (Y, b) = (b' b) = 1 にならなければならないからだ。これは Y が a' であると仮定しても、c' であると仮定しても同じように矛盾が生じる。

パラドックスが発生するということは、そのような行の数列が対照表のなかには見つけられないということと同じなのだ。

背理法では Y 0 1 1 という数列が対照表の行には現れないということは証明するが、それでは 0 1 1 が表す集合 {b, c} はどこに行ったのかということまでは示してくれない。

実際、上の対照表に現れるべき数列は、X = {a, b, c} の要素数をはるかに超えて 2^3 = 8 もあるのである。

Prelude> table = [[x1,x2,x3] | x1 <- [0,1], x2 <- [0,1], x3 <- [0,1]]
Prelude> table
[[0,0,0],[0,0,1],[0,1,0],[0,1,1],[1,0,0],[1,0,1],[1,1,0],[1,1,1]]
Prelude> mapM_ print table
[0,0,0]
[0,0,1]
[0,1,0]
[0,1,1]
[1,0,0]
[1,0,1]
[1,1,0]
[1,1,1]

3 × 3 の対照表ではそのごく一部しか表現できない。3×3の対照表では表現できなかった 0 1 1 という集合も、非対称な表を考えればちゃんとその中に入っている。このように対角線論法は8ある可能性の3つだけを取り上げて対照表を作り、表現できない集合があると主張しているにすぎない。確かに正しいのだが不十分な観察だ。

有限集合だからそれは明白かもしれないが、カントールの定理は無限集合について証明したから重要なのだという主張もあるだろう。しかし、上の対照表はもちろん無限に拡張することができるが、それにつれて、対照表に記述できない集合も無限に増えていくのだ。どんなに無限に対照表を拡張していったとしても、それが対照行列である限り、冪集合の全てを記載するには不足している。

対角線論法による論証は、冪集合の要素の全てについて考慮するのではなく、その一部を正方行列の対照表に押し込めた場合に成立する論理なのだ。

おなじことが、すべての集合の集合についてもいえる。全ての集合の集合にはその集合のべき集合も必然的に含まれてしまう。このような場合に、集合の全てを全ての集合の集合という対称行列に埋め込もうとすれば、ラッセルのパラドックスが発生するのは当然なのだ。集合を矛盾なく取り扱うためには、すべての集合の集合という領域の中ですべてを組み立てるという無理を通さずに、非対称な対照表のなかに集合を構築していけば、ラッセルのパラドックスのような矛盾は発生しないのではないだろうか。

公理的集合論の公理は、集合にとって自然なものではなく、技巧的に、上のような正方対照表のなかで集合を組み立てようとしているように見える。集合とそのべき集合の非対称性を受け入れれば、ラッセルのタイプ理論のほうが、集合の世界を自然に組み立てていけるような気がする。ラッセルのタイプ理論は煩雑で使い難いとのことのようだが、Haskell のような厳密な型を取り扱う言語が、意外に使い勝手が良いのを考慮に入れると、集合論をタイプ理論で使い勝手良く構築するというのもあるのではないかという気がする。

おそらく、問題点は、無限集合を「全ての集合の集合」のようなくくり方をするところにあるのではないか。どのような集合 X であっても、そのなかに冪集合の要素をかかえこむことはできないのに、全ての集合の集合のようなくくり方をすると、それをできるかのような取扱をすることになるからだ。その場合ラッセルのパラドックスが発生するのは当然だ。

安易な実無限の乱用が、集合に矛盾があるような推論を導いているのではないだろうか。

不動点とカリー化

集合 A について直積 A × A から集合 B への関数 ψ :: A × A -> B があるとする。ψ は ψ(x, y) と書くことができる。このとき、y の値を y0 に固定して、

g(x) = ψ(x, y0)

を定義することができる。g(x) は集合 A から B への関数である。g(x) は２変数関数 ψ(x, y) をカリー化して得られる１変数関数である。

また、カリー化ではないが ψ の対角成分 ψ(x,x) の値に注目した対角関数 diag :: A -> B を考えることもできる。diag は y の値には依存しないので、カリー化とは別の方法で２変数関数から作られる関数である。これは、次のように定義できる。

diag(x) = ψ(x,x)

ここで、集合 B から B への自己写像 f :: B -> B を考える。これと diag の合成関数は A -> B 型の関数になる。そこで、これを g(x) と等しい仮定すると、

g(x) = f(ψ(x,x))

と置ける。このとき x = y0 の場合を考えると、

g(y0) = f(ψ(y0, y0)) = ψ(y0, y0)

となる。ψ(y0, y0) は集合 B の要素で、これを b とおくと上の等式から

f(b) = b

となり、b は f の不動点でなければならない。もし f が不動点を持たない関数である場合、g(x) = f(ψ(x,x)) となるような g(x) は存在しない。

このことから２変数関数 ψ(x,y) をもとにした１変数関数で、カリー化できない場合があることがわかる。

対角線論法を Haskell で実験する

前回は対角線論法を図式化してみたが、頭の中だけで考えるのはしっくり行かなかったので対角線論法を Haskell で実験してみた。

まず A = {a, b, c, d} という集合について考えた。

Prelude> a = ["a","b","c","d"]

A の冪集合を作った。

Prelude> {power [] = [[]]; power (x:xs) = [x:ps | ps <- power xs] ++ power xs}
Prelude> power a
[["a","b","c","d"],["a","b","c"],["a","b","d"],["a","b"],["a","c","d"],["a","c"],["a","d"],["a"],["b","c","d"],["b","c"],["b","d"],["b"],["c","d"],["c"],["d"],[]]

A の直積 A × A を作った。

Prelude> [(x,y) | x <- a, y <- a]
[("a","a"),("a","b"),("a","c"),("a","d"),("b","a"),("b","b"),("b","c"),("b","d"),("c","a"),("c","b"),("c","c"),("c","d"),("d","a"),("d","b"),("d","c"),("d","d")]

ψ :: A × A -> {0, 1} の対照表にあらわれる可能な行を作成した。

Prelude> raws = [[x1,x2,x3,x4] | x1<-[0,1],x2<-[0,1],x3<-[0,1],x4<-[0,1]]
Prelude> raws
[[0,0,0,0],[0,0,0,1],[0,0,1,0],[0,0,1,1],[0,1,0,0],[0,1,0,1],[0,1,1,0],[0,1,1,1],[1,0,0,0],[1,0,0,1],[1,0,1,0],[1,0,1,1],[1,1,0,0],[1,1,0,1],[1,1,1,0],[1,1,1,1]]

A × A の表の行数は 4 しかないが、そこに現れる可能性のある行は 2^4 = 16 ある。A × A の表ではそのほんの一部しか取り上げることはできない。冪集合の要素の全てを A × A の表に載せることはできない。表には現れない集合はたくさんある。

そのうちから４つを選ばないといけないが、面倒なので機械に助言してもらった。

Prelude> import System.Random
Prelude System.Random> candidate = take 20 $ randomRs (0,15) (mkStdGen 7)
Prelude System.Random> candidate
[11,8,3,10,0,11,0,1,9,3,15,11,9,13,14,5,1,9,4,10]

そこで、raws の 11, 8, 3, 10 の要素を使って A × A の対照表を作った。

Prelude System.Random> table = [raws !! x | x <- [11,8,3,10]]
Prelude System.Random> table
[[1,0,1,1],[1,0,0,0],[0,0,1,1],[1,0,1,0]]

この対照表の対角線部分から数列を作った。

Prelude System.Random> diagonal = zipWith (!!) table [0..]
Prelude System.Random> diagonal
[1,0,1,0]

この数列が対照表の行の中に現れるかどうかを検証した。

Prelude System.Random> elem diagonal table
True

たしかに table の４行目が [1,0,1,0] だ。

今度は対角線成分のビットを反転させてみた。

Prelude System.Random> {invert 0 = 1; invert 1 = 0}
Prelude System.Random> inverted = map invert diagonal
Prelude System.Random> inverted
[0,1,0,1]

これが対照表のなかに現れるかどうかを見てみたがなかった。

Prelude System.Random> elem inverted table
False

対照表 table とは対角線の部分で必ず異なるので当然といえば当然だ。これが対角線論法の推論だが、どの行も対角線部分で異なると考えるから、対照表が無限になってもそれに含まれない行が存在するというイメージがなんとなく受け入れがたい感じがする。

前回の記事では、対角線部分をビット反転した数列が対照表の行に現れたと仮定しても、対角線と行の交点でビット演算の不動点が生じるので、ビット反転の場合は不動点ができず、そのような数列は A × A の表には現れることがないと考えた。この方ががイメージ的には納得しやすい。

この実験でわかるように、冪集合の要素の数は幾何級数で増えていくのにたいし、対照表の行数が算術級数的にしか増加しないから対照表に収めることができない集合の数は、集合 A の要素が増えるに従って膨大なものになる。

また、ビット反転した対角線成分は対照表の中には現れることはできないが、これが表す A の部分集合と、対照表の中の行で表される集合との集合演算は可能だ。集合 A の部分集合のうち対照表に現れないものはクラスとして、集合との集合演算ができる。むしろ、集合 A の冪集合はクラスの集合と考え、いわゆる集合はクラスの一部分で対照表に載せることができるものを指すと考えたほうがいいのではないだろうか。

また、対照表は集合が他の集合を要素として含むかどうか ψ(x,y) を表している。しかし、上の実験は集合の全体を集合と集合の所属関係 ψ(x,y) で全て表すことはできないことを示している。