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

第21話 ペアノ算術 数学的帰納法

結局午前1:00か。

湾はようやく解放されたといった様子で、繁華街を歩いていた。

こんな時間では電車もない。タクシーだと莫大な料金がかかる。しかたない、カプセルホテルにでも泊まるか。この近くならいくらでもあるだろう…。

「おーい、五十藤さん！」

「ああ、和音さん」

「こんな時間じゃ帰るの大変でしょ。今後の打ち合わせも兼ねて、どこか入らない？」

「さすがに疲れましたよ。勘弁してくださいよ」

「そんなこと言わないで、居眠りOKのいいスペース知ってるから」

無理やり和音に連れて行かれたのは休憩スペースだ。リクライニングチェアと机があり、寝るも良し、話すも良し、食べるも良し、テレビを見るも良し。一晩居て一人3000円。体のいい終電逃しのためのスペースである。

「いつも、こういう感じのところ使うんですか」

慣れた感じで手続きを済ませる和音を見ながら言ったが、湾はどちらかというと一人に早くなりたかった。そもそも眠い。

しかしリクライニングチェアに座るや否や先に寝落ちしたのは和音のほうで、湾はそれを見てノートパソコンを開いた。藍からの長文メッセージが着ていることを知っていたからである。

4×3

か。藍は

S(S(S(0)))=3

というように数字を使っていたけど、まだ慣れてないからSと0だけでやってみようかな。

(S(S(S(S(0))))×S(S(S(0))))

まじか。これは大変そうだ。

まず×の公理を使って地道に解こう。公理の式はこうだ。

∀n∈ℕ((n×0)=0)

∀n,m∈ℕ((n×S(m))=(n+(n×m)))

この2番目を何度も使うってことだな。

(S(S(S(S(0))))×S(S(S(0))))

=(S(S(S(S(0))))+(S(S(S(S(0))))×S(S(0))))

=(S(S(S(S(0))))+(S(S(S(S(0))))+(S(S(S(S(0))))×S(0))))

=(S(S(S(S(0))))+(S(S(S(S(0))))+(S(S(S(S(0))))+(S(S(S(S(0))))×0))))

カッコが多すぎる。なんだこの模様は。さて、ここで、×の公理の一個目を使おう。

=(S(S(S(S(0))))+(S(S(S(S(0))))+(S(S(S(S(0))))+0)))

ここで、+の公理を思い出せ。

∀n∈ℕ((n+0)=n)

∀n,m∈ℕ((n+S(m))=(S(n)+m)

この一個目を使って+0が計算できる。

=(S(S(S(S(0))))+(S(S(S(S(0))))+S(S(S(S(0))))))

そうか、こうなってみると、もう×は終わりで、あとは+だけだ。そして+はSの数を、保ったままだから12になるのはわかる。けれども地道にやってみよう。

=(S(S(S(S(0))))+(S(S(S(S(S(0)))))+S(S(S(0)))))

=(S(S(S(S(0))))+(S(S(S(S(S(S(0))))))+S(S(0))))

=(S(S(S(S(0))))+(S(S(S(S(S(S(S(0)))))))+S(0)))

=(S(S(S(S(0))))+(S(S(S(S(S(S(S(S(0))))))))+0))

=(S(S(S(S(0))))+S(S(S(S(S(S(S(S(0)))))))))

=(S(S(S(S(S(0)))))+S(S(S(S(S(S(S(0))))))))

=(S(S(S(S(S(S(0))))))+S(S(S(S(S(S(0)))))))

=(S(S(S(S(S(S(S(0)))))))+S(S(S(S(S(0))))))

=(S(S(S(S(S(S(S(S(0))))))))+S(S(S(S(0)))))

=(S(S(S(S(S(S(S(S(S(0)))))))))+S(S(S(0))))

=(S(S(S(S(S(S(S(S(S(S(0))))))))))+S(S(0)))

=(S(S(S(S(S(S(S(S(S(S(S(0)))))))))))+S(0))

=(S(S(S(S(S(S(S(S(S(S(S(S(0))))))))))))+0)

=S(S(S(S(S(S(S(S(S(S(S(S(0))))))))))))

終った。これは壮観だな…。よし、藍にこれをメールするか。

***

藍へ

メールありがとう。読めたよ。わかりやすかった。ありがとう。

数字を使うと混乱するからSと0だけで4×3を計算してみたよ。なかなか壮観だね。

(S(S(S(S(0))))×S(S(S(0))))

=(S(S(S(S(0))))+(S(S(S(S(0))))×S(S(0))))

=(S(S(S(S(0))))+(S(S(S(S(0))))+(S(S(S(S(0))))×S(0))))

=(S(S(S(S(0))))+(S(S(S(S(0))))+(S(S(S(S(0))))+(S(S(S(S(0))))×0))))

=(S(S(S(S(0))))+(S(S(S(S(0))))+(S(S(S(S(0))))+0)))

=(S(S(S(S(0))))+(S(S(S(S(0))))+S(S(S(S(0))))))

=(S(S(S(S(0))))+(S(S(S(S(S(0)))))+S(S(S(0)))))

=(S(S(S(S(0))))+(S(S(S(S(S(S(0))))))+S(S(0))))

=(S(S(S(S(0))))+(S(S(S(S(S(S(S(0)))))))+S(0)))

=(S(S(S(S(0))))+(S(S(S(S(S(S(S(S(0))))))))+0))

=(S(S(S(S(0))))+S(S(S(S(S(S(S(S(0)))))))))

=(S(S(S(S(S(0)))))+S(S(S(S(S(S(S(0))))))))

=(S(S(S(S(S(S(0))))))+S(S(S(S(S(S(0)))))))

=(S(S(S(S(S(S(S(0)))))))+S(S(S(S(S(0))))))

=(S(S(S(S(S(S(S(S(0))))))))+S(S(S(S(0)))))

=(S(S(S(S(S(S(S(S(S(0)))))))))+S(S(S(0))))

=(S(S(S(S(S(S(S(S(S(S(0))))))))))+S(S(0)))

=(S(S(S(S(S(S(S(S(S(S(S(0)))))))))))+S(0))

=(S(S(S(S(S(S(S(S(S(S(S(S(0))))))))))))+0)

=S(S(S(S(S(S(S(S(S(S(S(S(0))))))))))))

夜遅くになってごめんなさい。また会える日連絡するね。

湾

***

こちらもさっさと寝ることにするか。湾は慣れないリクライニングチェアで、なんとか寝ようと試みる。

………

　………

　　………

寝れない。身体は疲労の極致だというのに。

あれ、メールが来ている。

***

お疲れ様。

よくできたね。湾はもう和と積は理解できている。ここから数学的帰納法を使って、自然数にスタートが2つないことを言おう。

まず、数学的帰納法の公理がこうだ。

(φ(0)∧(∀n∈ℕ(φ(n)→φ(S(n)))))→∀m∈ℕ(φ(m))

そして、φは自由変数が一つの論理式なら、どんな論理式でも良い。

これは

①φが0で成り立つ

②φがnで成り立つならばS(n)でも成り立つ

①と②が両方成り立つとき

すべての自然数mでφが成り立つ

ということをいっている。

0で成り立つ。

0で成り立てば1で成り立つ。

1で成り立てば2で成り立つ。

2で成り立てば…

と繰り返していけば、全ての自然数で成り立たせられる、というわけだ。

ここでφを"nが0でないならば前者数が存在する"という述語にしてみよう。こうだ。

φ(n):↔

n≠0→∃t∈ℕ(S(t)=n)

tは束縛変数、ℕは定項記号なので、自由変数はnだけとなり、これは一つの自由変数を持つ論理式になる。

これを、数学的帰納法の公理に代入するとこうだ。

((0≠0→∃t∈ℕ(S(t)=0))∧(∀n∈ℕ((n≠0→∃t∈ℕ(S(t)=n))→(S(n)≠0→∃t∈ℕ(S(t)=S(n))))))→∀m∈ℕ(m≠0→∃t∈ℕ(S(t)=m)))

さて、これは公理なので無条件に認めて良い。と言われてもこんな長い式では困ってしまう。なので日本語を借りて読み解こう。

まず数学的帰納法の公理の日本語版がこう。

①φが0で成り立つ

②φがnで成り立つならばS(n)でも成り立つ

①と②が両方成り立つとき

すべての自然数mでφが成り立つ

このφが

n≠0→∃t∈ℕ(S(t)=n)

となる。まず、"①φが0で成り立つ"を調べよう。

このnに0を代入した式

0≠0→∃t∈ℕ(S(t)=0)

は成り立つ。なぜなら、"ならば"の前が成り立たないからだ。"ならば"の前が成り立たない命題は、常に成り立つ。よって①はOK。

②φがnで成り立つならばS(n)でも成り立つ

次はこれについて調べる。まず、nとS(n)を代入した式を作る。

n≠0→∃t∈ℕ(S(t)=n)

これが成り立つならば

S(n)≠0→∃t∈ℕ(S(t)=S(n))

これも成り立つ

ところで、これは、

∃t∈ℕ(S(t)=S(n))

がどんなnでも成り立つ。なぜならt=nにすればよいからだ。

ここで、"ならば"の右が常に正しいとき、つまり

A→B

でBが常に成り立つときを考えよう。

この式は常に成り立つ。なぜなら、Aが成り立たないなら式は成り立つし、Aが成り立つときもBが成り立っているので、式は成り立つ。なので、

A→B

は常に成り立つ。

C→(A→B)

でBが成り立つなら、(A→B)も常に成り立つので、この式も常に成り立つ。

よって②全体の論理式

n≠0→∃t∈ℕ(S(t)=n)

→［S(n)≠0

→∃t∈ℕ(S(t)=S(n))］

この構造の一番下の行が常に成り立つので、

②も成り立つことがわかった。よって、次の式が成り立つ。

∀m∈ℕ(m≠0→∃t∈ℕ(S(t)=m))

これは、

どんな自然数mも、0でないなら前者数を持つ

という命題で、これは公理で認められた。

すると、

0→S(0)→S(S(0))→…

C→S(C)→S(S(C))→…

というモデルのCは前者数を持たないので、自然数として相応しくない。これで、晴れて、

0→S(0)→S(S(0))→…

自然数はこういうモデルになった。

まあ、

0→S(0)→S(S(0))→…→C'→C→S(C)→…

（C'はCの前者数）

こういう怪しいモデルはあったりするが、これについては今は考えないようにしよう。少なくとも通常の範囲では、我々の使う自然数を上手く論理式で表現できたことになる。

湾が目の前にいないと教えるインスピレーションも、リアルタイムな反応も無いからやり辛いな。もしわからないところがあったら遠慮なく送ってね。

体調に気をつけて。

藍

***

「ふぅん、ペアノ算術ね」

「え？和音さん？」

「もし数学的帰納法やるなら、自然数の部分集合は必ず最小元を持つ、もやりたいところだな。このことを自然数は整列集合である、という」

「和音さんも数学されるんですか？」

「趣味だ」

「趣味…と言いますと」

「そうだな…大きい数なんて大好物だ」