無限はいつまでたっても極められないという性質がある。例えば自然数の集合では最大の数と言うものは考えられない。どんなに大きな数 N を考えても N + 1 がそれより大きい自然数として存在すからである。従って、自然数の要素を「全て」数えつくすことはできない。数えつくしたと思っても常にその先がまだあるのである。
このような無限の要素を含んだ集合の要素全体とは何だろうか。数えつくすことができないのにどうしてその要素全てを把握することができるのだろうか。確かに無限の要素を数えつくすことはできない。しかし、任意の要素をとりあげてその要素がある性質を満たすか満たさないか言うことができれば無限の要素を持った集合を「間接的に」定義することができるとは考えられないだろうか。つまり、無限集合の全ての要素について確定的に述べることはできないが、ある性質の要素を集めたものとして無限集合を「確定的に」定めることができるのではないかと言うことである。
実際自然数の集合は次のような再帰的定義で「確定的に」定義されているように見える
1) 1 は自然数である
2) n が 自然数であれば n + 1 は自然数である
3) 上の方法で得られるもののみが自然数である。
この定義法には「全て」という言葉が含まれてはいない。しかし任意の要素について上の定義を満たすかどうかは簡単に検証することができる。従って全ての自然数を集めた集合はこの帰納的定義によって完全に定義されると考えることができる。また、見方を変えると、全ての自然数を列挙することは確かにできないが、上の帰納的定義を１回適用する毎に新しい要素が一個発生する。従って、この定義を無限回発生させてできる要素の全体を自然数全ての集合と考えようということである。
このように定義すると厳めしいが、要するに小石を１つずつどこまでも一列に並べていくところを想像すれば良い。偶数や順序対など可算な無限集合は結局この小石のように無限に一列に並べていくことができる。
それでは自然数の冪集合の全体とはどのようなものだろうか。自然数の部分集合は簡単に作ることができる。例えば {1, 2, 5} のようなものである。しかし、自然数の部分集合全てを集めた集合はどのように定義したら良いのだろうか。冪集合の要素は先の例のように確定的なものもあるが、無限の要素を持つものもある。従ってこのような集合を表すために特性関数 f(n) というものを導入しよう、これは正規な用語ではなく著者が勝手に導入したものである。自然数の集合の部分集合 F が n という要素を含むときには F に対応する特性関数の値は f(n) = 1 であり、n という要素を含まないときは f(n) = 0 であるとする。するとこの特性関数は集合 F にたいし一意的に決まる。また、逆に、特性関数が分かっていればそれに対応する集合 F を定めることもできる。したがって、自然数の集合の部分集合全体の集まりを考えるのではなく、この特性関数の集合を考えることによって冪集合の要素全体の性質を知ることができる。
この特性関数の全てを集めた集合を考えるためにはまず、これをシステマチックに定める方法が必要である。自然数全体を定義するときの帰納的定義のようなものが欲しい。そこで次のような帰納的定義を考える。
1) f(1) = 1 または f(1) = 0 のとき f(x) は x <= 1 の範囲で特性関数である。 2) f(x) が x <= n の範囲で特性関数であるとき f(n+1) = 1 または f(n+1) = 0 であれば f(x) は x <= n+1 の範囲で特性関数である。
3) 上の 1) 2) を満たすもののみが特性関数である。
この操作を図示するとつぎのような二分木になる
.
f(1) 1 0
f(2) 1 0 1 0
f(3) 1 0 1 0 1 0 1 0
: ....................
f(n) ....................
: ....................
このような二分木を無限に作り作り続けて行ったときにその木の枝の経路の一つが個々の特性関数を表し、全ての経路を集めたものが特性関数の全体となり自然数の冪集合を表していると考えられる。こうして f(x) を x が無限大になるまで定義したものが冪集合の一つの要素の特性関数になる。しかし、ここで考えておかないと行けないのは f(x) をほんとうに「一つの要素」として考えて良いかどうかと云う事である。簡単に f(x) を無限大まで定義したものと言ってしまったが、無限大と言うのは本質的に決定不能なのである。f(x) は充分に大きな数 N までは他の特性関数から区別することができるが f(N+1) については不定なのである。N をどんどん大きくして行くことでどんどん詳細に検討することができるが、しかし、f(x) が他のどの特性関数とも異なっているかどうかはどんな大きな N をもってしても保証できないのである。
集合{1, 2, 3} が個としてイメージできることから、無限集合の特性関数 f(x) (とそれによって表される集合) も個として存在できるように感じるが、f(x) をある１つの無限集合だけを表すものとすることは不可能なのである。f(x) は常にある無限集合のグループを示唆できるにすぎないのである。f(x)は常にある複数の無限集合を含んでいる。つまり x <= N までは f(x) と同じ振舞をする特性関数のグループである。f(x) が単一の集合を表し得ないことは上の二分木からも分かる。すなわち、f(x) がすべての x で 0 となるような特性関数に対応する集合は空集合であるが、上の二分木では空集合の隣の枝は x が無限大のときに f(x) = 1 とならなければならない。このような集合を空集合と区別する方法はないのである。こう考えると、1 と 0.9999.... が同じものであるかどうかと言う議論も違った観点から考えることが出来るのではないだろうか、1 と 0.9999.... は明らかに違う数なのである。なぜなら 1 位の数が一致していないからである。しかしその差を求めることはできない。その差は小数点下無限大で 1 にならなければならないからである。
それではこの特性関数 f(x) を用いて自然数の集合とその冪集合の全単射ができないことを確かめてみよう。かりに冪集合と自然数の集合の全単射ができたとして、自然数 1, 2, ..., n, ... に対応する冪集合の要素を F1, F2, ..., Fn, ... とし、それぞれの特性関数を f1(x), f2(x), ..., fn(x), ... とする。ここで各冪集合に対応する自然数のうち、n not ∈ Fn となるような数(この場合明らかに fn(n) = 0 である)を集めた集合 G を考える。G = { m1, m2, ..., m, ... } とすると fm1(m1) = 0, である。そこで G に対応する m が G の要素ではないとすると gm(m) = 0 であるが、これは m が G の要素であることを示しているので矛盾である。同様に m が G の要素であるとしても矛盾が起きる。したがって、G に対応する m は存在しない。
自然数集合と実数集合の全単射がないことの証明は上の方法とは異なるように見える。ところが、f(1), f(2), f(3), ..., f(n), ... のように特性関数の値を並べたものは二進数で表現した 0 以上 1 未満の実数と全単射で対応させることができるから、f(x)を１つの実数と同一視してもよい。このときに自然数と実数との全単射について論じた対角線論法はどうなるだろうか。そこで、1, 2, ..., n, ... に対応する特性関数(すなわち実数)を f1(x), f2(x), ..., fn(x), ... としたとき、次のような特性関数 g(x) を考える。すなわち、fn(n) = 0 のとき g(n) = 1、fn(n) = 1 のとき g(n) = 0 となるとする。このようにすると g(x) はどの fn(x) とも違う関数となる。なぜならどのような n に対しても g(n) != fn(n) なので g(x) = fn(x) とはならないからである。ところが、全ての自然数は fn(x) に対応づけられているので、g(x) に対応する自然数 n を見つけることはできない。ところで、特性関数 g(x) に対応する集合 G とはどのような集合だろうか G = { m1, m2, ..., m, ... } であるとする。すると m1 が G の要素であるためには g(m1) = 1 である。ところが仮定からこの場合には fm1(m1) = 0 となる。すなわち m1 not ∈ Fm1 である。したがって、G は「対応する冪集合には要素として含まれない自然数」を集めた集合となり、上で述べた G と同じものになるのである。
つまり、自然数集合とその冪集合の対角線論法も、自然数と実数の対角線論法も実は全く同じ議論であったのだ。
このように自然数の集合と冪集合の全単射が不可能なのは対角線論法からあきらかであるが、どうしてそう言うことが起きるのだろうか。それは、上でも述べたように、冪集合の１つの要素だけを特性関数では表現するのが不可能なために起こる現象なのではないだろうか。{1, 2} のように明らかに一個の集合と認められるような場合でさえ、上で述べた特性関数の定義では {1, 2, ∞} のように、1 と 2 以外に無限大も要素とする集合との区別ができないのである。したがって、どんな場合も特性関数 f(x) は冪集合の一個の要素だけを表すことが出来ず、要素の集合しか表すことができないのである。対角線論法で自然数に対応づけられた冪集合の要素は一個の要素ではなく、要素の集合なのだ。それにも関わらず自然数と一個の冪集合を対応させることができると仮定してしまったために対応づけ不可能な冪集合の要素を作りだしてしまったのではないだろうか。
また、上の対角線論法では、自然数と実数の全単射をつくってしまった「後」になお自然数に対応づけることのできない数 g(x) が存在するというような議論になっているが、無限の対応づけを完了してしまうということができるのだろうか。g(x) は x = 1, 2, ..., N についてはたしかに自然数と対応づけられてはいない。しかし、N までであれば g(x) はある実数の集合を代表しているのであって、たった１つの実数を表しているのではないのである。つまり x = N 以下に無限の選択子がある。従って fN(x) と異なる数を見つけることが必ず可能なのである。この事情は N がどのように大きくなってもかわらない。自然数 N の次に来る数は N+1 １つだけだが 小数点下 N 桁以下の g(x) の取り得る値は無限なのである。つまり、N をどのように大きくしていっても、g(x) はいつまでも単一の数ではなく数の集合を表しているのに過ぎないのである。
こういう訳で、自然数とその冪集合はそれぞれが帰納的な定義で要素を生成するときの自由度の違いのために全単射のアルゴリズムを見つけることができないのである。また、無限小数と言うものは単一の数を表すのではなく、数の集合を表すことしかできない。x であったものが x + dx に変化するという連続の性質は、x が常にある範囲を持った数でなければ矛盾が起きてしまうのである。
このことに関して思いつくのはゼノンの「飛ぶ矢は静止している」というパラドックスである。これは「飛んでいる矢はある瞬間には静止している。時間は瞬間の集合だから矢はすべての時間静止している。」という議論である。しかし瞬間と言うものが時間の一点ではなく常にある範囲の時間を合わせ持っていると考えると、静止した矢の瞬間と運動している矢の瞬間が同じものではないと考えることが出来る。すなわち、ある瞬間の矢は常に位置と速度(無限小時間における位置の変化率)という二つの要素を合わせ持っているのである。
自然数集合とその冪集合の全単射ができないことは納得できるが、つぎのような疑問が発生するのは自然だろう。つまり、「自然数集合とその冪集合ではどのくらい要素数が違うのだろうか。全単射で対応づけることのできない自然数集合の部分集合は一個だけなのだろうかそれとも無限に存在するのだろうか。」という質問である。
ところで、自然数と冪集合の関係はそのまま、自然数と実数の関係に置き換えることができるのは上で述べた通りである。したがって、その問題については自然数と実数の対応関係を考えるのが便利である。
例えば 0 から 1 までの実数のうち自然数と対応づけられたものの集合を A としよう。A の要素は全単射で自然数と対応づけられているのでひとつとして同じ数はない。そこでこの A の要素を小さい方から整列してみる。そうすると整列した A の要素は隣同士の数が異なっているため必ずその間に自然数と対応づけられていない 0 から 1 の範囲に含まれる実数を見つけることができる。したがって、自然数と対応づけることのできない実数は無限にあるのである。