数理科学と日本古代史のブログ

　前回、自然数論の公理（Peanoの公理）を論理式で記述しました。
　しかしこれらを言葉で説明するときは、次のように説明するのことが多いはずです。

(a) 0 は自然数である。

(b) 自然数の次のものは自然数である。

(c) 0 はいかなる自然数の次のものでもない。

(d) ２つの自然数は、次の自然数が等しければ等しい。

(e) 自然数に関する性質が、0 について成り立ち、ある自然数について成り立つと仮定すると次の自然数についても成り立つならば、この性質はすべての自然数について成り立つ。

　前回与えた公理系：

(1) ∀n [ s(n) ≠ 0 ]

(2) ∀n ∀m [ s(n) = s(m) ⇒ n = m ]

(3) [ P(0) ∧ ∀n ( P(n) ⇒ P(s(n)) ) ] ⇒ ∀n P(n)

は、実は (c), (d), (e) に対応するものだけしか表わしていません。(a) や (b) は、定項 0 と１変項関数記号 s を持つ、ということで表現されているといえば表現されているのですが、(a) や (b) という日本語のそのままの“直訳”ではありません。

　もっと、もとの日本語の直訳に近い形で論理式に翻訳することはできないものでしょうか。
　そのためには、まず (a)〜(e) の各文に必ず出てくる「〜は自然数である」という言葉が翻訳できるようにする必要があります。

　そこで、１変項述語記号 N を導入して、「n は自然数である」という文を N(n) と翻訳することにしましょう。すると、上の (a)〜(e) は、次のように翻訳されることになります：

(A) N(0)

(B) ∀n [ N(n) ⇒ N(s(n)) ]

(C) ∀n [ N(n) ⇒ s(n) ≠ 0 ]

(D) ∀n ∀m [ ( N(n) ∧ N(m) ∧ s(n) = s(m) ) ⇒ n = m ]

(E) P(0) ∧ ∀n ( N(n) ∧ P(n) ⇒ P(s(n)) ) ⇒ ∀n [ N(n) ⇒ P(n) ]

　ちょっと論理式が複雑になるので、省略記号 ∀_N を

(4) ∀_Nn R(n) ≡ ∀n [ N(n) ⇒ R(n) ]

で定義すると、上の (A)〜(E) は

(A)' N(0)

(B)' ∀_Nn N(s(n))

(C)' ∀_Nn s(n) ≠ 0

(D)' ∀_Nn ∀_Nm [ s(n) = s(m) ⇒ n = m ]

(E)' P(0) ∧ ∀_Nn ( P(n) ⇒ P(s(n)) ) ⇒ ∀_Nn P(n)

となります。
　こうして、日本語で記述したPeanoの公理をなるべく忠実に論理式で表現することができましたが、敢えて新しい１変項述語記号 N を持ち込んだ御利益は、単に「日本語の表現に近くなった」というだけではありません。
　新しい記号 N を導入し、Peanoの公理を (1)〜(5) のように定式化し直すことによって、ε量化記号を導入したときに非構成的な命題が証明されるのを防ぐことができるのです。

　実際、非構成的な命題：

(5) (P ⇒ Q) ∨ (P ⇒ Q)

が証明されたプロセスを再現すると、

(6) R(n) ≡ (n=0 ∧ P) ∨ (n=1 ∧ Q)

(7) t ≡ εnR(n)

と置いたとき、

(8a) P ⇔ R(0)

(8b) Q ⇔ R(1)

が成り立つので、

(9a) P ⇒ R(t)

(9b) Q ⇒ R(t)

が成り立ちます。
　ここで、任意の自然数は 0 と異なるか 1 と異なるかどちらかなので、特に

(10) t≠0 ∨ t≠1

であり、更に

(11a) t≠0 なら R(t) ⇒ Q

(11b) t≠1 なら R(t) ⇒ P

が成り立つので、場合分けにより、(9a) と (11a) 、又は (9b) と (11b) を組み合わせれば、非構成的な (5) が得られる …… と言いたいところですが、実は上の (10) のところで“ダウト！”です。

　上記の証明で、「任意の自然数は 0 と異なるか 1 と異なるかどちらかなので」というところは、きちんと論理式で書けば、

(12) ∀n [ n≠0 ∨ n≠1 ]

となるように思われるかもしれませんが、そうではありません。
　Peanoの公理の新しい定式化のもとで証明できるのは、前回の証明を新しいPeano公理系 (A)〜(E) のもとでの証明に書き直せばわかるように、(12) ではなくて、

(13) ∀_Nn [ n≠0 ∨ n≠1 ]

あるいは省略記号を使わずに書き下せば

(13)' ∀n [ N(n) ⇒ ( n≠0 ∨ n≠1 ) ]

という論理式になります。

　さて、この (13) あるいは (13)' を用いて (10) が導出できるでしょうか？
　答は No です。
　なぜなら、(13)' から推論規則 (∀消去) を用いて得られるのは

(14) N(t) ⇒ ( t≠0 ∨ t≠1 )

です。従って、これから (10) を導くためには

(15) N(t)

を導いておかなければなりません。
　確かに R を満たす項が存在すれば、∃n R(n) が、従ってそれと同値な R(t) が導かれ、そこから t = 0 ∨ t = 1 が得られ、従って (A) と (B) により (15) が得られます。
　ところが、そもそも R を満たす項が存在すること自体が証明できません。
　なぜなら、そのような項が存在するためには、P∨Q が成り立つことが必要十分であり、従ってそのような項の存在が一般的に証明できるはずがないからです。

　以上で確かめたように、１変項述語記号 N を導入して公理系そのものを書き換えることによって、ε量化記号を導入しても、(10) が証明できず、従ってそれ以降の証明がすべて無効になって、(5) のような非構成的な結論が証明されることを回避できることがわかりました。