カントールの対角線論法 - 数えられない無限があるということ

無限にはいくつかの「大きさ」があり、しかもそのあいだには決して埋まらない差がある――19世紀末、ゲオルク・カントールはこの驚くべき事実を、対角線論法と呼ばれる一つの巧妙な議論によって証明しました。自然数を数えるように、整数も、分数(有理数)も、実は自然数と「同じ大きさ」の無限でしかないのに対して、小数で表される実数の全体は、それよりも真に大きな無限になっている、というのがこの論法の結論です。

この記事では、高校数学までの知識を前提として、まず無限どうしの大きさを比べるとはどういうことかを一対一対応という考え方から確認したうえで、対角線論法の中心である「実数は数えられない」という証明を一歩ずつたどります。そのうえで、この論法がより一般に「どんな集合も、その部分集合をすべて集めたもの(べき集合)より真に小さい」という形に一般化できること、そしてカントール自身が解決できなかった連続体仮説という問いへとつながっていくことを順に見ていきます。

無限を比べるとはどういうことか - 一対一の対応

個数を数えるとはどういうことか

私たちが「りんごが5個ある」と言うとき、実際にやっていることは、りんご一つひとつに「1」「2」「3」「4」「5」という数を、重複も抜けもなく割り振っていく作業です。この、ものの集まりと数とのあいだに、抜けも重なりもない対応をつけることを「一対一対応」と呼びます。有限個のものを数えるかぎり、この作業はいつか終わり、最後に割り振った数がそのまま個数になります。

無限集合どうしを比べる - 一対一対応という道具

では、要素が無限個ある集まりどうしの「大きさ」を比べたいときはどうすればよいでしょうか。無限個のものを一つずつ数え上げて「全部で何個」と言うことはできません。そこでカントールは、有限の場合の考え方をそのまま無限へ拡張し、「二つの集合のあいだに、抜けも重なりもない一対一の対応がつけられるならば、その二つの集合は同じ大きさ(濃度)を持つ」と定義することにしました。この定義の利点は、要素を最後まで数え終える必要が一切なく、対応のルールさえ与えられればよい、という点にあります。

たとえば自然数全体1, 2, 3, 4, …と、偶数全体2, 4, 6, 8, …を考えてみます。一見すると偶数は自然数の半分しかないように思えますが、n番目の自然数nに対して偶数2nを対応させるというルールを使えば、自然数と偶数のあいだに抜けも重なりもない一対一対応がつきます。この定義に従うかぎり、自然数全体と偶数全体は「同じ大きさ」の無限だということになります。無限を相手にすると、部分が全体と同じ大きさになりうる、という有限の世界にはない事態が起こるのです。

整数も有理数も自然数と「同じ大きさ」

この考え方を推し進めると、一見もっと「たくさんありそう」な集合も、実は自然数と同じ大きさであることが分かります。整数全体0, 1, -1, 2, -2, 3, -3, …は、0, 1, -1, 2, -2, …という順番で並べ直せば、1番目、2番目、3番目、…と自然数に対応づけることができます。

もっと驚くべきなのは、分数(0でない整数を分母とする有理数)の全体もまた、自然数と同じ大きさだという事実です。すべての分子・分母の組み合わせを、たとえば分子と分母の和が小さいものから順に、格子状に並べて斜めに数え上げていけば(カントールが実際に使った方法です)、どの分数もいつかは何番目かとして数えられる順番に並べ直すことができます。二つの整数のあいだには無限に多くの分数が詰まっているにもかかわらず、分数全体はやはり自然数と同じ「数えられる無限」にすぎないのです。このように、自然数との一対一対応がつけられる無限を「可算無限」と呼びます。

実数は数えられない - 対角線論法

背理法の準備 - 実数を並べられたと仮定する

自然数、整数、有理数がすべて可算無限だとすると、次に気になるのは、小数で表される実数全体もやはり可算無限なのだろうか、という問いです。カントールは1891年に発表した論文のなかで、これに「否」と答える証明を与えました。これが対角線論法です。

証明は背理法で進みます。話を単純にするため、実数全体ではなく、0より大きく1より小さい実数、たとえば0.3540921…や0.1000000…といった数だけを考えることにします(実数全体が数えられないことは、ここから容易に導けます)。もしこの範囲の実数全体が可算無限であり、自然数と一対一に対応づけられる、すなわちすべて漏れなく1番目、2番目、3番目、…という順番に並べられると仮定します。それぞれの実数を無限に続く小数として、次のように書き並べたとします。

1番目: 0. a11 a12 a13 a14 …
2番目: 0. a21 a22 a23 a24 …
3番目: 0. a31 a32 a33 a34 …
4番目: 0. a41 a42 a43 a44 …
   ⋮

ここでaijはi番目の実数の小数第j位の数字を表します。この表には、0と1のあいだのすべての実数が、一つの漏れもなく現れているはずだ、というのが今の仮定です。

対角線をずらして新しい数をつくる

ここでカントールは、この表の対角線上に並んだ数字a11, a22, a33, a44, …(1番目の数の小数第1位、2番目の数の小数第2位、3番目の数の小数第3位、…)に注目します。そしてこれらの数字を一つずつずらすことで、新しい数Nを次のように作ります。

Nの小数第i位の数字bi を、「aiiが5ならば4、aiiが5でなければ5」というルールで決め、N = 0.b1b2b3b4…とします。

こうして作られた数Nは、表のどの実数とも異なることが保証されています。なぜなら、Nと1番目の実数は小数第1位で異なり(b1はa11と違う数字になるように選んである)、Nと2番目の実数は小数第2位で異なり、同様にNとi番目の実数は小数第i位で必ず異なるからです。表の中に並んだどの実数を持ってきても、Nはその実数と少なくとも一桁は違う数字を持っているので、Nはこの表のどこにも現れていない新しい実数だということになります。

端っこの処理 - 0や9が続く場合の注意

ここで一つだけ、細かいけれど重要な注意点があります。小数の表し方には、0.5000…と0.4999…のように、同じ実数に二通りの小数表示が存在してしまう場合があります(このように末尾が0だけ、あるいは9だけがずっと続く場合に限って、この重複が起こります)。もし新しい数Nの各桁biを不用意に選んでしまうと、Nの小数表示が実は表の中のどれかの数の「もう一つの表し方」に一致してしまい、証明が崩れてしまう恐れがあります。

先ほど示したルール、「aiiが5ならば4、そうでなければ5」を使うと、Nの各桁は必ず4か5になり、0や9が並ぶことは決してありません。したがってNの小数表示はただ一通りに定まり、この重複の心配が生じないことが保証されます。この一見些細な工夫が、対角線論法を厳密な証明として成立させるために欠かせない部分です。

矛盾の発生 - ゆえに実数は数えられない

さて、Nは0と1のあいだの実数であり、確かに一つの実数として存在します。ところが最初の仮定では、0と1のあいだの実数はすべて、先ほどの表のなかに1番目、2番目、3番目、…として漏れなく並んでいるはずでした。しかしNは、表のどの実数とも(対角線上での構成により)異なることが示されています。これは、「すべての実数が表に並んでいる」という最初の仮定と真っ向から矛盾します。

したがって、0と1のあいだの実数全体を、自然数と一対一に対応づけて数え上げることはできない、という結論が導かれます。実数全体は、自然数・整数・有理数とは異なり、可算無限ではないのです。これが対角線論法の核心です。

対角線論法が明らかにしたこと - 無限にも大きさの違いがある

可算無限と非可算無限

この証明が示しているのは、単に「実数はたくさんある」という漠然とした事実ではありません。自然数と一対一に対応づけられない無限、すなわち「可算無限より真に大きい無限」が実際に存在する、という点が重要です。このような、自然数と対応づけられない無限を「非可算無限」と呼び、実数全体の大きさは「連続体の濃度」と呼ばれます。可算無限を表す記号として、カントールはヘブライ文字の最初の文字であるアレフを使い、最小の無限をℵ₀(アレフゼロ)と名づけました。自然数・整数・有理数はいずれもこのℵ₀の大きさを持ち、実数はそれよりも真に大きな濃度を持つことになります。

なぜ「対角線」なのか - 論法の名前の由来

この論法が「対角線論法」と呼ばれるのは、先ほどの表においてa11, a22, a33, …という、表の左上から右下へと斜めに並ぶ対角線上の数字だけを取り出して新しい数を作った、という手続きに由来します。表全体をすみずみまで調べなくても、対角線上の一列だけを見て、それをずらすという単純な操作から、表の外側に出てしまう新しい要素を作り出せる、という発想の鮮やかさが、この論法が数学のなかで特別な地位を占め続けている理由の一つです。

べき集合への一般化 - カントールの定理

べき集合とは何か

カントールは対角線論法の考え方を、実数だけでなく、もっと一般的な状況にも適用できることを示しました。そのために必要なのが「べき集合」という概念です。ある集合Aに対して、Aの部分集合(Aの要素の一部、あるいは全部、あるいは一つも含まない空集合)をすべて集めてきたものを、Aのべき集合と呼びます。

たとえばA = {1, 2, 3}という3個の要素からなる集合を考えると、その部分集合は、空集合{}、一個の要素からなる{1}、{2}、{3}、二個の要素からなる{1,2}、{1,3}、{2,3}、そして全体である{1,2,3}の、合わせて8個です。要素数がnの有限集合のべき集合は、必ず2ⁿ個の部分集合を持ちます(それぞれの要素について「含む・含まない」の2通りの選択肢があるためです)。3個の要素に対して2³ = 8個ですから、べき集合はもとの集合よりも必ず大きくなります。

どんな集合も自分自身より真に大きいべき集合を持つ

カントールが証明したのは、この「べき集合の方が真に大きい」という関係が、有限集合だけでなく、自然数全体のような無限集合についても成り立つ、という一般的な定理でした(カントールの定理と呼ばれます)。証明の骨格は、実数の場合の対角線論法とまったく同じ発想に基づいています。

いま、ある集合Aから、そのべき集合への一対一対応(すべての部分集合が、Aのどれか一つの要素にきちんと対応づけられる対応)が存在すると仮定します。つまり、Aの各要素aに対して、Aの部分集合f(a)が一つずつ割り当てられ、しかもすべての部分集合がどれかのf(a)として現れるとします。ここで、次のような特別な部分集合Dを考えます。

Dとは、「aがAの要素であって、しかもaがf(a)には含まれていない」という条件を満たすaだけを集めた部分集合です。

Dは確かにAの一つの部分集合ですから、最初の仮定により、DはあるAの要素dに対応するf(d)として、必ずどこかに現れているはずです。すなわちD = f(d)となるdが存在します。ではこのdについて、「dはDに含まれるか」と問うてみましょう。

もしdがDに含まれるなら、Dの定義(f(a)に含まれないaを集めたもの)により、dはf(d)には含まれません。ところがD = f(d)なので、dはDに含まれないことになり、「dはDに含まれる」という最初の仮定と矛盾します。

逆にもしdがDに含まれないなら、D = f(d)なのでdはf(d)に含まれず、これはまさにDの定義(f(a)に含まれないaを集めたもの)を満たすので、dはDに含まれることになり、やはり「dはDに含まれない」という仮定と矛盾します。

dがDに含まれても含まれなくても矛盾が生じてしまうため、最初の仮定、すなわち「AからAのべき集合への一対一対応が存在する」という仮定そのものが誤りだったということになります。したがって、どんな集合Aについても、そのべき集合はAよりも真に大きい、という結論が得られます。この証明のなかで、部分集合Dを「aがf(a)に含まれるかどうか」で作っている部分が、実数の場合に「i番目の実数のi桁目と一致するかどうか」で新しい数の桁を決めていたことと、まったく同じ対角線の発想になっていることに注意してください。

無限に続く無限の階層

この定理を自然数全体の集合ℕに当てはめると、ℕのべき集合はℕよりも真に大きく、さらにそのべき集合(べき集合のべき集合)はもっと大きく、これがどこまでも続いていきます。つまり、「もっとも大きな無限」というものは存在せず、ある無限が与えられれば、そのべき集合を取ることで、必ずそれよりも真に大きな無限を作り出すことができるのです。実は、自然数のべき集合の大きさは、ちょうど実数全体の大きさ(連続体の濃度)と一致することが知られており、この意味で実数の非可算性の証明とべき集合の定理は、同じ一つの構造の二つの現れだと言うことができます。

連続体仮説 - カントールが解けなかった問い

自然数の無限と実数の無限のあいだ

自然数の濃度ℵ₀と、実数の濃度(連続体の濃度)という、少なくとも二種類の異なる無限の大きさが存在することを示したカントールは、次に、この二つのあいだに、ちょうど中間の大きさを持つ集合が存在するのかどうかを問いました。カントールは、そのような中間の大きさは存在しない、すなわち自然数より真に大きく実数より真に小さい濃度は存在しないはずだ、と予想しました。これが「連続体仮説」です。

カントールは生涯をかけてこの仮説を証明しようと試み続けましたが、ついに証明することはできませんでした。1900年、ダフィット・ヒルベルトはパリの国際数学者会議において、20世紀の数学が取り組むべき23の問題を提示しましたが、連続体仮説はその記念すべき第1問に選ばれています。

独立性という思いがけない結末

連続体仮説の運命が明らかになったのは、それから数十年後のことでした。1940年、クルト・ゲーデルは、連続体仮説を「偽である」と証明することは、集合論の標準的な公理系(ツェルメロ=フレンケルの公理系)からは不可能であることを示しました。続いて1963年、ポール・コーエンは、逆に連続体仮説を「真である」と証明することもまた、同じ公理系からは不可能であることを示しました。

この二つの結果を合わせると、連続体仮説は、標準的な公理系のもとでは、真であるとも偽であるとも証明できない、独立な命題だということになります。カントールが解けなかったのは、彼の力量が足りなかったからではなく、そもそも当時知られていた数学の公理系そのものが、この問いに答えを与えるだけの情報を持っていなかったからだったのです。

対角線論法とその後

対角線論法は、カントールが実数の非可算性を示すために考案した一つの証明技法にとどまらず、その後の数学と論理学に繰り返し現れる、きわめて息の長いアイデアとなりました。「あるものをすべて列挙・記述できると仮定し、その列挙・記述の手続き自身に手を加えることで、列挙・記述からこぼれ落ちる新しい対象を作り出す」というこの発想の型は、20世紀に入るとラッセルのパラドックスやゲーデルの不完全性定理、チューリングの停止問題といった、自己言及にまつわる数々の重要な定理のなかに、形を変えながら繰り返し立ち現れることになります。カントール自身は、自らのこの技法がのちにこれほど広い射程を持つことになるとは、おそらく想像していなかったでしょう。

結論

本稿では、ゲオルク・カントールが1891年に示した対角線論法を、高校数学までの知識を前提に一歩ずつたどってきました。自然数・整数・有理数がいずれも「同じ大きさ」の可算無限であるのに対して、実数全体は対角線論法によって、それよりも真に大きな非可算無限であることが証明されます。この論法はさらに、「どんな集合も、そのべき集合より真に小さい」というカントールの定理へと一般化され、無限には上限がなく無限個の異なる大きさが階層をなして存在することが明らかになります。そしてカントール自身が生涯をかけて挑み、ついに解くことのできなかった連続体仮説は、20世紀半ばのゲーデルとコーエンの仕事によって、標準的な公理系からは真とも偽とも証明できない独立な命題であることが判明しました。対角線論法は、無限という捉えどころのない対象に対して、人間の思考がどこまで厳密に切り込めるかを示した好例であると同時に、その切り込みの果てに、証明も反証もできない問いが待ち受けているという、数学の限界そのものをも同時に指し示しているのです。

参考文献