第 8 章 無限集合
本章では無限集合と、無限集合に関する性質を証明するときに注意が必要な点を説明する。
ちょっと待った！ 「情報科学のための数学」で無限を考える理由などあるだろうか？ 結局、コンピューターが扱えるデータセットの大きさはコンピューターのメモリに制限される。そしてメモリの容量には制限がある: 宇宙が (少なくとも我々の目には) 有限であるのと同じ単純な理由である。それなのに、どうして大きさに制限のない無限集合など考えるのだろうか？ これは良い質問である。無限集合を避けては通れないとあなたを説得してみよう。
これまで意識してこなかったかもしれないが、本書では既に整数、有理数、無理数、そしてそれらの列を扱ってきた。これらは全て無限集合の要素である。あるいは、物理量の計測が有限の宇宙に対して有限の精度でしか行えないことを理由に物理学などの分野は実数の取り扱いを諦めるべきだろうか？ そういった巨大で曖昧な限界 (宇宙は今も大きくなり続けているらしい) を無視して実数を使う理論を受け入れた方が、ずっと説得力のある ── そして格段に単純な ── 結果が得られる。
同様に情報科学でも、夜空に浮かぶ星 ── 数十億個の星が含まれる銀河が数兆個あると言われている ── と同じだけの桁数を持つ二つの整数を加算するプログラムを、桁数に上限を設けない任意の二つの整数を加算するプログラムと区別する理由は存在しない。コンパイラの設計でも同じことが言える: 有限の宇宙でコンパイルされるプログラムが有限個しか存在しない事実を活用できないかと考えることは有用でもなければ賢明でもない。
というわけで、本章では覚悟を決めて無限について学んでほしい。