Ⅸ二

=x

l161  gx(y) わかる^:

(1)

(2)

=σ^打キ

(g(x,y))

=σ

^Tr■

(gx(y))

&り

 

基底 と帰納 の ステ ラプが成 り立つ こ とを順次示 す 。

1.基

底 ic伸 ∈

G

なぜ な ら

,kx(cTf・ )=Ψ ^l(mx(cイ

^*))

=Ψ

^l(cxN4)

[gが 上の条件 (1,2)を 満たす ことによる^] [再び^g文の gに よる定義 による]

[kxの

定義 による]

[mxが

準同型であるか ら

(1)よ

り]

主Ψl((c打・

,f(x)〉

)  [cx下^{*の定義による]}

=Cttrキ [射影関数Ψlの定義 による]

む る ん ,c打^{・ ∈N・ で あ る か ら},cOf*∈ ^Nキ &kx(c「 *)=c打 半

。^.・.c打・ ∈G。

2.帰

納のステ ップiVyCN*(y∈

G⇒

σ下*(y)CG)

任意のyCN*をとり

,y∈ ^Gと

仮定す る。

Gの

定義 より,kx(y)=y… ^…①

さて

,kx(σ

^下・

(y))=Ψ ^l(mx(σ

^下

^{*(y))) [kxの}

^{定義による]}

田畑博敏 :第二階論理によるペアノ算術

=Ψ

_{l(gx打 と.̀里誉.tェ,ユ必}̲   [ xが 準同型 だか ら(2)の条件 による]

ところが

,最

後の式 の下線部分 Ⅲ…Ⅲ」こついては

,以

下のようになる^:

ヱ

^1ぜr.ど

堕モ 々と 」圭σ が ・

(〈

Ψ

l(mx(y)),Ψ2(mx(y))〉) [mxの定義 により

mx(y)が

順序 対 で あ る こと と射影 Ψ^l,Ψ2の定 義 に よ る]

=〈

σ

「

*(Ψ l(mx(y))), g(x,Ψ l(mx(y)),Ψ 2(mx(y)))〉

[σ が ■の 定義 に よる]

=〈

σ打

*(kx(y)),g(x,kx(y),hx(y))〉

[kxの定義より

kx(y)=Ψ l(mx(y)),

hxの 定義より

hx(y)=Ψ 2(mx(y))に

よる]

よって,ま とめ る と,

kx(σ^Tf・

(y))=Ψ

l(σ x碑

(mx(y)))

=σ

「

*(kx(y))

[.̲…

p部 _分が

̲̲の

^{ような順序対で}

あることと

,射

影Ψlの定義による]

[①よりkx(y)=yによる]

=σ

^下・ (y)

こうして ,σ

Tr*(y)∈ N*&kx(σ

^打

*(y))=σ

下￨(y)で_{あるか ら}

_,Gの

_{定義 によ り}

,

σイ・ (y)CG  となる。以上 より,

VyCNキ (y∈

G⇒

σ

Tf*(y)∈ _G)

が示 された。すなわち

,帰

納のステ ップが成 り立つ ことが示 された。

Q9 

構造上の「合 同関係」 とは

,構

造 Я

=〈 A,(An〉

.≧1,(ca〉 c∈oPER.CONS〉 の二項関係

R⊆

AXAで,以下の条件 (i)― (lii)を満たす ものの ことである^:

(1)Rは A上

の同値 関係 (すなわち反射的・対称 的・推移的である関係

)で

ある。

(ii)任意の

n項

関数定項

f,お

よび

Aの

要素^xl,…,X■vl, ,ynに対 して,

〈xl,yl〉 ∈

R, 

^・・・,(Xn,y.〉 ∈R=⇒ 〈fЯ (xl,"・,xn), fa(yl,"・,yl)〉 ∈

R

すなわち

,関

^係

Rを

満たす個体の一方 (のグループ

)に

適用 された関数の値は

,同

じ関係 を満たす他方 (のグループ

)に

適用 された関数値 に対 して

,再

び関係

Rを

満たす。

(iti)任意の

n項

関係定項

T,お

よび個体xl,… ,Xn,yl,…,yn C Aに対 して,

〈xl,yl∈

R, 

^・中,(xn,yn〉 ∈_R=⇒

 (響

 (xl,・…_,Xn)ぐ〉TЯ (yl,中^,,yn))

すなわち

,関

係

Rを

_{満たす個体の一方} (のグループ

)は ,同

じ関係にある他方 (のグルー プ

)と ,任

意の関係 を満たすか否かに関 して常に一致する。

田畑 [20011139‐140頁 参照。

t9 

復習を兼ねて

,田

^畑 [20011から

,関

連す る「命題」を (証明ぬきで

)拾

い出してみる。

(1)命 題2.7.2(田畑 [2001〕 140頁

):hを

構造

aか

ら他の構造

3の

中への強い準同型である とする。このとき,〜

h=￨〈 x,y〉

∈

AXAlh(x)=h(y)￨と

して定義 される関係〜

hは

,

A上

の合同関係である。

この命題は

,強

い準同型 (「強い」という限定は,も との構造での要素間の関係成立が

,写

され た先での関係成立の,十 分条件のみならず必要条件でもあることを示すが

,関

係ではなく関数の みをわれわれはいま問題にしているので_,この限定の有無は無関係である

)に

よって他の構造の 同一個体に写 されるもとの構造の個体同士が関係〜 hを 満たす,と して〜 hを 定義すると,この 関係〜

hは

合同関係にある,と 主張 している。要するに

,(他

_の構造の

)同

一の要素に写 される,

もとの構造の要素 どうしは,ある程度の類似性がある筈だと予想 されうるが_,実際 に,「合同関係」

を満たすという,相当に類似度の高い関係にあることになる。つ ぎの図示により_,その状況 を(大

鳥取大学教育地域科学部紀要

 

地域研究

 

第

4巻  

第1号 (2002)

まかで は あるが

)視

覚 化 で きよ う^:

A(=Я の個体宇宙

)

￨￨

B(=ら の個体宇宙

)

￨￨

〜

hi合

同関係

(11)命題 2,7.3(田 畑 [20011140‐141頁 ):Я上の任意の合 同関係

=に

^{対 して}

,≡ =〜 hで

あるよ

う な,Я^{か ら},徹 か ら 作 ら れ る)別の 構 造 :Я==〈 _{A二 ,(ca=〉c∈o配R,CONS〉 の 上 へ の (onto)} 強い準同型

hが

存在す る。

この命題 は

,上

の命題 (命題 2,7.2)と は逆 に,元の構造上 に合 同関係 が存在すれば,それ を言 わ ば材料 に して

,合

同関係 を満 たす

,同

じ同値類の要素 は

,す

べて自らが属す る当の同値類 に写 さ れる,とい う仕方で (強い

)準

同型 を作 ることがで きる,と主張 してい る。以下の図で この こと を大 まかに示す ^:

tr

A

０ ０

● ０

●

h

○      

○  

○

●

★  

○

☆  

□

田畑博敏^:第二階論理によるペアノ算術

(iti)命題^2,7.4(田畑

[2001]141頁 ):hが

冤か ら

3の

上への (onto)強い準同型であるとす る。

.その とき,

Яtth茎 0  (た だ し Я 〜h=(A〜 _{h,〈 C〜}h〉 cC oPER CONS〉

A〜

h=￨[x]〜 hix∈

AI=〜

hの

同値類の集合)

この命題の内容 は以下の ようなことである。Яか らCの_{上への強い準 同型}

hが

_{存在す るとすれば,上} の命題2.7.2に よ り,冤の個体宇宙

A上

に〜 hと い う合同関係 が定義で きるが ,命題^2.7.3によ り,こ の合同関係〜hに基づいて ,Я か らЯ〜^hの上への強い準同型

h*が

作れ る。この とき

,〜

^{hと い う} 合同関係 その ものが,「

Bの

同一要素 に写 され る

Aの

要素 を(言わば

)同

一視す る」とい う関係 とし て定義 されていたので

,Bの

同一要素bに_{写 される}

Aの

要素

a,aア

^…・が全部 ,こ んどは^A〜hの同 一要素 [a]〜^hに (aか らЯ^tthへの準同型

h*に

よ り

)写

され るか ら

,Bの

要素bと

,A〜

^hの要素 [a] ^hを同型対応 させ ることがで きる筈である。これが,この命題の意図である。以上の ことは,

つ ぎの図によ り

,大

まかに理解で きる^:

A〜

^h

ll

tL

Ｂ

＝

田 田 田

◇  

◆  

△

(

)命 題

2,7.5(田

畑

[20011142頁

):hlと h2が ,そ れぞれ

^,Я

から

01の

上への ,お よび

,

Яか ら

82へ

の

,強

い準同型で あり

,か

つ〜

hl=〜 h2の

とき

,ol≡ ^o2で

^ある。

この命題 は

,命

題2.7.4よ り

,31茎

^Я〜

^hl=Я

^〜

h2茎 82が

導かれ ることと

,≡

が同値関係 であることか ら証明 され る。つ ぎの図により,この命題の意図の概略 を示す ことがで きる:

Ｂ Ｈ

０ ★  

○ ☆  

□

鳥取大学教育地域科学部紀要

 

地域研究

 

第

4巻  

第 1号

(2002)       77

A〜

h2=A〜

hl

901 定義に基づいて

,Rm,nの

具体例 を考える。

m=3,n=0,す

なわちR3,0をとる。定義は 〈x,

y〉 ∈_R3,0⇔ (1)x,y<0&x〓 ^{yま たは}

(2)x,y≧ 0&ヨ z(x=y+3zVy=x+3z)

であるが

,Nで

は,(1)は 常に偽であるから,(2)が実質的定義条件である。(2)の連言の前半は常 に成 り立つから

,事

実上 ,後 半部が定義条件である。つまり

,xが ^yに

^{対 してR3,0の関係にある}

のは

,x―

^yまたは

^{y一 xが 3の}

倍数である場合である。通常「 3を 法として合同」と表現 され る関係

,す

なわち

3で

割った剰余が同 じか否か

(0か

^1か

2か

否か

)で

当の関係の有無を決める ものである。「同一剰余を持つ」関係で分類 してできる剰余類は

[0卜

=10,3,6,9,12,15,… ^￨ [1]… 11,4,7,10,13,16,… ^￨

[2卜

=12,5,8,11,14,17,… ￨

となる。 ここで

,見

^{られ る循環が}

,帰

納法モデルの中の循環モデル と関連す る。

また

,別

の具体例 として

,Rm,n=R5,2を

とる。       ^・

定義条件 は

,(x,y〉

^∈R5,2⇔

(1)X,yく

2&x=yま たは

(2)x,y≧ 2&ヨ

z(x=y+5z Vy=x+5z)であるか ら

,2よ

り小 さい自然数 までの同値類はその 自然数か ら成 る単元集合で,

2以

_{上の 自然数の場合, 5を}法 とす る剰余類 となる。

[0]〜=101

[1卜 =111

[2]〜

=12, 7, 12, 17, 22, 27,…

^￨

[3]〜

=13, 8, 13, 18, 23, 28,…

￨

[4卜=14, 9, 14, 19, 24, 29,…

￨

[5卜=15, 10, 15, 20, 25, 30,…

^￨

tL Bl B2

(0★

￨

tO☆

l

０ ★   Ｏ ☆  

□

1●

★

￨

10☆

l

(口￨

◇  

◆  

△

◎  

▲  

▽

田畑博敏 :第 二階論理によるペアノ算術

[6卜 =16, 11, 16, 21, 26, 31,…

_￨

ここで見 られる_,「一直線」と「循環」の結合

,す

なわち「スプーン型」は

,帰

納法モデルの スプーン型 と関連する。

9り

 

実際

,ま

ず,〈n,n〉 か ら 〈n+1,n■〉,〈 n+2,n+2〉 ,…

,つ

まり

,表

^の (左上か ら右下の方向に 走 る

)対

角線上の順序対がすべて

Rを

満たす (図①)。 つ ぎに,〈n,n+m〉 か ら出発 して,

(n+1,n+m+1〉 _,〈n+2,nttm+2〉 ,…

 

の列 (対角線 と平行に右下に走 る図②の列

)の

^)慣序対が

Rを

満たす。この列 と対角線に対 して対称な列 ^:〈n+m,n〉 ,(nttm+1,日+1〉 ,〈n+m+2,n+2〉 ,―

 

の順 序対列 も

Rを

前 たす (図③)。 これは_,この列の出発点 〈n+m,n〉 が_,(n,n+m〉 ∈

Rと Rの

_対称性 により得 られるからである。さらに,〈n,n+m〉∈

Rと 〈nttm,n+2m〉 ∈

Rよ

_{り県の推移性により,}

〈n,n+2m〉 を出発点として対角線 と平行に走る列

(図④

)が

得 られ,この列 と対角線に対 して対称 な くn+2m,n〉 で始 まる列 が (図⑤

)得

られ,

〈n,n+2m〉 ∈Rと  〈n+2同1,n+3m〉 ∈

RIR?推       

^Ψ｀_、、

  

＼ 移性か ら くn,n+3m〉 で始 まる列 (図⑥

)が

得 られ

,… ,等

々 となる。

99 

最初の仮定か らは

,Rが

合同関係である_,ということしか知 られないが

,nと mを

定義するこ とにより

,言

^わば

,Rの

「正体」を調べるための「探 り」を入れた。n=oな らば

,Rは

^「

^mを

法とする合同」の関係である。もし

n半 0な

らば

,0≦

^k≦ n‑1までの各自然数

kに

ついては,

〈

k,k〉

とい う形の順序対のすべてが

,か

つそれのみが

Rを

_満たす。

Rm,nの

_{定義により}

,(k,

k〉 は

Rm,nを

満たす。そこで

,い

^ま

,x,yの

いずれもが nに 等 しいか

,nよ

り大 きいとして,

y≧

xと した。もし

x=n tt w,y=n+w+vな

らば

y=x+vだ

か ら

,順

序対 〈x,y),す

なわち 〈n+Ln+wttv〉 は,表 において,対 角線の列より上の列に現れる。そのとき,

n tt w+v"

の

v"の

部分は

,あ

る自然数 zに 対 して

,v=zmで

ある。

そうすると

,y=x+zm,∴

^ヨ

z[zcN&(x=y+zmvy=x+zm)]。

_{ゆえに,〈x,}

y〉 ∈Rm,nと なる。

991)Rm,nは

同値関係である。x=xは常に成 り立つので

,x<n&x=x⇔ x<n。

また

,0∈

N&x=x+0=x+0・ _m,∴

ヨ

z[z∈ N&(x=x+z・ m)]。

ところが

,x<nvx≧

ⁿ

よって

,x<nvx≧ R&ヨ z[z∈ N&(x=x+z・

m)],すなわち 〈

x,x〉

^∈Rm,n。 よっ て反射性が成 り立つ。また

Rm,nの

_{対称性は,}

&"と ="と v"の

対称性 に由来 して成 り 立つ。最後に

,推

移性を示す。

(x,y〉

∈

Rm,nか

つ く

y,w〉

_{∈Rm,nと し},x=y+zl m,

W=y ttZ2 mと

_{する (他}の場合 も同様だから省略する)。

x≧ wの

とき

,x― w=(zl―

z2)・

m≧

0,m≧ 0だ から

,(zl―

z2)≧

0,∴

(zl― z2)∈ N。 ∴

x=w+(zl―

z2)°

mo W≧

xの

_{ときも同様に}

w=x+(z2 Zl)° m,z2 ZlC N。

∴どちらにせよ

,ヨ z[z∈ N&(x

=w+zmvw=x+zm)],∴

〈

x,w〉

^∈Rm,n。

(li)つぎに_,まず関数に関 して

,Rm,nの

関係にあるもの同士が保存 されることを示す。

(x,y〉

∈Rm,nと する。(Sx,Sy〉 ∈

Rm,nで

ある。なぜなら_,(イ

)x<nで

x=yのとき

,Sx

=Syo Sx<nの

とき

,Rm,nの

定義により,(Sx,Sx〉

=(Sx,sy〉

^∈

Rm,nで

あ

る。 Sx≧ nの ときも ,Sx=sx+0=sx+om,∴ ヨ

z[z∈

N&(SX=Sy+(zm)v

Sy=Sx+(zm)].・ .〈Sx,Sy〉 ∈Rm,n。 そこで,(口

)x,y≧

nと し

,y≧ x,y

=x+zmと

_する。

Sy=s(x+zm)=s(zm+x)=zm+sx=Sx+zm(こ

_こで

＼

＼

鳥取大学教育地域科学部紀要

 

地域研究

 

第

4巻  

第1号

(2002)       79 +"の

交換律 を仮定する

),∴

ヨ

z[z∈ N&(Sx=Sy+zmvSy=Sx+zm)]。

_いず

れにせよ

,(Sx,sy〉

^∈Rm,n。

つぎに加法に関 して。(xl,yl〉 ∈

Rm,nか

つ くx2,y2〉 ∈Rm,ぃ とする。示すべきは,〈

xl+x2,

yl+y2〉 ∈

Rm,nで

ある。いま,xl=yl+zl・ m,y2=X2+Z2・

mと

する (他の場合 も 同様か簡単)。

(xl+x2)― (yl+y2)=(Xl― yl)― (y2 X2)=(Zl―

z2)° m。 (イ

)zl≧

Z2のとき

,m≧ oだ

か ら,(zl二 z2)・

m≧ 0,∴

ヨ

z[(xl+x2)=(yl+y2)+zm]。

(口

)Z2>Zlの

とき

,m≧

0だ から_,(zl―z2)°

m≦ 0,∴

ヨ

z[(yl+y2)=(Xl+x2)十

zm]。

いずれにせよ

,ヨ z[z∈

N&(xl+x2=yl+y2+z mVyl+y2=Xl+X2+zm)]。

ゆ えに ,(x二 十

x2,yl+y2〉

∈

Rm,nで

あ る。

乗 法 の場合 も同様 。

      Q. E. D.

卸

 

実 際

,[y]〜

^∈

N〜

とす る。す ると

,y∈

^{N。 とこ ろが}

,①

^{よ り}

,Vy∈ N(S(y)/[0]〜

=101)だ

ったか ら

,[S(y)卜

半 [0]〜。 しか し

,②

^{よ り}

,[S(y)卜 =S〜

([y]〜).・.S〜 (

[y卜

)+[0]〜

。

90  まず ,基 底

^ica c Gか

ら。 hxも

hx・

も ,条 件

(1)を

満たすから

,hx(ca)=x,hx*(ca)

=x,∴

hx(ca)=hx*(ca),i ca∈ A&hx(ca)=hx*(ca),i cacG。 _{つぎに,帰 納の}

ステップ :Vy∈

A(y∈

G⇒ σa(y)∈ G)を 示す。任意の

^y∈

Aを とり

,yCGと

仮定する。

これにより ,hx(y)=hxキ (y)で ある……①。

hx(σ

^Я

(y))=σ a(hx(y))

=σa(hx半

(y))

[hxが

(2)を満たすから]

[上の①より]

=hx*(σ a(y))       [hx・

_{が (2)を満たすから}

]

90 

まず

,基

^{底 ica c Hを}示す。

x=caの

場合のhx,すなわちh caと して

,同

一性関数^:h cЯ

(z)=z(z∈

^A)′ をとる。すると,h ca(ca)=ca=x,∴ ^(1)を満たしている。また

,hx

(σЯ

(y))=h ca(σ

^Я

(y))=σ

^Я

(y)=σ

・

(h ca(y))=σ A(hx(y))。

よって,(2)を 満たす。

こうして

,h ca:A→ A&h♂

は _(1),(2)を満たす。むろんca∈A。 ∴cЯ ∈H。 つぎに

,帰

納の ステップ

iVy∈

A(y∈

H⇒

σ

a(y)∈ _H)を

_{示す。任意の y∈}

_Aを

_とり

_,y∈

_{Hと 仮定する。}

すると

,Hの

定義より,(1),(2)を満たすような関数^hメ

A→ Aが

_{存在する。いま関数}h σa(y)を ,

規則^:

(※

)∀

^x∈

A:h 

σ

A(y)(x)=σ

Я

(hy(x))

によって定義する。すると_,この関数h σa←)イよ_(1)を満たす。なぜなら,

h σ^a←

)(Ca)=σ

^Я(hy(ca))       [上 の規則 (※

)に

よる]

=σ

^Я

(y)         [仮

定により

hyは

(1)を満たすか ら]

つまり,z=σ^Я

(y)と

おくと,hz(ca)=zと ^{なっているので}

,(1)を

満たしている。また,

h σ^a●

)は

_,(2)も満たす。なぜなら,

h σ^A(の (σЯ

(X))=σ a(hy(σ

^Я

(x)))  [上

の規則 (※

)に

よる]

=σ

^Я(σa(hy(x)))  [hyは _{,(2)を 満たす}

_:hy(σ

■_(x))

=σ

A(h y lX))]

=σ A(hび

a←

)(x))  [再

ぴ規則 (※

)に

^よる]

こうして

,z=σ

^■

(y)と

お くと

,hz(σ

・ (x))=σ

4(hz(x))と

_{なっているので}

,h 

σ^a(♪ 1よ,

(2)を満た している。こうして,σ

A(hy(x))1よ Aか

_ら

Aへ

の関数だか ら, h σ

a.):A→

A&h σ^a

lylイよ(1),(2)を満たす,とい うことが示 された。従 って

,ヨ z(hパ A→

A&z=σ^ス_(y)&h

田畑博敏^:第二階論理によるペアノ算術

zは (1),(2)を 満たす

)&σ a(y)∈

A。   ∴ σ

a(y)∈

_{H。 こうして}

_,帰

納のステ ップが示 さ れた。

9, 

実際

,以

下の ように して

,fは

条件 (1.1),(1,2)を 満 たす^:

(1.1)f(x,ca)=hx(cЯ

)      [定 義 による]

=X      [hxが _{(1)を満たす ことによる]}

(1.2)f(x,σ

A(y))=hx(σス(y))    [定 義 による]

=σ

4(hx(y))    [hxが _{(2)を満たす ことによる}

]

=σ

A(f(x,y))   [再 _{び定義 による}

]

90 fキ

^xが

,補

題

1で

_{述べ られた条件}

(1),(2)を

満 たす ことは

,つ

ぎのよ うに して示 され る^: 条件(1)if*x(ca)=f*(x,ca)       [f*xの f*に_{よる定義 による}]

=X      [f*が (1,1)を 満 たす ことによる]

I条件

(2):f*x(σ

^■

(y))=f・ (x,σ

A(y))  [f*xの _{f■による定義 による}

]

=σ a(f・

(x,y))  [f*が (1,2)を満たす ことによる]

=σ^Я

(f*x(y)) [f*xの

^f*に

よる定義による

]

99《 補題

1の

証明》唯―性から示す。kxと

kx・

が

(1),(2)を

満たす二つの一項演算であるとする。

ここで ,G=ly∈ Alkx(y)=kx*(y)￨と する。Aの 部分集合であるGに 公理 3Pを 適 用する

(aが

帰納法モデルだから)た めに

,ま

ず

.1.基

底 ica∈ _{Gを 示す。kxも}

kx・

も仮定 により

(1)を

満たすから ,kx(cA)=cA,kx・ (ca)=y,∴ kx(ca)=kx・

(ca),∴ cA c A

&kx(ca)=k xt(ca),∴

cac G。

つぎに

,2.帰

^{納のステップ}

:Vy(yCG⇒

σ

^a y∈

G)を 示す。任意の

^y∈

Aを とり ,yCGと 仮定する。Gの 定義より ,kx(y)=kx・

(y)…

…・ ①。こ

の とき,

kx(σ

a(y))=kx(y)+Ax

=kx辛 (y)+Я

x

=kx中

(σA(y))

o・・σЯ(y)∈A&kx(σ^冤

(y))=kx*(σ ^a(y)),∴

σ

A(y)∈

_{G。 こうして}

_,帰

_{納のステ ップ}

も成 り立つ ことが示 されたか ら,公理

3Pに

より,G=Aが成 り立つ。。∴VyCA[kx(y)=

kx・ (y)1,ゆえに

kx=k xI。

す なわち唯一性が示 された。

つ ぎに存在性 を示す。まず,

H=lxCAIヨ

z(kガ A→

A&kzは (1),(2)を満 たす&z=x)￨

とお く。

Hは ,xを

固定 したとき

,kxが

(1),(2)を満たす

,A上

の一項関数 となるような,そのよ うなxの_{集合で ある。まず},1.基底

i cacHを

_示す。k caと して

,定

数値 関数

:k ca(z)=

ca(z∈ A)を

とる。

k ca(ca)=♂

^.・.条件(1)が満たされた。

k♂

(σ

a(y))=ca,他

_方

_,十

aは

A上

の加法だか ら

,k ca(y)+aca=k ca(y)=cacゆ

えにk ca(σ

a(y))=k ca(y)十

acA,

∴条件(2)が満 た された。こうして

,k cAは

(1),(2)を満 たす

A上

の一項関数だか ら,ca∈H。 よっ て

,基

底 が成 り立つ ことが示 された。つ ぎに,2.帰納のステ ップiVy(y∈

H⇒

σЯ(y)∈

H)を

示す。任意のycAを とり

,y∈

^Hと仮定す る。

Hの

定義 よ り,(1),(2)を満たす関数

ky(k

ガ

A→ A)が

存在す る。いま

,k 

σЯ●

)を ,つ

ぎの規則

(%)に

よ り定義す る^: k σ^aけ)(x)=ky(x)+Я x ……

(%)

この関数 k σЯ●

)は

(1)を満たす。なぜな ら

,Kσ

^■

(y)(Ca)=ky(Ca)十

aca=ky(ca)=ca

[仮定 により

kyは

(1)を満 たすか ら]。 k σ^a(〕 イま(2)も満 たす。実際,

[kxは

(2)を満たすか ら]

[上の①より]

[kx■は(2)を満たすから]

鳥取大学教育地域科学部紀要

 

^地域研究

 

第

4巻  

第1号 (21D2)

k σЯ●)(σЯ

(x))=ky(σ

^Я

(x))+a 

σЯ(x) [上の定義

(%)に

よる]

=(ky(x)+Ay)+Я  σ4(x)  [kyが _{(2)を満 たすか ら]}

=ky(x)+・

(y+Я

 σЯ(x))   [Aで の加法の結合律]

=ky(x)+a  σa(y+4ズ)    [加 法の定義条件 による]

=ky(x)+a  σЯ(x+ay)    [Aで の加法の交換律]

=ky(x)+4(x+a  σЯ

(y))   [加

法の定義条件]

=(ky(x)+Я x)+a σa(y)  [加 _{法の結合律}

]

=kσ

・

(y)(X)十

^a σa(y)     [下 _{線部 Ⅲ}

…Ⅲ^.に (%)を 適用]

以上 より,Я は帰納法モデルだか ら

,公

理

3Pを

適用 して

,H=A。

^ゆえに

,Aの

すべての要 素

xに

_{対 して,(1),(2)を満 たす一項関数}

kxが

存在す る。

001《補題

2の

_{証明》条件} (2.1),(2.2)を 満たすような

,A上

の二項演算

hが

_{存在することを示す。}

いま

,hを ,す

^べての

x,yCAに

対 して

,h(x,y)=kx(y)…

^…。

(#)と

定義する。

ここで,kxは

,上

の補題

1で ,そ

の唯一存在がすでに証明されている関数である

(kxを

^一 項関数と考 えていたときは

,xを

固定 していたが,こ れから

,xは A上

で変化するものと見な す)。 この

hが

条件 (2,1),(2,2)を 満たすことは

,つ

ぎのようにして示せ る。

条件

(2.1):h(x,cA)=kx(ca)=cA     [kxが

補題

1で

述べた条件(1)を満 たす ことによる]

条件

(2.2):h(x,σ A(y))=kx(σ

a(y))   [上_の定義

_(#)に

_よる

]

=kx(y)+Ax     [kxが

条件(2)を満たすから]

=h(x,y)+ax   [上

の定義

(#)に

^よる]

こうして

,(2.1),(2.2)を

満たす二項演算

hが

存在することが示 された。

つ ぎに_,この

hの

唯―性 を示す。

h+を

,条 件 (2.1),(2.2)を 満たす他の関数 とせよ。示す べきことは

,h*=hで

^{ある。いま}

,任

^意のxCAを固定 して

,h・

^xを,

Vy∈ A:h■

x(y)=h・ (x,y)…^… (〒)

として定義 され る一項関数 とせ よ。この

h*xは ,補

題

1で

_{述べた条件}(1),(2)を満 たす。実際

(1):h*x(ca)=h・

(x,ca)     [上 の定義 (〒

)に

^よる]

=ca      [hホ が条件 (2.1)を 満 たすか ら]

(2):hキx(σ ■

(y))=h・ (x,σ

a(y)) [定 _{義 (〒}

_)に

_よる

]

=h・

(x,y)+4x  [h・ が条件 (2.2)を 満たすか ら]

=h*x(y)十 Ax    [定 義 (〒

)に

よる]

ところが,補題 は り,(1),(2)を満たす このような一項関数 は唯一つに決 まる。それが

kx

であった。よって,h*x=kxで^{ある。ゆえに},(〒

)よ

り,h*(x,y)=kx(y)で ^ある。

しか し

,hは

,h(x,y)=kx(y)と して定義 されていた。従 って

,h・ =hで

ある。

Q. E. D.

eO 

まず,1.基底

:0∈ Gが

成 り立つ ことを示す。

h(x)・

^Яh(0)=h(x)。・ ca      [hが 準同型 ,∴

h(0)=σ

^Я]

=ca       [・ ・ は Яでの乗法 だか ら]

h(x・

0)=h(0)      [x・ 0=0だか ら]

=ca      [h(0)=σ ^Aだか ら]

∴

 h(x)・

ah(0)=h(x・ ₀₎

82 田畑博敏 :第二階論理によるペアノ算術

つ ぎに,2.帰納のステ ップ:Vy(yCG⇒

_{Sy∈ G)が}

成 り立つ ことを示す。任意のy∈

Nを

とり,yCGと仮定す る。

Gの

定義 によ り

,h(x)・

・

h(y)=h(x・

y)… …。①。 さて,

h(x)。

Ah(Sy)=h(x)・ as(h(y))      [hが

準同型だか ら]

=h(x)・

ah(y)+Ah(x)      [・

・ は

A上

の乗法]

=h(x・ y)+Я

h(x)       [上 _{の① よ り]}

=h(x・

y+x)        [定 _{理5。1,2よ り}

_{,hは Nめ}

_加法

_+を

冤の加法+・に写像 しているか ら]

=h(x・

Sy)      [・ _{は ヽこの乗法で (2.2)を満たすか ら]}

こうして

,h(x)。

Ah(Sy)=h(x,sy),iSyCG。 _{以上 よ り},Vy(yCG⇒ SyC

G)が

示せた。ゆえに

,公

理

3Pに

よ り,G=No       Q.E.D.

gの_{定義の仕方か ら}

,任

意のx,y,zcNを _とり, f( ,y)=zと す ると,

(h(x),h(y), h(z)〉

∈g

である。通常の関数の書 き方で,つま り (a,b,c〉

Cg"の

_{代わ りに}

g(a,b)=cと

_{い う書 き方}

で書くと

^,

h(f(x,y))=g(h(x),h(y))

で あるか ら

,N｀

上 の 関数gは

,イ

にお ける関数 fの

,hに

よ る準 同型 像 となってい る。

まず,1.基^{底 :[0]〜∈}

G 

を示す。 _,〜 [x]〜は仮定により(1)を満たすから, j〜 [x]〜 [0]〜

=f〜 [x]〜。 _,Nキ [x]〜も(1)を満たすから,I留*[x]〜

[0]〜 =f〜 [x]〜。∴^j〜*lx]〜 [0卜

=

j斜ホ

Ex]〜 [0]〜 。 もちろん_,[o]〜CN〜_{だか ら}

_,[0卜

∈G。

つ ぎに,2.帰納のステップ

:V[y]Ⅳ C N〜

_([y]〜CG⇒

SN[y]NC G)を

_{示す。任意の}

[y卜 ∈N〜 をとり,[y]〜

CGと

_{仮定する。}

_Gの

_{定義により, 1〜 [x]〜 [y]〜=j〜 キ瞭}

]〜 [y]〜

021

031

・ ・… ①。ところが

,

,〜 [x]〜S'[y]〜

=g留

[x]〜 [y]〜 (,〜 [x]〜

=g付 [x卜 [y]〜 (,〜

キ

=j〜^*[x]〜S〜 _[y]〜

むろん ,S留 [y]〜 CN〜_{であるか ら}

_,Gの

_{定義 により}

,

V[y]NC N〜

 _([y]N∈

_G⇒

S〜 [y]〜 ∈

G)

が示 された。すなわち

,帰

納のステ ップが示 された。

0つ まず,1.基底 :[0卜

CHが

成 り立つ ことを示す。いま

j〜

的

]〜 =f〜

と,す なわち

V[x]〜 CN〜 :jN的 ]N[x]N=f〜 [x卜 =[fx]〜  _{・ … …} (★)

と,定義せ よ (仮定 により

,fが

ユニバーサルだか ら

,定

理5,3.2から

,Nた

上 にfの_準同型像

f〜が存在す るゆえ,こ の定義が可能である)。 この とき,,〜m]〜 が条件(1),(修)を満 たす ことは,

以下のように して示 され る。

条件(1):itt Ю]〜 [0]〜=f〜 [o]N 条件(2):j〜 的]〜 S〜 [y]N=f〜 S〜 [y]N

[y]〜

)   [iN[x]〜

11(2)を満たすか ら]

隊]〜 [y卜 ) [帰納法の仮定 :①]

[l〜・ 阿Ⅳは 鬱)を満 たすか ら] S〜 [y]〜

CG。

_{以上 よ り,}

[上

の定義

(★

)に よる

]

[定

義

(☆

)に よる

]

=f〜 [Sy]〜

      [s付

^は

sの

_{準同型像だから}]

=[f Sy]〜        [定

義 (★

)に

^よる]

=[i SyO卜   [jは f,gか

ら原始回帰により得 られるから条件 (イ)よ り]

ドキュメント内 第二階論理によるペアノ算術 (ページ 37-48)