自然数の集合Nは, ペア ノ21 の公理[Peano’s Axioms]と呼ばれ る次の5つの公 理を満たす集合とし て定義され る:
(N1) 1∈N (1は自然数である)
(N2) S :N→N (S(x)を xの次の数[successor]と呼ぶ) (N1)と (N2)におけ る 1と Sに 関し て, 以下の条件が 成立する:
(N3) ∀x∈N, S(x)= 1 (1はど んな数の次の数にもならない)
(N4) ∀x, y ∈N(S(x) = S(y)⇒x=y) (異なる数の次の数は 互いに 異なる) (N5) A⊂Nが 次の 2 条件を満たすならば, A=Nとなる:
(i) 1∈A, (ii)∀x∈A, S(x)∈A
後で 定義する加法を 用いれば, S(x) = x+ 1 とな る. 公理 (N4) は Sが 単射で あることを意味する. (N3)は 1 ∈S(N)を意味するが, (N5) より N= {1} ∪S(N) なので, N\ {1} = S(N) とな る. また, (N5) は(数学的)帰納法[(mathematical) induction]を 意味する. 実際, 条件 P(x) に 対し, A = {x ∈ N | P(x)} とおけば, A =N とい うことは“∀x∈ N, P(x)が 成立する” とい うことを意味する. これを 示すには, (N5) の (i), (ii)を示せば よいが, それは 以下を示すことに 他ならない:
(i)P(1)が 成立, (ii)P(x)が 成立⇒P(x+ 1)が 成立
注意: 自然数の集合 Nとはペアノの公理を満たす集合(体系)であると定義する には,このような体系が 存在し て一意的に 決まることを示す必要があるが,ここで
21Giuseppe Peano, 1858–1932.
はそのことを認めて出発する. このようにし て自然数集合 Nを定義するとい うこ とは, Nをアラビ ア数字全体の集合{1,2,3, . . .}と考えようと,ローマ数字全体の 集合 {I, II, III, . . . }と考えようと,また英語で one, two, three, . . . という言葉全 体の集合や日本語で イチ,ニ,サン,. . . という言葉全体の集合,さらにそれらが 表 すもの(概念)全体の集合と考えようと,みな同じ であり,ペア ノの公理さえ満たし ていれば よいとい うことである.22
集合論では, 0を自然数に 含めるのが 大勢である. ここでは,零 0∈Nを Nに加 えて ω =N∪ {0}と書くことに する. S(0) = 1 とすることにより Sを ω 上に 拡 張する. すなわち,
(P1) 0∈ω (P2) S :ω →ω
この 0と Sに 関し て, 以下の条件が 成立する: (P3) ∀x∈N, S(x)= 0
(P4) ∀x, y ∈ω (S(x) = S(y)⇒x=y)
(P5) A⊂ωが 次の 2条件を満たすならば,A =ω となる: (i) 0∈A, (ii)∀x∈A, S(x)∈A
これらの条件もペア ノの公理と呼ばれ るが, まず 最初に,これらを満たす集合とし て ω を定義し てから, N= S(ω) (=ω\ {0})とすれば, 1 = S(0)と S|Nに 関し て, (N3) – (N5)が 成立する. (数学的)帰納法に 関し ては, “∀x∈ω, P(x)が 成立する” とい うことを示すには, 以下を示せば よいことになる:
(i)P(0)が 成立, (ii)P(x)が 成立⇒P(x+ 1)が 成立
論理的には, (N1) – (N5) と (P1) – (P5)は 全く同じ であり, (N,1,S)と (ω,0,S) も体系とし て全く同じ である. 両者の違いは, 演算を定義し た時に 現れ る. すなわ ち,加法と乗法の定義の仕方により, 最初の条件である (N1)と (P1)にある特別な 元 0と 1のにおけ る役割が 違ってくるのである.
注意: ペア ノの公理 (P1) – (P5) を 満たす体系 (ω,0,S) の 存在は, 無限公理 [Axiom of Infinity]と 呼ば れ る公理に よる.23 無限集合の存在を 仮定すれば,
22
アラビ ア 数字に よる表記法では,幾らで も大きな数を 表すことができるが,漢数字やローマ数 字による表記では 無理であり, 言葉では「· · · 倍 」とか「· · · に · · · を 加えた数 」など とい う言葉 を 繰り返し て用いることにより幾らでも大きな数を表現し 得る.
231.1節,「 無からの創生 」では,自然数を“集合”という“もの”で 定義し た. 実際, 0 =∅ と 定 義し, S(n) =n∪ {n}(すなわ ちn+ 1 =n∪ {n})とい う操作によって,nを帰納的に定義し た. し かし,そこでの説明では nの全体であるω という集合が,何であるか,ど のよ うな広が りを 持つも のなのか 判然とし ない. 実際には,ある性質を 満たす集合とし てω を確定的に 定義できる. それ で も,その 存在を 示すには 無限公理と 呼ばれ る公理が 必要である. この無限公理は 無限集合の存在を 保証する公理であるが,「 帰納的集合が 存在する 」と定式化できる. 帰納的集合とは,集合を要素と する集合であり,操作 S(n) =n∪ {n}に関し て閉じ ている集合のことで, (ω,0,S)は0を含む最小 の帰納的集合あると 定義できる. —田中・鈴木：数学のロジ ックと集合論, 2.1, 4.5, 5.6節を 参照.
このような体系の存在を示せる(6.3 節の補足事項を 参照). また,このよ うな 体系 (ω,0,S) は 本質的に 一意的であり, よって N も本質的に 一意的であ る.
— 本節末の補足事項を参照.
以下, (P1) – (P5)を満たす ωを出発点とする.
演算: 2 つの元x, y ∈ω の和 x+yと積 xy(=x·y)をつぎ のように 帰納的24に 定義する:25
(a-i) x+ 0 =x, (a-ii) x+ S(y) = S(x+y);
(m-i) x·0 = 0, (m-ii) x·S(y) = x+xy.
この演算により, ωは 分配律をみたす加法と乗法を持つが,それぞれに 関し て可換 半群とな る. このとき, 0は 加法に 関する単位元(零元), 1 = S(0)は 乗法に 関する 単位元となり, (a-ii)において,y = 0とすれば, S(x) =x+ 1が 得られ る.
注意: これらの演算を 制限することに より Nの演算が 得られ るが,Nを出発 点にし て, Nに おけ る演算を 直接に 定義するには, (a-i), (m-i) の条件をつぎ の条件で 置き換えれば よい:
x+ 1 = S(x), x·1 =x
演習 5.1 ω におけ る加法と乗法の結合律, 交換律および 分配律を証明せよ. す なわち, 以下を証明せよ:
(x+y) +z =x+ (y+z) ; (xy)z =x(yz) ; x+y=y+x; xy=yx ; x(y+z) =xy+xz
ヒント (x+y) +z = x+ (y+z) は z に 関する帰納法; x+y = y+xは y に 関する帰納法だが, まず 0 +x =x と S(y) +x = S(y+x)を xに 関する帰納法 で 示せ; x(y+z) = xy+xz は 加法に 関する結合律, 交換律と z に 関する帰納法; (xy)z=x(yz)は分配律と zに関する帰納法. xy=yxは yに関する帰納法だが,ま ず 0x=xと S(y)x=x+yx を xに 関する帰納法で 示せ(このと き, 加法に 関する 交換律よりx+ S(y) = S(x) +y に 注意).
演習 5.2 ω におけ る次の加法に 関する簡約律を証明せよ: x+z =y+z ⇒ x=y
ヒント zに 関する帰納法.
演習 5.3 ω において, 以下を証明せよ:
x+u=x ⇒ u= 0 ; x+y= 0 ⇒ x=y= 0
24正確には,再帰的[recursive]とい う.
25実際には,これにより写像とし ての演算(x, y)→x+y, (x, y)→xyが 定義で きることは, 証 明を 要することである(本節末の補足事項を 参照).
ヒント 前半は 加法に 関する簡約律. 後半は 背理法. y = 0 であれば, ∃u∈ ω such that S(u) =yに 注意.
ωにおけ る乗法の簡約律は 順序に 関する性質を調べた後に扱う.
順序: ωは, つぎ のように 定義され る大小関係に 関し て全順序集合となる: xy ⇔
def∃u∈ω such thaty =x+u
上の定義において, 簡約律(演習 5.2)により, uが 一意的に決まる.
注意: Nに おいて, 上の定義を採用すれば,これは 狭義の順序 x < y となる. 命題 5.1 上で 定義し た が ω 上の全順序となり,この順序に関し て 0が ω の最 小元となる.
証明 4.3節の (O1) – (O4)を 示せば よい. (O1): x=x+ 0 よりxx
(O2): xy,yxとすると, ∃u, v∈ω such thaty=x+u,x=y+v このとき,x=x+ (u+v)となり,簡約律よりv+u= 0
さらに 演習5.3よりu=v= 0 ∴x=y+ 0 =y
(O3): xy,yzとすると∃u, v∈ωsuch thaty=x+u,z=y+v このとき,z=x+ (u+v)となり, xz
0の最小性: ∀x∈ω, 0xを xに 関する帰納法で 示す x= 0のと き自明. (O3)より0x⇒0x+ 1 = S(x) (O4): ∀x∈ω, ∀y∈ω, xy oryxを xに関する帰納法で 示す
x= 0のと きは, 0 = minωより自明 xに 対し て成立すると 仮定.
xyのと き, ∃u∈ω such thaty=x+u u= 0のと き,x=y
u= 0のと き,∃v∈ωsuch that u= S(v) y=x+ S(v) = S(x) +v より S(x)y
yxのと き, xx+ 1 = S(x)であるので, (O3)よりyS(x).
∴∀y ∈ω, S(x)y or yS(x)
演習 5.4 空でない ω のど んな部分集合 A も最小元 minA を持つことを示せ.
ヒント x∈ωに 関する命題“∀A⊂ω, (x∈A⇒ ∃minA)”を 帰納法で証明. xに 対 し てこの 命題を 仮定し, S(x)∈Aと する. A∪ {x}は 最小元 aを 持つが, a∈Aと a∈Aの場合に 分けて,Aの最小元について 考えよ.
つぎ の(数学的)帰納法は (P5)が 意味する帰納法とは 異なるものであり, 上の問 題 5.4にある ω の順序に 関する性質に 基づ くものである.
演習 5.5 条件 P(x)に 関し て, “∀x ∈ N, P(x)が 成立する”ことを 証明するの に,つぎ を示せば 十分であるとこを示せ:
(*) (∀y < x, P(y)が 成立)⇒P(x)が 成立
ヒント (*)には, P(0)が 成立することが 含まれ る. A={x∈ω | ¬P(x)} =∅とす れば,演習5.4よりAは 最小元aを 持つが, (*)と 矛盾が 生じ る.
演習 5.6 ω において, 次を証明せよ:
x < y, z∈N=ω\ {0} ⇒ x+z < y+z, xz < yz 演習 5.7 N (=ω\ {0})におけ る次の乗法の簡約律を証明せよ:
xz =yz ⇒ x=y
ヒント 命題5.1と 演習5.6を 用いて,対偶を 示す.
[補足事項]
ペアノの体系の一意性と 帰納的(再帰的)定義: ω におけ る演算は ω2 =ω×ω から ω へ の 写像であるので, ω に おけ る加法と 乗法を 定義するには, 下記の写像を 定義し なければ ならない:
+ :ω2 ∋(x, y)→x+y∈ω ; · :ω2∋(x, y)→xy ∈ω
し かし,下の条件では,各x, y∈ωに 対し て x+y, xy∈ωが 与えられたに すぎ ない:26 (a-i) x+ 0 =x, (a-ii) x+ S(y) = S(x+y);
(m-i) x·0 = 0, (m-ii) x·S(y) =x+xy.
ここでは, 下記の 再帰定理[Recursion Theorem]と 呼ばれ る定理を 用いて,ペア ノの公 理をみたす体系 (ω,0,S)の一意性と 上の条件により加法と乗法が 定義できることを 示す. 定理 5.2 (再帰定理) 集合W に写像 ϕ:W →W とa∈W が 与えられたとき,つぎ の条 件を満たす写像 f :ω→W が 一意的に 存在する:
(r-i) f(0) =a, (r-ii) f(S(x)) =ϕ(f(x)).
証明 f の一意性は 帰納法により, 容易に 示せる 実際,f′:ω→W も(r-i), (r-ii)を 満たすと き,
f(0) =a=f′(0); f(x) =f′(x)⇒f(S(x)) =ϕ(f(x)) =ϕ(f′(x)) =f′(x)
帰納法により, ∀x∈ω,f(x) =f′(x) ∴f =f′
写像f の存在を 示すには,そのグ ラフの存在を示せば よい.
つぎ の条件を 満たす ω×W の部分集合A全体のなす集合族をAとする: (s-i) (0, a)∈A, (s-ii) (x, y)∈A⇒(S(x), ϕ(y))∈A ω×W ∈AよりA=∅なので, Γ =
Aと 定義できるが, Γ∈Aが 容易に 分か る すなわ ち, Γは 包含関係⊂に 関するAの最小元
26実際には,公理(P2)より, 各y ∈ωに 対し て, 写像αy :ω∋x→x+y∈ωが 与えられ るが, ω∋y→αy ∈ωωが 定義され たわけではない. 加法が 定義され たとし ても,各 y∈ωに 対し て,写 像 µy:ω∋x→xy∈ωが 与えられ るが,N∋y→µy∈ωωが 定義され たわけではない.
このとき, prω|Γ : Γ→ωが 全単射であれば, Γが 求める写像のグ ラフとなる27 (全射) (P5)を 適用し て, prω(Γ) =ωを 示す
(i) Γは (s-i)を 満たすので, 0∈prω(Γ)
(ii)x∈prω(Γ)とすると∃y∈W such that (x, y)∈Γ
Γは (s-ii)を 満たすので, (S(x), ϕ(y))∈Γとなり, S(x)∈prω(Γ) (P5)より, prω(Γ) =ω
(単射)D={x∈ω|(x, y), (x, z)∈Γ⇒y=z}とおき, D=ω を 示せば よい そのために, (P5)を 適用する
(i) 0∈Dを 示すには, (0, y)∈Γ⇒y=aを 示せば よい y=aとすればΓ\ {(0, y)} ∈A — Γの最小性に 矛盾
(ii)x∈D⇒S(x)∈Dが 成立し ないと すると∃x∈D such that S(x)∈D prω(Γ) =ωより∃y∈W such that (x, y)∈Γ
このとき, Γは(s-ii)を 満たすので, (S(x), ϕ(y))∈Γ
一方, S(x)∈Dより,∃z∈X such that (S(x), z)∈Γ,z=ϕ(y) このとき, Sは 単射なので, Γ\ {(S(x), z)} ∈A — Γの最小性に 矛盾 (P5)より, D=ω
この再帰定理5.2は, (ω,0,S) をペアノの公理を満たす(w′,0′, S′)で 置き換えても成立 する.28 このことを 用いて,ペア ノの公理を満たす体系 (ω,0,S) の一意性が 示せる. 定理 5.3 ペアノの公理を満たす(ω,0,S)は 本質的に 一意的である. すなわち, (w′,0′, S′) もペア ノの公理を 満たすならば,つぎ を 満たす全単射h:ω→w′ が 一意的に 存在する:
h(0) = 0′; ∀x∈ω, h(S(x)) =S′(h(x)) 証明 再帰定理5.2を W =w′,a= 0′,ϕ=S′ に適応し て,
∃1h:ω→w′ such that∀x∈ω, h(S(x)) =S′(h(x)) 一方, (w′,0′, S′)に 対し ても再帰定理5.2は 成立するので,
∃1h′:w′ →ω such that∀x∈w′, h′(S′(x)) = S(h′(x)) 再帰定理5.2を W =ω,a= 0, ϕ= Sに 適応すれば,
写像の一意性より,h′h= idωが 得られ る
同様にし て,hh′= idw′ ∴hは 全単射でh′=h−1
再帰定理5.2の証明と同じ 議論で,ωにおけ る加法と乗法の演算+, · :ω2→ω の存在 を 示せるが,ここでは 再帰定理 5.2を応用する.
(加法の定義) 再帰定理を ωω, idω ∈ωω と写像 ωω ∋f →S◦f ∈ωω に 適用し て,つぎ の条件を満たす写像 α:ω→ωωが 一意的に 存在する:29
α(0) = idω; ∀y∈ω, α(S(y)) = S◦α(y) このとき, + :ω×ω→ωを x+y =
defα(y)(x) と定義すれば,つぎ の条件が 満たされ る: (a-i) x+ 0 =α(0)(x) = idω(x) =x,
(a-ii) x+ S(y) =α(S(y))(x) = S(α(y)(x)) = S(x+y).
273.1節,「 集合による写像の定義 」を 参照.
28特に, (N,1,S)に 対し ても再帰定理が 成立する.
29各 y∈ωに 対し て,α(y)は ω∋x→x+y∈ωとい う写像を 想定し ている.
(乗法の定義)まず,写像α˜:ωω →ωω をつぎ のよ うに 定義する:
∀f ∈ωω, ∀x∈ω, α(f˜ )(x) =α(f(x))(x) =x+f(x)
再帰定理を ωω, c0 ∈ωω (∀x∈ ω, c0(x) = 0)と 上の写像 ϕに 適用し て,つぎ の条件を 満 たす写像 µ:ω →ωω が 一意的に 存在する:30
µ(0) =c0; ∀y∈ω, µ(S(y)) = ˜α(µ(y)) このとき,· :ω×ω→ω をx·y =
defµ(y)(x)と定義すれば,つぎ の条件が 満たされ る: (m-i) x·0 = µ(0)(x) =c0(x) = 0,
(m-ii) x·S(y) =µ(S(y))(x) = ˜α(µ(y))(x) =x+µ(y)(x) =x+x·y.
数列の 漸化式に よ る定義: 再帰定理 5.2 に おいて, ω, 0 を それぞれ N, 1 に 置き 換えれ ば, (N,1,S) に 対する再帰定理が 得られ る. この再帰定理に おいて, W =Rの場合は,写 像 f : N → R は 実数列 f(1), f(2),· · · に 他ならな い. すなわ ち, 初項の 値 a1 と 漸化式 an+1=ϕ(an)を 与えることにより,数列 (an)n∈
が 定義できるとい う意味である. 初項 a1 を与え,漸化式を 写像ψ:
n∈Rn→Rによって,an+1 =ψ(a1, . . . , an) と 与 え ることに より, 数列 (an)n∈ を 定義する場合の正当性も再帰定理に よる. 実際, 再帰定 理において,W =
n∈Rn,a1 ∈R⊂
n∈Rnとし,ϕ:
n∈Rn→
n∈Rnをつぎ の よ うに 定義され た写像とする:
ϕ(x1, . . . , xn) = (x1, . . . , xn, ψ(x1, . . . , xn)) この場合に 得られ る写像f :N→
n∈Rnはf(1) =a1 でつぎ の条件を 満たす: (a1, . . . , an+1) =f(n+ 1) =ϕ(f(n)) = (a1, . . . , an, ψ(a1, . . . , an))
写像 g:
n∈Rn→ Rを g|Rn= prnと定義する. これらの合成 gf :N→Rが,漸化式 an+1=ψ(a1, . . . , an) を満たす数列に 他ならない.