ペアノの公理の５番目の公理（いわゆる数学的帰納法）

質問

ペアノの公理の５番目の公理（いわゆる数学的帰納法の原理）について、
なぜこれが自然数の定義に必要なのか気になって、考えたり調べたりしています。
（つまり、１～４の公理だけでは何が不十分なのかについてです）

そんな中、自然数の加法を定義するときに公理５が必要であるということを聞きました。自然数の加法を定義するときに公理５が必要な理由について、
ご教示、またはアドバイスいただけないでしょうか。

もうすこし具体的には、
N=(N,S,0) S:successorの写像
において、以下のように加法（二項演算a）を定義するとき
(i) a(x,0) = x
(ii) a(x,S(y)) = S(a(x,y))
この(ii)の定義の際に必要だと思いますが、
どのように第五公理が効いているのかが理解できていません。

回答No.4

tmppassenger · ベストアンサー

はい、いずれもいいです。

(Q6) - (Q8)で、少なくとも(i)(ii)を満たす写像が一つであることを示すのに、実際に(5)を使うことが分かると思います。この証明の時にも、結局 0->s(0)->s(s(0))->...という列を考えるわけですね。で、この列全部で「埋めつくす」というのを保証するのが(5)というわけです。
逆に (Q1)-(Q5)で、(5)を満たさないようなシステムの場合は、(i)(ii)をつかって、0 -> s(0) -> s(s(0)) -> ..... という「列」を考えるだけでは定義できないような要素（この例でいうと-1と-2に対するaの値）が出てきて、うまく定義できない、というのが、何となくわかってもらえたかな？と思います。

お礼

この度は丁寧なご説明と理解の誘導をありがとうございました。凝り固まってた疑問がほぐれて理解がとても進みました。

加法の写像の存在性については自身の課題として、早速とりかかろうと思います。それも含めて、ペアノの公理の理解を深めたいと思います。

回答No.3

tmppassenger

もう一問書いておきます。今度はPeanoの公理を満たす場合。

今度は (N, s, 0)がPeanoの公理 (1) ~ (5)をすべて満たすとする。写像 f:N× N→N, g:N×N→N が、 f(x,0) = x, f(x, s(y)) = s(f(x,y))　及び g(x,0) = x, g(x, s(y)) = s(g(x,y)) を満たすとする。
この時、
(Q6) x∈Nを一つとる。Nの部分集合Aを、A = {y∈N | f(x,y) = g(x,y) } とおく。Aは、0∈Aかつs(A)⊂Aを満たす事を示せ。
(Q7) f = gであることを証明せよ。
(Q8) (N, s, 0)がPeanoの公理 (1) ~ (5)をすべて満たすとする。(i)(ii)の関係を満たすa:N×N→Nは、（存在するなら）ただ一つであることを示せ。

aが実際に存在することは、証明がちょっと長くなりますので、一旦やめておきます。

補足

(Q6)～(Q8) についても、誠にありがとうございます。

(Q6)　
x∈Nを任意に一つとって固定する。
A = {y∈N | f(x,y) = g(x,y) } とおく。
このとき、
(1)0∈Aを示す
f(x,0)=x=g(x,0)　なので、0∈A
(2)s(A)⊂Aを示す
任意のy∈Aに対して、
f(x,s(y))
=s(f(x,y))　∵fの定義
=s(g(x,y))　∵y∈Aより、f(x,y) = g(x,y)
=g(x,s(y))　∵gの定義
よって、s(y)∈A
よって、s(A)⊂A

(Q7)
A={y∈N | f(x,y) = g(x,y) }は、
(Q6)とPeanoの公理 (5)から、A=Nである。
よって、任意のy∈Aと任意のx∈A((Q6でとったxの任意性から))にたいし、
f(x,y)=g(x,y)

(Q8)
(i)(ii)を満たすf(x,y)とg(x,y)が存在したとする
(Q6)と(Q7)の結果から、
任意のy∈Aと任意のx∈Aに対し、f(x,y)=g(x,y)

何度もお時間を頂戴して恐縮ですが、いかがでしょうか。

回答No.2

tmppassenger

いいですね。

そこで、そのようなNが与えられたときに、(i)(ii)という2つの関係を満たす演算 N×N→Nが本当に存在し、なおかつそれが一意に定まるか、という事が問題になります。そこで(5)の「制約」があると、a(x,0) = xから始めて、a(x,1), a(x,2), a(x,3), .... , と帰納的に計算をすることで、全てのｎ∈ Nに対してきちんと　a(x,n)が定義されることが証明されます。

それには実際に証明してみればいいのですが、ここでは実際に(5)が「ないと」どういう不都合が起こるかを見てみましょう。

ここからは『逆質問』です。以下、<は普通の不等号、 +は普通の加法とする。

M = { -2以上の整数全体} = {-2, -1, 0, 1, 2, .... } とする。s:M→Mを、 s(n) = n+1 (n≧0の時）, s(-1) = -1, s(-2) = -2 で定める。

(Q1) (M, s, 0) は、Peano の公理のうち、(1)(2)(3)(4)は満たすことを確かめよ。
(Q2) (M, s, 0) は、Peano の公理のうち、(5)は満たさ『ない』ことを証明せよ（ヒント：A={0以上の整数全体}を考えよ）。
(Q3) b:M×M→Mを、 b(x,y) = x+y (x≧0, y≧0), x (x=-1またはx=-2であって、かつy≧0), y (y<0)で定める。bは b(x,0) = x, b(x, s(y)) = s(b(x,y)) を満たしていることを証明せよ。
(Q4) 一方、c: M×M→Mを、 b(x,y) = x+y (x≧0, y≧0), x (x=-1またはx=-2であって、かつy≧0), -2 (y=-1), -1 (y=-2)で定める。cは c(x,0)=x, c(x,s(y)) = s(c(x,y))を満たしていることを証明せよ。
(Q5) (M, s, 0)においては、 a(x,0) = x, a(x, s(y)) = s(a(x,y)) という関係式だけでは、写像aが一意に定まらないことを確認せよ。

一度(Q1) ~ (Q5)まで解いて、 Peano の公理の(5)がないと、なぜ(Q5)のようなことが起こってしまうかを何となく考えてみてください。

補足

とても詳細に記載いただき、また段階を踏んで理解を助けていただいて、
誠にありがとうございます。
時間がかかっていて申し訳ございませんが、
まずこちらの(Q1)から(Q5)について考えてみました。

(Q1)
確認できました。
(Q2)
A={0以上の整数全体}とすると、A ⊂ Mであり、
0 ∈ A かつ s(A) = {1,2,3,…} ⊂ A である。
しかし、A ≠ M
(Q3)
【b(x,0)=xを示す】
(1)x≧0　のとき、
b(x,0)=x+0=x
(2)x=-1,または-2　のとき、
b(x,0)=x
【b(x, s(y)) = s(b(x,y))を示す】
(1)x≧0, y≧0　のとき、
b(x,s(y)) = b(x,y+1)= x+y+1
s(b(x,y)) = s(x+y)=x+y+1
(2)x=-1またはx=-2であって、かつy≧0のとき
b(x,s(y)) = x
s(b(x,y)) = s(x) =x　(sの定義から)
(3)y<0のとき
b(x,s(y))=b(x,y) =y
s(b(x,y))=s(y)=y

(Q4)
【c(x,0)=xを示す】
Q3のbと同様
【c(x,0)=x, c(x,s(y)) = s(c(x,y))を示す】
(1)x≧0, y≧0　のとき、
c(x,s(y))= c(x,y+1)=x+y+1
s(c(x,y))=s(x+y)=x+y+1
(2)x=-1またはx=-2であって、かつy≧0のとき、
c(x,s(y))=x
s(c(x,y))=s(x)=x
(3)y=-1のとき、
c(x,s(y))=c(x,-1)=-2
s(c(x,y))=s(-2) =-2
(4)y=-2のとき、
c(x,s(y)) =c(x,-2)=-1
s(c(x,y))=s(-1)=-1

(Q5)
Q3のbと、Q4のcは、共に関係式
a(x,0) = x, a(x, s(y)) = s(a(x,y))
を満たすが、
b(x,-1) = -1
c(x,-1) = -2
であり、写像として一致しない

【なぜ(Q5)のようなことが起こってしまうか？】
こちら言葉がうまくまとまらなくて申し訳ございません。
Peano の公理の(5)があると、自然数は
0→s(0)→s(s(0))→s(s(s(0)))→…　という列のみで構成されているとわかる
しかし、今回のM=（M,s,0）の例では、
このMは、0→s(0)→s(s(0))→s(s(s(0)))→という列から外れた
-2と-1がそれぞれ孤立した点のような状態として存在する構造になっている。

加法　a(x,0) = x, a(x, s(y)) = s(a(x,y))という関係式は、
tmppassenger様に記載いただいた通り、
> a(x,0) = xから始めて、a(x,1), a(x,2), a(x,3), .... , と帰納的に計算
というのが感覚的に理解できました。

a(x, s(y)) = s(a(x,y))　という定義は、
s(y)の"前の数"yの存在が前提のため、自然数は一列の0→s(0)→s(s(0))→s(s(s(0)))→
という構造であってほしい。
ということを考えました（まだ観察の段階でうまくまとまってなくて失礼します）

引き続き、考えさせていただければと思います。
間違いや、不足がありましたら、指摘いただければ大変ありがたいです。

回答No.1

tmppassenger

認識の齟齬があるといけないので、念のためにあなたが見ているPeanoの公理 1-5というのを、全て書いてもらえますか？

補足

コメントをいただきまして、誠にありがとうございます。

説明不足、勉強不足なところがあり大変恐縮です。
自分の見ているペアノの公理を記載させていただきます。

(1) 0 ∈ N.
(2) 写像 S : N → N が与えられていて、任意のx ∈ N に対してS(x) ∈ N
(3) 0 ∈\ S(N) (∈\は属さないを意味する)
(4) S は単射．
(5) AをNの部分集合とする。このとき、次の条件 (a)(b) を満たすならば A = N
・ (a) 0 ∈ A
・ (b) S(A) ⊂ A

何卒よろしくお願いいたします。