Otaku ワールドへようこそ![257]想像の限界を突破する論理の力
── GrowHair ──

投稿:  著者:



数学で無限を扱おうとする際に、ちょろっ、ちょろっと気配を漂わせる悪魔について話をしてきました。今回は、シリーズ第6回目になります。

いよいよお待ちかねの、でもないかもしれませんが、カントールの「対角線論法」の話を今回します。シリーズのひとつの核心です。

有限な存在たるわれわれには想像の域外にある無限の世界ですが、さらにいっそう想像の及ばない、無限を超えた無限の世界が存在していることを示すものです。

想像の力では霧の向こうであっても、論理の力をもってすれば、その世界の扉を開けることができてしまったというわけです。想像力よりも論理力のほうが、見通す射程が長いというのも、ちょっと意外な感じがしますけども。

証明の筋道に論理の穴が空いていないことを確認できた後においても、われわれは自転車の乗り方を体得したときのような「自分のものになった」という感覚をもって、血肉化することは、けっしてできません。

「納得いかないけど、証明されちゃったもんはしょうがない」と屈する気持ちで受け容れる以外にないのです。

数学って往々にして、そんなもんです。





●これまでのおさらい

集合の「濃度」という概念を覚えてますか? 集合Aと集合Bとの濃度が等しいとは、集合Aの各要素と集合Bの各要素との間に、過不足なく、一対一の対応づけができることを言うのでした。

扱う集合が有限集合の場合、「濃度」は「要素の個数」と呼び替えても問題ありません。呼び替えていいなら呼び替えたほうが簡単なわけで、「濃度」という概念が本領を発揮するのは無限集合に対してです。

たとえば、集合Aを自然数の集合Nそのものとしましょう。要素を書き並べる形で表記すると、

  A = {1, 2, 3, 4, 5, 6, 7, ...}

です。次に、Bを0以上の整数からなる集合としましょう。集合Nに、0という要
素を追加した集合です。つまり、

  B = {0, 1, 2, 3, 4, 5, 6, ...}

です。

さて、集合Aの各要素と、集合Bの各要素との間に、次のような対応づけを考えてみましょう。

  1 ∈ A と 0 ∈ B とを対応させ、
  2 ∈ A と 1 ∈ B とを対応させ、
  3 ∈ A と 2 ∈ B とを対応させ、
  4 ∈ A と 3 ∈ B とを対応させ、
  5 ∈ A と 4 ∈ B とを対応させ、
  ...

そうすると、上記点々々の部分はどこまでも続けることができ、双方の集合の要素間を過不足なく対応づけることができています。なので、集合Aと集合Bとは濃度が等しいことが確認できたということになります。

自然数の集合Nと濃度が等しい集合を「可算無限集合」と呼びます。いま、集合Bが可算無限集合であることが証明された、というわけです。

ところで、集合Bは、集合Aに要素を一個追加してできた集合でした。ということは、「要素の個数」という考え方をすれば、一個分だけ増えている勘定になるはずです。

この一個の違いは、上記対応づけにおいて、点々々の中に消えてしまいました。

可算無限に1を足したぐらいでは焼け石に水で、ちっとも増えていかないということです。

で、ヒルベルトの「可算無限ホテル」のようなたとえ話が出てくるわけです。可算無限個の客室を備えたホテルが満室状態だったところへ、新たに旅人が一人やってきて「泊めてくれ」と言うので、部屋を一個ずつずれてもらい、空室を作り出すことができ、無事泊まることができた、という話です。

可算無限個の客室を備えたホテルとか、可算無限人の宿泊客とか、現実に引き寄せて想像しようとすると頭が痛くなってきますけど。無限に広い土地をどこに確保するか、とか、無限の食糧をどこからどうやって調達するか、とか、考えないほうがいいです。

さて、可算無限は1を足したくらいじゃ、ちっとも増えていきませんでしたが、2倍したらどうでしょう。これでも増えていかないことをみてきました。2倍して増えなければ、3倍しても4倍しても増えません。

では、2乗したらどうでしょう。これまた増えませんでした。ということは、3乗しても4乗しても増えません。

では、2の肩に載せて、2の可算無限乗だったらどうだろうか、というのが前回までの話です。

この場合も、やっぱり増えていかないということを示すことができたようにみえたのですが、それはニセの証明であって、論理の欠陥があることが明らかになりました。

ここまでが前回までの話で、じゃあ、本当のところはどうなんだ、って話を今回します。本題に入る前に、いろいろと準備をしておきます。

●対応づけいかんでどっちが多いようにも見せかけられる

上記の集合Aと集合Bに話を戻しましょう。どちらからも余りの要素が生じないように、要素間の対応づけができることを示しました。

ここで、別の対応づけを考えてみましょう。

  0 ∈ B には A の中に対応する相手がなく、
  1 ∈ A と 1 ∈ B とを対応させ、
  2 ∈ A と 2 ∈ B とを対応させ、
  3 ∈ A と 3 ∈ B とを対応させ、
  4 ∈ A と 4 ∈ B とを対応させ、
  5 ∈ A と 5 ∈ B とを対応させ、
  6 ∈ A と 6 ∈ B とを対応させ、
  ...

こうすると、集合Bの中に、余る要素が出て来るように見せかけることができています。

では、さらに別の対応づけを考えてみましょう。

  1 ∈ A には B の中に対応する相手がなく、
  2 ∈ A と 0 ∈ B とを対応させ、
  3 ∈ A と 1 ∈ B とを対応させ、
  4 ∈ A と 2 ∈ B とを対応させ、
  5 ∈ A と 3 ∈ B とを対応させ、
  6 ∈ A と 4 ∈ B とを対応させ、
  7 ∈ A と 5 ∈ B とを対応させ、
  ...

こうすると、今度は集合Aの中に、余る要素が出て来るように見せかけることができています。

有限集合だったら、どんな対応づけを考えようとも、要素の個数の多いほうが、その差分だけ必ず余ります。無限集合の場合、そうはなりません。

逆の見方をすると、対応づけいかんによって余ったり余らなかったりするのが、無限集合の特徴である、というふうにみることもできます。

対応づけいかんによって、一方の集合の要素が余るようにみえたとしても、どちらからも余りが出ないような対応づけのしかたが一通りでもあれば、濃度が等しいと言えます。

ここは大事なところです。

●濃度が等しくないことを証明するためには?

2つの集合の濃度が等しいことを言うためには、どちらからも余りが出ないような、要素間の一対一の対応づけをひとつ示せばよいのでした。

では逆に、2つの集合の濃度が等しくないことを言うためには、どんなことを示さなくてはならないのでしょうか。

2つの要素間の対応づけのしかたにはいろいろあるけど、どんな対応づけを持ってきても、必ず一方の側に余りが出ることを示さなくてはなりません。

これは大変です。無限集合が2つ与えられたとき、要素間の対応づけのしかたなんて、それこそ嫌になるくらいたくさんあって、ひとつひとつ、しらみつぶしに確認していく作業は不可能です。シラミが無限に涌いてくる状況というのは、あまり想像したくありませんが。

では、どうしたらいいのでしょう。こういうときのための強力な武器があります。その名を背理法といいます。

いまの状況は、こうです。2つの集合の濃度が等しいことを示すためには対応づけをひとつだけ示せばよかったのに対し、等しくないことを示すためには無限にある対応づけを全部調べ尽くさなくてはならないのでした。

こういうときは、話をひっくり返しちゃうと、一気にラクになります。

●背理法は無限を避けるための強力な武器

背後にオソロシイ無限が控えていたとしても、それをきれいに隠蔽してしまい、背後の無限の存在をまったく感じさせなくする魔法の手法があります。それが背理法です。

いま、命題Pを証明したいとします。でも、正攻法でいくと、無限の大海で溺れてしまうのが目にみえています。

背理法は、問題を背後から攻めます。命題Pの否定命題「Pではない」が正しいと暫定的に仮定するのです。

そこを出発点として、正しい論理にしたがって、論を進めていきます。それで、矛盾にぶち当たれば、一丁上がりです。

途中の論理の進め方が間違っていなければ、この矛盾が生じた原因は、最初の仮定が間違っていたからにほかなりません。

つまり、最初の仮定「Pではない」が間違っていたということで、よって、命題Pが証明された、というわけです。

●対角線論法の対角線とは?

「対角線」というと、ふつうは図形の話です。例えば、長方形があるとして、左上の頂点から右下の頂点へ、長方形の内部を通るように引かれた線分が対角線です。右上の頂点から左下の頂点へ引かれた線分も対角線です。

しかし、これから述べる「対角線論法」の対角線とは、それではなく、縦横に整列する数の並びについての話です。

例えば、9以下の自然数が下記のように配置されているとしましょう。配置される数の選択はまったく適当ですが。

  4 8 2 9 5 8 1 6 3 3 ...
  9 2 1 8 4 2 6 3 1 2 ...
  4 9 1 7 6 3 2 8 1 4 ...
  3 5 9 6 2 8 1 4 2 9 ...
  8 1 2 4 7 5 2 9 7 3 ...
  2 2 9 1 5 8 6 3 4 5 ...
  4 7 3 5 9 6 2 8 1 9 ...
  5 1 9 3 8 5 7 2 2 5 ...
  6 4 3 8 1 2 5 3 5 1 ...
  1 9 1 7 4 8 6 3 2 5 ,,,
  ...

ここで、対角線上にある数字というのは、1行(ライン)目の1列(カラム)目、2行目の2列目、3行目の3列目、... というふうに、行番号と列番号とが一致するところに配置された数字のことを言います。

では、上の配置で、対角線上の数字だけを残して、それ以外を記号 _ で置き換えてみましょう。

  4 _ _ _ _ _ _ _ _ _ ...
  _ 2 _ _ _ _ _ _ _ _ ...
  _ _ 1 _ _ _ _ _ _ _ ...
  _ _ _ 6 _ _ _ _ _ _ ...
  _ _ _ _ 7 _ _ _ _ _ ...
  _ _ _ _ _ 8 _ _ _ _ ...
  _ _ _ _ _ _ 2 _ _ _ ...
  _ _ _ _ _ _ _ 2 _ _ ...
  _ _ _ _ _ _ _ _ 5 _ ...
  _ _ _ _ _ _ _ _ _ 5 ...
  ...

数字が生き残っている場所、これが対角線です。

●これから証明したいこと

では、だんだんと本題に入っていきます。

すべての自然数からなる集合を集合Nとします。集合Nの部分集合の集合を考えます。これを集合2^Nと表記します。集合2^Nの要素には例えば次のようなものがあります。

  {1, 3, 4} ∈ 2^N

  {2, 4, 6, 8, 10, 12, 14, ...} ∈ 2^N

  N ∈ 2^N

  φ ∈ 2^N

    ただし、φ は空集合を表す。

集合2^Nは、集合Nと濃度が等しいということを“証明”したのが前々回です。でも、その証明は正しくないことを示したのが前回です。

しかし、これをもって、集合2^Nと集合Nとは濃度が等しくないと言えたということにはなりません。等しいという命題が正しいことを言おうとした、ある“証明”が間違っていることが指摘されただけであって、元の命題自体が正しいか正しくないかは、今の時点では不明です。

結論を先に言っちゃうと、この命題は正しくありません。つまり、集合2^Nの濃度は、集合Nの濃度よりも大きいのです。

これが、今から証明したい命題です。「集合2^Nと集合Nとは、濃度が等しくない」。

●表記を置き換える

自然数の集合Nの部分集合の集合2^Nのひとつひとつの要素を表記する際、上記の例のように、それの要素を書き並べる形式があります。これを最後まで押し通しても、やってやれないことはない気がしますけど、視覚的にごちゃごちゃします。

そこをスッキリさせるため、「0と1の並び」による表記に置き換えます。この表記の置き換えには、前回のニセの証明で用いた手が拝借できます。ただし、ちょっとした点で違いがあります。

前回は、ある自然数n以下のすべての自然数からなる集合Nnを考え、後からnを無限大へと持っていったのでした。で、そこがまずかったわけです。

今回は、最初っから、nを無限大にしておきます。つまり、集合Nから出発するのです。

集合2^Nの要素の例として、上記の

  {1, 3, 4} ∈ 2^N

を再び引き合いに出します。これは、「1があり、2がなく、3があり、4があり、5がなく、6がなく、7がなく、...」と言い換えることができます。

そこから、「1が」、「2が」、...の主語を省き、「あり」を1で置き換え、「なし」を0で置き換えると、次のような表記になります。

  1 0 1 1 0 0 0 ...

この表記置き換えの過程は、逆向きにたどることもできます。つまり、

  1 0 1 1 0 0 0 ...

という表記を見たとき、元の

  {1, 3, 4}

という表記に戻すことができます。

末尾に点々々がついているところが前回と違うところです。0と1の列が有限で終わっていないのです。

試しに集合2^Nの要素のいろいろな例に対して、表記を置き換えてみましょう。

  A0 = φ
  A1 = {1}
  A2 = {2}
  A3 = {1, 2}
  A4 = {3}
  A5 = {1, 3}
  A6 = {2, 3}
  A7 = {1, 2, 3}
  A8 = {4}
  E = {2, 4, 6, 8, 10, 12, 14, ...}

これらの例について、表記を置き換えると、

  A0: 0 0 0 0 0 0 0 0 0 ...
  A1: 1 0 0 0 0 0 0 0 0 ...
  A2: 0 1 0 0 0 0 0 0 0 ...
  A3: 1 1 0 0 0 0 0 0 0 ...
  A4: 0 0 1 0 0 0 0 0 0 ...
  A5: 1 0 1 0 0 0 0 0 0 ...
  A6: 0 1 1 0 0 0 0 0 0 ...
  A7: 1 1 1 0 0 0 0 0 0 ...
  A8: 0 0 0 1 0 0 0 0 0 ...
  E: 0 1 0 1 0 1 0 1 0 ...

となります。

集合2^Nのどんな要素が来ても、この形式に置き換えることが可能です。

つまり、集合2^Nの任意の要素は、「0と1からなる可算無限長の列」という形式に置き換え可能ということになります。縮めて「0/1可算無限列」とでも呼んでおきましょうか。

集合2^Nは、集合Nの部分集合すべてからなる集合なので、その要素を0/1可算無限列の表現に置き換えた場合、0と1の並びについて、すべての場合を尽くしていなくてはなりません。

●対角線論法を味見してみる

例のニセの証明について、どこに誤りがあるのか指摘せよ、という問題を前々回の最後に出題しています。

この問題自体は、いちおう自力で思いついたものです。もちろん、先に思いついてたって人は、きっと何十年も前からいるでしょうけど。

カントールの対角線論法は前から知っていたので、あのニセ証明を容認しちゃうと決定的に矛盾が起きてしまうので、けっして容認してはいけないのは分かっていました。

きっとどっかに間違いがあるはずだ、と。しかし、その間違いを発見するまでにずいぶんと時間がかかりました。七転八倒の苦悶の日々でした。

さて、同じ問題を、関根正幸氏にも聞いてみました。関根氏は、3月29日(火)から隔週くらいの頻度でデジクリに寄稿してくれており、高円寺の「岡画郎」(誤字ではない)のことなど、すでに5回書いています。

関根氏に聞いた時点で、私は正解を知っていました。自力で答えに至るのはあんなにたいへんだったけど、関根氏はどうだろう、と実力を試す魂胆でした。こういうのはものすごく失礼な態度で、中国には「鼎(かなえ)の軽重を問う」という故事があります。

関根氏は、3月にJR高円寺駅の北口から徒歩3分ほどのところにある「バー鳥渡(チョット)」で写真の個展を開催していました。3月3日(金)の夜、私が行ったとき、在廊(在バー?)していたので、聞いてみたってわけです。

即答でした。「対角線論法を適用してみれば、一発で分かるんじゃない?」。はい、仰せのとおりでございます。

私はいちおう早稲田大学の数学科で修士課程まで修了しているけれど、関根氏は東京大学理科一類からの数学専攻で、博士号を取得しています。格が違う、とはこのことです。

関根氏ご指摘の方法を、これからやってみましょう。

ニセ証明の論法では、0/1可算無限列を一行にひとつづつ書き出していき、すべての場合を書き尽せば、1行目に自然数1を割り当て、2行目に自然数2を割り当て、...と順番に番号を割り振っていくことができるので、自然数の集合Nとの間に一対一の対応づけができる、としていました。

その書き出し順を下記のように設定していました。すなわち、0/1可算無限列に対し、桁順をひっくり返し、それを自然数の二進表記とみなして、小さい順に並べていくというものでした。

実際に書き出すとどうなるか、それが上記の集合A0から集合A8までです。この調子でずっと続くわけですが。

では、これに対角線論法を適用してみる、とはどういうことでしょうか。

この論法の適用により、この並べ方では、すべての場合を尽くしていないではないか、というのが、はっきりと浮かび上がります。「ほら、ここに、数え忘れがあるではないか」と、具体的にその例をひとつあぶり出すことができるのです。

その手続きとは、下記のようなものです。

先ほどの集合A0から集合A8に対応する0/1可算無限列を、まず再掲しておきます。これは、A9, A10, ... と限りなく続きます。

  A0: 0 0 0 0 0 0 0 0 0 ...
  A1: 1 0 0 0 0 0 0 0 0 ...
  A2: 0 1 0 0 0 0 0 0 0 ...
  A3: 1 1 0 0 0 0 0 0 0 ...
  A4: 0 0 1 0 0 0 0 0 0 ...
  A5: 1 0 1 0 0 0 0 0 0 ...
  A6: 0 1 1 0 0 0 0 0 0 ...
  A7: 1 1 1 0 0 0 0 0 0 ...
  A8: 0 0 0 1 0 0 0 0 0 ...
  ...

これの対角成分だけを残して、それ以外を記号 _ で置き換えます。

  A0: 0 _ _ _ _ _ _ _ _ ...
  A1: _ 0 _ _ _ _ _ _ _ ...
  A2: _ _ 0 _ _ _ _ _ _ ...
  A3: _ _ _ 0 _ _ _ _ _ ...
  A4: _ _ _ _ 0 _ _ _ _ ...
  A5: _ _ _ _ _ 0 _ _ _ ...
  A6: _ _ _ _ _ _ 0 _ _ ...
  A7: _ _ _ _ _ _ _ 0 _ ...
  A8: _ _ _ _ _ _ _ _ 0 ...
  ...

生き残ったやつをつなげて、ひとつの0/1可算無限列を生成することができます。これをBとしておきましょう。

  B: 0 0 0 0 0 0 0 0 0 ...

次に、これに対して0と1の反転をかけます。つまり、1が出てきたら0に置き換え、0が出てきたら1に置き換えます。こうしてできたやつをCとしましょう。

  C: 1 1 1 1 1 1 1 1 1 ...

さて、得られた0/1可算無限列CをA0, A1, A2, ... それぞれと突き合わせてみましょう。

CはA0とは異なります。なぜなら1文字目が異なるから。
CはA1とは異なります。なぜなら2文字目が異なるから。
CはA2とは異なります。なぜなら3文字目が異なるから。
...

こうして、Cは、どれとも合致しないことが確認できます。

そーら、数え忘れですよー! 実際、Cを自然数の二進表記とみなすと、その自然数とは、プラス無限大になっちゃいます。つまり、対応する自然数がないってことです。

このCの表記を元に戻すと、

  C = {1, 2, 3, 4, 5, 6, 7, ...}

となります。つまりは、自然数の集合Nそのものです。

まとめると、上記のような書き並べ方をしたのでは、集合N自身が、間違いなく集合2^Nの要素であるにも関わらず、どこまで行っても決してリストに現れない、ってことになります。

だから、この書き並べ方では自然数との間に一対一の対応関係がとれておらず、集合2^Nの側には、集合Nに対して余る要素が生じている、というわけです。

いま見てきた手続きが、カントールの「対角線論法」の骨子です。

対角成分を拾い集めてBを作り、0と1とを反転してCを作ると、これはリストのどこにも現れていない新たな0/1可算無限列となるので、これを数え忘れてたでしょ、と指摘できるわけです。

ただし、今みてきたのは、関根氏の案にしたがって、例のニセ証明に対角線論法を当てはめることによって、数え忘れをあぶり出すことができたということだけです。

証明の全体像については、まだ何も言ってなく、それをこれから述べます。

●カントールによる証明

準備は整ったので、いよいよ核心に入ります。ここまでしっかり準備しておくと、案外、さらっと通り抜けられちゃいそうです。

証明したいことは、前述したとおりです。集合2^Nと集合Nとは、濃度が等しくない、と。

これを背理法で証明します。証明したいことの反対を暫定的に仮定します。つまり、集合2^Nと集合Nとは、濃度が等しい、と。

濃度が等しいということは、すなわち、集合2^Nの各要素と集合Nの各要素との間に一対一の対応づけができるということです。

そのような対応づけができているとき、自然数1に対応する集合2^Nの要素を1行目に書き出し、自然数2に対応する集合2^Nの要素を2行目に書き出し、...と続けることによって、集合2^Nのすべての要素を、可算無限の行に書き出すことができている、ということになります。

ここのところにしおりを挟んでおきます。☆みたいな。

さて、1行目にどのような要素が置かれているのか、具体的には分かりません。2行目も3行目も、それ以降も、同様です。しかし、濃度が等しいと仮定している以上、集合2^Nのなんらかの要素が、各行に配置することができているはずだ、というわけです。

集合2^Nの各要素は、0/1可算無限列による表記に置き換えることが可能であることは、さきほど見たとおりです。なので、各行に配置されている集合2^Nの要素を、0/1可算無限列表記に置き換えます。

これに、さきほどの手続きを適用します。つまり、対角成分を拾い集めて、ひとつの0/1可算無限列Bを作ります。それに対して、0/1反転を施して、0/1可算無限列Cを作ります。

すると、いま作った0/1可算無限列Cは、先ほどと同じ論理で、1行目とは1文字目が異なり、2行目とは2文字目が異なり、...という具合で、どの行とも異なることが分かります。

つまり、0/1可算無限列Cは、どの行にも表れてこない、ということになります。

さて、ここで、先ほどしおりを挟んでおいた☆の直前をもう一度見てみましょう。集合2^Nのすべての要素が書き出されていると言っています。

ところが、いま、0/1可算無限列Cは集合2^Nの要素でありながら、リストのどこにも表れていないと言っています。これは矛盾ですね。

よって背理法により、証明したい命題、すなわち、濃度が等しくない、が言えました。

以上、証明終わり。

●結局、何が言えたのか?

対角線論法による証明で言えたことは、集合2^Nと集合Nの要素間に一対一の対応づけをしようとどんなにがんばっても、集合2^Nの側に必ず余りが出てきちゃう、ということです。

言い換えると、集合2^Nの濃度は集合Nの濃度よりも大きい、ということです。

つまり、可算無限よりも大きい無限がある、ってことです。さしあたって、非可算無限と呼んでおきましょう。

ならば、それよりもさらに大きい無限っていうのは、あるのでしょうか。実はあります。いま得られた非可算無限を 2 の肩に載せてやると、これまた大きくなります。それをまた、...と繰り返すことができ、いくらでも大きいやつが出てきます。

いやはや、もう、なんか...、絶句しちゃいますね。

どうです? 想像の力の及ばない領域であっても、論理の力をもってすれば、突破できちゃうことがある、って感じ、お分かりいただけたでしょうか。

突破できたからといって、得られた成果を、感覚的にも把握して、自分のものへと還元したい、と望んでも、まあ、無理なんですけどね。

カントール、すげぇ! 大天才っ! これが発見されたのが 1891年と言われており、19世紀もそろそろ終わりに差しかかるころです。

われわれが、微分やら積分やらを、わずかに分かるとか、分かったつもり、とか言って苦闘していても、それってだいたいニュートン(1642-1727)とかライプニッツ(1646-1716)とかの功績であって、17世紀ごろの話です。

それなりに難解ではありますけど、数学の古典といいますか、古きよき時代の素朴な香りがします。

それに引き換え、20世紀に入るあたりから、数学もなんか、ちょっと、病んできちゃったかなぁ、という感じがします。

現代アートがあんなことになっちゃってることと、なんか関係あったりするんでしょうかね。


【GrowHair】GrowHair@yahoo.co.jp
セーラー服仙人カメコ。アイデンティティ拡散。
http://www.growhair-jk.com/


ここに書くネタもいろいろあったのですが、本文を書きすぎました。先送り。このところ、硬ーい数学ネタが続いたので、次回あたりは小ネタを拾い集めて、軽〜い感覚でいきましょうかね。

5月27日(土)、28日(日)の週末、大阪に行ってきました。レポートは後回しにして、写真だけ。
https://goo.gl/photos/B3ViPzjZmYx4sCv87