福西です。

『無限論の教室』(野矢茂樹、講談社現代新書)を読んでいます。

「第5週」(p60~84)を3週にわたって読み、2進数と対角線論法を学びました。

対角線論法は、オセロの駒を使うのが分かりやすかったです。

1 ●〇〇〇

2 〇〇〇●

3 ●●〇〇

4 〇〇〇〇

のように、適当に「異なる」パターンを作ります。

そして次に、上の4つと異なるパターン5を作ります。(どこかが1か所でも違っていれば別のパターンとみなします)

全部で16パターンあるので、残り12パターンのうちから1つを探すわけですが、それを機械的にできるのが、以下の方法です。

1)1~4までの対角線上にある駒を持ってきて並べる。

 〇

  〇

   〇

2)そしてそれを裏返す。(これがミソです)

〇●●● =5

できあがり。

実際、

5(〇●●●)は、
その左はしで、1(●〇〇〇)の左はしと少なくとも異なり、
その左から2番目で、2(〇〇〇●)の左から2番目と少なくとも異なり、
その左から3番目で、3(●●〇〇)の左から3番目と少なくとも異なり、
その右はしで、4(〇〇〇〇)の右はしと少なくとも異なっています。

だって、そのように作ったからです(裏返したから当たり前)。

そして、この有限での「当たり前」を自然に延長し、駒を無限個に増やしても同じように言えることが、対角線方法の利点です。

1 ●〇〇〇……

2 〇〇〇●……

3 ●●〇〇……

4 〇〇〇〇……

……

n 〇〇●●……

に対しても、対角線から成分を持ってきて、それを裏返したものをn+1とすれば、必ず1~nと異なるパターンが作れる。それはn→∞でも保証される。

これが対角線論法です。すごい切り口だと思います。

これによって、「自然数と実数は1対1対応できる」と仮定して作った(詳しくはテキスト参照)、上のオセロのような自然数の集合には、+1個目が現れてしまいます。あれ? 一対一対応してたら、漏れがないはずじゃないの? そうか、1対1対応できるという仮定がそもそも間違っていたんだ! ということになり、自然数と実数は同じ無限個でも、濃度が違う(一対一対応できない)ことが言えました。

次回は、「第六週」を読みます。

 

【おまけ】

2進数の話の脱線で、次のような計算もしました。

偶数=0、奇数=1として、1桁ずつさいころをふり、4桁の数を作る(たとえば0110)。これを16セット行う。1回も同じパターンが出ない確率はいくらか?

正解は、16/16×15/16×14/16×…×3/16×2/16×1/16

=20922789888000/18446744073709551616

=0.00000113…

≒100万回に1回

試行したところ、受講生の二人とも5セット目で同じパターンが出ました。

Share