Indiscernible Secuence
1 Order Indiscernible
1.1 Ramsey’s theorem and Indiscernible
モデル理論を勉強するうえで一様列 (indiscernible sequence) の知識が必要になると感じたので自分なりに
まとめた. 随時加筆予定.
definition 1.1.1. (indescernible sequence)
M を L-structure, (J, <) を無限順序集合, I = {ai }i∈J を M の元の列とする.このとき I が M の一様
列 (indiscernible sequence) とは,
M |= φ(ai0 , . . . , ain ) ⇔ M |= φ(aj0 , . . . , ajn )
が成り立つこと.ここで ai0 , . . . , ain と aj0 , . . . , ajn は I の有限部分列, φ は勝手な L(M)-f ml とする.
つ ま り 一 様 列 は 一 階 の 論 理 式 で は 区 別 を つ け る こ と が 不 可 能 な 列 と い う こ と で あ る .今 勝 手
な L-structureM を と っ て く る と Ramsey ′ s theorem に よ り 必 ず 一 様 列 を と る こ と が 出 来 る.こ れ を
説明する.
theorem 1.1.2. (Ramsey’s theorem)
I を無限集合, n ∈ ω とする.また [I]n = A0 ∪ A1 とする.このときある無限集合 J ⊂ I があって [J]n ⊂ A0
か [J]n ⊂ A1 が成り立つ.
proof
簡易のため I を可算無限集合とする.I を整列させて I = {ai }i<ω とおく.各 m ∈ ω について Fm = {i ∈
I | i > im } とおくと F = {Fm | m ∈ ω} は有限交差性を持つ.よってこれを I 上の ultraf ilter D に拡張する
.また F ⊂ D より D は有限集合を含まない.よって D は principal.各 r < n について An−r
, An−r
⊂ [I]n−r
0
1
を帰納的に次で定義する.
1) An0 = A0 , An1 = A1
n−(r+1)
2) A0
= {(y1 , . . . , yn−(r+1) ) | y1 < · · · < yn−(r+1) ,
∼D
∀
n−(r+1)
A1
i(yn−(r+1) < i かつ {y1 , . . . , yn−(r+1) , i} ∈ An−r
)}
0
= {(y1 , . . . , yn−(r+1) ) | y1 < · · · < yn−(r+1) ,
∼D
∀
i(yn−(r+1) < i かつ {y1 , . . . , yn−(r+1) , i} ∈ An−r
)}
1
∼D
ただしここで ∀ xφ(x) とは {x ∈ I | φ(x)} ∈ D のこととする.このとき以下が成り立つ.
Claim 1. 各 r ∈ ω について [I]n−r ⊂ A0n−r ∪ An−r
1
proof
帰納法による.r = 0 は ok.r = k − 1 までできたとせよ.勝手なy = (y1 , . . . , yn−k ) ∈ [I]n−k を y1 < · · · <
yn−k となるようにとる.yn−k < i となる i ∈ I を付け加えた (y, i) を考えるとこれは [I]n−k+1 の元なので, 帰
納法の仮定より (y, i) ∈ An−k+1
∪ An−k+1
.ultra f ilter は和集合で閉じているので結局
0
1
∼D
∀ i (yn−k < i かつ (y, i) ∈ An−k
∪ An−k
)
0
1
が成り立つ.以上よりy ∈ An−k
∪ A1n−k となる.2
0
Claim1 より最終的に I = A10 ∪ A11 となる.ここで I ∈ D であるので A10 ∈ D または A11 ∈ D となる
.A10 ∈ D と仮定してよい.j0 ∈ A10 を勝手に取ってきて無限上昇列を以下のように帰納的に構成する.jm まで構
成されたとして jm+1 を構成する..
与えられた勝手な r ∈ ω と勝手な {j0 , . . . , jm } の上昇列 y1 < · · · < yr に対して以下の集合 Xy1 ,...,yr を考え
ると
Xy1 ,...,yr = {i ∈ I | yr < i かつ {y1 , . . . , yr , i} ∈ Ar+1
}∈D
0
Xy1 ,...,yr は高々有限個しかないので有限交差性より Y =
り jm+1
∩
Xy1 ,...,yr も D に属する.D は non principal よ
> jm が Y か ら 選 べ る . こ れ を 繰 り 返 し て い く こ と に よ り 最 終 的 に 以 下 の 性 質 を 持
つ J = {j1 , . . . , jm , . . . } ⊂ I を作り出すことが出来る.
勝手な有限個の J の上昇列 y1 < · · · < ym をとってくると {y1 , . . . , ym } ∈ A0 .
A1 についても同じように考えると A10 ∈ D のときは [J]n ⊂ A0 , A11 ∈ D のときは [J]n ⊂ A1 となる無限集
合 J ⊂ I が取れるので証明が完了する.2
theorem 1.1.3. T を無限モデルを持つ L-theory.(I, <) を勝手な無限線形順序集合とする.このとき T のモ
デル M で (xi )i∈I を一様列として持つものが存在する.
proof
各 i ∈ I に対して new constants ci を用意して L′ = L ∪ {ci | i ∈ I} とおく.L-theory T について考えた
とき, 次の L′ -teory T ′ はモデル M を持つことを示す.
T ′ = T ∪ {ci ̸= cj | i ̸= j} ∪ {φ(ci1 , . . . , cim ) ↔ φ(cj1 , . . . , cjm ) | φ (v1 , . . . , vm ) : L-f ml,
m∈ ω, i1 < · · · < im , j1 < · · · < jm }
T ′ の最後の部分は {ci | i ∈ I} の解釈が I で添え字付けられた M の一様列になることを意味していることに
注意. T ′ の有限部分集合∆ ⊂fin T ′ がモデルを持つことを示せばよい.Ramsey ′ s theorem を使って以下を示す.
Claim 2.
各∆ ⊂fin T ′ についてある J∆ ⊂fin I が存在して, J∆ の勝手な無限上昇列 j1 < · · · < jn < . . . につい
て (M, jn )n∈ω を満たす.
proof
∆の sentences の数に関する帰納法で示す.ある有限集合∆ ⊂ T ′ まで成り立ったとせよ.L-sentence φ(v1 , . . . , vm ) を
勝手にとる.このとき [J∆ ]m は次で定義する A0 と A1 に分割される.(i.e.[J∆ ]n = A0 ∪ A1 ).
A0 ={(x1 , . . . , xm ) | x1 < · · · < xm , xj ∈ J∆ かつ M |= φ[x1 , . . . , xm ]}
A1 ={(x1 , . . . , xm ) | x1 < · · · < xm , xj ∈ J∆ かつ M |= ¬φ[x1 , . . . , xm ]}.
このとき ramsey ′ s theorem によりある無限集合 K ⊂ J∆ が存在して [K]m ⊂ A0 あるいは [K]m ⊂ A1 .
このとき K の勝手な無限上昇列 k1 < · · · < kn < . . . をとると明らかに (M, kn )n∈ω はφ(ct1 , . . . ctm ) ↔
φ(cs1 , . . . , csm ) をみたす.ここで s1 < · · · < sm , t1 < · · · < tm .結局∆ ∪ {φ} について, ある K ⊂fin I があっ
て K の勝手な無限上昇列 (ki )i∈ω について (M, kn )n∈ω が言えたので帰納法が完了する.2
参考文献
[1] Chang, Chen Chung; Keisler, H. Jerome (1990) [1973]. Model Theory. Studies in Logic and the
Foundations of Mathematics (3rd ed.).
[2] Marker, David (2002). Model Theory: An Introduction. Graduate Texts in Mathematics 217.
Springer.
[3] ゲーデルと 20 世紀の論理学３ 完全性定理とモデル理論.(2006) 田中一之編, 東京大学出版会.
© Copyright 2024 ExpyDoc
