シーン1: 研究発表へのコメント
「では，コメントさせてもらってよろしいですか」
「はいお願いします」
「処理手順が3ステップで書かれているスライドですが…」
「えっと…これですね?」
「そうです．2番目のステップに変数が一つ入っていますが，これは特定の1個の値ではなくて，何らかの値の集合があって，そのそれぞれについて処理をしようということですね」
「あ…そうです」
「その結果を，最後にソートして出力する，と」
「はい」
「手順の書き方として，そこが分かりにくかったんです．どう書けばいいのかな，少々古い表記法だと，2番目のステップの先頭に「∀p」と書くというのもあります．まあプログラミングで言うと，foreachなんですけどね」
「あ，そうなんですか」
「もちろん使用するプログラミング言語によります」
シーン2: 対角線論法の詭弁
「対角線論法は，どこかの授業で学習しましたか?」
「はい」
「それを使って，どんなことを証明しました?」
「実数の集合が，整数の集合よりも多いという説明，だったと思います」
「言葉は厳密さに欠けてるけど，おおよそそんなんですね．少々丁寧に書くと，0以上1以下の実数全体の集合が，自然数全体の集合よりも濃度として真に大きいことを，カントールの対角線論法を用いて証明できます((記憶に間違いがなければ，この命題について対角線論法を用いない証明が先にあったことを，今年，梅田の旭屋書店の，上のフロアで立ち読みしたことがあります．買って手元に置いていたらと，少々公開しています．))」
「あ…はい」
「カントールはもちろん，人名です．濃度という言葉は，大丈夫ですか?」
「はい，えっと，有限集合なら要素数を数えられますが，無限集合の場合には要素数ではなく…あれ? 何をするんでしたっけ」
「二つの無限集合があるとき，それらの間の全単射が存在すれば，同じ濃度と考えます」
「あ! 全単射でしたね」
「用語はそれでよかったでしたか．学生時代に読んだ本では，双射と書いて，全単射と区別してたりするんですけどね．全単射が存在せず，真の包含関係があるときに，濃度に大小をつけることができます」
「あの，先生…」
「何でしょう」
「『0以上1以下の実数全体の集合』と『自然数全体の集合』って，重なるところがほんの少ししかないんですけど」
「ああ，真の包含関係という言い方に，引っかかった? 『0以上1以下の実数全体の集合』というのは，ある全単射によって，数学的な意味での関数を一つ用意すればよかったんだったかな，『実数全体の集合』と同じ濃度だと分かります．そうすれば，『自然数全体の集合』をみな含んでいますよね」
「なるほど，分かりました」
「さて，カントールの対角線論法をうろ覚えという状態で，こんな証明問題を考えてみてください」
「はい?」
「自然数全体を，順に並べます．並べ方は何でもかまいません」
「任意，ですね」
「そうです．そして，それぞれの数の2進数表記を考えます．i番目の数の，最下位から数えてjビット目の値を，b_ijと表記することにします」
「ビーのアイ・ジェイですね．分かりました」
「これからは『最下位から数えて』を省略することにしますね．さてここで，xという自然数を作ることにします．具体的には，b_ii，すなわちi番目の数のiビット目の値が，0なら，xのiビット目の値を1とし，i番目の数のiビット目の値が，1なら，xのiビット目の値を0とします」
「あれ…対角線論法ですか?」
「そうです．こうするとxは，並べた1番目の数と違います．1ビット目の値が違いますからね」
「2番目の数とも違うし…xとi番目の数とを比較すると，iビット目の値が違うので，一致しない．だからxは並べたどの数とも違う?」
「ええ．ということで何が言えるのかというと，自然数全体からなる集合について，並べてみたものの，そこに現われない自然数が存在する，したがって，自然数全体の集合が，自然数全体の集合よりも大きな濃度になるという証明なのです」
「いやその結論は何かおかしいです」
「はい，実際，間違った証明方法です」
「気持ち悪いんで，ちょっと考えさせてください（紙に0と1の行列を書いていく…）」
「おかしなところは，見つかりましたか?」
「たぶんここではないかと…」
「言ってみてください」
「xが本当に自然数であるかのチェックが抜けているような」
「そこですね．でも，納得していない顔ですよ」
「はい．並べ方が任意なので，ある条件ではxが自然数にならないけど，別の条件ではxが自然数ってもいいのかなと思うと，どうおかしいと言えばいいのか分からないのです」
「じゃ，解説してみますか．カントールの対角線論法には，背景となるロジックがあります．議論を簡単にするため，集合Sと書くとして，これが，可付番集合でないことを証明するとして，そのロジックを確認することにしますか」
「かふばんしゅうごう？？」
「英語でいうとcountable setです．自然数全体からなる集合と同じ濃度の集合のことです」
「なるほど，了解しました」
「Sが可付番集合であると仮定します．背理法です．そして1番目はこれ，2番目はこれ，と，Sの要素を並べていきます」
「列挙，ですね」
「そうです．その列挙されたものに対して，どの要素とも違うけれど，Sに属する要素というのを作れば，ないのにあるってどないなっとんねん，で矛盾．Q.E.D.です」
「はい」
「ここに全称記号が隠れています」
「え? えっと…」
「Sの要素の並べ方です．対角線論法が成立するには，『どのような並べ方に対しても』，その並べ方に応じて，Sの要素なのだけれども，並べられているどの要素とも違う，したがってSの要素ではない，そんなのが存在することを示す必要があるのです」
「並べ方が，全称?」
「全称量化または全称化と言います．並べ方というのは，Sから自然数全体への全単射です．写像に∀をつけるのが気持ち悪いと思うなら，写像の代わりに，{(1,1番目の値),(2,2番目の値),(3,3番目の値),...}という集合を想像してください」
「そういう，写像の代わりになるどんな集合に対しても，とするわけですか」
「そうです．さて…対角線論法の命題と，その対偶を，書いてみてくれますか」
「はい，対角線論法が…あれ?」
「言い忘れた．命題を書くときには，対角線論法という言葉は現れません．あと，自然数全体からなる集合を，Nと書くことにしましょう」
「分かりました．NからSへの任意の全単射に対して，Sの要素xが存在して，その全単射に基づきxがSのどの要素でもないなら，SはNよりも大きな濃度である，ですか」
「うん．濃度は明示せず，『Sは可付番集合でない』のほうがスマートかな」
「あ，はい」
「その対偶を書いてください」
「えっと…Sが可付番集合であるなら，NからSへの全単射が存在して，任意のSの要素xに対して，その全単射に基づきxはSのどこかの要素である」
「そうです．“ならば”も，うまく処理できましたね*1」
「はい，離散数学の科目で，何問もやりましたので」
「了解．さてこれを，さっきの，『自然数全体の集合が，自然数全体の集合よりも大きな濃度になるという証明』に当てはめてみてください」
「はい…対象とする集合は実際にはNなんですが，『NからNへの全単射』と書くと混乱するので，Sのままにしておきます」
「そうですね」
「それで，NからSへの全単射が存在して…?」
「何か一つでいいから見つけてきて，その後ろに書いた性質を満たしてくれればいいのです．ここでは恒等写像でかまいません．集合で書くと{(1,1),(2,2),(3,3),...}です」
「恒等写像ですか…」
「そうしたときに，先ほどの，どのビットとも違うというxは，どんな値になりますか?」
「えっと，最初の値は1で，1の1番目のビットが1なので，xの最下位ビットは反転して0です」
「そうですね．次は?」
「最初の値は2で，2進数にすると10ですから，2の2番目のビットが1．xの2番目のビットは反転して0です」
「あと2，3個，言ってください」
「3番目の値は3で，2進数にすると11ですから，3の3番目のビットは0．xの3番目のビットは反転して1．4番目の値は3で，2進数にすると100ですから，4の4番目のビットは0．xの4番目のビットは反転して1．5番目の値は5で，101の5番目のビットは0．xの5番目のビットは反転して1」
「それでいいでしょう．そこからあとで，xのi番目のビットが0になることはありますか?」
「ないですね．対角線のところに，『1』が来そうにありませんから」
「そうです．これでまあ，この問題での対角線論法の詭弁を論破したようなものですが，もう少し確認しておきましょう．3番目のビットが1，4番目も，5番目も，ずっとずっと1というxを考えたとして，その値はいくつですか」
「無限の等比級数の和で，無限大になります」
「そうですね，発散しますね．すると，xはSに属しますか?」
「しません」
「対角線論法の対偶として，言ったことに当てはめると，どうなりますか?」
「はい…『任意のSの要素xに対して』に反する，ということですね」
「そうです．恒等写像に基づく並べ方の場合，対角線論法の方法で要素xを決めると，それはもとの集合Sには属さないので，Sが可付番集合であることを証明したいときには，そんなxは除外してよいのです」
元ネタ
シーン1は，今週火曜日の小ゼミのコメントです．本当に言いたかったのは（たぶん本人と指導教員にも伝わったと思いますが），1番目ステップの処理が，ステップ2以降のforeachすなわちループの外にあることでした．
シーン2は，NAISTでM1のときの勉強会でした．複数の研究室の人が集まり，講義室を借りて，当番を決めて発表をしました．学術的というよりは技術的なものでした．私の番になったときに，プログラミング関連ではほかの参加者が満足できるトピックを出すのが難しいと考え，数理論理学として，学部時代に学んだことを整理してみました．本論の最後は対角線論法と，それを用いた停止性問題の決定不能性（任意のプログラムと入力を与えたときに，そのプログラムがその入力をとって実行したら停止するか否かを，判定できないこと）の略証でした．おしまいのところに，ちょっと考えてみてくださいとして，上の詭弁の問題だけ書いていたのですが，解答まで書くのは今回が初めてです．
（最終更新：2013-11-08 晩．「すべての実数全体の集合」を「実数全体の集合」に変更しました）
*1:念のため，必要な性質を並べておきますと，X→Yの対偶は¬Y→¬Xです．¬∀x P(x)は∃x ¬P(x)，¬∃x P(x)は∀x ¬P(x)と等価です．
