どうせなら厳密なほうがいい

第35話 超限帰納法 証明

二人は浴槽に浸かりながら話す。

「付き合って3年になるよね」

湾は壁を見ながら話しかける。

「そうだね」

「最近特に仲良くなれたような気がする」

「そうかな」

「うん。数学の話してるときの藍の顔はいつも輝いてるよ。なんで3年間全く数学の話しなかったんだろう？」

「全く…ではないと思うけど、記憶に残るようなことではなかったんだね」

「そうか。あんまり興味なかったのかな」

「湾が？そんなことはない。多分、私の方が数学について喋り続けるのが少し怖かったんだと思う」

「そうなの？」

「数学で盛り上がるのは、あまりマジョリティではない気がしてた」

「なんでうちら二人の間にマジョリティを持ち出すの？二人は二人、世界のどの二人とも違う二人でしょ。人間も、環境も、性格も。何から何まで。だったら、怖がらずに話しても良かったのに」

「別に怖がってたわけじゃないけど」

「そうかな」

「例えば、"超限帰納法"という言葉を出したら、何も知らない人なら"なんだ難しそうな専門用語だな"って思うに決まってるし、それで数学の話に蓋をされたらこまっちゃうからな」

「ε-N論法だってはじめは何のこと？って思ったけど、楽しく最後までできたよ」

「つまりまだ私は湾の魅力を全部はわかってなかったってことだ」

「惚れなおした？」

「月並みに言えば、そうかな」

ふたりは身体を流しながら話を続ける。

「超限帰納法を証明と言ったけど、超限帰納法は公理ではないの？」

「公理ではない。証明できる」

「数学的帰納法は証明はできないわけか」

「ペアノの公理ではそうだね。いまは実はペアノの公理を使っているのではなくZFCという公理を使っている。でもZFCはまだやっていないから、あまり深く突っ込むことはできない。そのうち、しっかりZFCをやろう」

「わかった」

風呂から上がると、さっそく藍はノートに超限帰納法を確認する。

(A,≺)を整列集合とする。P(x)を任意のAの要素xで定義された述語とする。

このとき、次が成り立つ。

∀x,y∈A((y≺x→P(y))→P(x))→∀z∈A(P(z))

「やっぱり読みにくいから具体例がほしい」

「具体例を作るのは難しいから、先に主張とその証明を理解してしまおう。大丈夫、あとでいくらでも超限帰納法を使う場面は出てくる」

藍は一息おいて続ける。

「数学的帰納法では、自然数全体の命題を証明するために、2つのステップ

・0において成り立つこと

・kで成り立つならk+1でも成り立つこと

を証明すればよかった。

これに対して、超限帰納法では、整列集合における命題を証明するために、

・x未満において成り立つなら、xにおいても成り立つ

を証明すればよい」

「0というか、整列集合の最小の要素について言及する必要はないの？」

「言及する必要はない…というか、この一つの条件に内包されている。論理式を見ればわかる」

藍はノートに目を向け、式の一部を指さす。

(y≺x→P(y))→P(x)

「この部分が、"x未満において成り立つならxも成り立つ"を表している部分だけども、xが最小の要素なら、y≺xを満たすyは存在しない。

y≺x→P(y)

のy≺xが常に成り立たないので、この式全体は常に成り立つ。つまり、

(y≺x→P(y))→P(x)

この式においては、y≺x→P(y)が常に成り立つから、P(x)が成り立たなければ式全体は成り立たない。だから、xが最小の要素であれば、P(x)が成り立つことは条件になっている」

「そもそもx未満の要素はないから、xは成り立たないといけないってことだね」

「そして、超限帰納法全体の式の意味はこうだ」

∀x,y∈A　

xとyはAの要素とする。

((y≺x→P(y))→P(x))

どんなxに対しても、x未満の要素yに対してPが成り立つなら、xに対してもPが成り立つ

→

という条件が成り立つならば

∀z∈A(P(z))

Aの全ての要素についてPは成り立つ

「なるほど。順序数は整列集合で、順序数の要素はものすごくたくさんあるのに、簡単な条件だけで全て成り立つことが証明できるのはすごいね」

「そう。そして、超限帰納法の証明はそこまで難しくない。背理法をつかう」

「背理法？」

「命題φを証明するために、￢φを仮定して、何らかの命題Qと￢Qを証明できたらφが証明できたことになる、という論法。簡単にいうと、その命題が成り立たないとすると矛盾するなら、成り立つということだ」

「ああ、高校生のときにやったかな」

「では、超限帰納法の否定を仮定しよう。形式的にはこうだ」

￢(∀x,y∈A((y≺x→P(y))→P(x))→∀z∈A(P(z)))

↔

∀x,y∈A((y≺x→P(y))→P(x))∧￢(∀z∈A(P(z)))

↔

∀x,y∈A((y≺x→P(y))→P(x))∧∃z∈A(￢P(z))

「つまり、超限帰納法の条件が成り立つにもかかわらず、Pが成り立たないAの要素が存在する、ってことだね」

「そう。そして、具体的に矛盾を作ろう。

まず、整列集合Aに対して、Pが成り立たない、つまり￢P(x)を満たすx全体の集合をBとしよう。超限帰納法の否定が仮定されているので、Bは空集合ではない。Aは整列集合なので、空集合ではない部分集合は必ず最小元を持つので、それをbとしよう」

「整列集合の定義だね」

「そう。そして、P(b)は成り立つ？成り立たない？」

「bはPが成り立たない集合の要素だから、当然成り立たないよ」

「よし。では、これを書いておこう」

藍はノートに書く。

￢P(b)

「ではその次に、b未満の要素についてPが成り立つかどうか確認しよう」

「bはPが成り立たない集合の最小元だから、これより小さい要素はPが成り立つね」

「その通り。しかし、超限帰納法、つまりPの条件はこうだった」

藍はノートを見返す。

∀x,y∈A(

(y≺x→P(y))→P(x)

x未満の要素yに対してPが成り立つなら、xに対してもPが成り立つ

「そして、b未満のAのどんな要素に対してもPが成り立つのだから、P(b)が成り立たなければならない」

「つまりこういうことだね」

次は、湾がノートに書く。

P(b)

「これで、背理法が成立したね」

湾は少し嬉しそうに言う。そして、二つの式を並べる。

￢P(b)

P(b)

「その通り」

「あれ？でもちょっとまって」

「どうかした？」

「これ、bがAの最小元でも大丈夫？」

「大丈夫。なぜならb未満の要素に対してPが成り立つというのは真なので、同じくP(b)が成り立つ」

「あ、さっきやったやつだね」

「そういうこと」

「なんか証明は簡単といえばたしかに簡単な気がする…これをどうやって使っていくの？」

「よし、例えば順序数の和の結合法則を証明しよう。湾はできるかな？」

問題　α,β,γを順序数とする。次の式をγに対する超限帰納法で証明せよ

α+(β+γ)=(α+β)+γ