モデル理論とその周辺

モ デ ル 理 論 とそ の 周 辺

坪 井 明 人(筑

波 大 学 数 理 物 質 科 学 研 究 科)

モ デル 理論 は,数 理論 理 学 あ るい は数 学 基礎 論 とよばれ る分野 のな か

の一 つ で あ る.大

ざっぱ に言 えば,数

学 的構 造 の一 般論 で あ る.興 味 を

持 って い る数 学 的構 造 を直接 に研 究せ ず,そ

の構 造 の 間接 的 な性 質 に注

目 して議 論 をす る こ とは,数 学 の研 究 上 で は頻繁 に あ る こ とだ が,モ

デ

ル 理論 で はそれ が主 要 な方法 論 とな る.

本 稿 で はモデ ル 理論 全 体 を概 観す る こ とは諦 めて,む

しろ基本 的 な定

理や モ デル 理論 にお い て特徴 的 な議 論 を ご くや さ しい例 を用 い て紹 介 す

る こ とを 目指す.

モ デル 理論 を理解 す る上 で重 要 な概 念 は 「

言 語 」 の概念 で あ る.

・ 定数記 号,関

数記 号,述 語 記 号 か らな る一 つ の集 合 を言語 とよぶ.

例 え ば実数 体Rの

言語 は{0,1,＋,−,・}で あ り,順 序 体 として のRの

言 語

は{0,1,＋,−,・,＜}と な る.与 え られ た構造 で,ど の言語 に注 目 してい る

か を表 す た めに,(R,0,1,＋,−,・),(R,0,1,＋,−,・,＜)な

どとか く.

Lを 言語 とす る.Lを

使 って表 され る形 式 的命 題 が論 理式 で あ る.例 え

ばLが

群 の言語{e,*・*,*−1}の

場合,記

号列 ∀x∀y(x・y＝y・x)は

論 理

式 で あ り,群 が可換 で あ る こ とを主 張す る.∀x∃y(x＝y・y)も

論 理 式 で

あ る.量 化記 号 ∀(全 称 記 号)や

∃(存 在 記号)の 解 釈 は これ らの例 にお

い て,そ れ ぞれ 「

すべ て の元 につ い て」,「あ る元 につ い て」 とな る.論

理 式 を作 る際 に,「す べ ての部 分集 合 につ い て」 あ るい は 「

あ る部 分集 合

につ い て」 の よ うな集 合 に関す る量化 記 号 を許 さない 場合,特

に1階 論

理 式 とよばれ る.本 稿 で は論 理 式 とい え ば,も

っぱ ら1階 論 理式 の こ と

で あ る.論 理 式 ∃y(x＝y＋y)に

お いて,xは

代 入 が可 能 な変数 で 自由変

数 とよばれ る.論 理 式ψ が 自由変 数xを 持 つ とき,ψ(x)と

か く場合 が あ

る.自

由変 数 を持 た ない論理 式 を閉論 理 式 とい う.

数 学 的構 造Mに

お いて,そ の言 語 がLの 場合 にL-構 造 とよぶ.論 理 式

ψがM成

立す る とき,M￨＝

ψ とか く.Tが

論理 式 の集 合 の とき,M￨＝T

はTに

属す るす べ て の ψ に対 して,M￨＝ψ

とな る こ とで あ る.M￨＝T

の とき,MはTの

モデル で あ る とい う.「物 理現 象 の数学 的モ デル 」 とい

う場合 の使 い方 とは多少 異 な る.本 稿 の場合,モ

デル は 「

具 体例 」 とい

う感 覚 が近 い か も しれ な い.

例11.(適

当 な言語 の も とで)群

の公 理7環

の公 理,体

の公 理,順

序 の公 理 な どは論 理式 の有 限集 合 で表現 す るこ とが で きる.ま た体

K上

のベ ク トル 空 間 の公理 も論 理 式 の集合 で表現 で きる.

2.無 限体K上

のベ ク トル 空 間 の次 元 を論 理 式 で表 現す る こ とはで き

ない.

3.Tgpを

群 の公 理 とす る とき,G￨＝Tgpと

は単 にGが

群 であ る こ とを

意 味 す る.

言 語Lを

持 つ 二 つ の数 学 的構 造MとNが

同型 の と きM≒Nと

か く.

また任 意 のLの

論理 式 ψ に対 して,M￨＝

ψ ⇔N￨＝ψ

とな る とき,

M≡Nと

か く.Mで

成 立す る論理 式全体 をTh(M)と

か く.N￨＝Th(M)

な らばM≡Nで

あ る.M≒Nな

らば必ずM≡Nで

あるが,逆

は一 般

に は成 立 しない.

例2 

1.な

ので,

した が って

もわ か る.(注 意:

一般 に有 限構 造 に対 して は

,≡

と≒ は同等 で あ る.)

2.(Q,＜)≡(R,＜)で

あ るが,濃 度 が違 うの で(Q,＜)弊(R,＜).

3.Q≡Q(π)で,と

もに可 算 で あ るが,次 元 が違 うの でQ≠Q(π).

モ デル 理 論 で は あ る公 理 を満 た す構 造 が 同型 を除い て どの くらい あ るか

に興 味 を持 つ場 合 が 多い.特

に,2あ

るい は3に 代 表 され る よ うに,論

理 式 で は区別 され ないが,同

型 で ない構 造 に興 味 が あ る.

1  コ ンパ ク ト性 定 理

コ ンパ ク ト性 定理 な く しては,モ

デル 理 論 を語 る こ とはで き ない.コ

ンパ ク ト性 定理 は,論 理 式 の集 合 に よ る表 現能 力 が 大 き くな い こ とを あ

る 意 味 で 主 張 す る が,同 時 に そ れ を 逆 手 に と っ て 議 論 を す る こ と で 大 き な 収 穫 が あ る こ と を 示 唆 す る. 以 下 に お い て,Tは 言 語Lの 論 理 式 か ら な る 集 合 と す る. 定 理3(コ ン パ ク ト性 定 理)以 下 は 同 値 で あ る: 1.Tの モ デ ル が 存 在 す る. 2.Tの 各 有 限 部 分 集 合T0に は モ デ ル が 存 在 す る. 証 明 に は,完 全 性 定 理 を 利 用 す る 方 法 と,超 積 を 利 用 す る よ り 直 接 的 な 方 法 が あ る が,い ず れ も 準 備 を 必 要 とす る の で,こ こ で は 述 べ られ な い. 系4(Lowenheim-Skolem-Tarskiの 定 理)Mを 無 限 構 造 とす る.こ の と き,任 意 の 無 限 基 数 κ ≧￨L￨に 対 し て,濃 度 κの 構 造NでM≡Nと な る も の が 存 在 す る. (証 明 の 概 略)T＝Th(M)と す る.κ 個 の 定 数 記 号c0,c1,…,ci,… を 用 意 し て, とす る.T*の 各 有 限 部 分 はciた ち をMの 中 の 適 当 な 元 と し て 解 釈 す る こ と に よ り,Mが モ デ ル と な る.し た が っ て,コ ン パ ク ト性 に よ りT*全 体 が モ デ ルM*を 持 つ.M*の 濃 度 は κ 以 上 で あ る.ま たM*￨＝Tな の でM*≡Mも 成 立 す る.M*の 中 のc0,c1,…,ci,… た ち に 関 係 す る 部 分 だ け を 集 め てNを 作 れ ば,￨N￨＝ κ と な り,要 求 さ れ る 性 質 を 持 つ. 例5 TRをR上 の ベ ク トル 空 間 の 公 理 とす る.V,WをTRの 任 意 の モ デ ル とす る.こ の と き,V≡Wと な る こ と を 示 そ う.κ を 連 続 濃 度￨R￨よ り 大 き な 基 数 と す る.Lowenheim-Skolem-Tarskiの 定 理 に よ り,濃 度 κの ベ ク トル 空 間V*お よ びW*で _, V*≡V,W*≡W と な る も の が 存 在 す る.dimV*＝dimW*＝ κ で あ る.ベ ク トル 空 間 は 次 元 よ っ て 決 定 され る の で,'V*≒W*.特 にV*≡W*も 成 立 す る.≡ の 推 移 性 に よ り,V≡Wを 得 る.こ の こ と か ら 次 の 二 つ が わ か る. 1.R上 ベ ク トル 空 間 の 公 理 賑 は 完 全 で あ る.す な わ ち,任 意 の 論 理 式 の 真 偽 は 職 か ら決 定 で き る.

2「 次 元 」 と い う概 念 は 論 理 式 の 集 合 で は 記 述 で き な い 概 念 で あ る. Lowenheim-Skolem-Tarskiの 定 理 に よ り,公 理Tが 完 全 で あ っ て も(無 限 モ デ ル を 持 つ 場 合 は)そ の モ デ ル は 各 濃 度 に 存 在 し て,一 つ に 定 ま ら な い.ま た,上 の ベ ク トル 空 間 の 例 で も わ か る よ う に,例 えTが 完 全 で 濃 度 が 与 え ら れ て も,そ の 濃 度 の モ デ ル は 複 数 存 在 す る 可 能 性 が あ る. 定 義6Tを 完 全 と す る.κ を 無 限 基 数 と す る. 1.I(κ,T)＝ 濃 度 κ のTの モ デ ル の 個 数; 2.Tが κ-範疇 的 ⇔I(κ,T)＝1. こ の 定 義 を 用 い る と,TRは κ ＞2N0に お い て κ-範疇 的 で あ り,I(2N0,TR)＝ 2N0と な る.TRの 言 語 は 非 可 算 で あ る が,言 語 が 可 算 の 場 合 も 重 要 で,特 に そ の 場 合 のN0-範 疇 性,N1-範 疇 性 は 重 要 で あ る.い く つ か の 例 を あ げ る. 例7  1.ACFpを 標 数pの 代 数 閉 体 の 公 理 とす る.ベ ク トル 空 間 の 場 合 と 同 様 に,次 元 に よ っ て 構 造 が 決 定 され る こ と を 用 い る と,ACFp はN1-範 疇 的 で,可 算 モ デ ル の 個 数 はN0と な る こ と が わ か る. 2.Tを 稠 密 全 順 序 の 公 理 に 最 大 最 小 が 存 在 し な い こ と を 付 け 足 し た 公 理 とす る(例 え ばQ＝(Q,＜)は 一 つ の モ デ ル で あ る).こ の と き, Tは 完 全 で,N0-範 疇 的 で あ る がN1-範 疇 的 で な い. 3.ラ ン ダ ム グ ラ フ の 公 理TRGもN0-範 疇 的 で あ る がN1-範 疇 的 で な い. 4.空(＝ だ け を 持 つ)言 語 に お い て,無 限 集 合 の 公 理(元 が 無 限 個 あ る こ と を 主 張 す る 論 理 式 の 集 合)はN0-範 疇 的 か つN1-範 疇 的 で あ る. ま たpを 素 数 と し て,Z/pnZの 無 限 直 和 をGと す る.T＝Th(G) はN0-範 疇 的 で な お か つN1-範 疇 的 で あ る. 5.実 閉 体 の 公 理ROOFは,N0で もN1で も範 疇 的 で な い.実 際 モ デ ル は 非 常 に 多 く存 在 す る.例 え ば,I(N0,RCOF)＝2N0で あ る. 可 算 モ デ ル の 個 数 に 関 し て は,次 の 有 名 な 未 解 決 問 題 が あ る. [Vaught予 想]1＜I(N0,T)⇒I(N0,T)＝2N0.

[Lachlan予 想]1＜1(No,T)＜N0な ら ばTの 適 当 な モ デ ル の 中 に 順 序 構 造 が あ る.す な わ ちM￨＝Tと 論 理 式 ψ(x,y)お よ びMの 有 限 列 の 無 限 列ai(i＝0,1,…)を 適 当 に 選 べ ば, が 成 立 す る. 定 義8MをL-構 造 とす る.A⊂Mnが 論 理 式 ψ(x1,...,xn)で 定 義 可 能 で あ る と は, と か け る こ と で あ る.適 当 な ψ に よ っ てAが 定 義 可 能 と な る と き,単 に 定 義 可 能 で あ る と い う. 有 限 個 の 定 義 可 能 集 合 の ブ ー ル 結 合 は 再 び 定 義 可 能 集 合 と な る.ま た,定 義 可 能 集 合 は 構 造Mの 自 己 同 型 に 対 し て(集 合 と し て)動 か な い. 例9  1.体 に お け るZariski閉 集 合 は,方 程 式 と い う特 殊 な 形 の 論 理 式 た ち に よ る 定 義 可 能 集 合 と 思 え る. 2.順 序 体 に お け るsemi-algebraic setは 方 程 式 と 不 等 式 と い う特 殊 な 形 の 論 理 式 た ち に よ り得 ら れ る 定 義 可 能 集 合 と 思 え る. 例10整 数 の な す 群(Z,0,＋,−)に お い て 偶 数 全 体 は ∃y[x＝y＋y]で 定 義 可 能.し か しZに お い てS(x)＝x＋1な る 関 数Sだ け を 言 語 と し て 考 え た 構 造(Z,0,S)に お い て は,偶 数 全 体 は 定 義 可 能 と な ら な い:コ ン パ ク ト性 に よ り(M,0,S)≡(Z,0,S)で 濃 度 がN1の モ デ ル が 存 在 す る.も し偶 数 全 体 が 論 理 式 ψ(x)で 定 義 さ れ れ ば,ψ(x)はMに お い て も 何 ら か の 集 合Xを 定 義 し て い る.ま たXはx∈X⇒S(x)≠Xな る 性 質 を 持 つ.し か し,0の 属 す るMの コ ン ポ ー ネ ン ト上 で は 恒 等 写 像,残 り のM の コ ン ポ ー ネ ン ト上 で は 一 つ 左 に 移 動 させ る 写 像(す な わ ちS)はMの 自 己 同 型 に な っ て い る.こ れ は 矛 盾 で あ る.

2 

構 造 の 拡 大

L-構 造Mの

拡 大 を考 え る.Z⊂Qは

環言 語L＝{0,1,＋,−,・}に

お け

る構 造 の拡 大 に な ってい るが,こ

こでは も う少 し強 い意 味で の拡 大 を考

え る.拡 大M⊂Nが.M＜N(elementary extension)で あ る と は,任 意 の 論 理 式 ψ(x1,..,xn)と 元a1,…,an∈Mに 対 し て, が 成 立 す る こ と で あ る. 例11 自 然 数 全 体 の 構 造N＝(N,0,1,＋,・,＜)に お い て,無 限 個 の 論 理 式 の 集 合 を 考 え る.p(x)か ら 有 限 個 の 論 理 式 を 任 意 に 選 ん だ と き,そ れ ら の 共 通 解 はNに 存 在 す る.一 般 に 論 理 式 の 集 合 の 任 意 有 限 部 分 集 合 が 共 通 解 を 持 つ と き,そ の 集 合 を タ イ プ と い う.上 のp(x)はNに お け る タ イ プ で あ る. Mに お け る タ イ プp(x)は 解 をM内 に 持 つ と は 限 ら な い.実 際 上 の 例 のp(x)＝{x＞0,x＞1,x＞2,....}の 共 通 解 はMに 存 在 し な い.し か し, コ ン パ ク ト性 定 理 を 用 い る とMを 拡 大 し たL-構 造N＞Mの 中 でp(x) の 解 を 与 え る こ と が で き る. 例12 Qの 代 数 閉 包Qに お い て, は タ イ プ に な る(p(x)は 点xが 超 越 元 に な る こ と を 主 張 し て い る).し か し解 はQに 存 在 し な い.C＞Qに お い てpは(連 続 濃 度 だ け)解 を 持 つ. (あ る 範 囲 の)タ イ プ が 必 ず 解 を 持 つ 構 造 を 飽 和 構 造 と よ ぶ.任 意 の(無 限)構 造 は 飽 和 構 造 に 拡 大 で き る.代 数 閉 体Cは 飽 和 構 造 の 例 で あ る.一 方 実 閉 体Rは 飽 和 構 造 で は な い.Rを 飽 和 構 造R*＞Rに 拡 大 す る と,そ こ に は 無 限 小,無 限 大 の 元 を 持 つ よ う に な る.こ れ ら を 利 用 して 解 析 を 行 う の が 超 準 解 析 で あ る. 例13 R＝(R,0,1,＋,−,・,f,...)を 考 え る.た だ しfはR→Rな る 関 数 で あ る.R*＞Rを 飽 和 拡 大 とす る.こ の と き 次 は 同 値 で あ る. 1.fは 連 続 関 数 で あ る. 2.任 意 のa∈Rと 任 意 の α ∈R*に 対 し て, が 成 立 す る.た だ し,a≒ α は 任 意 の 正 の 実 数rに 対 して,￨a-α￨＜r が 成 立 す る こ と を 意 味 す る.

(2で 任 意 のa,α ∈R*に 対 し てa≒ α ⇒f(a)≒f(α)を 仮 定 す る と,一 様 連 続 性 と 同 値 に な る.) 飽 和 構 造 は 大 き な 構 造 で あ り,多 く の タ イ プ の 解 を 持 っ て い る.タ イ プ の 解 が な る べ く 存 在 し な い よ う に す る た め に は 次 の 定 理 が 基 本 的 で あ る. 定 理14Mを 可 算 言 語 の 構 造 と し,p(x)をMに お け る タ イ プ とす る.い まp(x)が 一 つ の 論 理 式 で 生 成 さ れ な け れ ば,p(x)の 解 を 持 た な い モ デ ル N≡Mが 存 在 す る. 例15  1.Cに お い て,p(x)＝{xは 超 越 数}は タ イ プ で あ る が,超 越 数 で あ る こ と は,一 つ の 論 理 式 で は 書 き き れ な い.し た が っ て,p(x)の 解 を 持 た な い モ デ ル が 存 在 す る は ず.Qが ま さ に そ の モ デ ル で あ る. 2M＝(Q,＜,0,1/2,2/3,3/4,…)を 考 え る.p(x)＝{0＜x,1/2＜x,2/3＜ x,3/4＜x,…}は タ イ プ で あ る が,一 つ の 論 理 式 で は 表 現 で き な い. し た が っ て,p(x)を 排 除 す る モ デ ル が 存 在 す る.M'＝((-∞,1),＜ ,0,1/2,2/3,3/4,…)がそ の よ うな モ デ ル で あ る.実 はM"＝(Q＼{1},,＜ ,0,1/2,2/3,3/4,…)もM"≡Mと な り,Mと ≡ と な る 可 算 モ デ ル は,実 は 上 のM,M',M"の い ず れ か と 同 等 と な る.

3  量 化記号 消去

こ こでは技術 上 の問題 か らLは 少 な くとも一つ の定数 記号 を持つ とす る.

定義16公

理 の集 合Tが

量化 記 号 の消 去 を許す とは,Tの

も とで,任

意

の論 理式 ψ(x)が,量

化記 号 のな い あ る論 理 式 ψ(x)と 同 等 に な る こ とで

あ る.す

なわ ち任 意 のM￨＝Tに

対 して,

例17論 理 式 ψ(x,y)がA⊂Mn×Mを 定 義 し て い る と す る.こ の と き, ∃yψ(x,y)はAのMnへ の 射 影proj(A)⊂Mnを 定 義 す る.こ の こ と か ら, 次 が わ か る: Tが 量 化 記 号 の 消 去 を 許 す とす る.Dを,Mに お い て,量 化 記 号 の な い 論 理 式 で 定 義 可 能 な 集 合 の 全 体 と す る.こ の と き,の は ブ ー ル 結 合 と 射 影 で 閉 じ て い る.

例18量 化 記 号 の 消 去 を 考 え る と き,何 を 言 語 と し て 考 え て い る か は 重 要 で あ る.実 際,言 語 を 拡 大 す れ ば,任 意 のTは 量 化 記 号 を 許 す よ う に で き る.言 語 を(あ ま り)拡 大 し な い で 量 化 記 号 の 消 去 が で き る 場 合 が 重 要 と な る. 1.ACFpは 言 語{0,1,＋,−,・}で 量 化 記 号 の 消 去 を 許 す.こ の こ と か ら, 代 数 体 に お い て,構 成 可 能 集 合 は プ ー ル 結 合 と射 影 で 閉 じ て い る. 2.ROOFは 言 語{0,1,＋,−,・,＜}で 量 化 記 号 の 消 去 を 許 す.し た が っ て,実 数 体 に お い て,semi-algebraic setた ち は ブ ー ル 結 合 と射 影 で 閉 じ て い る(Tarski-Seidenberg). 全 順 序 構 造 を 含 む 構 造M＝(M,＜,…)が 順 序 極 小(o-minimal)で あ る と は,一 次 元 定 義 可 能 集 合 が,有 限 個 の 区 間(a,b)(a,b∈M∪{± ∞})と 有 限 個 の 点 と の 和 と し て 表 現 で き る こ と で あ る.R＝(R,0,1,＋,−,・,＜) に お い て,量 化 記 号 の 消 去 を 許 す こ と か ら,Rは(o-minimalで あ る こ と が わ か る.Rの 具 体 的 な 性 質 を 用 い な く て も,o-minimalと い う こ と か ら,多 く の 重 要 な 性 質 を 導 く こ と が で き る.例 え ば,cell decomposition theoremは 一 般 にo-minimalの 仮 定 だ け か ら 導 か れ る. 例19Rに 指 数 関 数expを 言 語 と し て 加 え た 構 造 もo-minimalに な る こ と が 知 られ て い る.Rに 三 角 関 数sinを 加 え る と,sin(x)＝0と い う論 理 式 で 定 義 され る 一 次 元 の 定 義 可 能 集 合 は,無 限 個 の 孤 立 点 か ら な る の で, o-minimalで な く な る.し か し,解 析 関 数 を 有 限 区 間 に 制 限 した も の を 言 語 に 加 え て も,o-minimal性 が 保 存 さ れ る こ と が 知 られ て い る.

4 N0-範

疇 性 と ジ エ ネ リ ック 構 造

丁 の可算 無 限モ デル が 唯一 つ存在 す る ときが,N0-範

疇 的 で あった.有

限体F上

の無 限次元ベ ク トル空 間 の公 理 な どはN0-範 疇 的 で ある.も

う一

つ重 要 な例 と して(す

で に述 べ た が)ラ

ンダム グ ラ フの公理TRGが

あ っ

た.こ

れ につ いて復 習 す る.

定義20言

語 を2項 述 語Rだ

けか らな る とす る.Rが

対象 性 と非反 射 性

を満 たす 構 造Gを

グ ラフ とい う(R(a,b)な

る2点a,bは

線 で結 ばれ てい

る と思 う.ま た,自 分か ら自分 自身へ の線 は ない として い る).Gが

次 の

性 質

を満 たす とき ランダ ム グ ラフ とよぶ.ま

た上 の性 質(論

理 式)全

体 の集

合 をTRGと

か く.

ランダム グ ラフ(TRGの

モ デル)は 存 在す る.実 際,必 要 な点zを 可 算 回

繰 り返 し付 け加 えて ゆ けば 目的 のモ デル を得 る.さ

らに往 復論 法 と呼 ば

れ る論法 を用 い る と,TRGの

可算 モ デル はす べ て 同型 に な る こ とが わ か

る(す なわ ちN0-範 疇 的 に な る).こ

の ランダ ム グラ フはモ デル論 的 な ラ

ンダム グラフで あ るが,確 率論 的 なラ ンダム グラ フ とい う概念 もあ る.そ

れ は,n個

の点 か らな る集合Mn＝{1,…,n}の

異 な る2点

に対 して,(一

定 の)確 率pで 辺 を与 え る こ とに対 応 す る.こ の とき,グ

ラ フの言 語 で

書 かれ た論理 式 ψに対 して,

Mn￨＝ ψ あ るい はMn￨＝￢

ψ

が:確率 的 に決 定 す る.論 理 式 ψ に よ らず,

が 必 ず0か1に な る こ とが 知 られ て い る(zero-one law).確 率1に な る 論 理 式 の 集 合 がTRGか ら論 理 的 帰 結 と して 得 られ る 論 理 式 全 体 と一 致 す る. 上 の 場 合 はnに よ らず 辺 確 率 が 一 定 で あ っ た が,Mnに お け る 辺 確 率 が pn＝n-α(α は0＜ α ＜1な る 無 理 数)の 場 合 も 興 味 が あ る.こ の 場 合 は,Hrushovskiの 開 発 し た ジ ェ ネ リ ッ ク 構 造 と呼 ば れ る 無 限 構 造 と 密 接 な 関 係 が あ る こ と が 知 ら れ て い る(Shelah-Spencer, Baldwin-Shelah). 定 義21有 限 グ ラ フGに 対 し て,次 元 δ を δ(G)＝ 点 の 個 数 − α ・辺 の 個 数 で 定 め る.そ の 部 分 グ ラ フ が 必 ず δ ≧0を 満 た す 有 限 グ ラ フG全 体 の ク ラ ス をKα とす る.Kα 全 体 を 張 り合 わ せ て で き る 構 造G*をKα-ジ ェ ネ リ ッ ク 構 造 と よ ぶ. こ の と き,G*はN0-範 疇 的 で は な い が,ラ ン ダ ム グ ラ フ と似 た 性 質 を 持 ち,limn→ ∞Pr(Mn￨＝ ψ)＝1と な る ψ 全 体 はG*で 成 立 す る 論 理 式 全 体 と 一 致 す る.し た が っ て,こ の 場 合 もzero−one lawが 成 立 す る.

参考文献

[1] Chen Chang Chang and H. Jerome Keisler, "Model Theory" (Studies

in Logic and the Foundations of Mathematics), North-Holland; 3rd

edition (1990).

[2] Lou Van Den Dries, "Tame Topology and O-Minimal Structures"

(London Mathematical Society Lecture Note Series), Cambridge

Uni-versity Press (1998).

[3] Leonid Libkin, "Elements Of Finite Model Theory" ( Texts in

Theo-retical Computer Science. An EATCS Series), Springer (2004).

[4] Saharon Shelah, "Classification Theory and the Number of

Non-Isomorphic Models" (Studies in Logic and the Foundations of

Math-ematics), North-Holland; 2nd revised (1990).

[5] 田 中 一 之(編),ゲ ー デ ル と20世 紀 の 論 理 学(ロ ジ ッ ク)〈2〉 完 全 性 定 理 と モ デ ル 理 論,東 京 大 学 出 版 会(2006).