第二階論理の特性について

三階論理 の特性 について

田

畑

博

敏

*

は

じ

め

に

第一階論理の拡張 としての第二階論理は

,個

体変項の量化のみな らず

,関

係変項 の量化 も許 され る。それゆえに

,第

二階論理は強力な表現力を備 えている。だが

,そ

の表現力 と引き換えに

,第

一 階論理の持つメタ定理のいくつかが失われる。本論文の 目的は

,古

典的 (標準的

)な

仕方で提示さ れる第二階論理の持つ このような基本的な特性を

,可

能なかざ り丁寧 に調べる ことである。(尚, 本論文は

,以

後実行する予定の

,第

一階論理のさまざまな拡張論理研究の序 となる。)

まず

,第

二階論理の持つ強い表現力の実例を瞥見することから始める°七

(1)算

術的帰納法

(arithmetical induction:い

わゆる数学的帰納法

)は

以下のように表現され

る

:.

∀

X[XO∧

∀

x(Xx→ Xsx)→

∀

xXx].

この式は 「ゼ ロにつ いて成 り立 ち

,か

つそれ につ いて成 り立つ任 意 の数 の後者 につ いて も成 り立 つ よ うな

,任

意 の性質は

,す

べ て の数 につ いて成 り立つ性質で ある」 と言 つて いる。

(2)個

体 の 同一性が, ライ プニ ッツの考 え方 に従 って第二 階論理 で定義 され る。

Vx∀ y[x=y←

→ ∀

x(xx←

→

_Xy)]

この式 は こう言 っている :「個体 が 同一で あるのは

,あ

らゆ る性質 を共有す る とき

,か

つそ の とき にか ぎる」。

(3)「

大 抵 の

Rは

Sで

あ る」 または 「性質

Rを

持 つ大 部分 の事物 は性質

Sを

も持 って い る」 とい う ことを第一階論理 で表現す る ことは きわ めてむず か しい。 しか し

,第

二 階論理で は, この文 を, 「集合

R∩ Sか

ら集合

R― Sの

中へ の一対一対応 関係が存在 しな い」 と解釈す る ことによって

,つ

ぎの式で表現 で きる②:

… ョ

x2[∀ x(ョ yX2xy←

→

RxASx)A∀

x(ヨ

yX2 yx→ Rx∧

司

Sx)

A∀

xVy∀ z(X2xyAX2xz→

y=z)∧

∀

x∀ y∀

z(X2xyAX2zy→

x=z)]

この式 は,「 集合

R∩

Sは

集 合

R― Sよ

り大 きい (濃度 が大 で あ る)」 と言 って いるので,「 大抵 の

Rは Sで

ある」 の通常 の意 味 を表現 して いる, と考 え られ る。

(4)有

限性 と無 限性 が第二 階論理で定式化 で きる。量化 可能な関数変項 を認 める として

,式

:

∀

f[∀

x∀

y(fx=fy→

x=y)→

∀yヨ

x(y=fx)]

は,「(個体 の全宇 宙 を

Aと

す る とき

)一

対 ― の関数

f:A→

Aが

す べ て上 へ の

(onto)関

数 とな る」 を意 味す るか ら, これ は個体 の字宙が 「有限で ある」 とい う ことを表現 して いる③。 もち ろん,

同 じことが 関係変項 のみ を用 いて も

,以

下 のよ うに表現で きる:

∀

x2[∀

x(ョ

yX2xy←

→

x=x)A∀

x∀ y∀

z(X2xy∧ x2xz→ y=z)

A∀

x∀ y∀

z(X2xy∧ x2zy→ x=z)→

∀yヨ

xX2xy]

第

田畑博敏 :第 二階論理の特性 について

(5)整

列順序 (we■ Ordering)の 公理。 “≦

"が

順序④のとき

,式

:

∀

X[ヨ

yXy→

ヨ

u(Xu∧

∀

z(Xz→

u≦

z))]

は,「すべての非空の (個体 の

)集

合 には最小元が存在する」 ということを表現 している。

(6)包

括公理 (colllprehelas e axioms)。 この公理は 「定義可能なすべての関係は存在す る」 と主張す るが

,つ

ぎの式で表現 され る: ヨ

Xn∀

xl・…∀

xn(X・

xl・…

xn←

→ φ) (ここで

,Xnは

φの中で 自由変項 としては出現 していない。)

(7)可

算である (being countable)と いう性質 も第二階論理で表現可能である。一つの集合が 可算であるのは

,そ

の集合上で定義 され る線形順序が存在 して

,そ

の集合のすべての要素がその順 序に関する有限個 の先行者 しか持っていないとき

,か

つそのときにかぎる。 ところで

,二

項関係

R

が線形順序である ことは第一階論理で表現 される し°

,集

合の有限性 も上の(41と同様な仕方で第 二階論理で表現 される。よって

,集

合

Sの

可算性はつぎのような第二階論理の式で表現できる: ヨ

R[LinearOr(R)∧

∀

x(Sx→ {z:Rzx)は

有限である)]③ 数学的な例のみな らず, 日常的な表現の例 も挙げることができる。

(8)「

どんな種類の人 もいる」はつぎのように表現できる: ∀

Xヨ

yXy

(9)「

右翼にせよ左翼 にせよ

,あ

らゆる独裁体制に共通な少な くとも一つの特徴がある」: ヨ

X∀

z[A3∧ (RzVLz)→

Xz]

(10)「共通な性格の全然無い異なる男性 を愛す ることのできる何人かの女性がいる」:

ヨ

x[Wx∧

ヨ

yヨ

z(MyAMz∧

y≠

zALxyALxz∧

コ ヨ

X(Xy∧ Xz)}]

さて, このように強い表現力を持つ第二階論理は

,そ

の強さのメ リッ トとして

,第

二階算術 のペ アノの公理系が (どの二つのモデル も同型であるという意味で

)範

疇的である (categorical), と いうことが帰結する。 しか し

,反

面

,第

二階論理はコンパク ト論理ではない (つま り

,コ

ンパク ト 性定理が成 り立たない

)し

, レーヴェンハイム

=ス

コー レム定理 も成 り立たない。 また

,コ

ンパク ト性の不成立によ り

,不

完全である。 さらに

,第

二階論理に対 して標準的または非標準的意味論を 与えるとき

,背

景 となる集合論 に依存する。 これ らの点は

,論

理体系相互間の比較

,集

合論 との比 較をお こな うとき

,考

慮せねばな らない論点 となる⑭。以下

,本

論文では

,そ

れ らの考察 の準備的 研究 を目的 として

,古

典的・標準的な提示法 に依拠する

,第

二階論理の諸特性 を調べ る。

1.第

二 階 文 法 第二階論理に厳密な構文論を与えるために

,第

二階言語の文法 (第二階文法

)を

提示する。まず, 量化可能な変項のタイプと

,予

め用意する定項にタイプを与える関数を定義する。以下に述べるよ

うな条件を満たす集合

VARと

関数

FUNCか

ら成る順序対 Σを記号系 (signtture)と 呼ぶ:

Σ

=(VAR, FUNC)。

(1)VARは

つ ぎ の条 件 (1)― (4)を 満 たす 集 合 で あ る①:

(1)1∈ VAR, (0,1)∈

VAR;

(2)α

∈

VAR

の とき, α

=(0,1,・

♀・

_,1)(n≧

1)ま

_{た は α}

=(1,寸11);

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

3巻

第

1号 (2001) 135

￨ (4)β

∈

VAR

かつ β

=(1,・

]・

,1)(n>1)の

とき_,(1,1・

11)∈

vAR。

￨ (工 )FUNCは

,定

項 (関係定項・関数定項・個体定項

)の

集合

OPER.CONSを

定義域 と

￨

し

,そ

の値 として

,(0,1,・

♀・

,1)(n≧ 1)の

形か

,ま

たは

(1,1,li:1)(n≧

0)の

形 のタイプを取 る関数である。 こうして

,可

能なかざ リー般的な三階言語 を考えるとき

, VARは

量化可能な変項 の持つすべて のタイプを含む集合である。他方

, FUNCは

そのような言語での演算定項 にタイプを割 り当てる 関数である。タイプのうち

,タ

イプ

1は

個体 のタイプであ り

,個

体変項 もこのタイプを持つ。

0の

後 に

1が

n個

並んだ形 のタイプ:(0,1,'I・

,1)は

n項

関係変項 (定項

)の

持つタイ プである。

1が

n+1個

並 んだ形のタイプ

:(1,1,■

i11)は

n項

関数変項 (定項

)の

タイプである。 尚, ゼ ロ項関数は個体 と同一視 され る。 また

,タ

イプ

0は

真理値 (真または偽

)の

タイプである。 これか ら考察す るわれわれの第二階論理

SOL(Second Order Logic)の

言語である第二階 言語では

,量

化可能な変項 としては

,個

体変項 と関係変項のみを用意す る。(関数変項 に関わ る文 や概念は関係変項 によって表現 し直せ るか らである。

)わ

れわれの論理

SOLま

たは λ

SOL(抽

象化演算子 を含む第二階論理

)の

言語の記号系 Σは, Σ

=(VAR(SOL), FUNC)

となる。 ここで

, VAR(SOL)と FUNCは

以下のものである:

(1)VAR(SOL)=(1,(0,1),(0,1,1),(0,1,1,1),一

} (

)FUNCは

上で定義 された関数 と同じもの。

1.l

λ

SOLの

言語 λ―

L2の

アル フ ァベ ッ ト われわれの言語 λ―L2の記号 (アル ファベ ッ ト

)は

つぎのものである:

(1)論

理結合子 (logical connectives):司

,V,A,→ ,一

(2)量

化子 色uantifiers):∀, ヨ

(3)抽

象化子 (abstractor) : 入

(4)括

弧

: ),(

(5)等

号

:E, El,E2,中

0(個体間 と関係間の同一性 または同等性 を表す) これ らはタイプ として

,(0,1,1),(0,(0,1),(0,1)〉

,…

, (0,(0,1,・♀.,1),(0,1,・♀・

,1))等

を持つ③。

(6)偽

i上 (タイプは 0)

(7)個

外変項

:x,y, z, xl; X2, X3,・

…(タイプは

1);

1項

関係 (性質

)変

項

:Xl,Yl, Zl, Xll,X12, X13,中

●(タイプは

(0,1));

2項

関係変項

:X2,Y2, z2,x21,x22,X23,…

(タイプは

(0,1,1));

等々。

(8)0項

関数定項

(=個

体定項

):a, b, c, Cl,C2,C3,・

…(タイプは

1);

1項

関数定項

:fl, gl, hl, f ll, f12, f13,…

(タイプは

(1,1));

2項

関数定項

i f2, g2, h2, f21, f22, f23,…

(タイプは

(1,1,1));

等 々。(タイプ (1,1,丹士

11)(n>1)が vAR(SOL)に

含 まれないのは

,上

記 のよ うに

,関

数変項 を量化可能な変項 に含めないか らである。)

1項

関係 定 項

:RI, Sl,Tl,R ll,R12,R13,…

°(タイ プ は

(0,1));

2項

関係 定 項

;R2, s2,T2,R2ぃ

R22,R23, °

(タイ プ は

(0,1,1));

等々。 これ らの定項 の集合が

OPE

言語L2の_{アル ファベ ッ ト (の集合}

_)は

, “λ

"を

除いた ものである。

1.2

表 現

:項

,述

語

,式

田畑博敏 :第二階論理の特性について

R.CONSで

ある。 言語 λ―L2の_{アル ファベ ッ ト(の集合}

_)か

_{ら抽象化子} (複合 文) (量化 によ る一般 文) アル フ ァベ ッ トの有 限列 の うち言語的 に有意 味な ものを三 つ に分類する。それは

,項

(何 らか の 形 で個体 を表示す る

)と

述語 と式で ある。

(1)項

(term)は

,個

体 変項 か

, OPER.CONS中

_{の個体 定項 か}

_,ま

_{た はf τl― τnの 形} を して いる°°七

(2)述

語 は

,等

号 か

,関

係変 項か

,ま

た は

OPER.CONS中

_{の関係定項か}

_,ま

_{た は} λ xl―xn φ

という形をしている°

1七

(3)式

_{は以下 の形 のいず れかの形 の記号列 で あ る}°2七

(a)Π

n τl― τ

n (述

語 と項 によって作 られ る原子 式)

(b)τ

=t

_{(個体 間 の同一性)} (c)上 _{(恒偽 文} )

(d)Π

n=vn

_{(関係 間 の同一性} )

(e)司

φ

,(φ

∧ ψ

),(φ vψ ),(φ

→ ψ

),(φ

←→ ψ)

(f)∀

xφ_, ョxφ

_,VX・

_φ, ヨ

Xn

これ らの表現はいずれも帰納的に定義されるので

,表

現が何 らかの性質を共通に持つことの証明 は

,数

_{学的帰納法に基づいて実行される。また, これ らの表現には}

_,通

_{常の代入規則が適用できる。}

2.標

準 構 造 次節で展開する第二階論理の意味論の準備として

,本

節では標準構造を与え

,そ

れに関連するい くつかの命題を証明する。われわれの第二階言語は

,記

号系Σ

=(VAR, FUNC),す

なわち, 量化可能な変頂と演算定項 (関係・関数定項

)に

_{タイプを与える関数を持つ構造について何事かを} 語るためにデザィンされている。そこで

,記

号系 Σを持つ標準構造をつぎのように定める。

2.1

記号系Σを持つ標準構造 (standard structure)と は

,以

下の(1)―( )を満たす順序

3組

:

ン =(A,(An)a≧ _{1,(Cン )ccoPER COhlS)}

である。

(1)A≠

グ

(個

体 の宇宙

Aは

非空の集合である)

(

)各

n≧

1に対 して

,An='An,

すなわち

, n頂

関係 の宇宙

Anは

,個

体宇宙

Aの

n項

デカル ト積

Anの

巾集合

(Anの

部分集 合の集合

)で

ある。従って

, n項

関係の宇宙は

,A上

の (つま り個体間の

)す

べての可能な

n項

関係 を含んでいる。

(■

)各

n項

関係定項

R∈

OPER.CONS,お

よび

Rの

タイプ

FUNC(R)=(0,1,■

1)

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

3巻

第

1号 (2001) 137

I Rン

⊆

A×

・P・×

A

こうして

,構

造ンでの関係Rンは個体の

n項

デカル ト積の部分集合である。

￨ (

)各

n項

関数 定項f∈

OPER.CONS,お

よびfのタイ プ

FUNC(f)=(1,■

11)

に対 して, fン (標準構 造 ノ で のfの意 味

)は

個 体 上 の

n項

関数 で あ る。 す なわ ち, fン

:AX・

P・×

A→

A

一旦

_,個

体 の宇宙が決定 されれば

,そ

れ に伴 い

,個

体 間の関係宇宙 も決定 され るか ら

,標

準構造ノ

=

(A,(An)n≧ 1,(Cン )ccoPER CONS)は ,順 序 対 ノ =(A,(Cメ )ccoPER CONS)と 同 一 視 で き る 。

標準構造 に関す る記述は

,(第

二階論理の対象言語である第二階言語 に対す る

)メ

タ言語 によっ て記述 される。 この場合に

,わ

れわれは背景 となる集合論を前提 していることになる。以後

,比

較・ 考察 される二つの標準構造は同じ記号系 Σ

=(VAR(λ SOL), FUNC)を

持つ とする。

2.2部

分 構 造

ン と

Bを ,お

な じ記号系を持つ二つの標準構造 とする:ノ

=(A,(Cン

_{)ccoPER COSS),B=(B,}

(Cお)ccoPER CONS)。 こ の と き,ノ が Bの 部 分 構 造 (substrtlcture)で あ る の は,ノ が 以 下 の (1)一

( )を満 た す と き

,か

つ そ の と き に か ぎ る :

(1)A⊆

B

(五

)す

べ て の

n項

関 数 定 項 f∈

OPER.CONSに

対 して,

fン

=fB,An (fB IAnは

,関

数

fBの , Aの

n項

デカル ト積への制限)

特殊なケースとしてゼロ項関数 (個体定項値

)は

両構造で同一であるiaン

_=aB。

(

)す

べ て の

n項

関 係 定 項

R∈

OPER,CONSに

対 して,

Ry=RB∩

An. こ こで ,“ノ 堅

B"は

“ン は

Bの

部 分 構 造 で あ る

"を

意 味 す る もの とす る。

2.3

準 同 型 ン と

Bが

同じ記号系を持つ二つの標準構造であるとする。関数 (または写像

)hが

ンか ら

Bへ

の 準同型 (hornornOrphism)で あるのは

,丁

度

hが

以下の(1)― ( )の条件 を満たす場合である。

(1)h:A→ B (hは

,定

義域が

Aで

値域が

Bの

関数である) (

)す

べての

n項

関数定項f∈

OPER.CONS,お

よび個体xl,・・・

_,Xn∈

Aに

対 して,

h(fン

(xl,・・・

,X.))=fB(h(xl),中

●

,h(xn))。

(特

殊ケースとして

, h(♂

)=aB)

(五

)す

べての

n項

関係定項

R∈

OPER,CONS,お

よび個体xl,・・・

,Xn∈

Aに

対 して, (xl,…・

_,x.)∈

Rン ⇒

_(h(xl),…

,h(xn))∈

R亀

この( )の条件法が双条件法 “⇔

"に

なる場合

,強

い準 同型 と呼ばれる。

hが

ノから

Bの

中への準同型であるということを “

ン

4B"と

表し,ノ から

Bの

中への準同型が存

在することを “メ→

B"と

表す。準同型は

,多

少荒っぽい仕方で一方の構造の持つ性質を他方の構 造に対応づける°3七

2.4

同

型 ノ と

Bが

同じ記号系を持つ二つの標準構造であるとする。関数

h:A→

Bが

ンか ら

Bの

上への (onto)同 型 [写像

](lsomorphism)で

あるのは

_{, hが}

以下の

(1)―

( )の条件を満たす とき,

田畑博敏 :第 二階論理 の特性 について

かつそのときにかぎる:

(1)関

数

hが

一対― (iniectiol■

Jで

上への (suttectionl関 数 фttectionlで ある。すなわち,

Vx∀

y[h(x)=h(y)→

x=y]か

つ

h[A]=Bで

ある。 ここで

, h[A]は

, Aの

,

hによる像

(lmage)で

ある

:h[A]={y∈

BIヨ

x(x∈

A∧

y=h(x)))。

(

)準

同型 の場合の条件( )と同じ。 (

)す

べての

n項

関係定項

R∈

OPER.CONS,お

よび個体

xl,…

,Xn∈

Aに

対 して, (xl,・…

,xn)∈

Rン ⇔

_(h(xl),…

_,h(xn)〉

∈

R亀

hが

ンか ら

Bの

上への同型であるということを “ノ≧

B"と

表 し

,ノ

か ら

Bの

上への同型が存在す ることを “ノ些

B"と

表す。

2.5埋

め 込 み ン と

Bが

同じ記号系を持つ二つの標準構造であるとす る。関数

h:A→

Bが

ノか ら

Bの

中への埋 め込み

(embedding)で

あるのは

, hが

以下 の条件(1)― ( )を満 たす とき

,か

つそ のときにか ぎる!

(1)関

数

hが

一対―である。すなわち

,Vx∀ y[h(x)=h(の

→

x=y]。

(

)同

型の場合の( )と同 じ。 (

)同

型の場合の(

)と

同 じ。 h

hが

ンか ら

Bの

中への埋め込みであるということを “ノ 重

B"と

表 し

,ン

か ら

Bの

中への埋 め込み が存在す るということを “ノ 壁

B"と

表す。

2.6

これか ら準同型

,同

型

,埋

め込み といった標準構造 間の写像 の間での関係 を調べる。 命題

2.6.1:hを

ノか ら

Bの

中への強い準同型 とす る。 この とき

, hが

ンか ら

Bの

中への埋め 込みであるとき

,か

つその ときのみ

, hが

ノか らh[ノ

]の

上への同型である。

(ここ で , h[ン ]=(h[A],(h[Cン ])ccoPER CONS〉 Q°)

《証明》 hをメか ら

Bの

中への強い準同型 とす る。 いま

, hが

ンか ら

Bの

中への埋め込み と仮定する。埋め 込みの定義の

(1)よ

り

, hは

一対―である。 また

hは

,ン

の部分構造

h[ノ

]に

お いて

, h[A]

(⊆

B)の

上への関数である。 よって

, hは

h[A]へ

の一対一上への関数である。 さ らに

, hは

埋 め込みであるか ら

,同

型の定義条件の(五)と( )を満た している。 よって

, hは

ンか ら

h[ン

]の 上への同型である。逆に

, hが

ノか ら

h[ノ

]の上への同型であるとす る。

h[A]⊆

Bだ

か ら

,関

数

h:A→

Bは

,一

対一中への関数である。よって

, hは

埋め込みの定義条件の(1)を満たす。 ま た

hが

Aか

ら

Bの

部分集合の上への同型であるか ら

, hは

(同型の場合 と同じ

)埋

め込みの定義条 件(

),(

)を満た している。 よって

, hは

ンか ら

Bへ

の埋め込みである。

(Q.E.D.)

命題

2.6.2:hを

ンか ら

Bの

中への準 同型 とする。 このとき

, hが

埋め込みであるとき

,か

つ その ときのみ

, hは

ノか ら

Blh[A]の

上へ の同型である。(ここで

,Bド h[A]は

,個

体領域

h[A]を

持ち

, n項

関数 として

(h[A])nに

制限された

,Bに

おける

n項

関数 を持ち

, n項

関係 として

,Bに

おける関係 と

(h[A])nと

の共通部分 を持つ

,Bの

部分構造である。) 《証明》

h[ノ

]=B,h[A]で

あるか ら

,上

の命題

2.6.1の

系 として導かれる。

(Q.E.D.)

命題

2.6.3:hが

ンか ら

Bの

中への埋め込みであるとき

,か

つそ のときのみ

,構

造σが存在 し

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

3巻

第

1号

(2001)

てσ

ttB(す

なわちσは

Bの

部分構造

)か

つ

hが

ンか らσの上への同型である。 《証明》

hが

ノか ら

Bへ

の埋 め込みであるとす る。 この とき

,命

題

2.6.2に

よ り

, hは

,ン

か ら

BIh

[A]の

上への同型である。 ところで

,構

造

B'h[A]は

,そ

の個体領域が

h[A]で

,関

数は

(h[A])nに

制限された

Bの

関数

,関

係は

(h[A])nと Bに

おける関係 との共通部分であるよう な

,Bの

部分構造である。 よって

,BⅢ h[A]を

σ と見なす ことによ り

, hは

ノか ら

Bの

部分構 造σの上への同型 となっている。逆 に

,σ

ttBか

つ

hが

ノか らσの上への同型であるような構造σ が存在す るとす る。 σにおける関数は

Bの

関数 の

(h[C])nへ

の制限であるか ら

,σ

での関数 の 値はそ のまま

Bで

の関数の値 とな り

,σ

における関係は

Bに

おける関係 と

(h[C])nと

の共通部 分であるか ら

,σ

における関係はそのまま

Bに

おける関係で もあること

,お

よび

hが

同型であるこ とか ら

,埋

め込みの定義条件の( )と( )は満たされ る。

hは

Bの

中への一対一関数だか ら

,埋

め 込みの定義条件(1)も満たす。 よつて

, hは

ノか ら

Bの

中への埋め込みである。

(Q.E.D.)

命題

2.6.4:上

で定義された部分構造 (堅

),準

同型 (→

),同

型 (些

)お

よび埋 め込み (重) は

,相

互に以下のような含意関係 (矢印

)に

ある。 ン匡

B

癖

_→

_{亡“ →巾}

《証明》 ②の含意は

,同

型 と埋め込みの定義 と

,上

への関数は中への関数の特別なケースである ことによ り 示される。③の含意 も

,埋

め込み と準同型 の定義 と

,一

対―の関数が関数の特別なケースであるこ とと

,双

条件法か らその一方の条件法が導かれ ることによる。①の含意は命題

2.6.3を

用 いて以 下のように示 され る。ノ を

,お

内部でのノ 自身のコピーであると見なす。すなわち

,恒

等写像

:h

(x)=xは

,ノ

か らンの上への (自己

)同

型である。 いま

,仮

定によ リノ匡

Bだ

か ら

,σ

堅おかつ

hが

ノか らσの上への同型であるような

,Bの

部分構造 σ (つまリノそのもの

)が

存在す る。よっ て

,命

題

2.6.3に

よ り

, hは

ンか ら

Bの

中への埋め込みである (ノ巨B)。

(Q.E.D.)

2.7

合 同関係 と準 同型 これか ら

,同

値関係よ りももっと類似性の高い関係 として合 同関係 を定義 し

,そ

れ と準 同型 との関 連 を調べる。

2.7.1

合同関係

標準構造ン と

2項

関係

R⊆ A×

Aが

与え られた とす る。

Rが

合同関係 (congruence relation) であるのは

,以

下の条件(1)―( )を満たす とき

,か

つそのときにかぎる:

(1)Rは

A上

の同値関係である。すなわち

, Rは

反射的

,対

称的

,推

移的であ り

,そ

の定義域 と 値域は

Aで

ある。

(

)任

意の

n項

関数定項 f∈

OPER.CONS,お

よびxl,・中

,xn'yl,…

,yn∈

Aに

対 して

(xl,yl)∈ R,

中●

,(xn,‰ )∈

R⇒

(fン (xl,中●,xn), fン (yl,い。,yn)〉 ∈R

すなわち

,関

係

Rを

満たす個体 どうしに適用された関数の関数値 も再び関係

Rを

満たす。

田畑博敏 :第二階論理の特性について

〈xl,yェ

)∈

R,… ,(xn,る

)∈

R⇒

_[(xl,・・・

_,Xn)∈

Tン◇ (yl,・・・,る

)∈

Tン]

すなわち

,関

係

Rを

満たす個体グループが同一の関係を満たすかどうか

,は

常に一致する。

命題

2.7.2:hが

ンか らの

,他

の構造

Bの

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

∼

h={(x,y)∈

A×

A:h(x)=h(y)}

は

A上

の合同関係である。

この命題は

,強

_{い準同型によって他の構造の同一個体に写される元の構造の個体 どうしを関係∼}

hと

_{定義するとき, この関係∼}

hは

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

《証明》

(1)∼

hが

_{同値関係であることは容易に示す ことができる}°5七

(■

)任

意の

n項

関数定項 f∈

OPER.CONS,お

よびxl,・・・_{,Xtl,yl,… ,yn∈}

Aに

_{対 して} , (xl,yュ〉 ∈∼

h,一

,(xn,恥

〉 ∈∼hと仮定する。 この とき

,∼

hの

定義 によって,

h(xl)=h(yl),… , h(xn)=h(る

)・……① である。

hは

準同型であるか ら,

h(fン

(xl,い。

,XIa))=fB(h(xl),一

,h(xn)) [準

同型の定義(五)より]

=fお (h(yl),…

_{,h(yn)) [①}

よ り]

=h(fン

(yl,―・

,yn))…

…②

[再

び準同型 の定義 よ り]

さ らに

,(fン

(xl,…。,Xn), fン (yl,中●

,yn))∈

A×

A…

…③。 よって

,②

と③ と∼

hの

定義か ら

,(fン

(xl,・・・,Xn), fン (yl,・・・,端

))∈

∼

h

が導かれる。

(

)任

意の

n項

関係定項

R∈

OPER.COPNS,お

よびxl,…・_,Xn,yl,…・_,yn∈

_Aに

_{対 して}

(xl,yl)∈

∼

h,…

,(xn,y.)∈

∼

hと

仮定す る。 このとき

,∼

hの

定義 によ り

h(xl)=h(yl),…

_,h(xn)=h(恥

)・…・④ である。そ こで, (xl,…・,xn〉 ∈Rン ◇

(h(xl),…

,h(xn))∈

RB [強

_{い準同型 の定義 よ り}] ⇔

(h(yl),一

,h(恥

)〉 ∈

RB [④

よ り] ⇔ (yl,●中

,yn)∈

Rン

[強

_{い準同型の定義よ り}]

すなわち

,(xl,…

・,Xn〉 ∈Rン ◇ (yl,―。,yll)∈Rン。

(Q.E.D。

)

命題

2.7.3

ノ上の任意の合同関係≡に対 して

,≡ =∼

hで

あるような

,ノ

か ら他 の構造 :

ノ

_==(A三

,(Cン

三)ccOPER COhS)の上への

(onto)強

い坤 同型

hが

存在する。 《証明》

構造ノ

_=が

以下のように定義 されるとせよ:

(1)A三

=([X]=:x∈

A}は

,関

係 茎によって生成 される同値類 [x]≡

=(z∈

A:x≡

z}

の集合。 (

)任

意の

n項

関数定項 f∈

OPER.CONS,お

よびxl,… ,Xn∈

Aに

対 して, fy=([xl]≡,…,[xll]三

)=[fン

(xl,・・・,x.)]=。 すなわち

,Aこ

のメンバーである同値類間に適用 された新 しい関数fン=の関数値は

,同

値類 の代表元 に適用 された元の関数fンの関数値 の≡による同値類である。 (

)任

意の

n項

関係定項

R∈

OPER.CONS,お

よびxl,… ,xn∈

Aに

対 して, ([Xl]三,…・

,[xn]=)∈

Rン

=⇔

(xl,・・・

,Xn)∈

Rン。 すなわち

,A三

のメンバーの同値類間に新 しい関係Rン

=が

成 り立つのは

,同

値類 の対応す る 代表元 の間に元 の関係Rンが成 り立つ とき

,か

つそのときにかぎる。

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

3巻

第

1号

(2001)

hが

_,Aの

任 意 の元

xを

そ れ の 同値 類[x]=に写 像 す る 関 数 で あ る

,

とせ よ。 す な わ ち,

h:A→ A_

x卜→_[週

=(つま り

, h(x)=[x]≡

とい う こ とで あ る)

1,こ

の とき

, hは

上 へ の

(onto)関

数 で あ る。 実 際, A三 ={EX]三

:X∈

A)={z:ヨ x(x∈

AAz=lxl

Ξ

))だ

か ら

,任

意 の

zに

つ いて

, z∈

Aこ とす る と

_,あ

るx。 ∈

Aが

存 在 して

, z=

lXO]三で あ る。

hの

定 義 よ り, h(x。)=[x。

]==zで

あ るか ら

, z∈

{z:ヨ

x(x∈

A∧

h(⊃

=z)}=h[A],つ

ま り

zは hの

値 域

h[A]に

属 す る。 こ う して

,A三

⊆h[A]。

hは

Aか

ら A三 へ の 関数 と して定 義 され て い る ので

,

トリヴ ィ アル に

h[A]⊆

A三 。 これ らに よ り

h[A]=

A=,す

なわ ち関数

hは

上へ の関数で ある。

2.つ

ぎ に準 同型 の定義条件

2,3(■

)に相 当す る等式 を示 した い。実 際, h (fン (xl, ,・・, Xn)) ==[fン (xl, ・…, xn)]=

=f】

三([Xl]三,中●,[xn]三)

=fン

Ξ

(h(xl),…

,h(xn))

[上の( )より] [hの定義よ り]

3.さ

らに準同型 の定義条件

2.3(

)を双条件法 に強めた式が成 り立つ ことを示す。 (xl,…・,xI.)∈Rン ⇔ ([xl]三, ・,[xn]三

)∈

Rノ

Ξ ◇

(h(xl),…

,h(xn))∈

Rノ

₌

4.最

後 に

,==∼

hということを確かめる。任意の

x,y∈ Aに

対 して, (x,y)∈ ≡ ⇔ x≡ y ◇ [x]≡=[y]Ξ

[=が

合同関係だか ら同値関係でもあるか らQ°] ⇔

h(x)=h(y)

_{[hの定義よ り]}

⇔

(x,y)∈

∼

h[(x,y)∈

A×

Aお

よび∼

h={(x,y)∈

A×

A:h(x)=h(y)}よ

り]

(Q.E.D.)

命題

2.7.4 hが

ンか ら

Bの

上への (ontの 強い準 同型であるとす る。そ のとき, ノ ∼httB. (た だ し ノ ∼h=(A∼ h,(C∼ h)ccoPER.COSS) 《証明》

hが

ノか ら

Bの

上への強い準同型であるとする。 このとき

,先

の命題

2.7.2に

よ り

,ノ

上の合同 関係∼

hが

定義できる。す ると

,命

題

2.7.3に

よって

,ン

か らノ∼hの上への関数で

,∼

h=∼

h′であるような強い準同型h′_{が存在す る。 このとき}

,ノ

∼

httBで

_{ある。なぜな ら} ,

H:A∼

h→

B

[x]∼h卜→

h(x) (た

だ しA∼

h={[x]∼

h:x∈

A)で

ある) によって定義 され る関数

Hは

同型 偽

ornOrphism)で

あるか らである。実際に

, Hは

以下の(1)一 ( )を満たす。

(1)Hは

十分 に定義 されていて

,一

対―で上への関数である。なぜな ら

_,ま

ず,

(x,y)∈

∼

h◇

[x]∼h=[yl∼

h [∼

hが

合同 (.l同値

)関

係であることか ら] ⇔

h(x)=h(y)

[hの定義 よ り] [上の( )よ り] [hの定義 よ り]

[Hが

関数 で あ る ことと∼

hの

定義 よ り]

[Hの

定 義 によ り] ⇔ H([x]∼

h)=H([y]∼

h) こうして

, Hの

関数値 の同一性

h(x)=h(y)が

,(x,労

の∼

hの

帰属如何 によって決定 さ れるが

,仮

定 よ り

hは

,従

って∼hは十分 に定義 されているか ら

, Hも

十分 に定義 されてい ることになる。 また

,上

の必要十分の中に

, h(x)=h(の

⇒[x]∼h=[y]∼hが含 まれている

田畑博敏 :第二階論理 の特性 につ いて の で_{, Hは} 一 対 ― で あ る 。 さ ら に hが上 へ の (onto)関数 だ か らHも上 へ の 関 数 で あ るQ7七 (

)任

意の

n項

関数定項f∈

OPER.CONS,お

よび

A∼

hの 任意 の要素 [xl]∼ h,… ,[xn]∼h に対 して,

H(fン

∼h([xl]∼h,…・_,[xn]∼h))

=H([fン

(xl,・・・

,xn)]∼

h) [命題

2.7.3の

A三 における(五)による]

=h(fン

(xl,・・・,為

)) [Hの

定義]

=fB(h(xl),…

,h(為

)) [hが

ノか ら

Bへ

の準同型であることか ら]

=fお

(H([xl]∼h),…

,H([xn]∼

h)) [Hの

定義による] (■

)任

意の

n項

関係定項

R∈

OPER.CONS,お

よび

A∼

hの 任意の要素 [xl]∼ h,… ,[xn]∼h に対 して, ([xl]∼h,…・,[xn]∼h〉 ∈Rン ∼h ⇔ (xl,・・・

,為

)∈

Rン

[∼

hを

,命

題

2.7.3の

( )での三と見 る] ⇔

(h(xl),一

,h(xn))∈

Rお

[仮

定 によ り

hが

強い準同型であるか ら] ⇔ (H([xl]∼h),一,H([xl]∼ h))∈ RB[Hの 定 義 :H(lx]鴇 )=h(x)に よ る]

(Q.E.D.)

命題

2.7.5 hlと

h2が

,そ

れぞれ

,ノ

か ら

Blの

上への

,お

よびノか ら

B2の

上への

,強

い準 同型であ り

,か

つ∼

hl=∼

h2のとき

,Bl些

B2で

ある。 《証明》 命題

2.7.4よ

り

,ノ

∼hi ttBl,ノ ∼h2些

B2が

導かれる。 しか し

,仮

定によ り

,∼ hl=∼

h2で ある。 ∴

Bl些

ノ∼hittB2。 主は同値関係だか ら

,Bl些

B2。 (Q・

E.D.)

3.標

準 的 意 味 論 これまでの節でわれわれは

,言

語 とそれが表現すべき存在

(=構

造

)を

提示 した。標準的構造は 個体の宇宙を基盤 として

,そ

の上に個体間の関係の宇宙を築いていた。本節では 「意味」

,す

なわ ち

,言

語 と存在 (構造

)を

繋 ぐものを

,解

釈 と充足の概念によって展開する。解釈は

,変

項の持つ 不定性を構造の要素の割 り当てという形で捉えたものである。 この解釈が項 と述語の意味を与え, それによって文の充足が定義され

,真

理の概念の基礎となる。 これ らの事柄を

,一

歩一歩具体的に 展開し

,そ

の後

,メ

タの性質

,高

次の関係

,表

現力の問題等へ と探究を進めることにする。

3,1

割 り当て (岱

signmene

3.1.1

第二階論理において

,割

り当ては変項の集合か ら宇宙への写像

Mで

ある:

M:ソ

∪(∪ ソ

.)→ A∪

(∪ An) n」 n≧

(こ こで

,各

nに

対 して

,M(ソ

)⊆

A,M(ソ

n)⊆

An=ヂ

An。 すなわち

, n項

関係は常に

Anの

巾集合 において値 を得 る。)

3.1.2 Mが

割り当てであり

, xが 個体変項で, xが Aの 元であるならば

,M4は

Xを xに 写

像する割 り当てであり

,xと

異なる変項については

Mと

全く一致する。従って

,M生 =(M―

((X,

WI(x))})∪

{(x, x〉

)。

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

3巻

第

1号 (2001) 143

は

,変

項

Xnを

関 係

XPへ

と写 像 す る割 り当 て で あ り

,他

の変 項 に関 して は

Mと

一 致 す る。 従 って, MXゝ

n=(M―

{(Xn,M(Xn))})∪

{(X・,Xn)}。

3.1.4

同様 に して

,わ

れ わ れ は

_,タ

イ プ の相 異 な る任 意 の変 項vl,…・

,Vn,お

よ び これ ら と同 じ添 え字 の 変 項 と同 タイ プ を持 つ

, A中

の個 体 また は個 体 間 の 関係vl,…

,Vnに

対 して, W[Vl Vnvl vュ

、 を 定 義 す る 。 す な わ ち,M ‐Vn vn=(M {(vl,M(vl)),一 ,(vn,M(vn)〉 })∪ {(Vl,vl), ・・・_{,(vn,Vn〉 }。}

3.2

角早釈 (interpretation) 標準構造上の解釈 √は

,順

序対 (ノ

,M)で

ある: デ

=(ン

,M)

ここで

,Mは

ノ上の割 り当てである。一旦

,解

釈が与え られると

,す

べての項は

Aに

おける要素を 表示 し

,そ

の解釈の下ですべての式は真か偽 となる。「解釈の下で真である」 という概念が 「充足」 関係によって

,正

確 に定式化 され る。

3.2.1

項 と述語の指示の定義

,

λ―L2の式の充足の定義 解釈 デをデ

=(ノ

,M)と

す る。τが項で

x∈

Aの

とき, √(τ

)=xは

,項

τが デの下で個体

xを

表 していることを示す。

(Tl)√

(x)=M(x)

(T2)√

(a)=aン

(T3)ノ

(f τl―・τ

n)=fン

(デ (τ l)・…∫(τ.)) Πnが

n項

述語で

Xn∈

An='Anな

らば, デ(Π

n)=Xnは

,Π

nが解釈 デにおいて関係

Xnを

表現 していることを示す。

(Pl)√ (Xn)=M(X・

)

(P2)√

(R)=Rン

(P3)√ (=)={(x,y)∈

A2:x=y}∪

(∪

{(Xn,Yn)∈ An2:xn=Yn})

n型

(P4)√

(λ xl・・・xn φ

)=((xl,…

・

,xn)∈

AX…

×

A:デ

瀾 Xn xl―

xn SAT

φ}

こ こで, デXl xl…Xtl SAT φは

,解

釈 デXl Xn xl―xnが式 φを充 足 す る とい う こ と を示 す 。一 般 に, ノ

SAT

φ と書いて

,解

釈 √が式 φを充足する (satisfy)こ とを示す。

(Fl)デ

SAT

Πユτl―τ

n◇

(ノ(τl),一,√ (τ

.))∈

デ(Πn) 特 に √

SAT

τ_l=τ

_2⇔

デ(τ

l)=デ

(τ2)。 ま た

, F SAT上

は 不 成 立 。

(F2)F SAT

Π

n=vn⇔

デ(Π

n)=√

(Vつ

(F3)F SAT司

φ⇔ √

SAT

φで な い

;

ノ

SAT

φ

Vψ

⇔

F SAT Oま

た は √

SAT

ψ ;

F SAT

φ∧ψ⇔ デ

SAT

φ力ゝつ √

SAT

ψ;

デ

SAT

φ→ ψ⇔ デ

SAT

φな らば デ

SAT

ψ;

F SAT

φ←→ ψ⇔ デ

SAT

φの ときかつそのときのみ デ

SAT

ψ

(F4)F SAT∀

xφ ⇔ すべての

x∈

Aに

対 して ∫上

SAT

φ;

F SATヨ

xφ ⇔ 少 な く とも一 つ のx∈

Aに

対 して √上

SAT

φ;

田畑博敏:第二階論理の特性 について

√

SATヨ

Xn。 ⇔ 少 な く と も 一 つ の

Xn∈ Anに

対 して √Xtt SAT φ

3.2.2

式のモデル 式 φが与え られた とき

,解

釈 ノが φのモデルであるのは デ

SAT

φ(ノが φを充足す る)と きかつ そのときにかぎる。また

,式

の集合 「 が与え られた とき

,解

釈 √が

Fの

モデルであるのは

,す

べての 式 φ∈ 「 に対 して,デ

SAT

φの ときかつそ の ときにか ぎる。解釈 √が式 φのモデルであることを デFE φ と表記 し

,解

釈

Fが

式の集合 「 のモデルであることを √卜 「 と表記する。 また

,

φが割 り当てを必要 としないような文 (自由変項 を含 まない文

)で

あるとき, 「構造ンは φのモデルである」または 「φはンで真である」 と言い,“ノ トφ

"と

表記す ることがあ る。 「 が割 り当てを含 まない文の集合であるとき

,構

造ンが

Fの

モデルであることを “ノ ト

F"と

表記する。

3.2.3

充足性の定義 式 φが充足可能である (satisfiable)の は

,少

_{な くとも一つの解釈 √が存在 して デト φであると} き

,か

_{つそのときにかぎる。式の集合「 が充足可能であるのは}

_{, F中}

_{のすべての式 を同時 に充足す} る解釈が存在す る

,す

なわち (ョ デ)(∀φ)(φ∈ 「 ⇒ ∫卜 φ

),の

ときかつそ のときにかぎる。 ま た

,式

φが充足不可能である (unsatisfiable)の は

,

φが充足可能ではないとき

,か

つその ときに かぎる。式の集合 「 が充足不可能であるのは

, Fが

充足可能でないとき

,か

つその ときにかぎる。

3.3

帰結 と妥 当性 帰結関係は正 しい推論の仮定 (または仮定の集合

)と

_{結論 との間に成 り立つ意味論的関係であ り}, 論理の基本概念である。正 しい推論 とは

,さ

まざまなモデルや状況・世界の差異にも関わ らず推論 の過程 を一貫す るあるパターンである, という考 えを定式化 したものが

,(論

理的

)帰

結 の概念で ある。それは

,正

しい推論においては真なる仮定 の集合

rか

_{ら偽なる結論 φが導かれ る ことは在 り} 得ない, とも言 い換えることができる。そ して

,モ

デルの概念 を用 いて, 「 ∪ {￢φ) がいかなるモデル をも持たないこと

,と

して定式化 される。 これは

_,「

_{の中の任意の式 を充足す る} 解釈が常 にφのモデルで もある(∀デ(√卜 Γ⇒ デト φ

))と

いうことに他な らな い。意味論的な 帰結の概念 (卜)に対応するのが構文論的な導出可能の概念 (卜

)で

あ り, これは推論過程 を形式的 に具象化す るものである。 また

_,わ

れわれは

,妥

当性 を式の空集合か らの帰結 と定義す る。任意の 解釈が空集合のモデルであるか ら

,

この定義 によ り

,妥

当な式を

,す

べての解釈がそのモデル とな るような式 (直_{観的にはあらゆる世界で成 り立つ式}

)と

_{して定義できる。}

3.3.1(論

理的

)帰

結の定義 式 φが式の集合 「 の帰結

(consequence)で

あるのは

, Fの

モデルである任意 の解釈 が φのモ デルで もある

,す

なわち 「 FE φ (詳しくは

Vデ

(√卜

F⇒

√卜 φ

)),の

ときかつそ の ときにか ぎ る。式 φが集合 「 の帰結であることを 「 卜 φ と表記する。 φが 「 の帰結ではないことを “

F/φ

"と

表記す る。 このとき

, oは Fか

ら独立 して いる (independent)と _{も言 う。}(われわれは同 じ記号 “卜

"を ,モ

デル を表す にも帰結 を表す に も用 いるが

,文

脈 によ り混乱は避けうる。)

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

3巻

第

1号

(2001) 145

3.3.2

妥 当性 の定義 式 φが妥当である (validlのは

,″

卜φであるとき

,か

つそのときにかぎる。任意の解釈が式 の空集合のモデルであるから

,結

局

,妥

当な式とはすべての解釈で充足される (すべての解釈をモ デルとする

)式

のことである。式φが妥当であることを FE φ と表記する。すべての

F(式

の集合

)と

式 φに対 して,「F tt _φ◇

F∪

{勺φ}力ゞ充足不可能」 と

いうことが成り立つ

C8七

3.4

論理的同値

以 下 で二 つ の式 が互 いに他 の帰結で ある ことを論理 的 同値 として定義す る。 これ はメタ概念 で あ る。 この概念 は

,わ

れ われ の言語 の単純化や

,別

形 の意 味論提示 の際 の基礎 とな る。

3.4.1定

義

二つの式φとψが論理的に同値である (logically equ alent)の は, φ tt ψかつゆ卜φ (言い

換えるとφのモデルである任意の解釈がりのモデルでもあり

,

ψのモデルである任意の解釈が φの モデルでもある

)と

き

,か

つそのときにかぎる。 φとψが論理的に同値であることを φ 卜引 ψ と表記する。

3.4.2

命 題 す べ て の式 φ, ψに対 して, φ卜引 ψ ⇔ 卜 φ←→ ψ。す なわ ち

,二

つ の式が論理 的 に同値 で あ

るということは

,そ

の二つの式からなる双条件法の文が妥当であるということに他ならない°

9七

3.4.3

命題

:す

_{べての式φ, ψに対して以下のことが成り立つ}

:

(1)上

卜引 …

x=x

(2)φ

∧ ψ 卜引 司 (司φ

V司

ψ)

(3)φ

→ ψ 卜引 … φ

vψ

(4)φ

←→ψ 卜引 勺 (φ

Vψ

)V司

(司φ

V司

ψ)

(5)∀

vφ 卜引 勺 ョ

v司

φ 《証明》 命題

3.4.2に

よ り

,容

易に証明できる乾O七

3.4.4

命題 :す_{べての式φ, ψに対して以下のことが成 り立つ。(証明略)}

(1)―

φ 卜引 φ→ 上

(2)φ

∧ ψ 卜引 (φ→ (ψ→ ■))→上

(3)oVψ

卜引 (φ→ 上

)→

ψ

(4)φ

←→ ψ 卜引 ((φ → ψ

)→

((ψ → φ

)→

上

)}→

上

(5)∀

vφ 卜引 (ヨ

v(φ

→ 止

))→

上 他 に も

,第

二 階論理 にお ける論理 的 に同値 な式 の対 が ある。例 えば

,二

つ の個体

x, yが

同一 で あ る こ とを表現 す る式 :∀

Z(Zx―

Zy)は

_,つ

_{ぎ の式 と論理 的 に同値 で ある} :∀

Z2(vz

z2zz→

z2xy)。

後 者 の式 は

,個

体

xと yは

任 意 の反 射 的

2項

関係 にあ る, と主張す る。 同一 性が最小 の反射 的関係で ある ことと

,標

準構造 にお いて はす べて の集合や関係 が関係宇宙 の中に与 え られて いる こととによ り, この同値 関係が成 り立 つ。 よって

,等

号記号 を原始 記号 として用 いな い第二 階論理 にお いて

,VZ(Zx←

→

Zy)と

_∀

_Z2(∀

_{zz2 zz→ z2xy)の}

_{いず れ もが} ,

田畑博敏 :第 二階論理 の特性 につ いて

x=yの

代わ りに用 い られる。 また

,言

語 を単純化 して

,(司

,V,ヨ

)の

みを原始論理記号 とす る場合

,他

の記号:上

_,A,→

, 一

,Vを

命題

3.4,3を

基礎 として定義できる。(上

,→

,∀ }の

み を原始論理記号 とす る場合 (様相論理の場合等

),他

の記号 :コ

,A,V,←

→_{, ヨは命題}

_3.4.4を

_{基礎 として定義できる。}

3.5

与え られ た構 造 にお ける定義 可能な集合 と関係

標準構造ノ

=(A,(An〉

n≧1,(Cン)ccoPER CONS)と 第二階言語 λ―L2または

L2が

与え られると,

単にンの個体間関係のみな らず

,個

体間の関係の関係 (第二階関係

)や ,言

語 を用 いて定義される 関係, といった関係 をも定義できる。われわれの言語 の記号系によって標準構造 に当初か ら与え ら れているのは個体 の宇宙 と

,そ

の上での関係である。 しか し

,そ

れ以外 に

,い

くつかの言わば隠さ れた関係がある。本節ではそれ を

,当

初の個体間関係 (第一階関係

)も

含めて統一的に扱 う。

3.5.1

まず構造ンの第一階関係 をつぎのように定義す る。ンを標準的な第二階構造だ とする。 ン上の

n項

の第一階関係

Xと

は

,個

体 の宇宙の

n項

デカル ト積 の部分集合である

:X⊆

Ano RE

L ttT(ノ

)を

ン上のすべての第一階関係のクラス とする:

RELお

T(ン

)=(X:ヨ

n(X⊆

An))=∪

_n塾

'An。

任 意 の第 一 階 関 係

Xが

ン の 中へ の (into)関係 で あ る の は

, X∈

An='Anま

た は

X=Rン

の 場 合 である。ンの中への第一階関係全体のクラスをR E LttT(∈ン

)と

表記する。 ここで定義された関係は第一階関係

,す

なわち個体間の関係である。標準的第二階構造ンの宇宙 に存在する関係は

,す

べて個体間の関係である。逆に

,構

造が標準的であるとき

,個

体間の関係は すべて構造の宇宙の中にある。 こうして

,標

準的構造では

,ノ

上のすべての

n項

第一階関係はンの 中への関係である。上の定義より

,以

下の命題が成 り立つ:

3.5.1.1

命題 :標準構造ノに対 して,

(1)R E LlST(ン

)=∪

_n」

An(=∪

_n」 ヂ

An);

(2)R E LlST(ノ )=R E LlST(∈ ノ)。

3.5.2

ンの第二階関係の定義

ンが標準的第二階構造であ り, All,・ …

,Ainが

ン の宇宙である (各A ijが個体宇宙かまたは関係 宇宙

,す

なわちA馬

=Aま

たは

A ij=Am,m≧

1)と

き, これ らの宇宙のデカル ト積の部分集合

X:

X⊆

All× …,×A in

は

,ノ

の第 二 階 関係 (secOnd order relation)で あ る。

REL(ン

)をン の す べ て の第 二 階 関 係 の ク ラス とす る :

REL(ノ )=∪ {X:X⊆

All× 中,×

A in)=∪

'(All×

…・×Ain)o

X∈ Anま

た は

X=Rン

(ある

R∈

OPERoCONSに

対 して

)で

あ る とき (すな わ ち

Xが

構 造 に 当初 か ら与 え られ た 関 係 宇 宙 の一 つ で あ る とき

),第

二 階 関係

Xは

ン の 中へ の (il■tの 関 係 と言 う。

REL(∈

ノ

)を

,ノ

の 中へ の第 二 階 関係 全体 の ク ラス とす る。 固有 第 二 階 関 係 を,R E L2ND(ン )

=REL(ノ

)― R E LiST(ン )として 定 義 す る。 第二階の関係 において

,す

べてのA ijに対 して

Al,=Aの

とき

,定

義

3.5.1で

の第一階関係 と なる。 こうして

,第

二階関係の集合は

,(真

)部

分集合 として

,第

一階関係 の集合 を含んでいる。 また

,記

号系の選択によ り

,構

造の中に固有第二階関係を持たない (異なる記号系を選べば持てる)。 個体 の可算無限宇宙 を持つ構造ノ

(IAI=(0)に

対 して

,ン

の第一階関係 の集合R E LiST(ノ) は 2 NO個 のメンバー を持つ91と また

,ン

の (固有

)第

二階関係 の集合R E L2ND(ン

)は 2の

2＼0乗

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

3巻

第

1号

(2001) 個のメンバーを持つ°2七

3.5.2.1

命題:上_の定義

_(3.5.2)よ

り

,以

下のことが導かれる:

(1)R E LlST(ノ )⊆ REL(ン

), し か し R E LttT(ン

)≠ REL(ン

)

(2)R E LlST(∈

ノ

)=REL(∈

ノ)

3.5.3

つぎに

,与

え られた言語 を用いて

,ノ

で定義可能な第一階関係 を定義する。ン を第二 階構造

, X⊆ Anを

個体間の

n項

関係 とする。 このとき

, Xが

λ―L2を_{用 いてンで定義可能な第一} 階関係であるのは

, FREE(λ

xl… xn φ

)=〃

(すなわち述語 λ xl… xn φに含 まれる自由変項 が存在 しない

)で

あるような 入―L2の式

0と ,

どの二つも互 いに異なる個体変項が存在 し,

X=√

(λ xl… xn O) であるようなノ上の解釈 ∫が存在す るとき

,か

つそのときにかぎる。 λ抽象化子 を持たない第二階 論理の言語L2においては

, L2を

用 いて構造ノで

Xを

定義できるのは,

X= ((xl,・

…

_,Xn):(ノ

_{, MXl Xn xl_Xn)SAT}

_φ} の と き

,か

つ そ の と き に か ざ る 。 こ こ で

Mは

割 り 当 て で あ り

, FREE(φ

)⊆ (xl,…・_,Xn)。

DEFお

T(ン

_{, L2)を , L2を}

_{用 いてンで定義可能なすべての第一階関係 を含む最小クラス とする。} (以後

,(ン

,MXl Xn xl…

Xn)を

ノ

F

xl―

xn]ま

たはノ [xl,・・・,Xn]と略記す ることがある。)

3.5.4

与え られた言語 を用 いて

,ン

で定義可能な第二階関係 を定義す る。

Xが

言語 λ―L2 (または

L2)を

用 いてノで定義可能な第二階関係であるのは

, Xが

ン における第二階関係であ り, かつ λ―

L2(ま

たは

L2)の

式 φが存在 して,

X=((vl,中

●

_,L)∈

_{All×…・×A in:ノ}

_{[F Xnxl―}

_xn]SAT

φ}

で あ る と き

,か

つ そ の と き に か ぎ る 。(こ こで

, FREE(φ

)⊆

{vl,・・・

,ゝ

),各

j(1≦ j≦n)

に対 して 変 項viはタ イ プ 巧∈

VAR。 )対

応 す る 集 合 を

, DEF(ノ

,

入 ―

L2), DEF(ン

_{, L2)}

とす る。 われわれの第二階論理の言語は可算であるか ら

,変

項の有限列の集合 も可算である。よって

,言

語で定義可能な関係の集合 も可算であ り

,NO以

下の基数 を持つ。

3.5.4.1

命題 :以 下の事柄が標準構造 に対 して当てはまる:

(1)DEF(ノ , L2)=DEF(ノ

, λ― L2)

(2)DEFお

T(ン

, L2)=DEF｀

T(ノ, λ ―L2)

(3)DEF卜

T(ノ

, L2)⊆

DEF(ノ

, L2),

し か しD E FlST(ノ

_{, L2)≠}

DEF(ノ

, L2)

《証明》定義に基づいて実行できる°3七

3.5.5

続いて

,与

えられた言語を用いて

,か

つパラメータ (すでに構造において当初に与え られている個体および個体間の関係をこう呼ぶ

)に

よってンで定義可能な第一階および第二階関係 を定義する。

Xが

入―

L2(ま

たは

L2)を

用いてパラメータによ リンで定義可能な第一階関係であ るのは

_,つ

ぎの場合である:個_体変項xl,・…,為 と

_,タ

イプが各々11,・・・,im∈

VARの

変項vl,・…, vnaと

, FREE(φ

)⊆ (xl,…Ⅲ

,乳

,Vl, ,

生

n)で

あるような式 φが存在 して,

X=((xl,・

・・

_,Xn)∈

An:ノ

[知 .Xn _{…vn xl.…} Xn Vl・…

Vm]SAT

φ)。

ここで

_,パ

ラメー タvl,…

_,vmは

各 々タイ プil,…

,lmを

持 ち

,各

々宇宙

All,…

,Aim(各

j(1≦_J

≦

m)に

つ き, A可

=Ahで

hは

正 整数

)に

属 す る。 また

, Xが

入―

L2(ま

た は

L2)を

用 いてパ ラ メータ によ って定義可能な第二階関係であるのは

,つ

ざの場合 で あ る:(一_{般 の}

_)変

項ul,・・・,un,

Vl,¨・

_,吼

(各々のタイプはkl,… ,吼,11,・・・,im∈

VAR)と , FREE(φ

)⊆ {ul,・・・,un,vl,

田畑博敏 :第二階論理の特性について

X= {(ul,・

・・

_,un)∈

A(1× …・×Alg・ :ノ [m m tt Vm ul・ …鴫 vl―

Vm]SAT

_φ)。 ここで

,パ

ラメー タ

vl,…

,vmは

各 々 タイ プil,…

,lmを

持 ち

,各

々宇宙A ll,・・・,A im(各宇 宙 は 個体 間の関係宇宙

)に

属 す る。 任意 の構造ノ にお いて

,Anに

お けるすべて の

n項

第 一 階関係 はパ ラメー タ によって定義 され る。 とい うのは

,式

Xxl…

xnと解 釈 ∫―一 ∫

(Xn)が

望 ま しい関係 とな るよ うな解釈―― を取 る ことに よ り

,標

準構 造 の関係宇宙 に含 まれ る第一階集合 と第一階関係 を

,先

の式 を充足す る個体 の順序

n

組 の集合 と して定義 で き る (それがパ ラメータ による関係 の定義 で あった

)か

らで ある。パ ラメー タ によ る関係 の定義可能性 は

,一

見 トリヴ ィアル な もの と思われ るが, この概 念は非標準構造 を扱 う文脈 で有用 とな る。(本論 文 で は もっぱ ら標準構造 を扱 うので

,

この概念 につ いて は定義 のみ に 止 める。)

4.第

二 階 論 理 の 表 現 力 最後 に

,本

節では

,第

二階論理の表現力について再考 し

,い

くつかの否定的結果 を導 く。第二階 論理の表現力の強 さは

,意

味論 を記述す るメタ理論 として集合論 を受け入れる形で理論構成がなさ れている点に求め られ る。そのような背景集合論 として

,一

般 にはツェルメロとフレンケル による 集合論が前提 される。そ こでは

,矛

盾ないし悪循環 を避けるために

:す

でに手元 にある集合か ら一 歩一歩新 しい集合 を作 ってい く, という仕方で集合の階層構造が導入 され る。すなわち

,順

序数上 の帰納法によって

,空

集合か ら出発 して

,階

層の下のレベルの集合の中集合 を構成することによ り, つぎの レベルの集合が作 られる:

V(0)=〃

;

V(n+1)='V(n)。

さ らに

,V(ω )=V(0)∪

V(1)∪

…

_=∪

i≧

OV(1)と

し

,続

けて

,V(ω +1)='V

(ω

)と

す る。 一般 に

,後

者 で あ るよ うな (β

=α

+1)任

意 の順序数 βに対 して,

V(β

)=,V(α

) と言う仕方で高次の集合を作 り

,す

べての極限順序数λに対 して,

V(λ

)=∪

_α〈λ

V(α

) とする。 この集合の構成過程は終わることなく続き

,す

べての順序数の集合Ωによって

,集

合の全 宇宙

Vは

,

V=∪

β∈Ω

V(β

) と表せることになる。 こうして

,空

集合か ら出発 して

,(1)後

者 レベルでは

,先

行す る集合の可 能なすべての部分集合 の集合 を新 しい集合 と認め

,(

)極

限 レベルでは

,す

でに存在 しているす べての集合を一つの新 しい集合 として合併する, という仕方でわれわれは集合の宇宙 を構成す る。 これが

,ッ

ェルメロとフレンケル による集合論の集合構成 の大雑把な描写である。 この集合論その ものは

,第

一階の論理 をベースにした第一階の理論 として構成 されるが

,経

験上

,数

学の広範囲の 理論が この集合論 によって記述 されることが認め られている。われわれの論理体系である第二階論 理は第二階言語 によ り記述 されるが

,わ

れわれの論理の強 さは

,

このよ うな

,広

範囲の数学的宇宙

(=集

合

)を

背景 とす ることに由来 している。 ところで

,す

でに見てきたように

,わ

れわれの第二階論理 を記述す る形式言語は, このような数 学的宇宙か ら成 る構造 の中で解釈 されることによ り

,意

味を得た。各構造が

,そ

れ 自身の限定され

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

3巻

第

1号 (2001) 149

￨

た量化 の宇宙 を持つ とき

,そ

の宇宙 を領域

(domain)と

呼ぶ ことにする。以後

,構

造 の領域 に関

1

連する特性の定義 を与え

,特

性の具体例 を通 して

,第

二階論理

(SOL)の

表現力を考察する。

1 4.1

特 性 の表現 可能 性

4.1.1

まず

,領

_{域の公理化可能な特性 を定義す る。個体領域 の特性}

_Pが

_{公理化可能である} (axiomatizable)の は

_,つ

_{ぎの場合である :純 粋}

SOLの

_{文の帰納的集合} 「 が存在 して, (∀ノ

)[ノ

F― 「 ←⇒

Aが

特性

Pを

持つ]。 また

,個

体領域の特性

Pが

有限 に公理化可能である (inittly axiomatizable)のは

,つ

ぎの場合 である :純粋

SOLの

文 φが存在 して, (∀ノ

)[ノ

ト Φ←⇒

Aが

特性

Pを

持つ]。

4.1.2

つぎに

,広

域関係 を定義す る。(特定 された

)数

学的宇宙の広域

n項

関係

Rが

第一階 でかつ広域的 に定義可能である (globally definable)の は

_,つ

ざの場合である

:FREE(φ

)

⊆ lxl,¨ 。

,xn)で

あるよ うな

SOLの

式 φが存在 して, (∀ノ

)[((xl,

・・・

,xn):ノ

[Xl・・・ xl…

xn]SAT

φ

)=R∩

An]。 λ―

SOLの

_{言語では, この条件は}

_,ン

_{(λ xl… xn φ}

_)=R∩

_Anと

_{表現 され る。 また}

_,数

_学的宇 宙の広域

n項

関係

Rが

_{第二階であ りかつ広域的に定義可能であるのは}

_,つ

_{ぎの場合である :各 タイ} プが 11,…・,inであ る変項vl,中●_,■/11に_{対 して}

FREE(φ

_)⊆

_{(vl,…・,Vll}であ るよ うな}

SO

Lの

式 φが存在 して, (∀ノ

)[{(vl,…

,,端

_)∈

_{A札 ×…・×A in:ノ} [ ・・・Ⅶ

vl...Vn]SAT

_φ

}=R∩

(A ll×… ×A in)]o

4.1.3

さ らに

,構

造 の ク ラスが文 (のク ラス

)に

よ って表現で きる, とい う ことを表す公理 化 可能 ク ラス の概 念 を定義す る。構造 の ク ラス

Kが

公 理化 可能であ る (axiomztizable)の は

,つ

ぎの場合 である

ISOLの

文 の帰納 的集合 「 が存在 して, (∀ノ

)[ノ

∈

K

←⇒ _ノト 「 ]。 また

,構

造のクラス

Kが

有限に公理化可能である (anitely axiOmatizable)のは

,つ

ぎの場合で ある

:SOLの

文 φが存在 して, (∀ン

)[ン

∈

K

←⇒ _{ン ト φ}]。

4.1.4

与え られた構造

Bが

構造ン に対 して範疇的に公理化可能である (categorically axiomttizable)の_は

_,つ

_{ぎの場合である 「文 の帰納的集合} 「 が存在 して, [ノト 「 ←⇒

B隻

ノ]。 与え られた構造

Bが

構造ン に対 して範疇的に有限 に公理化可能であるのは

,つ

ぎの場合である :文 φが存在 して, [ントφ ←⇒ Btt A]。

4.1.5

数学的宇宙の特性

Pが

公理化可能であるのは

,つ

ぎの場合である :純 粋

SOLの

文 φ が存在 して, [卜φ ←⇒

Pが

数学的宇宙で成 り立つ]。

4.2

これか ら

,表

現可能な特性の具体例 を考察する。

1 4.2.1

_{無限公理 (axioms of infinity)} 「はじめに」 において見たように

,有

限性 と無限性 という領域の特性は第二階言語で公理化可能 である。事実

,無

限公理 として用 い られ る多 くの第二階の式が存在する。例えば

,式

(φ

ino:

田畑博敏:第二階論理 の特性 について

ヨ

X[∀

xyZ(XXyA Xyz⇒

Xxz)∧

∀

x司 Xxx∧

∀xヨ

y Xxy]

は

,そ

の領域 を全宇宙 とす るような

,反

反射的・推移的・連続的関係が存在す る, と主張するが, これは実際上

,無

限領域で

,か

つそのような領域でのみ成 り立つので

,無

限公理 と見 な しうる°つ。 第一階の公理の中には

,一

つの構造 において真 となるために

,個

体 の無限領域 を要求す るような 式が存在する。 しか し

,そ

れ らの公理は

,構

造がある特別 の記号系か ら成ることを要求 し

,い

くつ かの無限構造では成 り立たないものである。 よって

,無

限公理 とは, (∀ノ

)[ノ

トφ←⇒ンの個体宇宙

Aが

無限である] が成 り立つよ うな

,純

粋

SOLの

式 φの ことである。 しか し

,第

一階の式で無限公理 と見 な して よいものが存在す るよ うに思われ るか も しれ な い。 例 えば

,第

一階の式で表現 しうる初密全順 序

(dense order:異

なる二要素間 に必ず第二 の要素が存在す るよ うな全順序

)の

諸公理 の連言 を α DOとすると

,構

造ンが α DOのモデルな らば

,確

かにンの個体宇宙

Aは

無限である。 しか し

,逆

は成 り立たない。実際

,構

造

(N,≦ )は

無限である (個体宇宙

Nは

自然数の集合だか ら

)が

初密 全順序ではない。 また算術の公理の集合 : ∀

x(Sx≠

0) ∀

x∀

y(Sx=Sy→

x=y)

∀

y(y≠

0→

ヨ

z(Sz=y))

(ゼロは どんな数 の後 者で もな い) (後者 関数 は一対 ― で あ る) (ゼロでない数 は前者 を持 つ) も無限性 の公理化 で はない。 なぜ な ら, これ らの公理 を真 とす るには無限構造 が必 要 で ある9°が, 無 限構造 のす べて の関数 が これ らの公理 に従 う必 要 は な いか らだ。 例 えば

,構

造

(N, 0, I)

(ここでIは同一性 関数

:I(x)=x)に

お いて

,関

数

Sを

同一性 関数Iで解 釈 す れば

,

これ ら の公理がすべて真 とな る訳ではな い (第一 の公理が偽 とな る°°)。 こう して

,わ

れ われ は

,第

一 階論理 にお いて は

,領

域 の有 限性 も無限性 も一 つ の式 で表 現 す る こ とはで きな い, とい うことが分 か る。

4.2.2

同一性 (ldentity) 「は じめに」 にお いて も見 たよ うに

,個

体 間の 同一性 は ライ プニ ッツ に由来す る不 可 識 別 者 同一 原 理 によ って

,第

二 階論理で表現 しうる。す なわち

,二

つ の個体

xと yに

つ いて

,そ

れ らを区別す る性質がな い

,す

なわ ち

(#)

∀

X(Xx←

→

Xy)

とい う場合

,か

つそ の場合 にか ざ り

,同

一 で ある: (井

#) Vx∀ y[x=y←

→ ∀

X(Xx←

→Xy)]。 同一性 は

,最

小 の反射的関係で あるか ら

, xと

yが

す べて の反射的関係 にある ことを表 す 式 : ∀

z2 (vz z2z z→

z2xy)

によって も表現 され る。 なぜ

,第

一 階論理では同一性 を原始 的関係 とみなす のか

?そ

の理 由は

,同

一性 を定義 しうる第 一 階 の式 が存在 しな い ことによ る。考 察 の対 象 で あ る第 一 階言 語 が有 限個 の関係定項 しか持 たな い と き

,同

一性 を模倣す る式 を作 る ことがで きる。例 えば

,唯

― の1項関係定項 が

Rで

,唯

― の

2項

関 係 定項 が

Tで

あ るよ うな言語 を取 る。そ の とき

,式

:

(★

)(Rx←

→

Ry)∧

∀

z(Txz←

→

Tyz)∧

∀

z(Tzx←

→

Tzy)

は

, xと yが

われ われ の形式言語で 区別で きな い, とい うことを主張 して いる。 この式 (★

)を

H

xyと

す る と

,Hは

反 射的かつ対 称 的かつ推移 的で ある。 しか し

,こ

の定義は完全で はな い。実 際,