第二階論理 によるペアノ算術
田畑
博敏
* は じ め :こ 本論文の 目的は,第
二階論理の言語 (第二階言語)に
よって定式化 されたペアノ算術 (自然数 に ついてのペアノの公理か ら導かれ る定理の集合)が
カテゴ リカルで あること,す
なわち,す
べての モデルが同型であること,を示 し,その ことか ら帰結す ることが ら,特
に,自然数上の関数の回帰 性 (recurslon)に よる定義の可能性,について調べ ることである。われわれは第一階論理 と第二階 論理 の表現力の比較の観点か ら,す
でに,第
二階論理の持つ一般 的な特性 について調べ た (田畑 [2001])。 今回は,第
二階論理の定式化の特徴が特 に顕著に見 られ るペア ノ算術 を研究す る(う 。 よく知 られているように,ペアノは自然数 に関す る公理系 を作 ることにより,そ の公理 か ら算術 の真理 を定理 として導 こうとした。その公理の中に数学的帰納法の原理 が含 まれてい る。第一階の 論理 によるこの原理の定式化 は,い
わゆる公理図式 によるもので,具
体 的な一階の (自由変項 を含 む)論
理式 を代入す ることにより,無
数の公理 が得 られ る。それゆえ,数
学的帰納法の公理 は無数 の論理式 に対応す る無数の公理 を含む ことになる。しか し,論
理式 はせ いぜ い可算個 しかないゆえ に,論
理式が表す 自然数の性質 もせいぜい可算無限個 しかない。他方,第
二階論理 によって定式化 され る数学的帰納法の公理 は単一の公理で あり,それは,「すべての 自然数の性質 (集合)」 に言及 してい ると解釈 され,非
可算個の性質 (集合)を
量化の範囲に含んでい る。 さらにi第
一階の論理 によるペ アノの公理系 はコンパ ク ト性定理 によ り,標 準モデル とは同型でない非標準モデル が存在 す るのに対 して,第
二階のペアノの公理系はカテゴ リカルで ある (すなわち,す
べてのモデルが同 型的で ある)。 このよ うな相違 は ,な によりも定式化の基礎 にある論理の相違 に由来 してい る。論理 の表現力の比較 とい うi言
わば通奏低 音的動機 に導かれてい る本論文 は,特
に第二階ペア ノ算術の カテゴ リー性 に焦点 を当てる。方法 として,論
理 を表現す る言語 に,意
味の体系 としての構造 (こ れ自体 は集合論のメタ言語で語 られ る)を
対応 させ る,モ
デル論的アプ ローチを採用す る。 そこで,本
論文の梗概 はつ ぎの ようになる。まず第1節
では,第
二階ペアノ算術の公理系 を提示 して,そのモデルのい くつかを考 え,非
標準的モデルにも触れ る。第2節
では,第
二階論理 による ペアノの公理系がカテゴ リカルであることを示す。それを受 けて,第 3節
では,公
理系の意図 され たモデル を,互いに同型 なペアノ・モデルの代表 として とり,ここで原始回帰(pttmiuve recursion) とい う定義図式 によって定義 され る自然数上の演算 (加法・乗法・巾法)の
存在 を示す。第4節
で は ,数 学的帰納法のモデルではあるが ,他 のペアノの公理のモデル とはか ぎらないモデル と,(意 図 された)自
然数のモデル上の合 同関係 との,つ
なが りを論 じる。それ に関連 して,第 5節
では,帰
納モデルの あるものでは,中法の ように,原始回帰 によって定義 され る演算が存在 しない ことがあ*鳥
取大学教育地域科学部・地域設計学講座 。哲学田畑博敏 :第二階論理によるペアノ算術 ることを見る。そして,演算が自然数(のモデル
)上
の合同関係と両立するものであるかどうか,が それの決め手 となることを示す。1.第
二階のペアノ公理系
1,1
ペ ア ノ・モ デル と帰納法 モデル われわれは (ゼロを含む)自然数 について,素朴 な理解 を持 っている。まず最初の数0(ゼ
ロ)が
ある。(数 1を最初の数 とす ることもあるが,わ
れわれはゼロか ら始め る。)つ
ぎに,二
番 目の数 と しての数1,二
番 目の数 としての数2,等
々が続 く。直後の数 (後者)が
前者 によって一意 に決 ま ることが承認済みであるとすれば,数 1は
SO(successor of zero),数2は
SSO,等
々 と表現 され よう零すると,自
然数の全体 は,10,1,2,…
・ ￨ としてではな く,秒
しる10, SO, SSO,
い・ ￨ として表 され よう。これ ら自然数 は ,そ れぞれ特質 を持つ とともに,あ る共通性 も有す る。例 えば, (最初の数0を除いた)す
べての数には,その直前の数 (前者)が
存在す る(1の
前者 は0,2の
前 者 は1,等
)。 またn番
目以下の数 は丁度n個
存在す る(最初の数0以
下の数 は0その もので あるか ら一個存在 し,二番 目の数1以下の数は 1と0で
二個存在す る,等)。 この よ うな自然数の持つ特性 (各数の特質や共通性)を
統一的に把握す るにはどうしたらよいか。その一つの解答 は,G.ペ
アノ にようて与 えられた,以
下のペ アノの公理系 (公理 の集合 を “Π"で
表示す る)で
ある。ペアノの 戦略 は,この公理系 を中核 として ,そ の他の自然数の主要な法則・特性 を導 く,とい うもので ある。 定義1. 1. 1:以
下の公理の集合 Πをペアノの公理系 とい う。 Π: lP⇔
Vx￢
(c=σ
x)2P
⇔VxVy(σ
x=σ
y→
X=y)
3P'⇔ VX[XcAvz(xz→
Xσz)→
VxXx]
ここで,“c"は
数詞ゼロの一般化 ,す なわち,構 造の領域内に存在するある個体を表示する個体定 項 (または0項
関数記号)で
あり,“σ"は
「後者」をとる関数を表示する1項
関数記号である。そ れにより,通
常設定 される,「cは
自然数である」や「自然数の後者 も自然数である」といった命題 に相当する公理は,cが
領域のある特定の要素 を表示 し,σが領域か ら領域への関数を表示する,と いうこれ らの記号の用法にすでに含まれていることにより,不
要である。 公理系 Πの第一の公理:lPは
,「どんな個体 もcの
前者ではない」と主張 している。すなわち, cの 前に数はない,cが
何かの後者 となることはない,と主張 している。(集合論の語法では「cは
関数 σの range[値 域]に
含 まれない」と主張 している。)こ
の主張は,あ る個体 xと その後者:σxの
関係 を,視
覚的に,x→
σx
と表現するとすれば,O→
c
またはc←
○ という図は描 くこ とができない(→が cに 到達することはありえない),ということを意味する。第二の公理:2Pは
, 「異なる個体は異なる後者を持つ」または「 σは単射である」ということを主張 している。図式で示 すと,O→
x一
回 といった図が描けない(二箇所以上の異なる所から一つの個体に複数の→が到達することはない)こ鳥取大学教育地域科学部紀要 地域研究 第
4巻
第 1号(2002) 39
とを意味 している(ただし,上
図のOと
□は異なる個体 とする)。 第二の公理:3Pは
,数 学的帰納 法の完全な形の定式化であり,これは,「どんな性質 も,も しそれが,cが
持ち,それを持つ後者 も 再びそれを持つ (後者系列で遺伝する)よ
うな性質ならば,す
べての個体がそれを持つ」と主張 し ている。「性質」は外延的な解釈により,構 造の領域の部分集合 と解 されるから,言
い換えると,3
Pは
,「0を (要素 として含み),関
数 σに関 して閉 じている任意の集合は,領
域その ものと一致す る」を意味 していることになる。3Pの
第一階言語での表現が公理図式であり,代
入 される述語表 現がせいぜい可算無限個 しか存在 しないゆえに,非可算個以上ありうる性質または集合の十全な表 現に問題があったのに対 して,第
二階言語での3Pの
表現はその難点を免れている。 定義li l. 2
(1)Π
全体のモデルである構造をペアノ 。モデル (またはペアノ構造)と
いう。(2)公
理3Pの
モデルである構造を帰納法モデルという。(3)PA2は
Πの (意味論的)帰
結である文の集合 とし,CON(■
)と
表す。すなわち,P A2=lφ
∈sENT(L2)IΠ
トサ￨=lφ
CSENT(L2)IVMV″
∈Π(M
卜″⇒
M卜φl =CON(Π
). ここで,Π
の各公理のモデルの例 をい くつか見てお く。〔
例
11上
で述べた
,わ
れわれが素朴に知っている自然数の構造
: 打=〈 N, 0, S〉
, すなわちN=10,SO,SSO,SSsO,一
￨で
,0が
最初の数ゼロで,Sが
後者関数SIN→ N
である構造は,ペ
アノ・モデルである。それゆえ,帰
納法モデルで もある。実際,0が
最初の数 だ か ら,0=Sxと
なるxは
Nの
要素の中にはない (ゆえに公理lPが
満た され る)。x+yな
らば,Sx+Syで
ある。なぜ な ら,x+yと
い うことは,SS…
sO=x,SS…
SO=yで
,Sの
個数が異なることを意味するが,そ のとき,そ れぞれに
Sを
一個ず加えたSxと Syも
,依
然 としてSの
個数が異なるか らSx+Syと
なるからである。よって,対
偶をとれば,公
理2Pが
満たされ るこ とになる。さらに,XO(0が
性質Xを
持ち),か
つ任意のzCNに
対 して,Xz→
XSzが
成 り立 つならば,XO,xso,xSSO,…
となって,N中
のすべての要素 xに 対 して,Xxが
成 り立つ。 すなわち,公
理3Pが
満たされる。 【例2】 ゼロと,2を
加 えるという関数:+2(x)=x+2か
ら成 る偶数2N=10,2,4,…
￨ の構造: 〈2N,0,+2〉
もペ アノ 。モデルで あり,帰
納法モデルである。先の例 と同様 に,容
易に確かめ うる。 【例3】 構造:〈
N*,0*,S・
〉 一― ここで,N*=11,2,4,8,…
￨は 2の
中乗:20,21,22,23.…
の集合であり,0*=20
=1,す
べての x∈N■ に対 してS・
(x)=2xで
ある一―は,ペ
アノ・モデルであり,帰
納法 モデルである。【
例
4】構造
:
く
lal,a, f〉
―― ここで
, fはlal上
の可能な唯―の関数である一―は,帰納法モデルであるが,ペ アノ 。モ
デルではない。実際,公理
lPを
満たさない。しかし
,この構造は公理
3Pの
みならず,公理
2P
も満たす
121。田畑博敏 :第 二階論理 によるペ ア ノ算術
〔
例
5】構造
:〈 ta,bl, a,g〉
―― ここで,a+b,任
意のx∈la,blイ
こ対 してg(x)=b
一― は,帰
納法モデルであるが,ペ
アノ・モデルではない (ただ し,こ の構造で公理lPは
満 た される)③ 。【
例
6】構造
:Я=〈
A,ca,σ
a〉一一 ここで
,A=10, 1, 2,3,4,51,ca=0,σ
aはAか
らAへ
の1項関数,す
なわち,σ■
:A→
A
で あ り,σ Я=￨(0, 1〉
,(1, 2〉
,(2,3〉
,(3, 4〉 ,(4, 5〉
,(5,0〉
￨で
ある一― は,帰
納法モデルである。5/0娼
1 関数 σ・ の インプ ッ トとアウトプットの関連は
,
↑
↓
4 2
右 図 によって図示 で きる。 ＼3/
この構造 は,公
理2Pと
3Pの
モデルで はあ るが,公
理lPの
モデル で はない。よって,ペ
ア ノ・モ デル で は ない “ )。 【例7】 構造:0=(B,ca,σ
a〉 ―一 ここで,B=10,1,2,…
,121で
あり,ca=0,σ
ど=￨く0,1),(1,2〉
,(2,3〉
, ¨。,(11,12〉 ,(12,7〉￨と
する一―は,帰
納法モデルである。われわれは関数 σaの値の配分の仕 方を,0→
1→
2→ 3→ 4→ 5→
6ラ
7＼
12 8↑
↓
11 9 ＼10/
と図示で きる。この構造 は,公
理3P,お
よび公理lPの
モデルではあるが,公
理2Pの
モデルで はない6)。 以上のように,ペ
アノの三公理のモデルには,各
種の ものがある。各公理の意味す ることは,こ れ らのモデル を調べ ることにより,一
層明確 に理解で きる。つ ぎに,わ
れわれは,二
番 目の公理3P,す
なわち「数学的帰納法」の原理の定式化 を比較 しよ う。1.2
帰納法の定式化の比較
数学的帰納法
(以下「帰納法」と呼ぶことがある
)の
第二階言語による定式化
:vx[xcAVz(Xz→
Xびz)→
VxXx]
は,公
理図式ではな く,単
一の公理である。この公理 は,第
一階言語による,公
理図式 としての定 式化 (公理の無限集合): φX∧ VZ(φ Z→ φ σZ)→ Vxφ x (,Xは FREE=Ixlで あ る 第 一 階 の式) より,大
きな表現力を持っている。第一階論理による (一項述語に対応す る)論
理式は,可
算無限 個のアルファベ ットを認めたとしても,各 論理式の長 さが有限であるかぎり,可 算無限の個数 しか 持たない。それに対 して,標
準的な意味論を持つ第二階論理では,個
体の全宇宙の任意の部分集合 に帰納法原理は適用でき,そのような部分集合は(個体が可算無限個 しか存在 しないとして も),非
鳥取大学教育地域科学部紀要 地域研究 第
4巻
第1号(2002) 41
可算無限個存在す る。“VX"は
,その ような非可算無限個 ある部分集合 (または個体の持つ性質) のすべてに言及 している。 それだけでな く,第一階論理 を基礎 に した第一階ペア ノ算術 には,自然数の構造に代表 され る,意 図 されたモデル とは同型でないモデル,非
標準モデルが存在す る。この ことは,第
一階論理 におい て成 り立つコンパ ク ト性定理か らの帰結で ある。他方,以
下の補題 (補題1,2.1)に
見 るよ う に,第一階ペアノ算術のモデルで ある構造 Яが標準的数 しか持 たない ととと,標
準的数の集合 が Я において第一階の式 によって定義可能であることとは,必
要十分の関係 にある。よって,第
一階ペ アノ算術 が非標準モデル を持つ とい うことは,意
図 された数 (標準的数)が
第一階の論理式では定 義で きない,とい うことを意味す る。「算術 を適確 に表現す る」とい う観点か らも,第 一階論理の表 現力の弱 さが,こ こで浮彫 りになる。 さて,第
一階ペ アノ算術の非標準 モデル,す
なわち,意
図 された標準モデル と同型でないモデル の存在は ,第 一階論理のコンパ ク ト性定理か ら,(大まかには)以
下のよ うに導 かれ る。第一階ペ ア ノ算術の言語 に,新
しい個体定項 “k"を
加 えて,この言語の語彙 を拡大す る。 さらに,k tt c, ktt
σc, k+σ
σc,
……・ とい う無限に長い文の リス トを,第一階ペアノ算術の公理の集合 Πlに公理 として新 たに加 えて,公 理系 Πlを拡大す る:Πl*=Hl∪
lk tt c,ktt σc,kttσ
σc,…
￨。 この拡大 された公理系 Hlキの任意の有限部分集合H′=Π
l∪ lk tt c,… ,k tt σ 4..σclを
取 り,k=σ
…∵ cと 解 釈 し,cと
σは標準的解釈 を与 えることによって ,こ の有限部分集合 は自然数の構造でモデル を持 つ。 この とき,コ
ンパ ク ト性定理 か ら,Hlキ =Π
l∪lk tt c,kttσ
c,kttσ
σc,…
1自
体 もモデル を持つ ことが帰結す る169。 このモデル を , 町 とす る。飩 は第一階ペアノ算術PAlの
モデルである (つま りHlの
モデルである)と
ともに,新
しい式の集合lk tt c,k+σ
c,kキ
σσc,…
￨の
モデルで もある。従 って,餌
の領域 には非 標準数,す
なわち,ゼ
ロ(最初の数)で
もなく,ゼ
ロの後者で もな く,ゼ
ロの後者の後着で もな く, …,とい う数,が
存在す る。いま,飩
の領域 に含 まれ る (飢で解釈 された)標
準的数:財(c),飩
(σ と),堕
(σ σc),…
の集合 をN(釘)と
す る,す
なわち,N(飩
)=1飩
(c),斑
(σc),餌
(σ σc),…
l。 集合N(虹
)は
,構
造 釘 において,第
一階論理 によっては定義で きない。仮 に,N(朗)が
定義可能 であるとすると,N(町
)=Ix l町
[x]SATβ
l (ここでβは,FREE(β )=lxlで
ある第一階の式) となる。町 は第一階ペアノ算術のモデルだったから,第 一階の式 βで定義 された集合N(飩)に
数学 的帰納法が適用できる筈である。すると,飩
の宇宙は,N(飩 )の
要素,す
なわち標準的数以外の要 素は含まないことになり,町
は非標準的数を含むという,先 の結果 と矛盾する。こうして,N(町
) が,構
造 飩 において第一階論理では定義できない,と い うことが分かる。 一般に,PAl(第
一階ペアノ算術)の
標準モデル と,標
準的数の集合の (第一階論理での)定
義可能性 との間を結ぶ,つ
ぎの補題が成 り立つ。 補題1.2.1.
Я
=く
A,ca,σ
A〉 をPAlの
第一階モデル とする。この とき,
田畑博敏:第二階論理によるペアノ算術 ⇔標準 的数 の集合
N(Я
)が
Яで定義可能 で あ る。【
証明
, [⇒:]Я
が標準モデルであるとすると,冤の宇宙の要素はすべて標準的数である。このとき,第
一 階の論理式 “x=x"は
,そ のようなすべての要素に対 して成 り立つから,標
準的数の集合,す
な わち冤の領域Aそ
の ものは,(式
x=xに
よって)定
義可能である。 [⇒:]標
準的数の集合N傲
)が P Alの
モデル Яにおいて,第
一階の式 βによって定義可能だとす る。つ まり,N徹
)=lx:Я
[x]SATβ
l(こ
こでβは自由変項 としてxの
みを含む第一階の 式)が 成 り立つ とする……(イ)。 いま,(第一階の形での)帰
納法の公理の対偶 をとり,これを(★) で示す:(★
):
ヨ
x司φ
x→
[￢φ
CVヨ
y(φy∧
コφσ
y)]この式 は,帰納法公理の対偶 だか ら
,P Alの
モデル Яで ,自 由変項が “x"の
みであるような,任
意の第一階の式φ
xに
対して
,成り立つ。このφ
xを
,N`り
を定議する第一階の式βとみなすと
,式 (☆
)の
解釈 は,つ
ぎの ようになる:「
x/N(Я)で
あるようなx∈Aが
存在す るな らば,ca/N(Я
)で
あるか,さ もなければ,y∈
N(4)し
か しσa(y)〆 N仰
)で
あるような,y∈
Aが
存在す る」。いま仮 に
,x/N傲
)で
あるようなx∈Aが
存在す る,と仮定す る。すなわち,Яが非標準モデ ルである,と仮定す る…… (口)。 Яは (第一階の)ペ
アノ 。モデルで あるか ら,ca c N(Я)で
ある。よって
,(★
)に
よ り,y∈
N(Я)し
か しσ・(y)/N(Я
)で
あるような,yCAが
存在す る,とい うことが帰結す る。これは
,標
準数の集合がある要素 を欠いてい るとい うことに外な らず,標
準数の集合 を定義で きているとい う,最初の仮定 (イ)に
矛盾す る。従 って,二番 目の仮定 (口)は
成 り立たない。すなわち,Яは,非
標準モデルではな く,標
準 モデルで ある。Q. E. D.
こうして,帰
納法公理の,第
一階論理 による定式化 と,第
二階論理 による定式化 との違いが明確 になった。第一階論理 による帰納法公理の定式化に関 して,非
標準数 を持つ非標準モデル を取 った とき,(上の補題 によ り標準的数の集合 が第一階の式で定義で きないか ら)標準数の集合 に対 して帰 納法 を適用で きない。言い換 えると,第
一階の帰納法の図式 は,非
標準数の出現 を食い止 め られ な い。標準数であることの必要十分条件 を与 える第一階の式 βを,われわれが手 に入れたとす ると,￢ βは非標準数の必要十分条件 を与 えることになる。この式 βを,第一階の帰納法図式 に当てはめて, 非標準数の存在 を認 め ると,標
準数の集合が要素 を欠 く,と い う結果 を招 き,標
準数の集合 は定義 で きな くなる。第一階論理 を基礎 に取 るかぎり,コ ンパ ク ト性定理 を認めねばな らない。そうす る と,非
標準モデルの存在 をも認 めねばな らない。す ると,補
題1,2.1に
よ り,そ
の非標準モデ ルでは標準的数は定義で きなくなる。 これに対 して,第
二階論理で定式化 された第二階ペアノ算術 は,以
下で見 るようにカテゴ リカル であるか ら,第
二階の帰納法公理 は非標準数 を阻止す ることになる。1.3
非標 準 モデル ここで,非標準 モデル に関す る「状況」を一瞥 しよう。1930年
代 にスコー レム(T.skolem)
よって発見 された算術の非標準モデル は ,病理的な反例 といった程度の認識 を得たにす ぎなかった が,1950年
以降のヘ ンキ ン(L.Henkin)の
高階論理 と一般意味論の研究 ,さ らにロビンソン(A.Robinson)の
ノンスタンダiド
・アナ リシスの展開により,市
民権 を獲得 している。ヘ ンキ ン鳥取大学教育地域科学部紀要 地域研究 第
4巻
第1号(2002) 43
は,標
準意味論 とは異 なる,一
般構造 に基づ く一般意味論 を用いて,算
術 の (二重の意味で)非
標 準 なモデル を開発 した。一般意味論においては,第
二階論理は,強
い意味で完全 とな り,コ ンパ ク ト性 も取 り戻す。 第二階論理 において ,非 標準構造 Яは,個 体の宇宙 とじて集合Aを
持 ち,関 係宇宙 として,An⊆
T Anで
ぁるような,集
合族 : 〈An〉 n≧1 を持 ち,少
な くとも一つのm≧
1に対 して,A.m+?Am
…… (★★) である。この最後の条件 (★★)が
,第
二階の意味で「非標準的」 とい うことの,実
質的な内容で ある。 さて,自然数の第一階理論 (第一階ペアノ算術)が
持つ非標準モデルか ら,第
二階ペ アノ算術の 非標準モデルがどのように して創 られるか:その概略 を見 よう。いま,第
一階ペアノ算術の非標準 モデル を任意 に取 り,これ を 飢 とす る。任意の ■≧1に対 して,n項
関係の関係宇宙Mnが
,Mn⊆
?Mn(Mnが
Mの n項
デ カル ト積の巾集合の部分集合)で
あるよ うな,集
合の族 : (Mn〉 n≧1 を選ぶ ことによって,釘
か ら,第二階論理 に対応す る構造 を構成す る。こうして得 られた第二階の 構造 を いた* としよう。飢*は第二階ペア ノ算術(P A2)の
モデルだろうか?飩
半に関する詳 しい構成法が未だ 与 えられれていないが ,も し飩 半がP A2の
モデルであるならば,阿
*は必ず,第
二階の意味で非標 準で あらねばならない,と い うことが帰結す る。特に,Ml+,MI=TM
ヽ である(Mは
飢 の個体宇宙)。 その理 由はこうなる。PAlの
非標準モデル 堕 における標準数の集合 :N(飢
) を考 える。 もし第二階の構造 町*が
PA2の
モデルであるな らば,そ
れは特 に (第二階の)帰
納法 公理のモデルで もある。さて,標
準数の集合N(町
)が
,飢
*の一項関係の宇宙Mlの
中に含 まれて いる,す
なわぢ, ,
N(斑
)CMl…
…① と仮定 しよう。この集合N(い0は
,ゼ
ロを含み,後
者に関 して閉 じている(すなわち,この集合の 各要素の後者が再びこの集合の要素 となる)か
ら,帰
納法公理により,Vx(xC M→
xCN(飩
)), すなわち,M⊆
N(町
) である。ところで ,当 然,すべての標準数は飢 の個体宇宙Mの
要素であるか ら,N(飩
)⊆Mで
ある。 よって,これ らか ら,M=N(斑
) が導 かれ る。 しか し,こ の ことは成 り立たない。なぜ なら,飩
は非標準モデルで あったか ら,Mに
は,N(釘
)の
要素以外の,非標準的数が要素 として含 まれているか らである。従 って,先の仮定①田畑博敏:第二階論理によるペアノ算術
は成 り立たない。すなわち
,、
N(飢
)/Ml
である。しかし
,N(飢
)⊆M
であるから
,N(飩
)∈,M
ではある。よって
,Ml半
?M
が帰結す る。こうして,町
*は「第二階の意味で」(先の条件 (★☆)を
参照)非
標準的である (す なわち,一
項関係の宇宙 は,個
体宇宙の巾集合の,真
部分集合 となる)。 第二階ペアノ算術 がカテゴ リカルで あるのは,ス コー レムが指摘 したように ① ,帰 納法公理に現 れ る集合 が,標
準的な意味 によって解釈 され るときに,か
ぎる。すなわち,標
準的意味論一一 そこ ではn項
関係の宇宙は個体の宇宙のn項
デカル ト積の巾集合である:An=9An十
一 を用いて,メ タ 理論か ら意味 を与 えるときに,かぎられ る。しか し,ヘンキン (Henkin[19501)1ま,個
体宇宙の非 標準化 と関係宇宙の非標準化 とい う二重の意味で,非
標準モデルを構成す ることを可能 に した。も ちるん ,も し意味論 を変 えるな らば,わ
れわれは標準 的見方 を捨てて,一
般 的な集合概念 をモデル に付加 しなければな らない。 こうして,われわれが非標準的解釈 に踏み込 んで行 くや否や,第二階論理 は表現 力の ある部分 を 失い,もはやカテゴ リカルではな くなる。 しか し,意
味論 を変 えて も,第
二階ペア ノ算術 は第一階 ペアノ算術よりは強力である。なぜなら,PAlの
無矛盾性がP A2で
(意味論的に)証
明 され るか らである。 すでに見たよ うに,第
一階ペアノ算術 がカテゴ リカルでないのは,標
準数の集合N(飢
)=￨
飢(c),町
(σc),飢
(σ σc),… ￨が ,非
標準数 を持つ構造(=非
標準モデル)で
,第
一階の式 によって定義で きず ,そ れゆえ,この集合にたいして帰納法公理 を適用できないか らであった。な ぜ,標
準解釈 を持つ第二階ペアノ算術がカテゴ リカルであるか?その理由は,そ こでは,す
べての 可能な (個体の)集
合に対 して,帰
納法公理が適用できるからであり,非
標準数を持つ構造は,第
二階帰納法公理のモデルにならないからである。 われわれが,第
二階論理にとどまり,し かも,十
全でない (つまり個体宇宙のn頂
デカル ト積の 中集合の真部分集合を関係宇宙 として認める)構
造 を採用するとき,量
化は,そ の構造に現われた 集合や関係にしか適用 されない。そのとき,一
項関係の宇宙は,そ の要素の一つ として,標
準数の 集合を含まないかもしれない。ヘ ンキンの一般構造では,第 二階の式によってその構造で定義でき きる,す
べての集合と関係 とを,そ
の宇宙 とする。そうすると,第
一階のケースと同様に,非
標準 数を持つ構造では,第
二階の式によって標準数の数が定義できない,と い うことが起 こる。2.第
二階 ペ ア ノ公理 系 の カテ ゴ リ ー性 この節では,第二階ペアノ公理系がカテゴリカル (categonca)で ぁること,す なわち任意のペア ノ・モデルが同型である (isomorphic)で あることを示す。そのために,ま ず,二
つの補題を準備 し,こ れを用いて二つの定理を証明する。最初の定理 (定理2.2.1)は
,回
帰定理 (recurslonheorem)と
呼ばれるもので,これは,任
意のペアノ 。モデルN=〈
N,cr,σ
め と,こ れと同じ タイプの任意の構造 Я=(A,cA,σ
a〉 との間に,唯
一の準同型写像(homOmorphism)が
存在することを主張する。この準同型は,自 然数の切片 (ゼロまで減少する鎖
)を
定義域 とす る部分関数の合併 として定義できる。これが,の ぞましい準同型 となっているかどうかということ
,は
確認 さ鳥取大学教育地域科学部紀要 地域研究 第
4巻
第 1号(2002) 45
とす るとき,Я がNめ
ある準同型の像 となることの必要十分条件 は ,Я が帰納法モデルである,と い うことを主張す るものである。この二つの定理 によ り,任
意のペ アノ・モデルが同型的で あると い うこと (定理2.4.1)が
導かれ る。 この ような順序 で進むことに しよう。2, 1
準備 :部分関数 構造N=(N,cΥ
,σ→ をペ アノ 。モデル,す
なわち,ペ
アノの三公理lP,2P,3Pを
すべて満たす構造 とす る。Я
=〈
A,ca,σ
a〉 を,打と同 じタイプの signatureを 持つ(すなわち,caが
c「と同様 に個体 (ただ し
Aの
要素)で
あり,σaが σ下と同様 に一項関数 (ただ しA上
の)で
あるよ うな),任
意の構造 とす る。以下の定義 は,これ らの構造 に対 して与 えられ る。 定義2. 1. 1:切
片の定義Nの
部分集合H(す
なわちH⊆
N)が
切片 (segment)で あるのは,Hが ,ざ
まで減少す る鎖(chain) である場合,す
なわち cT∈H & Vx∈
N[σ
tt x∈H⇒
x∈H]
とい う場合,で
ある。 この定義 によれば,明
らかに,Nと
lc打￨は
,と もに切片である181。N自
身がNの
最大切片であり,IcΥ
Iは Nの
最小切片で ある。ic「￨が
切片で あるのは,特に公理lPに
よって保証 され る。Nの
切片 を小 さい方か ら描 けば,つ
ぎのようになる。 ic打￨icT,
σlcrrlicr,
σttc下, σΥσ 「 c下￨ ic下, σ州「cTf, σち 「 C下,
σ ttσ ttσ Trcて,
………￨ =N
定義2.1.2:(切
片上の)部
分関数の定義 fが切片上で定義 され る部分関数 (pa al function)で あるのは, fが
つ ぎの二つの条件 (1),(2)を
満 たす,切
片H(⊆ N)か
らAの
中への関数 (写像)で
ある場合 である:f:H→
A
(1)f(cr)=cЯ
(つまり,ペアノ・モデルNで
のゼロに相 当す る要素c(1ま,fに
よって,構
造 Яの特異要素cЯに対応づけ られる)(2)f(σ
tt x)=σ A f(x) (つまり, x∈Hが
, fによって, f(x)∈
A
へ と写 される な らば,x→
σ 「 xと い う対応 を,f(x)→
σA f(x)
とい う対応で模倣するように, fは
,びイxを
,σa f(x)へ
と写す) こうして,部
分関数 fは ,ま ず (1)イこより,Nの
特異要素 (最初の数ゼロ)で
あるc打を,Aの
特異要素caに写像 して,写
像の基底 とする。つぎに, fは
,双
方の構造における関数 σ 「 とσAの, インプッ トとアゥ トプッ トの対応の仕方 を保存する仕方で写像する。すなわち, fは , fに
より関 連づけられた,双
方の構造の要素x∈ Nとf(x)∈ Aが
,そ れぞれ,対
応する関数 σ 「 とびaの
イン プッ トであるとき,そ
れ らのアウ トプッ ト同士で,び 打xを
σa f(x)へ
と写像する: f(σ 「x)=σ
A f(x)。 この(2)の
条件 は,準同型 で あ る要件 の一つで ある0。
田畑博敏 :第二階論理によるペアノ算術
f(x)
￨ σЯ f (x) X ￨ σ`rx 補題2. 1.3:Nの
すべての要素 は,(なん らかの)部
分関数 fの定義域(domain):
Dom f中
にある。 I証明】 次の方針で証明する。まず,「ある部分関数の定義域に (要素 として)含
まれる」という条件 を満 たす,Nの
要素の集合Gを
定義す る。この,Nの
部分集合Gに
対 して,Gが
cイ を含み,「後者」関 数:σ打1こ関 して閉 じている,とい うことを示す。Nが
ペアノ 。モデルであることにより,公 理3P
をこのGに
適用 して,Gが
N全
体 と同一であることを導 く。そこで,ま ず,Gを
定義する:G=lx∈
NIヨ
f(fは
部分関数&Dom fは
切片である&x∈
Dom f)￨。1,基
底 ic下∈G。理由はこうである。fと して
,f(cr)=cAで
定義 される関数f itcTI→
A
をとる。先に述べ たように,公
理lPに
より,Icrl=Dom f⊆
Nは Nの
切片である。部分関数の定義より, fは
部分関数である。
cTC ic下
￨=Dom f。
∴ヨf(fは
部分関数&Dom fは
切片である&
c下 ∈
Dom f),i crc G。
2.帰
納 の ステ ップ:Vy(yCG⇒
σΥ y∈ G)。なぜなら一―。任意の
yCNを
とり,y∈
Gと
仮定す る。すると,Gの
定義により,あ る部分関数 fが存在 して,Dom fは
切片であり,y C Dom f。
いま,σtt yをとる。場合 を二つに分ける。(イ
)も
し,σ r y∈Dom fな
らば,Gの
定義により,σΥy C G。 (口)そ
こで,σイy/Dom fと
する。そして,H=Dom f∪
l σtt y lf*=f∪
￨(σtt y,σ a f(y)〉￨ と して,fの
拡 張 関数fキ を定義す る。この とき,以
下 で示 す よ うに,①
H,す
なわ ちDom f半
は切片となり,②
f・は部分関数である。しかも,③ σ
「
yCH=Dom f■
だから
,Gの
定義により
, σtt y∈Gで
あ る。 ① まず,上
の定義 により,H=Dom fIで
あるが,こ
のH
は切片で ある。なぜ な ら,Dom fが
切片であるか ら,∬
∈Dom f,ic打
∈H。 いま,任
意のxCNを
とり,σtt xを考 える。 σtt x∈
Dom f*=Dom f U lσ
ttyl=H
と仮 定す る。もしσtt x+σtt yかつ σttx C Dom fな
ら1ぎ,Dom fが
切片で あるか ら,切
片の定義か ら,x∈
Dom f⊆
Dom f*。
もしσtt x=σtt yな らば,ペアノ公理
2Pに
よ り,x=yで
ある。ところが,y C Dom fだ
か ら,x∈
Dom f⊆
Dom f*。
いずれにせ よ
,x∈
Dom f*=H。
こうして ,σtt x∈H
とい う仮定か らx∈Hが
導 かれた。す なわち,Vx∈
潤 (σダxGH⇒
x∈ H)。 こうして,Hは
(σ打に関 して)単
調減少条件 を満 た し, しか も,c下 ∈Hだ
ったか ら,このHは (Nの
)切
片である。②つぎに, f*が 部分関数であることを示すために,部 分関数の定義により, f*が
, (1)f・ (cり=ca
(2)f*(σ
tt x)=σa f*(x)(σ
Υ
x∈Hで あるすべての
x∈Nに 対して
)と
いう二つ
鳥取大学教育地域科学部紀要 地域研究 第4巻 第 1号
(2002) 47
の条件 を満たす ことを示せばよい。まず,(1)である。
Dom fは
切片だか らc打∈Do“f,し
か もfは部分関数だか ら
, f(cr)=cao f・
の定義 よ り f⊆ f*,.・.c「∈Dom f⊆
Dom f*。
よっ て,f*(∬ )=f(cr)=ca。
次 に(2)である。任意の x∈Nに
つ き,も しσtt x∈Dom fな
らば,
fが部分関数で あることとf⊆ f半 か ら
,直
ちに成 り立つ。もしσtt x/Dom fで
,σtt x=σtt yの とき,公理
2Pよ
り,x=y。
ところが,f・ はf・=f∪
￨くσtt y,σЯ(fy)〉
￨と定義 し,かつy∈
Dom f⊆
Dom f*だ
か ら, f*(σ
tt y)=σ
a f(y)=σ a f*(y)。
x=yだ
か ら,(2)が成 り立つ。
③
f*の
定義 により,σtt y∈Dom f■
である。こうして,「f・ は部分関数
&Dom fキ
は切片&σtty C Dom fキ 」である。よって,Gの
定義 によ り,σtty C G。 ゆえに
,上
の帰納のステ ップが成 り立つ ことが示 され た。 よって,基
底 と帰納のステ ップが成 り立つか ら,公
理3P(数
学的帰納法)に
よ り,Gは
N全
体 である。すなわち,G=No Q・
E.D.
以上の証明において,わ
れわれは二つの公理,lP,2P,3Pを
全部用いた。次 に二番 目の補 題 に移 る。 補題2.1.4
fとgが部分関数で,x∈
Dom f∩
Dom gと
す る。 この とき, f(x)=g(x)。
(この補題の意味 は,二
つの部分関数が,共
通の定義域に関 しては一致す る,と い うことで ある)【
証明】
先の補題のときと同様に,望 ましい性質を持つ
,Nの
部分集合を定義 して
,これが実際には
Nと一致することを,公理
3Pを
用いて証明する。まず ,そ の (Nの
)部
分集合として
,G=lx∈
NIVfVg(fと
gは部分関数である
&x∈
Dom f∩
Dom g⇒
f(x)=g(x)￨
を定義 す る。1.基
底:♂
∈G
なぜなら一―。任意の部分関数
fをとると,部 分関数の定義により
,fは
ある切片上で定義 される
が,そ の切片に
(切片の定義により
)c下が必ず含まれているから
,c下∈
Dom fで
あり,か つ
f(c→
=caで
ぁる。そこで
,いま
,fと
gが任意の二つの部分関数である
,とする。cTC Dom f
かつ
cΥC Domg,ゆ
えに
c下∈
Dom f∩
Dom g。このとき,f(cり
=c・,g(cり
=caで
ぁるか
ら
, f(cり=g(cり
である。こうして,cr∈
G.で
ある。
.2.帰
納のステップ
iVy(yCG⇒
σ
「
y∈ G)以下のようにして
,これが成 り立つことが分かる。任意の
yCNを
とり
,yCGと
仮定する。そし
て
, fと目を任意の部分関数とする。場合を二つに分ける。
イ
)σ tty C Dom f∩Dom gの とき。部分関数の定義の
(2)イこより
,f(σ tt y)=σ
a(fy)]…
… ①
g(σ
tt y)=σЯ(gy)
仮 定 よ り,σ 「 y∈Dom f
かつ σ tt y∈ Dom g。 また,部
分 関数 の定義 域 は切 片 で あ り,切
片 は σ下に関 して単調 に減少す るか ら,y C Dom f∩
Domgo y∈
Gだ
か ら,これ らの こ とか ら,f(y)=g(y)…
…②
田畑博敏:第二階論理によるペアノ算術
σtt y∈
Dom f∩
Dom g⇒
f(σtt y)=g(σ
Υy)・…・・・③。
口
)σ tt y/Dom f∩ Dom gの
とき。このとき, トリヴィアルに,上
の③が成 り立つ。 こうして,イ),口
)よ
り,VfVg[fと
gが 部分関数&σtty C Dom f∩ Dom g⇒
f(σΥy)=g(び
下y)]すなわち,σ 「 y∈
G
である。 こうして,帰
納のステップは成 り立つ ことが示 された。 以上により,帰
納法公理3Pに
よって,G=N。
Q. E, D.
二つの補題 が証明で きたので,本
題の定理 に移 る。2.2
回帰(recursion)に
関 する定理 定理2.2.1:回
帰定理 (recursion heorem) 任意のペアノ 。モデル:打
=(N,c下
,σめ と (これ と同 じタイプの)任
意の構造 :Я=(A,
ca,σЯ〉との間に,ただ一つの準同型写像(homOmorphism)が
存在す る。 【証明】 先 の二つの補題 を組み合わせ ることによ り,Nの
各要素は,(それを定義域 に含む)任
意の部分関 数によぅて,A中
の同一の要素 に写 され る。なぜ な ら,最
小の切片上で定義 され る最小の部分関数 か ら出発 して,σ下に基づいて切片 を大 きくす ることにより,部
分関数 を大 き くす るとき,補
題 2.1.4に
より,共
通の (つまり小 さい方の)定
義域 に含 まれ るNの
要素 は,同
一のAの
要素 に写 さ れ る。このように して,増
大す る部分関数の列 が生 じるが,大
きい関数 は,小
さい関数 を部分 とし て含んでいる。補題2.1.3に
よ り,Nの
要素は,♂
か ら始めて,この部分関数の列の,定
義域 の列 に新たに加わるが,新しい (大きな)部
分関数の定義 に含 まれたときも,写
され るAの
要素 は, 小 さい関数の定義域 に含 まれていた ときと同 じAの
要素がその まま引 き継 がれ るか らで ある。従 っ て,x∈
Nで
ある任意のxに
対 して,(x∈ Dom fと
なる)任
意の部分関数fに対 して,f(x)=z
とな るよ うな,唯
― のz∈Aが
存 在 す る。い ま,す
べ てのx∈Nに
対 して,h(x)を
,上
で述 べ た唯― の,Aの
要素zで
あ るよ うな,そ
うい う関数:
′hiN→
A
と定義す る。す なわ ち,h=￨〈
x,z〉 ￨ヨf(f:N→ A&fは
部分 関数&f(x)=z)￨と
す る。言 い換 えると,hは
す べ て の部 分 関数fの合 併 (uniOn)であ る。証 明すべ きことは,この 関数hが
Nみ
らЯへ の準 同型写像(homOmorphism)で
あ り,しか も,その よ うな唯― の可 能 な準 同型 で ある,とい うことで ある。 さて,部
分関数の定義により,す
べての部分関数 fに 対 して, f(cり=caで
あるか ら, h(cり =cЯ¨・…①ぅ である。さらに
,補
題2,1.3に
より,Nの
要素はなんらかの部分関数 fの 定義域 に含 まれてい る (σtty C Dom f)の
で,任
意の σr y∈Nに
対 して,あ
る部分関数 fが 存在 して, f(σ
r y)=zCA
である。ところで,hの
定義より,h(σ ar y)=zだ
から, h(σr y)=f(σ
tt y)… …② fは 部分関数だから,部
分関数の定義 [定義項の (2)1により, f(σT y)=σ
Я(fy)…
…③ 再び,hの
定義により,hy=fyで
あるから,こ
れ と③により, f(σtt y)=σ
a(hy)…
…④鳥取大学教育地域科学部紀要 地域研究 第
4巻
第 1号(2002) 49
② と④ より, h(σtt y)=σ
a(hy)…
… ⑤ ① と⑤により,関
数h(hiN→
A)が
準同型であること,が
示 された。 残 された課題は,hの
唯一性 (uniqueness)で ある。hの
定義 と,上
の①,⑤
により,hは
,切
片Nを
定義域 とする部分関数である。いま,定義域 をNと する任意の部分関数fをとる。補題2,1.
4に より,x∈
Dom h∩ Dom fで
ある任意の x∈Nに
対 して,h(x)=f(x)で
ある。ところが
,Dom h=Dom f=Nで
あるから,N=Dom h∩
Dom fで
ある。よって,任
意の x∈Nに
対して
,h(x)=f(x)で
ある。すなわち,f=h
で ある。 こう して,準
同型hは
唯― に決 まる。Q・
E. D.
2,3
帰納法 モデル とペ ア ノ・モデル つ ぎに,帰
納法モデル とペアノ・モデルの間の関係 に関す る定理 に移 る。 定理2.3.1
構造 打=(N,∬
,σ め をペアノ・モデル とし,Я=く
A,ca,σ
■)を
Nと
同 タイプの任意 の構 造 とす る。 この とき, 冤はNの
準同型像(homOmorphic image)で
ある ⇔ Яは帰納法 モデルである。 【証明】[⇒
:]冤
を,準
同型hiN→
Aに
よる,Nめ
準同型像 とす る (すなわちA=h[N])。
示すべ き ことは:Яが公理3Pの
モデルである,とい うことで ある。いま,caC H
かつVy(y∈
H⇒
σa y∈H)
であるような
,任
意のH⊆ Aを
考 える。われわれは,H=Aで
あることを示 したい。さて,仮
定 に より,Я はNめ
hに
よる準同型像であり,Nは
ペ アノ 。モデルで あるか ら,「
に対 して公理3Pを
用い ることがで きる。そこで,Nの
要素で,hに
よるその像 がHの
要素であるもの(Hの
要素の,h
による逆像)の
集合Gを
定義す る。すなわち,G=IxCNl h(x)∈
HI。 もし(1)基
底:∬
∈G,お
よび(2)帰
納のステ ップ:Vy(y∈
g→ σΥy c G)が
示 された とすると
,Nに
対 して公理
8Pを
適用して
,G=Nを
得る。すると,Gの 定義から
,G=Nに
より
,Vx(x
CN⇒ h(x)∈ H)で
あ る… …① 。 よって,h[N]⊆
Hで
あ る。 (実際,yCh[N]=ty∈
AIヨ
xCN(h(x)=y)￨と
す ると,あるxCNが
存 在 して,h(x)=y。
と ころが,①
よ り,h(x)CH
で あるか ら,y∈
H。 区上 よ り,yCh[N]⇒
y∈Hc∴
h[N]⊆
H。)仮
定 に よ り
,Aは
Nの hに
よ る写像の値域 に一致す る (つま りhは
Aの
上 へ の写像)で
あ るか ら,A
=h[N]で
あった。 ゆ えに,A⊆
H。 しか し,Hの
定 義 よ り,H⊆
A。 ∴H=A。
よ って,aは
公理3Pの
モデル とな る。 こ うして,右
辺 が導 かれ る。 そ こで,上の(1)と
(2)力I成り立 つ ことを示 せ ば十 分 で あ る。(1)基
底ic下∈G。なぜなら
,∬
CN,か
つHの 定義により,ca c H,そ してhは 準同型であるから,h(cり
=cA,∴
h(c州9 CH,ic下 ∈ lxCNlh(x)∈ HI=G。(2)帰 納のステップ
:Vy(y∈
G⇒
σ
ry C G)。田畑博敏 :第二階論理によるペアノ算術
任意のy∈
Nを
とり,yCGと
す る。Gの
定義 によ り,h(y)∈
Ho Hの
定義 より,Hは
後者 関数に関 して閉 じているか ら,σ■
(h(y))∈
H。 しか し,hは
準 同型で あるか ら,h(σ
tt y)=σЯ(h(y))。 .・.σΥ y∈
N&h(σ
tt y)∈ H。 ∴ σ「 y∈ Ix∈
Nlh(x)∈
HI=G。
こうして,Vy
(y∈
G⇒
σtty C G)が
示 された。[←:]Яを帰納法モデル とし,N‐をペアノ・モデル とす る。回帰定理 (定理
2.2.1)に
よ り,Nぬ
ゝらЯへの唯―の準同型 (写像)hが
存在す る。冤がNめ
準 同型像であることを言 うには,hが
「上への」(onto)写像であること,す
なわちh[N]=Aで
あること,を
示せ ば十分である。い ま,H=h[N]と
定義す る。す なわち,H=ly∈ AIヨ x(x∈ N &h(x)=y)￨
とする。もし
,(1)基
底icac H,(2)帰
納のステップ:Vy(y∈
H⇒
σa y∈H)が
成 り立てば,Яが帰納法モデルであることか ら
,公
理3Pを
適用 して,H=A,ゆ
えにh[N]=Aを
得 る。(1)基
底icЯ∈H。なぜなら一―。
hは
打からaへ
の準同型だか ら,h(cり
=ca
かっc下∈N。 もちろんcЯ∈Aだ
か ら
,ca∈
lyCAIヨ x(xCN&h(x)=y)￨=H。
(2)帰
納のステ ップ:Vy(y∈
H⇒
σЯy C H)任意の
y(∈
A)を
とり,y∈
Hとす る。Hの
定義 よ り,あるx∈Nが
存在 して,h(x)=yo h
は準同型 だか ら,h(σ
Υx)=σ
a h(x)=σ
a y。 しか も,σtt x∈ N。 ゆえに,
σΥ
x C N &h (σ tt x)=σ
a y∈A。∴ σЯ y∈ ly∈
AIヨ
x(x∈
N &h(x)=y)￨=H。
以上 よ り
,Vy(y∈
H⇒
・σyCH)が
示 された。Q. E.D.
2.4
ペ ア ノ・モデル の 同型性 さて,先
の二つの定理,す
なわち回帰定理 (定理2.2.1)と
定理2.3.1,を
用いて,ど
のような二つのペアノ・モデル も互いに同型であること,言
い換 えると,ペ
アノの公理系 Πはカテ ゴ リカル (範疇的・定型的i categonc』)で
ぁること,が
証明で きる。これ をつ ぎの定理 とす る。 定理2.4. 1:任
意のペ アノ 。モデルは同型的 (isomorphic)で ある。〔
証明】
、
構造:打
=(N,c下
,σTfy および 幹=〈
N*,c下■,σ下キ〉 を二つのペアノ・モデルとす る。定理2.2.1と
定理2.3.1に
より,Nか
ら御Pの
上への準同型hi
h:N→
が存在 し,か
つ,幹
幹 か らNめ
上への準同型h*:
ontoh*:幹
→ 打 が存在す る(10。 ここで,こ
れ ら二つの準同型 hと h・ の合成 : h・Oh
がNか
らNへ
の準同型写像 となることは,容
易に示 す ことがで きる 。う。 ところで,定
理2.2.
1(回
帰定理)に
よれば,Nセ
打 との間には唯―の準 同型 が存在す る。Nか
らNの
上への同一性 関鳥取大学教育地域科学部紀要 地域研究 第
4巻
第 1号(2002) 51
数 [恒等写像I(x)=x]は
準同型であ り,(関
数 としては)hキOhと
同一で ある。す なわち,h*
Ohは
打か らNへ
の唯―の同一性関数 に外 な らない。よって,hは
一対―でなければな らない (さ もなければ,世
がペアノ 。モデルであることに反す る事態が生 じる 住211。 従 って,hは ,Nか
ら N稗 の上への一対一写像で あるような,準
同型である。すなわち,hは ,Nみ
ら御卜 の上への同型 写像 (isomorphism)で ある。Q. E. D.
こうして,す
べてのペアノ,モデルは同型的であるから,あ たかも唯―のペアノ・モデルが存在 するかのように語 ることができる。いわば,同
型なすべてのペアノ 。モデルを代表す る構造を, 打=〈 N, 0, S〉
と表示する。以後 ,こ のモデルを「意図されたモデル」(intended model)と 同一視する。3.ペ
ア ノ・ モ デル と原 始 回帰G.ペ
アノは,未 定義の原始概念 として,自然数 ,ゼ ロ,後 者の概念 をとり,それ らについての公 理系 Π(通常は五つの公理の集 まりを考 えるが,わ れわれの場合は,「構造」を対応 させるので,三 つで十分である),す
なわち,lP,2P,3Pを
定めることで,自
然数 を公理化 している 住。。わ れわれは,こ の公理系の任意のモデルが,意
図 されたモデル: イ=(N, 0, S〉
と同型である (isomorphic),と いうところまで,自然数についての理解を確定 させた。 さて,これ らの公理に現れる一つの特異な対象としてのc打(すなわちゼロ)と一つの演算 σΥ(す なわち「後者」関数)だ
けでは,自然数の多面的性質をうまく表現す ることはむずか しい。そこで, 例 えば,自然数の加法・乗法・巾法などを導入 して,「素数性」といった興味深い概念を容易に定義 できるようにしたい。しか し,あ くまで ,そ の基礎 となるのは,ペ
アノの公理系でなければならな い。では,ど
のようにすれば,そ
れ らの演算を導入できるか? ペアデの方法は,数
学的帰納法の原理 を用いて,これ らの演算を定義することである。よく知 ら れた加法の定義は,つ
ぎの二つの方程式によって与えられる:(Vx,yCN)
x+0=x
x+Sy=S(x+y)。
では,その とき,加
法の定義 は自然数の構造,つ
まりわれわれの「意図 されたモデル」でのみ定義 され るのか,それ とも任意のペアノ構造で も定義で きるのか?われわれ は回帰定理(定理2.2.1)
によって,任
意のペアノ構造 に対 して,同
一の演算の存在 を示す ことがで きる,と い うのがその答 えである。実際,回
帰定理の存在意義 は,この ような定義 による関数 を一般 的化 した関数,す
なわ ち原始帰納的関数;の
導入 を正当化す ることにある。 では,どの ように して,回帰定理 がペアノ・モデルに共通の演算 を定義す るのか?われわれは,任 意のペアノ・モデル : 幹=〈
Nキ ,cΥ・ ,σ打*〉 と任意の (同タイプの)構
造:71=(A,cA,σ
A〉 を持つ とき,方
程式:(a)h(cTf・
)=ca
(b)h(σ
下*y)=σ
Я(h(y))
田畑博敏:第二階論理によるペアノ算術 が
,数
学的帰納法によって,hを
定義す ることになることを,以
後,具
体的に示す。 こういった定 義 は,こ れ らの方程式 によって定義 され る唯―の関数が存在することを示す ことによって,自 らを 正当化 しなければな らない。実際,この ような関数hが
唯一存在す ることは,回帰定理(定理2.2.
1)が
主張 していたことであった。以下で,わ
れわれは,ペ
アノ 。モデルで唯―の加法,乗
法,巾
法の各演算が存在す ることを示す (命題3.1.1,命
題3.1.2,命
題3,1.3)。
さらに, 回帰定理 によって,「ペアノ 。モデルでは,数学的帰納法 を用いることによって,すべての回帰的演 算 (recursive operation)が 導入 され うる」(定理3.2.1)と
い う,よ り強力な結果 が得 られ る (乗法 と巾法の存在 は,こ
の定理の系 として導かれ る)。 自然数上の関数の この ような定義法は,ペ
アノ 。モデル以外で も有効 だろうか?ペアノ・モデル ではない帰納法モデルでは ,(後 に見 るように)必
ず しもそうはな らない,とい うことをヘ ンキ ンが 示 している。 しか し,と もか く,こ
の節では,ペ
アノ・モデルでの関数の確保 を追究 しよう。3.1
ペ ア ノ・モデル にお ける加法・乗法・ 巾法 命題3. 1. 1:す
べてのペアノ・モデルで,唯
―の加法の演算が存在す る。 【証明】 N稗=(N■
,c下*,σ
Υ*〉 をペアノ構造 とす る。示 したいことは,以
下の (1.1)と (1.2)を満 た す,唯
―の演算fが存在す ること,で
ある(10:(1.1)f(x,c打
半)=x
(1.2) f(x,
σ9f・(y))=σ
Υ*(f(x, y))。
この こ と を,回
帰 定 理 (定理2.2.1)を
用 い て,証
明 す るた め に,わ
れ わ れ は,構
造 : 幹=(NI,carキ
, σΥ*〉 をとり,か
つ,す
べてのx∈ N■ に対 して,構
造 : い限*=(N・
, x,
σr*〉 をとる。回帰定理 によ り,幹
とヽ瀞 の間に,唯
―の準同型 (写像)hxが
存在す る。その関数 :hxは
,準
同型であるか ら,つ
ぎの(1),(2)を
満たす :(1)hx(cr*)=x
(2)hx(σ
「・
(y))=σ
Υ士(hx(y)) (た
だし,す
べてのyCN■
に対 して)。 二項関数fを,規
則 :f(x,y)=hx(y)
で定義 す ることによ り,こ の関数 fが上 の (1,1)と (1.2)イこ従 うことは容 易 に確 かめ うるCD。 従 っ て,関
数fの存在 は確 立 され た。 つ ぎに,このような関数 fが 唯一つ しか存在 しないこと(唯一性 。一意性)を
示すために,先
の 条件(1,1)お よび(1.2)を満たす,(別の)関
数gが 存在する,と仮定する。このとき,す べてのxCN■
に対 して,gxを
,規
則:gX(y)=目
(X,y) (た
だし,す
べての y∈N■ に対 して)によって定義する
(xを
固定 して,gxは
一頂関数とみなす)。 ところで,こ の関数gxは
上の条件(1)と (2)を
満たす 。0。 つまり,gxは
幹 から州卜への準同型である。ところが,回 帰定理 (定 理2.2.1)に
より,方
程式 (1)と (2)1こよって定義 される関数,す
なわち 幹 か ら郷徽への 準同型は唯一つに定まる。言い換 えると,す
べての x∈N*に
対 して,hx=gxで
ある。ゆえに, (二項関数 として見たhと gに対 して)h=gで
ある。Q.E, D.
鳥取大学教育地域科学部紀要 地域研究 第
4巻
第 1号 (2002) こうして,回
帰定理 (定理2.2.1)を
用いて,わ
れわれは,す
べてのx,y∈
N*に
対 して, (1.1)と (1.2)と によって定義 され る唯―の演算 (つまり,「後者」関数 σ下・ を基礎 に しての加法演 算)が
存在す ることを示 した。回帰定理が,任
意のペアノ・モデルで加法の定義 とその存在 を正当 化す る,と い うのは,この意味 においてである。同様の方法により,わ
れわれは乗法 と巾法 を定義 し,回
帰定理 によ り,それ を正当化で きる。以下の二つの命題 (命題3.1.2,命題3.1,3)1こ よ り,乗
法 と巾法が定義 され,存
在が主張 され る: 命題3. 1.2:乗
法の存在 すべてのペア ノ・モデル において,唯
―の乗法演算 が存在す る。すなわち,幹 =(N*,c打
*, σ峰 〉をペア ノ構造で あるとす ると,以下の条件 (2.1)と (2.2)を 満たす,唯―の演算gが
存在す る: (2.1)g(x,carキ)=crf*
(2.2)g(x,
σ打・(y))=g(x,y)+下
* x (た
だ し,す
べてのx,yCN*に
対 して) ここで,“十枠"は
,す
でに定義 され,そ
の唯一存在が確かめ られた二項演算 としての,加
法であ る。 命題3.1.3:巾
法の存在 すべてのペアノ・ モデル において,唯
―の中法演算 が存在す る。す なわち,幹
=〈
NⅢ ,c「*, σ下*〉 をペアノ構造で あるとす ると,以 下の条件 (3,1)と (3.2)を 満たす ,唯 ―の演算hが
存在す る:(3.1)h(x,∬
十)=σ
下*(Fr*)(3.2)h(x,σ
下・(y))=h(x,y)・
打*x (た
だ し,Vx,yCN・
) ここで,“.韓"は
,すでに定義 され,その唯一存在 が確 かめ られた二項演算 としての,乗法 で ある。 乗法 を定義す る方程式:(2.1),(2.2)の
通常の書 き方 は, (2.1)′:x'0=0
(2.2)′:x。
(y+1)=x・ y+x
で あ り,中法 を定義す る方程式:(3.1),(3.2)の
通常の書 き方 は, (3.1)′I xO=1
(3.2)′:xytI=xy'X
である。ペアノ 。モデルでは,す
べての回帰的演算 (帰納的関数)が
定義 され,回
帰定理 により正 当化 される。そのような一般的な定理を示す ことにより,上の二命題(命題 3.1。 2と命題3.1.
3)は
その定理の系 となる (そのことで,こ れ らの命題の個別的な証明は省略できる)。3.2
ペアノ・モデルにおける回帰演算 定理3. 2. 1:回
帰演算は,任
意のペアノ・モデルにおいて,数
学的帰納法によって導入 さ れる。 【証明】 簡単のため,わ
れわれが導入する回帰演算を二項演算にかぎる。まず ,そ のような特殊 な形での定 理 を述べ,つ
ぎに証明を与 える。構造: N稗=〈
N・, c*,
σ士〉 を任意のペアノ・モデル とし,fを
N・ 上の一項関数,gを
N半 上の三項関数とす る。この とき,以
下の方程式(1.1)と(1.2),す
なわち,原始回帰 (p mitive recursion)の 方程式,を満たすような,田畑博敏:第二階論理 によるペアノ算術
