結城浩著、プログラマの数学を読んだ。
内容は高校数学程度のもので、2進数、論理、数学的帰納法、順列組み合わせ、再帰、背理法あたりは高校数学で出てきた記憶がある。
剰余と再帰はプログラマーならば誰でも知っているぐらいよく使うのだが、なぜか高校数学までの間に剰余と再帰を学んだ覚えはない。私の記憶では、除算を学び始めた頃は商と余りとを区別していたはずだが、その後、実数や分数がでて余りを意識しなくなってしまう。整数の商を求めるのが除算演算子なのだから、整数の余りを求める剰余演算子も小学校ぐらいで教えていい気がするのだが、なぜ日本の教育では剰余を教えないのだろう。数学的帰納法は再帰だと言われれば再帰ではある気がするが、再帰という概念は高校数学までにしっかりと出てきた記憶がない。パスカルの三角形は高校数学で出てきた気がするが、パスカルの三角形は組み合わせの再帰的定義で表現できるという話は出てきただろうか、記憶がない。
カウンタブルな集合というのは高校数学では出てこないが、整数列の集合や実数の集合がカウンタブルではないことの証明に、カントールの対角線論法が必要なのがよく分からなかった。というのも、別に対角線である必要はないように思われるからだ。例えば各実数の1番目とか2番めの数字を順番に並べた実数とかでもいいのではないか。なぜ対角線に取る必要があるのか。調べてみると、カントールの最初の証明は対角線論法を使っておらず、後に対角線論法を使った証明を思いつき、とても便利なので様々な証明に転用されているそうだ。
第二版では、機械学習の仕組みについて軽く触れている。
本の内容の半分ぐらいはすでに学んでいたことではあったが、改めて丁寧な説明を読むことで理解が深まる。
m≡n (mod p) やら鳩の巣原理やらは、数学オリンピックでは平気で出てくるけれど高校ではやらない数学の代表。
ReplyDelete我が国の高校数学が国際的に遅れている証左である。
実数でも順に列挙できる時点ではカウンタブルです。たとえばn乗根すべてを含む方程式の解の「代数的数」全部はカウンタブルですし、そこに有限個のπやeを混ぜてもカウンタブルでしかない。
ReplyDelete対角線論法において、たった1個足せばカウンタブルでないことが成立するのは、その足す対象が「任意の(どのような)」カウンタブル集合に対して成立するからです。
これはイプシロンデルタ論法と同じ、いくらゴールポストがずらされても成立させるための論理です。
プログラマの数学を読んでみましたが、対角線に取る必要があるとはどこにも書かれていませんでした。実際「すべての実数の表」のどこにも含まれないことを証明できるような取り方は無数にあります。なぜ対角線が必要だと思ったのでしょうか。
ReplyDelete対角線論法周りはトンデモの宝庫なので、書かれてもいないことを読み取るようなレベルでは自力で調べることはおすすめできません。C++の初学者がネットで適切な入門記事を探し当てるくらい無理ゲーです。
対角線論法は闇への入り口
ReplyDelete対角線論法の要点は「可算な全体集合」を考えた上で「全体集合に含まれないことが(一見)明らか」な元を容易に構成出来ることにあると思います。
ReplyDeleteしかし実数のn進小数展開は(限られたケースではありますが)一意ではない(十進で 0.0(9) = 0.1 など)ため、致命的な間違いではありませんがそれをちゃんと理解した上で使うべきです。
また背理法を要することも特徴でしょう。
一方で背理法を要さない(構成的な)証明も比較的容易に行うことが可能で、「任意の集合Xについて、XからXの冪集合への全射は存在しない」という基本的な定理から導かれます。
写像 f: X -> P(X) を考えて A = { x \in X | x \notin f(x) } なる集合をとります(f(x)はXの部分集合です)。
このとき x \in X が x \in f(x) であるならばAの元であるための条件を満たさないために x \notin A であり, f(x) は x を含み A は x を含まないので f(x) と A とは異なる集合です。
また x \notin f(x) ならば定義より直ちに x \in A なので同様に f(x) \neq A となります。
したがって上記で構成した集合 A は P(X) の元であるにもかかわらず f(X) (= Im(f)) に含まれないため、f: X -> P(X) は全射でないことが示されます。
あとは実数体Rと有理数体Qの冪集合とで濃度が等しいことを言えばよく、こちらも背理法を要さず構成的に示すことが出来ます。