かかれていないことまでよみとらないこと!
昨日は眠るのが遅くなってしまったので起きるのが大変でしたが、頑張って起きて大学にゆきました。あと二回休んだらアウトですし。
図書館でM.Sipserの「計算理論の基礎」を借りました。良い本だと思います。なんというか海外の教科書って分厚いんだけどその分語りかけるような口調になっていて理解しやすいです。文章を読んでいるときって文に思考を奪われてしまういがちなのですけど、それを見越して、本文で考えてくれている感じ。理想としては、味も素っ気もない教科書からだって上手に内容を吸収できるようになりたいのだけど僕にはなかなか難しいです。読むことと考えることとを同時にやれないというか、平行してやっていると注意が分散してしまう。
その中にこんな問題があって、未だに納得がいっていません(頭が悪い)。
全ての馬は同じ毛色である,という以下の証明に対してその誤りをみつけよ.
主張:任意の頭の馬の集合に対して,すべての馬は同じ毛色である.
証明:に関する帰納法による.
基底:のとき.一頭の馬の集合を考えれば,すべての馬は明らかに同じ毛色である.
帰納法のステップ:に対して,のとき主張が真であると仮定し,のときにも主張が真であることを証明する.頭の馬を含む集合をとする.この集合に属するすべての馬が同じ毛色であることを示せばよい.集合から一頭取り除くと,ちょうど頭の馬が属する集合を得る.帰納法の仮定より,に属するすべての馬は同じ毛色である.次に,別の馬を取り除き,最初に取り除いた馬を戻して,別の集合を得る.同様に,に属するすべての馬は同じ毛色である.したがって,に属するすべての馬は同じ毛色でなければならない.以上が証明である.
明らかにおかしなことをやっているわけですが、しかしどこが本質的にまずいと指摘すればよいのかわからない。なんとなく、仮定からは集合の毛色と集合のそれが同じであることは導かれない点に不備があるのかなあと思っていて、しかし基底がおかしい気もする。ただ基底がおかしかったとしてどうしてではなく以上を使わねばならないのかきちんと説明することができないのです。ん、あーあーあー、やっぱり集合の毛色と集合の毛色が同じとは言えないことが原因っぽいですね。自己解決してしまった。わざわざ引用したのが無駄になってしまった感があるけれどまあはてブロでTeXの記法使うのちょっと楽しかったしまあいいや。