かなりいんちき。
ヒドラ対ヘラクレス戦のルール をてきとうに説明しておく。
ヘラクレスは1ターンに付き1つだけヒドラの頭を切り落とす事ができる。 nラウンドにヒドラの頭を切った時、 切った頭のすぐ下の首から上の部分がn+1個に分裂する。
1ラウンド目に首を切った時の例をあげておく。
そして、ヒドラの全ての首を切り落とせたらヘラクレスの勝ち、 いつまでたっても首が残ってしまう場合はヒドラの勝ちになる。
低い首は後回しにして高い首を先に切っていった方が良い事は 例からもわかる。 特に高さ1の首(1番下にある首)は切っても全く分裂が起きないので、 早いうちに切らずに、最後にまとめて切った方が良い。
逆に愚かなヘラクレスは、常に低い首から先に切っていくだろう (分裂によって低い首ができれば、必ずそちらを優先する)。
でも結局は、どんなヒドラと戦ってどんな風に首を切り落としていっても、 必ずヘラクレスが勝ってしまう。
以下その事を説明する。ただし正確な証明とかでは全く無い。
高さ1のヒドラの場合、高さ1の首がたくさんあるだけ。
この場合、ヒドラは全く分裂できないので全ての首を切り落とす事ができ、 ヘラクレスの勝ちとなる。
まず、高さ2の首のなかで1番簡単なもの(つまり頭が1つしかないもの) について考えてみる。 この首の頭を切り落とすと、高さ1の首がたくさん(ラウンド数+1)できる。
でも高さ1の首がどれだけできたとしても、地道に切っていけば良い。 またこの形の首が何本あっても、 結局は高さ1の首ができるだけなので、やっぱり全ての首を消す事ができる (正確には数学的帰納法で示す)。
次に高さ2で頭が2つある場合を考える。 この形の首の頭を切り落すと、 高さ2で頭1つの首がたくさんできる。
高さ2で頭1つの首がいくつあったとしても全て切り落とせる事は、 すでにわかっている。 なので高さ2で頭2つの首があっても勝つ事ができる。 そしてさっきと同じで、この形の首が何本あっても勝てる事もわかる。
さらに同様の事を繰り返していける。 高さ2で頭がk+1ある場合に頭を切り落とすと、 高さ2で頭がkある首がいくつもできる。
なので高さ2で頭がkの首がいくつあっても勝てれば、 高さ2で頭がk+1ある場合でも勝てる事がわかる。
数学的帰納法を使えば、 高さ2で頭が何個ある場合でも全て切り落とす事ができる事がいえる。
高さ2のヒドラは今まで出てきた首をいくつか並べたものだから、 高さ2のヒドラには必ず勝てる事がわかる。
もう面倒なので、高さ3の場合の初めだけを見る。
まず、高さ3の首で1番単純なのは頭が1つしかない首になる。 この場合、頭を切り落とすと高さが2になる。 という事は、全てを切り落とせるという事になる。
次に単純なのは、2段目から分岐してそこに頭がある場合になる。 この場合に下の頭を切ると高さ3で頭1つの首がたくさんできて、 それらを全て切り落とせる事はもうわかっている。
同じように考えていけば、 2段目から何個頭が出ていても それに勝てる事がわかる。
同様にしてうまく数学的帰納法を使っていけば、 高さ3以下のどんな形のヒドラにも勝てる事がわかる。
高さ4以上の場合も同じように数学的帰納法を使っていけば、 高さが高くなるほど証明が面倒にはなるけど、勝てる事が示せる。
ペアノ算術(PA)の体系では、再帰関数を扱う事ができる。 なのでヒドラを自然数でコード化してやって ヒドラ対ヘラクレス戦を扱う事ができる。 ヒドラの頭を切り落とすとどういう形になるのか、とか、 ヘラクレスがヒドラに勝つ、といった事はPAの式で書く事ができる。
ヒドラ対ヘラクレス戦では必ずヘラクレスが勝つというのを、 PAの式で書く事ができる。でも、その式はPAで証明する事ができない。 つまり独立命題となっている。
PAには数学的帰納法の公理があるので、上と同じような事を行なえば、 高さk以下のヒドラに必ず勝つ事は証明できる。 にもかかわらず、どんなヒドラにも必ず勝つというのは証明できない。
次のようにすれば証明できるように思える。 高さk以下のヒドラに必ず勝てる事を使って、 高さk+1以下のヒドラに必ず勝てる事を証明する。 そして数学的帰納法を使えば、どんなヒドラにも勝てる事が証明できる。
でもこれはうまくいかない。 具体的に数nが与えられた時、高さn以下のヒドラに必ず勝てる事を使って、 高さn+1以下のヒドラに必ず勝てる事は証明できる。 でも一般的なkに対して同様の事を証明する事は、 少なくともPAの枠組のなかではできない。 そのためPAでは、 ヘラクレスは、どんなヒドラにも必ず勝つという事が証明できない。
具体的な高さが与えられたりヒドラの形が具体的に与えられた時に、 その高さより低いどんなヒドラについても勝てるだとか、 そのヒドラには勝てる、というのは証明できるけど。
木に対してε_0より小さい順序数を対応させられる事がわかっていると、 順序数に無限下降列が無い事から ヘラクレスが必ずヒドラに勝てる事がわかる。 もっと正確にいえば、ε_0までの超限帰納法を使えば、 ヘラクレスが必ずヒドラに勝てる事を証明できる。
もちろんε_0までの超限帰納法から、PAの無矛盾性の証明ができる。 逆に言えば、PAではε_0までの超限帰納法は使えないという事でもある。
ε_0まで超限帰納法の正当化と自然数論の無矛盾性については
を、ヒドラ対ヘラクレス戦とそれがPAで証明できない事は
を参照。