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

第22話 整列集合

「じゃあ、自然数は整列集合である、という話でもしようか」

「ちょっと待ってください、和音さん」

「どうしたの？」

「ここでそんな話するのも少し変というか」

「そう？」

「仕事の話をしに来たんですよね」

「まあ建前上はね。でもこんな面白そうな話転がってるから。それに五十藤さんが数学好きだってこと知らなかったから少し嬉しくなっちゃう」

「数学好き…というわけでもないですよ」

「数学好きでもない人が、こんなに深夜にペアノ算術いじるかなあ」

「これは私の恋人との話ですから」

「五十藤さんの恋人さん、数学好きなの？」

「はい、好きだと思いますね。数学の話をしてる時は楽しそうで、私も楽しくなります」

「そうか」

和音は周囲を見渡した。照明は煌々と光り、仮眠をとっている人はアイマスクをしている。話したい人は会話スペースに行って話している。

和音は小声で話し続ける。

「でも、数学に恋愛感情も嫉妬もないでしょ。ここで数学の話をしたとこで五十藤さんの恋人さんが嫉妬するとも思えないけど」

湾は、それはそうかな、とも思ったが、実際のところよくわからないので黙っていた。それに、数学は深く心を動かすものと藍は言っていたし、思いついた公式を額縁に入れて飾ろう、なんて恋人としかできない発想だとも思う。

「黙ってるね。まあいいじゃない。五十藤さんの恋人さんが、この後整数や有理数を構築するかもしれないし、自然数を拡張するかもしれないし、もしくはまた全然別の何かを考えるかもしれないけど、ここでは自然数が整列集合であることをやろう。会話スペースに行こう」

「まいったな…」

和音の押しの強さをわかり始めた湾は観念したように会話スペースに向かった。

「まず、次の命題を理解しよう」

近くにあるメモ用紙に和音が書く。

自然数のみを要素にもついかなる集合Aも最小元をもつ

「最小元ってなんですか」

「ある集合の中で、それより小さい要素が無い、というような要素。例えば」

{1,3,4,6}

の最小元は1

{…,-3,-2,-1,0,1,2}

は最小元を持たない

「どう？」

「まあわかりますよ。つまりこういうことですよね」

∀A(∀x((x∈A→x∈ℕ)→∃y∈A(∀z∈A(y=z∨y<z))))

和音は心底驚いた。

「もしかして、この話題はすでに五十藤さんご存知だったかな」

「いや、整列集合も、最小元も初めて聞きましたよ」

「じゃあなんでこんな式すぐ書けるの？」

「意味を考えればいけますよね。

"自然数のみを要素にもついかなる集合A"だから、"Aの要素ならば自然数である"

と言って、

"集合Aは最小元を持つ"、ということは、"最小元yが存在する"

と言って、

最小元とは、"どんなAの要素も、その要素より小さいことは無い"、つまり、"Aの全ての要素zに対して、最小元yと比べて等しいまたはそれより大きい"

と言えば良い。

ってことですよね」

「五十藤さんはいつ数学始めたの？」

「この話題が始まったのはつい二日前くらいですよ」

「それでこの理解力はすごい」

湾は少しずつ得意になってきた。こんな論理式を自力で書けるようになったこともそうだし、それを外部の人に褒められるというのも初めての体験だからだ。

「だけれど、今から示したいことは、実はこの論理式ではない」

「あれ？間違ってましたか？」

「まあ、そうだな。間違っている。少なくともこの式は偽だ」

「偽…成り立たないってことですか」

「そう。なぜなら、Aが空集合のときが反例となるからだ」

「反例？」

「反例とは、AならばBのAが成り立つにもかかわらずBが成り立たないような例を言う」

「例えばどんな感じですか？」

「xが2の倍数ならその1の位は2,4,6,8のいずれかになる。という命題に対しては、x=10が反例になる。xは2の倍数という仮定を満たし、1の位が2,4,6,8のいずれかになる、という結論を満たさないからだ。今回は、"Aの要素yが存在する"という部分を満たさない。そもそも空集合に要素は存在しないからだ」

和音は式に目を落とす

∀A(∀x((x∈A→x∈ℕ)→∃y∈A(∀z∈A(y=z∨y<z))))

「わかりました。そうすると、修正しないといけないですね」

「そう。こういう風に修正しよう」

∀A(∀x((x∈A→x∈ℕ)∧￢∃y∈A(∀z∈A(y≦z)))→A=∅)

「これは反例なら空集合である、ってことだね。さきほどの例で言えば、

xが2の倍数ならその1の位は2,4,6,8のいずれかになる

の反例は

1の位は0になるときのみ

というのを

xが2の倍数かつ、1の位が2,4,6,8のいずれにもならない

ならば

1の位は0になる

と言い換えられるように、

自然数のみからなる集合Aは最小元を持つ

の反例は

Aが空集合のときのみ

というのを、

自然数のみからなる集合Aが最小元を持たない

ならば

Aは空集合である

と言い換えた。

あと、小さいことだけれども、"小なり"または"イコール"を"小なりイコール"に書き換えさせてもらった」

和音はもう一度式を指さす。

∀A(∀x((x∈A→x∈ℕ)∧￢∃y∈A(∀z∈A(y≦z)))→A=∅)

「さて、これを数学的帰納法を使って証明するよ」

「はい…、証明はさっぱりですけど」

「ここで、自然数のみを要素に持ち、最小元を持たない集合Aを用意しよう。

この集合が空集合であることを言いたいので、命題は

全ての自然数mに対してm以下の自然数はAの要素ではない

だ。少々遠回りな言い回しだけど、m以下の自然数がAの要素でなければ当然mもAの要素でないので、Aは全ての自然数を要素に持たない。

数学的帰納法は2ステップ。

0のとき、成り立つ

nのとき成り立てば、n+1のときも成り立つ

つまり

0以下の自然数はAの要素ではない

n以下の自然数がAの要素でないなら、n+1以下の自然数もAの要素ではない

この二つを証明すればよい」

「そうですね」

「まず、0以下の自然数、すなわち0は属しているだろうか」

「属していたら0が最小元になりそうですね」

「その通り。"小なりイコール"記号を次のように定義する」

x≦y:↔

∃n∈ℕ(x+n=y)

「そして"最小元"記号を次のように定義する」

min(S):

min(S)∈S∧∀y∈S(min(S)≦y)

「この定義と、公理"0は後続数ではない"と公理"数学的帰納法"から、

自然数からなる集合が0を要素に持てば0は最小元である

という命題を示せる」

「難しいこと言ってますけど、つまり0は最小の自然数ってことですよね」

「その通り。では、二つめのステップにいこう」

n以下の自然数がAの要素でないなら、n+1以下の自然数もAの要素ではない

「もし、n以下の自然数がAの要素でないのなら、n+1以下の自然数を見た時、n+1しかAの要素になれない。しかし、そうするとn+1はAの最小元になってしまう」

「それはそうですね」

「すなわち、n+1もn以下の自然数もAの要素になれないので、n+1以下の自然数もAの要素になれない。これで2つめのステップが完了だ」

「いつの間にか、という感じですけど、やってること一つ一つは難しくないですね」

「そうでしょ。これでもともとの命題は示せた」

Aを自然数のみからなり、かつ最小元を持たない集合とする。

0以下の自然数はAに属さない

（0が最小元になってしまう）

n以下の自然数がAに属さない→n+1以下の自然数がAに属さない

（n+1が最小元になってしまう）

よって、Aは全ての自然数mに対し、m以下の自然数を要素に持たない。

よって、Aは全ての自然数を要素に持たない。

よって、Aは空集合である

「これは結構すっきりしてる感じがしますね」

「そうでしょ。このようにある集合Sが

Sのいかなる部分集合Aも最小元を持たないならばAは空集合である

という述語を満たすとき、Sを"整列集合"という」

「論理式で書くとこうですね」

∀A(∀x((x∈A→x∈S)∧￢∃y∈A(∀z∈A(y≦z)))→A=∅)

「その通り。先ほどの式の"自然数"をSに変えればよいだけ」

「自然数全体の集合以外にどんな整列集合があるんですか？」

「たとえば、自然数の部分集合は整列集合だ。一般に、整列集合の部分集合は整列集合になる」

「ああ、そうですね。それはなんとなく証明できそうな気がします」

ふと湾が時計を見ると5時40分。もう始発が動いている。

「五十藤さん、帰りたいの？」

「え？」

「時計を見たから」

「そうですね…ちょっと疲れがたまってしまって。仕事の話できてなくて申し訳ないですけど」

「整列集合の話に熱中しちゃったからな」

「楽しかったですよ。とっても。それに、いつも習っている人以外から習うと、たまに用語が違ったりしてそれはそれで勉強になりますね」

「そう？それならよかったけど」

「すみません、おっしゃる通り、昨日は緊張続きで少し疲労がたまってるんで、家でゆっくり休んでもいいですか」

「それは止めるわけにはいかないでしょ。自分はここで少し寝ていくよ」

「そうですか、お疲れ様です。ごゆっくり。今日は本当にありがとうございました」

湾は荷物をまとめると、さっさと休憩スペースを後にした。