« 補間式 | メイン | ケーニヒスベルクの橋 »

対角線論法

○●●○●●○○○●○…

の様に○と●をひたすら並べていくような無限に長い列を考える。このような列のすべてのパターンに対して1番、2番、3番、…と番号を割り振ることは可能だろうか。並べ方のパターンは無数にある、とは言え、振り分けるための番号だって無数にある。一概に可能とも不可能とも言えないではないか。

カントールは画期的な方法でこれが不可能であることを証明した。これが歴史に名高い「対角線論法」である。

仮にすべてのパターンに番号を割り振ったリストが存在したとしよう。それを下図のように並べてみよう。

1: ○●●●●●…
2: ○○●●●●…
3: ●○●○○●…
4: ●●○○○○…
5: ●●○●○●…
6: ○●●○●●…

このリストの左上から右下に向けての対角線上に並んでいる○と●の無限列を抽出する。こんな感じになる。

○○●○○● …

次にこの白と黒を完全に反転させた列を作ってみよう。

●●○●●○ …

こうして作られた列はこのリストの中のどのパターンとも一致しない。(その作り方をよく考えてみると明らかである。要するに「n番目の列」とは左からn番目の白黒が異なるようなパターンを作っている。) ところが最初のリストは「すべてのパターンに番号を割り振ったリスト」であったわけだからこれは辻褄が合わない。ここから導かれる結論はひとつ、そんなリストはこの世に存在し得ない。

うなづくしかない。単純でありながら、この切れ味。はじめて聞いたときはそれこそ目の白黒が反転するくらい感銘を受けた。

この列を実数の無限小数表示に置き換えて考えれば、上とほぼ同じ議論で「実数に背番号をつけることができない」ということが示される。実数の無限は自然数の無限より深淵なり。「誰もに無限の可能性がある」なんていうけど、その無限すら序列と無縁ではいられない厳しい格差社会なのだ。