私的数学日誌

47日目「ペアノの公理と1+1（その1）」

我々が普段扱っている自然数がどのようなものかをしっかりと考え直してみよう。

次の定理を認める。

ペアノの公理を満たす集合の存在

次の様な性質を満たす集合X、写像φ:X→X、元eの3つ組が存在する。

1) e∈X

2) φは単射である

3) ∀x∈Xについて、φ(x)≠e

4) S⊂Xについて、

i) e∈S

ii) x∈S→φ(x)∈S

が満たされればS=X

この条件のことをペアノの公理と言い、(X, e, φ)の組のことをペアノの3つ組という。このとき、Xを自然数集合、φを後継者写像という。

これからは、何の言及なしに出てきたX,φ,eはこの定義に従うとする。

φが単射であることにより、後継者を決めることでその後継者の前が一意に定められる。eは感覚的に言えば一番小さい元である。（まだ順序が定まっていないことを抜きにして言えば）

φ(x)をxの後者と呼ぶ。eはいかなる元の後者にならない。これは3)と後者の定義より自明である。

また4) は特にこれからの証明によく用いられる。例えば、自然数では帰納的に写像を定義することが多々あるが（加法など）その時、帰納的定義により写像が一意に構成されることを示す定理に4)は使われる。

また、単純に4)はとても便利である。すべての自然数について〜という様な証明は4)を必ずと言っていいほど用いて証明する。要するに次の様に4)を用いる。

全ての自然数nに対してP(n)が成り立つことを示したいとき、

P(n)が成り立つ様な自然数の集合をSと置いて、そのSがXと一致することを示せば良い。この時、S=Xを示したいので4)を用いる。

先取りとして、e=1、φ(x)=x+1と略記すれば4)の条件は

4') S⊂Xについて、

i) 1∈S

ii) x∈S→x+1∈S

が満たされればS=X

という様に書き換えられて、数学的帰納法の様な見た目になる。実際にこれは数学的帰納法の原理と呼ばれている。

ペアノの公理が成り立つような(X,e,φ)について以下の定理が今のところ成り立つことがわかる。

後者は元（もと）の元（げん）になることは決してない

∀x∈X, φ(x)≠x

[証明]

早速4)を使う証明が現れた。Sは命題が成り立つ自然数全体の集合とする。

3)からe∈Sであることがわかる。

a∈Sであるとしよう。すなわち、φ(a)≠aであるとする。φは単射であるので、φ(φ(a))≠φ(a)が成り立つ。よって、4)より、S=Xとなり、すべてのXの元について命題は成り立つ。

前者はe以外であれば存在する

x≠e, x∈Xであるとき、あるy∈Xが存在して、φ(y)=xが成り立つ。また、このyのことをxの前者と呼ぶ。

[証明]

Sを前者の存在するようなすべてのXの元とする。この時、Sにeは含まれない。（3)より。）よって、新しくS'=S∪{e}を定義する。S'は定義よりeを含み、x∈S'だった場合、φ(x)の前者は定義によりxであるので、φ(x)∈S'。よって、S'=Xが示せた。ここで、両辺から{e}を取り除くと、S=X-{e}より題意は示せた。

ここからが重要な定理、推論になる。我々は自然数の加法と乗法を定義したい。演算も写像の一種であるから、ある写像を定義すれば良い。その時人間に扱いやすい様にするために次の様な定義で写像を構成する。

自然数の加法

加法演算+:X×X→Xを次の様に定義する。

+(x,1)=φ(x)

+(x,φ(y))=φ(+(x,y))

自然数の乗法

乗法写像×:X×X→Xを次の様に定義する。

×(x,1)=x

×(x,φ(y))=+(×(x,y),x)

これらの定義に共通していることは、f(x,φ(y))の定義にf(x,y)の値が使われていることである。このような写像の定義の仕方を写像の帰納的定義という。より形がわかりやすくなるように写像の帰納的定義を定式化すると、

写像の帰納的定義

ある集合A≠Øに対して、F:A→A、a∈Aが存在するとする。この時、次の様な写像f:X→Aが一意に存在する。

f(e)=a

f(φ(x))=F(f(x))

上の式を写像fの帰納的定義、もしくは漸化式という。

この定理は色々なところで現れる重要な定理である。証明をしていこう。

[証明]

この写像が存在していることを示し、一意性を示す。

存在性

写像の定義からfの存在性を示す。次のことを示せば良い。

あるΦ⊂X×Aが存在して、

(i)任意のx∈Xに対して、ある唯一のy∈Aが存在して(x,y)∈Φ

(ii)(e,a)∈Φ

(iii)(x,y)∈Φ→(φ(x),F(y))∈Φ

という三条件を満たす。

写像は実は定義域と終域の直積の部分集合によって定義されるのである。

このΦをどのように構成するかが、この証明で最も重要なポイントである。ここで、次の様な考えが浮かび上がってくる。

(ii)と(iii)を満たすX×Aの部分集合たちの共通部分Φ'は(ii),(iii)を満たしそうである。また、このΦ'が(i)を満たしてくれなければすべての(ii),(iii)を満たすX×Aの部分集合で(i)は成り立たない。

（Φ'はすべての(ii),(iii)を満たすX×Aの部分集合に含まれるのでxの被りがあった場合Φ'より大きい(ii),(iii)を満たすX×Aの部分集合ではこの被りを解消することができない。）

つまり、定理が成り立つかどうかはΦ'にかかっているということである。

しかし、我々は普段の経験から題意の写像が存在することを知っている。つまり、Φ'は写像であることを4)を用いて示すことができそうなのである。

(ii),(iii)を満たすX×Aの部分集合族をIとして、X×A∈IよりI≠Øであるので

Φ'=∩(Φ∈I) Φ

とΦ'を定義しよう。

ここでΦ'が(i)を満たすことを示そう。

そこで4)を用いる。S={x∈X| xは(x,y)∈Φ'となるy∈Aが一意に定まる様なXの元}と定義して、これが4)の2条件を満たすことを示そう。

e∈Sであることを示す。b∈Aが存在し、(e,b)∈Φ'であるとする。もちろん、仮定より、(e,a)∈Φ'である。ここで、aとbは異なる元であるとする。

この時、Φ'から(e,b)を除いた集合Φ"を定義する。この時、(x,y)∈Φ"→(φ(x),F(y))∈Φ'であることがわかる。（Φ"⊂Φ'より）3)よりφ(x)≠eであり、(φ(x),F(y))≠(e,b)であるので、(x,y)∈Φ"→(φ(x),F(y))∈Φ"が成り立つことがわかる。

よってΦ"は(ii)と(iii)を満たし、これはΦ'が最も小さい(ii)と(iii)を満たすX×Aの部分集合であることに矛盾する。よって、a=b。つまり、e∈Sが成り立つ。

次に4)の二つ目の条件が成り立つことを示そう。x∈Sであるとする。この時φ(x)∈Sであることを示そう。

φ(x)∉Sとして矛盾を導こう。

x∈Sより、xに対してy∈Aが一意に定まり、(x,y)∈Φ'。この時条件(iii)を用いると、(φ(x),F(y))∈Φ'が成り立つ。

φ(x)∉SよりあるF(y)と異なるu∈Aが存在して、(φ(x),u)∈Φ'が存在する。

Φ'から(φ(x),u)を除いた集合をΦ"と定義する。

注意するべき点として、このΦ"は先ほど定義したΦ"とは異なる集合であるということが挙げられる。記号の濫用（らんよう）は記号の節約のために許して欲しい。

3)よりφ(x)≠eであるので、(e,a)∈Φ"が成り立つ。

また、(r,s)∈Φ"であれば、(φ(r),F(s))∈Φ'であり、もし、r≠xであればφの単射性によってφ(r)とφ(x)は異なり、当然(φ(r),F(s))≠(φ(x),u)であり、(φ(r),F(s))∈Φ"。

もし、r=xであったのなら、sとyは等しくなり、(r,s)=(x,y)が成り立ち、(φ(r),F(s))=(φ(x),F(y))≠(φ(x),u)より、結局(φ(r),F(s))∈Φ"。

よって、Φ"は(ii)、(iii)を満たし、Φ'よりも小さいので、これはΦ'の最小性に矛盾する。よって、x∈S→φ(x)∈Sが成り立つ。

ここで4)を用いると、S=Xとなり、Φ'が(i)を満たすことがわかった。

よって写像fの存在性が示せた。

一意性

このようなfが一意であることを示そう。仮定を満たし、f≠gとなるfとgが存在すると仮定する。

再び4)を用いる。S={x∈X| f(x)=g(x)}とする。まず、f(e)=a=g(e)であることから、f(e)=g(e)であり、e∈S。

x∈S→φ(x)∈Sを示す。x∈Sとすると、f(x)=g(x)となるので、両辺にFを合成することで、F(f(x))=F(g(x))⇄f(φ(x))=g(φ(x))が示され、φ(x)∈Sが示せた。

4)を用いると、S=Xとなり、f≠gは誤りであることが示される。よって、f=g。

一意性が示された。

存在性の証明はe∈Sを示すときも、[x∈S→φ(x)∈S]を示すときも、どちらもかなり似た方法を用いていることがわかる。

端的に証明のエッセンスをまとめるとこの様になる。

もし一意にyが存在してくれないのであれば、仮定にない方のペアをΦ'から削除して、新しくΦ'よりも真に小さい、仮定を満たすΦ"が構成できる。これはΦ'の最小性に矛盾。

何か最小、最大のものを構成できた時は背理法がやはり利いてくることがわかる。また、証明中には何度も4)を用いた。自然数集合Xが重要なのは、4)の存在がかなり大きいのである。

次回はこれを用いて、ペアノの三つ組の一意性と加法乗法の定義をこの定理を用いて行う。