数理論理学

October 11, 2002

1 形式の世界

数学で使う記号のうち，定数記号，関数記号，述語記号に注目する．これらからなる一つの集合を固定して，それを言語とよぶ．

Example 1 1. 群の言語とは集合 {e, ∗ · ∗, ∗^{−1}} のことである．ここで， e は単位元を表現するための定数記号， ∗ · ∗ は群の演算を表現するための２変数の関数記号， ∗^{−1} は逆元を対応させる操作に対応する関数記号である． (∗ はそこに何かが代入できることを意味しようとしている． )

2. 体の言語とは集合 {0, 1, ∗ + ∗, −∗, ∗ · ∗, ∗^{−1}} のことである．

3. 順序体の言語とは集合 {0, 1, ∗ + ∗, −∗, ∗ · ∗, ∗^{−1}, ∗ < ∗} のことである．

上の例では，各記号はそれぞれ（ある程度）固有の意味を持っていた．たとえば，体の言語における 0 はもちろん加法に対する単位元をあらわすものだという暗黙の了解がある．

しかし，われわれが今後展開する理論においては，記号は単なる記号であり，それらに固有の意味はない．ただし，それぞれの記号は定数記号か，関数記号か，述語記号なのかは指定されているとする．また関数記号，述語記号の場合は何変数かも指定されているとする．言語は L,L′,... などであらわす．

次に変数記号の集合を一つ固定しておく．これらは， x,y,z,x_{0},x_{1},... などである．

Definition 2 (項) L を言語とする． L の項は次のように帰納的に定義される．

0. 変数記号と L に属する定数記号はすべて L の項である．

1. t_{1}, ..., t_{n} がすべて L の項で， F ∈ L が n 変数の関数記号ならば， F (t_{1}, ..., t_{n}) は L の項である．

2. 以上によって項とわかるものだけが L の項である．通常上のような帰納的な定義においては，条件３は省略される． Example 3 L = {c, F } とする．ただし， c は定数記号， F は２変数関数記号である．このとき，

x, c, F (x, c), F (x, F (x, c)), F (F (x, c), F (x, c)), ...

などは L の項の例である．定義??は次のように言ってもよい：

1. T_{0} = { 変数記号} ∪ {L の定数記号};

2. T_{k+1} = {F (t_{1}, ..., t_{n}) : t_{1}, ..., t_{n} ∈ T_{k} かつ F ∈ L は n 変数関数記号}

3. L の項の集合 = ⋃_{k∈ℕ} T_{k} Exercise 4 G を群とする． A ⊂ G によって生成される G の部分群 ⟨A⟩ を帰納的に定義せよ．

以上で変数記号の集合と言語（これも記号の集合）から項の集合という記号の有限列の集合が定義された．次に項を使って「命題」を意味する記号列である論理式を定義したい．そのために新たに論理記号の集合 {=, ∧, ∨, ¬, →, ∀, ∃} を導入する． Definition 5 (原子論理式)

1. t と s が L の項のとき，記号列 t = s は L の原子論理式である．

2. t_{1}, ..., t_{n} がすべて L の項で， P ∈ L が n 変数の述語記号ならば， P (t_{1}, ..., t_{n}) は

L の原子論理式である． Example 6 L = {c, F, ∗ < ∗} とする．ただし， c は定数記号， F は２変数関数記号， ∗ < ∗ は２変数述語記号である．このとき，

1. F (x, c) = y,

2. F (x, y) < F (F (x, y), c) などは原子論理式の例である．

L の項 t の中に現れる変数記号が x_{1}, ..., x_{n} に含まれるとき， t を t(x_{1}, ..., x_{n}) とかくことがある．

次に論理式の定義を与えるが，このために論理記号とよばれる記号 ¬, ∧, ∨, →, ∀, ∃ を用意する．

Definition 7 (論理式) L を言語とする． L の論理式（L-論理式）は次のように帰納的に定義される．

0. L の原子論理式は L の論理式である．

1. φ, ψ が L の論理式で x が変数ならば，

¬(φ), (φ) ∧ (ψ), (φ) ∨ (ψ), (φ) → (ψ), ∀x(φ), ∃x(φ)

はすべて L の論理式である．

L-論理式 φ の中に，変数 x があらわれていて，なおかつこの x に作用しているような ∀x または ∃x があるとき，この x を束縛（された）変数という．束縛されていない変数は自由変数とよぶ．たとえば φ が (∀x(F (x, y) = x)) ∧ (F (x, x) = z) のとき， ∧ の前に出てくる x は ∀x で束縛された変数だが，後半の x は自由変数である． φ の中の自由変数がすべて x_{1}, ..., x_{n} に含まれるとき， φ のことを φ(x_{1}, .., x_{n}) とかくことがある．また，このとき varphi は n 変数論理式とよばれる．

Definition 8 （閉論理式）論理式 φ の中に自由変数がないとき， φ を閉論理式とよぶ．

2 意味の世界

論理式はあくまでも記号の列であり，固有の意味は持たない．意味を与えるのは構造である．

以下で α,β... などは順序数を表す.

Definition 9 （構造） L = {c_{i} : i < α} ∪ {F_{i} : i < β} ∪ {P_{i} : i < γ} を言語とする．ただし， c_{i} は定数記号， F_{i} は m_{i} 変数の関数記号， P_{i} は n_{i} 変数述語記号とする．次の条件を満たす対

(M; {c_{i}^{M}}_{i<α}, {F_{i}^{M}}_{i<β}, {P_{i}^{M}}_{i<γ})

を一つの L-構造とよぶ：

1. M ≠ ∅ 2. c_{i}^{M} ∈ M (i < α)

3. F_{i}^{M} は M^{m_{i}} から M への関数 (i < β)

4. P_{i}^{M} ⊂ M^{n_{i}} (i < γ)

c_{i}^{M} を定数記号 c_{i} の M における解釈とよぶ．同様に F_{i}^{M} は関数記号 F_{i} の解釈， P_{i}^{M} を述語記号 P_{i} の解釈とよぶ． M を上の構造のユニバース（領域）とよぶ．

Remark 10 1. 定数記号は名前の示すとおり定数（特定の元）を表すための記号であるから，構造では実際特定の元に解釈されている．同様に関数記号は関数をあらわすための記号であり，構造ではまさに関数に解釈されているわけである．述語記号の場合は，少し注意を要する．述語記号の解釈は述語記号を成り立たせたい元全体として解釈されているわけである．たとえば実数の世界において < の「通常の」解釈は {(x, y) ∈ ℝ : x < y} になっている．

2. 言語の解釈を明示する必要がないとき（あるいは面倒なとき）ユニバース M だけを示して，構造とよぶ．しかし我々の立場で構造という場合は言語の解釈の部分も本来は明示すべきである．たとえば，実数の集合 ℝ を考えるとき，構造 (ℝ, 0., 1, +, ·) と (ℝ, 0, 1, +, ·, <) とはまったく異なるものとして扱う．前者は体としての実数構造であり，後者は順序体としの実数構造である．

3. L = {0, 1, +, ·} を言語として， ℝ を L-構造にする方法は１つでない．０は実数の０と解釈して，１は１に解釈， + は和を与える関数， · は積を与える関数に解釈するのが普通ではあるが，たとえば，０を実数の１と解釈しても我々の意味では L-構造になる．

次はまったく常識的な定義である． L の項 t は帰納的に構成されていた．したがって，項 t の M においての値も t がいかに構成されたかに従って帰納的に定義される：

Definition 11 (項の解釈) M を L-構造とする． L の項 t(x_{1}, ..., x_{n}) と a_{1}, ..., a_{n} ∈ M に対して，「t に a_{1}, ..., a_{n} を代入した値」（t^{M}(a_{1}, ..., a_{n})）を帰納的に左辺を右辺で定義する:

0. (a) t が変数 x_{i} のときのとき，

t^{M}(a_{1}, ..., a_{n}) = a_{i}.

(b) t が定数記号 c のとき，

t^{M}(a_{1}, ..., a_{n}) = c^{M}.

1. t が F (t_{1}(x_{1}, ..., x_{n}), ..., t_{m}(x_{1}, ..., x_{n})) （F は関数記号， t_{i} たちは項）のとき，

t^{M}(a_{1}, ..., a_{n}) = F^{M}(t_{1}^{M}(a_{1}, ..., a_{n}), ..., t_{m}^{M}(a_{1}, ..., a_{n})).

Definition 12 （論理式の解釈） M を L-構造， a_{1}, ..., a_{n} ∈ M とし， φ = φ(x_{1}, ..., x_{n}) を L-論理式とする．「M で φ(a_{1}, ..., a_{n}) が成立する」（M ⊧ φ(a_{1}, ..., a_{n})）という関係を帰納的に定義する．

1. • φ が原始論理式 t(x_{1}, ..., x_{n}) = u(x_{1}, ..., x_{n}))) のときは,

M ⊧ φ(a_{1}, ..., a_{n}) ⟺ t^{M}(a_{1}, ..., a_{n}) = u^{M}(a_{1}, ..., a_{n}).

• φ が原始論理式 P (t_{1}(x_{1}, ..., x_{n}), ..., t_{m}(x_{1}, ..., x_{n})) のときは，

M ⊧ φ(a_{1}, ..., a_{n}) ⟺ (t_{1}^{M}(a_{1}, ..., a_{n}), ..., t_{m}^{M}(a_{1}, ..., a_{n})) ∈ P^{M}.

2. • φ が φ_{1}(x_{1}, ..., x_{n}) ∧ φ_{2}(x_{1}, ..., x_{n}) のとき，

M ⊧ φ(a_{1}, ..., a_{n}) ⟺ “M ⊧ φ_{1}(a_{1}, ..., a_{n}) かつM ⊧ φ_{2}(a_{1}, ..., a_{n})′′.

• φ が φ_{1}(x_{1}, ..., x_{n}) ∨ φ_{2}(x_{1}, ..., x_{n}) のとき，

M ⊧ φ(a_{1}, ..., a_{n}) ⟺ “M ⊧ φ_{1}(a_{1}, ..., a_{n}) またはM ⊧ φ_{2}(a_{1}, ..., a_{n})′′.

• φ が φ_{1}(x_{1}, ..., x_{n}) → φ_{2}(x_{1}, ..., x_{n}) のとき，

M ⊧ φ(a_{1}, ..., a_{n}) ⟺ “M ⊧ φ_{1}(a_{1}, ..., a_{n}) ならばM ⊧ φ_{2}(a_{1}, ..., a_{n})′′.

• φ が ¬ψ(x_{1}, ..., x_{n}) のとき，

M ⊧ φ(a_{1}, ..., a_{n}) ⟺ “M ⊧ φ(a_{1}, ..., a_{n}) でない′′.

• φ が ∃xψ(x, x_{1}, ..., x_{n}) のとき，

M ⊧ φ(a_{1}, ..., a_{n}) ⟺ “適当な b ∈ M に対しM ⊧ ψ(b, a_{1}, ..., a_{n})′′.

• φ が ∀xψ(x, x_{1}, ..., x_{n}) のとき，

M ⊧ φ(a_{1}, ..., a_{n}) ⟺ “任意の b ∈ M に対しM ⊧ ψ(b, a_{1}, ..., a_{n})′′.

構造を保存する写像を同型写像とよぶ．正確には次のようになる． Definition 13 (同型) L を定義??における言語 L とする． M と N を L-構造とする．全単射 σ : M → N が同型写像であるとは次の条件を満たすことである．

1. σ(c_{i}^{M}) = c_{i}^{N} (i < α);

2. σ ∘ F_{i}^{M} = F_{i}^{N} ∘ \underbrace{(σ, ..., σ)}_{n_{i}} (i < β);

3. σ(P_{i}^{M}) = P_{i}^{N} (i < γ).

条件２，３は次のように言い換えることができる． 2’. F_{i}^{M}(a_{1}, ..., a_{m_{i}}) = b ⟺ F_{i}^{N}(σ(a_{1}), ..., σ(a_{n_{i}})) = σ(b), (∀a_{1}, ..., a_{m_{i}}, b ∈ M); 3’. (a_{1}, ..., a_{n_{i}}) ∈ P_{i}^{M} ⟺ (σ(a_{1}), ..., σ(a_{n_{i}})) ∈ P_{i}^{N} (∀a_{1}, ..., a_{n_{i}} ∈ M). Exercise 14 σ : M → N を同型写像とする．このとき，すべての項 t(x_{1}, ..., x_{n}) に対して，

σ(t^{M}(a_{1}, ..., a_{n})) = t^{N}(σ(a_{1}), ..., σ(a_{n})) (∀a_{1}, ..., a_{n} ∈ M)

が成立することを t の構成に関する帰納法で示せ． Exercise 15 L-構造の間の全単射 σ : M → N に対して次が同値になることを示せ．．

1. σ : M → N は同型写像;

2. すべての原始論理式 φ(x_{1}, ..., x_{n}) とすべての a_{1}, ..., a_{n} ∈ M に対して，

M ⊧ φ(a_{1}, ..., a_{n}) ⟺ N ⊧ φ(σ(a_{1}), ..., σ(a_{n})).

Definition 16 (基本写像) M,N を L-構造， A ⊂ M, B ⊂ N とする．写像 σ : A → B は条件 (*) すべての L-論理式 φ(x_{1}, ..., x_{n}) とすべての a_{1}, ..., a_{n} ∈ A に対して，

M ⊧ φ(a_{1}, ..., a_{n}) ⟺ N ⊧ φ(σ(a_{1}), ..., σ(a_{n})).

を満たすとき，基本写像とよばれる． Exercise 17 同型写像は基本写像になることを示せ．（ヒント：上の定義??の (*) の部分を論理式 φ の構成に関する帰納法で示せばよい．）

3 ウルトラフィルター

Definition 18 (ウルトラフィルター) 無限集合 I とその部分集合全体 P(I) を考える． U ⊂ P(I) とする．

1. U は有限交叉性を持つ ⟺ U の勝手な有限部分集合 F ⊂ U は共通部分を持

つ（すなわち， ∀ \underbrace{A_{1}, ..., A_{n}}_{finite} ∈ U に対して， A_{1} ∩ ... ∩ A_{n} ≠ ∅）．

2. U が I 上のウルトラフィルター ⟺ U は有限交叉性を持つ P(I) の部分集合の中で極大である（すなわち， U 自体は有限交叉性を持ち,U の真の拡大はもはや有限交叉性を持たない）．

Example 19 1. I を無限集合とする． A ⊂ I が補有限（cofinite）であるとは， A の補集合 A^{c} = I \ A が有限となることである． F = {A ⊂ I : A は補有限} とすれば， F は有限交叉性を持つ．

2. I を非可算集合とする． F = {A ⊂ I : A^{c} は高々可算} とすれば， F は有限交叉性を持つ．

Exercise 20 I 上のウルトラフィルター U に対して次を示せ：

1. A ∈ U, A ⊂ B ⊂ I ⇒ B ∈ U;

2. A ∈ U, B ∈ U ⟺ A ∩ B ∈ U.

Exercise 21 a ∈ I とするとき， U_{a} = {A ⊂ I : a ∈ A} は I 上のウルトラフィルターになることを示せ．（ヒント： U_{a} のすべての元は a を持つのでそれらの共通部分は空でない． {a} ∈ U_{a} に注意する． U_{a} を真に拡大する集合には a を含まない集合 B がある．このとき， {a} ∩ B = ∅ である．）

Remark 22 U ⊂ P(I) が有限交叉性を持つとき，次は同値である．

1. U はウルトラフィルターである．

2. 勝手な A ⊂ I に対して， A ∈ U または A^{c} ∈ U.

次の二つの補題はともに易しいが重要である．

Lemma 23 U_{i} ⊂ P(I) (i < α) を有限交叉性を持つ集合の上昇列とする．このとき， U^{∗} = ⋃_{i<α} U_{i} も有限交叉性を持つ．

Proof ：有限個の A_{i}, ..., A_{n} ∈ U^{∗} を勝手にとる．このとき，これらをすべて含む U_{i} が存在する． U_{i} は有限交叉性を持つので， A_{1} ∩ ... ∩ A_{n} は空でない． Lemma 24 U ⊂ P(I) が有限交叉性を持つとする．このとき，任意の A ⊂ I に対して，

U ∪ {A} または U ∪ {A^{c}}

の少なくとも一方は有限交叉性を持つ．

Proof ：両方とも有限交叉性を持たないとすれば，有限集合 F_{1} ⊂ U と F_{2} ⊂ U で， ⋂ F_{1} ∩ {A} = ∅, ⋂ F_{2} ∩ {A^{c}} = ∅ となるものが存在する．したがって， F = F_{1} ∪ F_{2} とすれば， ⋂ F = ∅ となる．これは矛盾．

例??で存在を示したのは，中心のあるウルトラフィルターである．中心のないウルトラフィルターも存在する．

Theorem 25 （ウルトラフィルターの存在） I を無限集合として， F ⊂ P(I) は有限交叉性を持つとする．このとき， F を拡大して I 上のウルトラフィルターにすることができる．（∃U ⊃ F s.t. U は I 上のウルトラフィルター．）

Proof ： P(I) の濃度を κ として， P(I) の元を一列にならべた列 {A_{i} : i < κ} を作っておく．以下のように i ≤ κ に関する帰納法で，上昇列 U_{i} ⊂ P(I) を作る：

1. U_{0} = F;

2. i = α + 1 のとき， U_{i} ⊂ P(I) は

• U_{α} ⊂ U_{i};

• A_{α} または A_{α}^{c} のいずれかは U_{i} に属する．

を満たす有限交叉性を持つ集合とする．（補題から存在がわかる）

3. i が極限順序数のとき U_{i} = ⋃_{j<i} U_{j}.

このとき，補題から U = U_{κ} は有限交叉性を持つことはすぐわかる．次に勝手な A ⊂ I が与えらえれたとき， A ∈ U または A^{c} ∈ U を示せばよい． A = A_{α} となる α を選ぶ．構成法から A ∈ U_{α+1} または A^{c} ∈ U_{α+1} である． U_{α+1} ⊂ U だから証明された．

Remark 26 中心のない ℕ 上のウルトラフィルターは次のように作ればよい.F ⊂ P(ℕ) を補有限集合全体とする．これは有限交叉性を持ち， ⋂ F = ∅ である． F はウルトラフィルターに拡大される．

4 ウルトラプロダクト

この節では，言語 L は関数記号だけからなる場合を考える．この仮定は表現を簡潔にするためだけのもので，一般の場合もまったく同様の議論ができる．

I ≠ ∅ を集合とする．各 i ∈ I に対して， M_{i} を L-構造とする．ユニバースの直積 N = Π_{i∈I}M_{i} を考えよう． N の元は (a_{i})_{i∈I} の形をしている．関数記号 F ∈ L の解釈を成分ごとの計算に帰着することにより L-構造となる．もう少し正確に述べれば，次のように定めることで L-構造となる：

F^{N}(a^{1}, ..., a^{n}) = (F^{M_{i}}(a_{i}^{1}, ..., a_{i}^{n}))_{i∈I}

ただし， a^{j} = (a_{i}^{j})_{i∈I} ∈ N (j = 1, ..., n) である．（j 乗というわけではないので注意．）

上の定義は，群や環の直積の定義を模したものになっている．しかし，次のことに注目してほしい．

Exercise 27 |I| ≥ 2 として， F_{i} (i ∈ I) たちを体とする．このとき， F_{i} たちの直積は体にはならないことを示せ．

そこで，構造に対する条件（群だったり体だったりという条件）を保存する拡大を考えたい．そのために必要となるのが，直積集合をウルトラフィルターによる同値関係で割るという操作である．

以下では，しばらく次の仮定をおく．

• I を無限集合として，

• U をその上のウルトラフィルターとする．

• 各 i ∈ I に対して， L-構造 M_{i} が与えられている．

• N をこれらの構造の直積とする．

• a ∈ N, i ∈ I に対して， a_{i} はその i 番目の座標とする．すなわち a = (a_{i})_{i∈I} である．

Exercise 28 直積集合 N 上の２項関係 ∼ を

a ∼ b ⟺ {i ∈ I : a_{i} = b_{i}} ∈ U

で定義する．このとき， ∼ は同値関係になることを示せ．

N を同値関係で割った集合を M^{∗} = ∏_{i∈I} M_{i}/U であらわすことにする． a ∈ N の同値類を [a] であらわすことにすると， M^{∗} = {[a] : a ∈ N}， [a] = [(a_{i})_{i∈I} である． Definition 29 （ウルトラプロダクト） M^{∗} = ∏_{i∈I} M_{i}/U は各関数記号 F ∈ L の解釈を次のように定めることで L-構造になる．

F^{M^{∗}}([a^{1}], ..., [a^{n}]) = [F^{N}(a^{1}, ..., a^{n})].

L-構造としての M^{∗} を M_{i} たちのウルトラプロダクトという．

Remark 30 上の定義が well-defined なことは調べておく必要がある．すなわち， a^{1} ∼ b^{1}, ..., a^{n} ∼ b^{n} のとき，

F^{N}(a^{1}, ..., a^{n}) ∼ F^{N}(b^{1}, ..., b^{n})

を示す必要がある．しかし，これは「A, B ∈ U のとき A ∩ B ∈ U」を使えば簡単である．

Lemma 31 t(x^{1}, ..., x^{n}) を L の項とする． [a^{1}], ..., [a^{n}], [b] ∈ M^{∗} に対して，

t^{M^{∗}}([a^{1}], ..., [a^{n}]) = [b] ⟺ {i ∈ I : t^{M_{i}}(a_{i}^{1}, ..., a_{i}^{n}) = b_{i}} ∈ U.

Proof ： t が変数記号 x のときは自明． t が L の関数記号 F のとき，

F^{M^{∗}}([a^{1}], ..., [a^{n}]) = [b] ⟺ [F^{N}(a^{1}, ..., a^{n})] = [b]
⟺ [(F^{M_{i}}(a_{i}^{1}, ..., a_{i}^{n}))_{i}] = [(b_{i})_{i}]
⟺ {i ∈ I : F^{M_{i}}(a_{i}^{1}, ..., a_{i}^{n}) = b_{i}} ∈ U.

後は t の構成に関する帰納法で示せばよい. 最も単純な場合を示しておく： t = F (u) で F は１変数関数記号， u は１変数の項とする． [a] ∈ M^{∗} に対して， u^{M^{∗}}([a]) = [d] とすれば，帰納法の仮定から， {i ∈ I : u^{M_{i}}(a_{i}) = d_{i}} ∈ U となる．したがって，

F^{M^{∗}}(u^{M^{∗}}([a])) = [b] ⇒ F^{M^{∗}}([d]) = [b]
⇒ {i ∈ I : F^{M_{i}}(d_{i}) = b_{i}} ∈ U & {i ∈ I : u^{M_{i}}(a_{i}) = d_{i}} ∈ U
⇒ {i ∈ I : F^{M_{i}}(d_{i}) = b_{i} & u^{M_{i}}(a_{i}) = d_{i}} ∈ U
⇒ {i ∈ I : F^{M_{i}}(u^{M_{i}}(a_{i})) = b_{i}} ∈ U.

逆も同様である．

Theorem 32 （ウルトラプロダクトの基本定理） φ(x^{1}, ..., x^{n}) を L-論理式とする．任意の [a^{1}], ..., [a^{m}] ∈ M^{∗} に対して次が成立する：

M^{∗} ⊧ φ([a^{1}], ..., [a^{n}]) ⟺ {i ∈ I : M_{i} ⊧ φ(a_{i}^{1}, ..., a_{i}^{n})} ∈ U.

Proof ： 0) φ が原子論理式のときは補題から明らか．後は φ の構成に関する帰納法で示せばよい．

1) φ が ¬ψ のとき：

M^{∗} ⊧ ¬ψ([a^{1}], ..., [a^{n}]) ⟺ M^{∗} ⊧ ψ([a^{1}], ..., [a^{n}]) でない
⟺ {i ∈ I : M_{i} ⊧ ψ(a_{i}^{1}, ..., a_{i}^{n})} ∉ U
⟺ {i ∈ I : M_{i} ⊧ ψ(a_{i}^{1}, ..., a_{i}^{n})}^{c} ∈ U
⟺ {i ∈ I : M_{i} ⊧ ψ(a_{i}^{1}, ..., a_{i}^{n}) でない} ∈ U
⟺ {i ∈ I : M_{i} ⊧ ¬ψ(a_{i}^{1}, ..., a_{i}^{n})} ∈ U.

2)φ が ∃yψ(x^{1}, ..., x^{n}, y) のとき：

M^{∗} ⊧ ∃yψ([a^{1}], ..., [a^{n}], y) ⟺ M^{∗} ⊧ ψ([a^{1}], ..., [a^{n}], [b]) for some b ∈ M^{∗}
⟺ {i ∈ I : M_{i} ⊧ ψ(a_{i}^{1}, ..., a_{i}^{n}, b_{i})} ∈ U for some b_{i}’s
⟺ {i ∈ I : M_{i} ⊧ ∃yψ(a_{i}^{1}, ..., a_{i}^{n}, y)} ∈ U

3) その他の論理記号の場合も同様である．

Corollary 33 φ を L-閉論理式とする．このとき，

M^{∗} ⊧ φ ⟺ {ı ∈ I : M_{i} ⊧ φ} ∈ U

上の系で主張していることを一言でいうと次のようになる：論理式 φ がウルトラプロダクトで成立するのは，（U の意味で）ほとんどの M_{i} たちが φ を成立させるときである．

Example 34 F_{i} （i ∈ I）が体のとき， R = ∏_{i∈I} F_{i} は1を持つ環になる． 𝔪をR の極大イデアルとする. a ∈ Rに対して， Z_{a} = {i ∈ I : a_{i} = 0}とおく． U = {Z_{a} ⊂ I : a ∈ 𝔪} とすれば， U は I 上のウルトラフィルターになる：最初に A ∈ U, A ⊂ B ならば B ∈ U が成り立つことに注意しておく．（有限交叉性） Z_{a^{1}}, ..., Z_{a^{n}} ∈ U とする．各 a^{i} ∈ 𝔪 に適当に R の元をかけておけば， a^{i} : I → {0, 1} と仮定できる．もし，

Z_{a^{1}} ∩ ⋯ ∩ Z_{a^{n}} = ∅

が成り立てば，関数 a^{i} たちの共通零点がない．よって関数 1 − a^{i} たちが共通に１となる点がない．このことから ∏_{i≤n}(1 − a^{i}) = 0 を得る．展開して整理すれば， 1 が a^{i} ∈ 𝔪 たちの積と和で表現されていることがわかる．これは 𝔪 が極大イデアルであることに矛盾する．（完全性） A ⊂ I に対して， i ∈ A のとき値 0 をとり i ∉ A のとき，値 1 をとる a_{A} ∈ R をとる． a_{A} ∈ 𝔪 ならば， A = Z_{a_{A}} ∈ U である． a_{A} ∉ 𝔪 のときは， 𝔪 の極大性により，

1 = a′a_{A} + b

となる a′ ∈ R と b ∈ 𝔪 がある．したがって， Z_{b} ⊂ (Z_{a′a_{A}})^{c}. しかし， A ⊂ Z_{a′a_{A}} なので， Z_{b} ⊂ A^{c}. よって， A^{c} ∈ U である．

5 コンパクト性定理

ウルトラプロダクトの基本定理は非常に重要な定理である．この定理の帰結として，コンパクト性定理がある．

\underline{言葉の使い方}： T を L-閉論理式の集合とする． L-構造 M が T のすべての論理式を満たすとき， M は T のモデルであるといい， M ⊧ T とかく．すなわち， M ⊧ T ⟺ M ⊧ φ (∀φ ∈ T)．

Theorem 35 （コンパクト性定理） T を L-閉論理式からなる一つの集合とする．このとき，次は同値である．

1. T はモデルを持つ（∃M s.t. M ⊧ T ）；

2. T の各有限部分はモデルを持つ（∀S ⊂_{fin} T ∃M_{S} s.t. M_{S} ⊧ S）．

Proof ： 1 ⇒ 2 は明らかである． 2 ⇒ 1 を示す． T の有限部分集合全体を I とおく．各 S ∈ T に対して， M_{S} ⊧ S となる L-構造を一つずつ選んでおく． φ ∈ T に対して，

A_{φ} = {S ∈ I : M_{S} ⊧ φ}

と定義する． A_{S} は空でない I の部分集合である． A_{S} たち全体を F とおく．

Claim 1 F ⊂ P(I) は有限交叉性を持つ．

A_{φ_{1}}, ..., A_{φ_{n}} ∈ F とする．このとき， M_{{φ_{1},...,φ_{n}}} は各 φ_{i} のモデルになっているから，

{φ_{1}, ..., φ_{n}} ∈ A_{φ_{1}} ∩ ... ∩ A_{φ_{n}}

したがって， A_{φ_{1}} ∩ ... ∩ A_{φ_{n}} ≠ ∅. （主張 1 の証明終わり）

したがって， F を拡大して I 上のウルトラフィルター U を作ることができる． M = ∏_{S∈I} M_{S}/U とおく． Claim 2 M ⊧ T.

各 φ ∈ T に対して， M ⊧ φ を示せばよい．そのためには，ウルトラフィルターの基本定理により， {S ∈ I : M_{S} ⊧ φ} ∈ U を示せばよい．しかし，これは A_{φ} ∈ U から明らかである．

Example 36 （自然数の超準モデルの存在）自然数の集合 ℕ を {0, 1, +, ·, <}-構造と考える． c を新しい定数記号として， T = {φ : ℕ ⊧ φ} ∪ {c > n : n ∈ ℕ} を考える．（c > n はこの言語では， c > \underbrace{1 + ⋯ + 1}_{n} とかかれている．） T の有限部分集合 T_{0} が与

えられたとき， T_{0} のモデルが存在することを示す． T_{0} は次の形（の部分集合）と思ってよい．

{φ : ℕ ⊧ φ} ∪ {c > n_{1}, …, c > n_{k}}

c の解釈を n = max{n_{1}, ..., n_{k}} + 1 とすれば， ℕ は T_{0} のモデルになる．コンパクト性定理により， T 全体のモデル ℕ^{∗} が存在する． ℕ^{∗} をもともとの言語 {0, 1, +, ·, <} に制限して考えよう．作り方から， ℕ と ℕ^{∗} は論理式で区別できない．しかし， ℕ^{∗} には c の解釈をとることができるので， ℕ と同型ではない．

Example 37 （濃度の表現不可能性） L-構造 M が 3 個の以上の元を持つということは，論理式 ∃x_{1}∃x_{2}∃x_{3}[x_{1} ≠ x_{2} ∧ x_{2} ≠ x_{3} ∧ x_{1} ≠ x_{3}] で表現される．同様に有限の n が与えられたとき， L-構造が n 個以上の元を持つということを表現する L-閉論理式 φ_{n} がある．このとき，

M ⊧ φ_{n} ∧ ¬φ_{n+1} ⟺ M の濃度は n

が成立する．しかし，

M ⊧ φ^{∗} ⟺ M は有限

を成り立たせる L-閉論理式 φ^{∗} は存在しない：このような φ^{∗} が存在したとする．各有限の n に対して，濃度が n 以上の有限 L-構造 M_{n} が存在する．このことは， T = {φ^{∗}} ∪ {φ_{n} : n ∈ ℕ} の各有限部分がモデルを持つことを意味する．したがって T 全体にもモデル M が存在する．この M は無限だが φ^{∗} を成り立たせている．矛盾． κ を無限基数とするとき，「M ⊧ φ_{κ} ⟺ M の濃度は κ」となる φ_{κ} も存在しないことがいえる．これは次の節で述べる Löwenheim-Skolem の定理からもわかる．

6 Löwenheim-Skolem の定理

Definition 38 （部分構造） M を L-構造とする．部分集合 N ⊂ M が次の条件を満たすとき M の部分構造と呼ばれる． 1. c ∈ L が定数記号のとき， c^{M} ∈ N ；

2. F ∈ L が関数記号のとき， F^{M} で N は閉じている．

N が M の部分構造のとき，各記号の解釈を N に制限することにより， N は自然に L-構造になる．すなわち，定数記号に対しては， c^{N} = c^{M}, n-変数関数記号に対しては， F^{N} = F^{M}|N^{n}, m-変数述語記号については， P^{N} = P^{M} ∩ N^{m} とする．

Exercise 39 群を {e, ∗ · ∗, ∗^{−1}}-構造と考えれば，部分群の概念と部分構造の概念は一致することを示せ．

Definition 40 M を L-構造とする．

1. A ⊂ M とする．言語 L に新しい定数記号 c_{a} たち（a ∈ A）を付加した言語を L(A) とかく． M は自然に L(A) 構造となる．すなわち， c_{A}^{M} = a と解釈する．

2. 部分構造 N ⊂ M は次の条件を満たすとき，基本部分構造（elementary substructure）と呼ばれる：

(*) 任意の L(N)-閉論理式 φ に対して， M ⊧ φ ⟺ N ⊧ φ．

このとき， M は N の基本拡大とよばれる．

3. N が M の基本部分構造のとき， N ≺ M あるいは M ≻ N とかく．

Example 41 M を L-構造とする． T^{∗} を M で成立する L(M)-閉論理式全体の集合とする．この T^{∗} を T の基本設計図（elementary diagram）という． T の勝手なモデルは M の基本拡大と思うことができる．実際 a ∈ M に対して， c_{a}^{N} を対応させる関数 σ が基本部分構造としての埋め込みになっている．すなわち， σ : M ≅ σ(M) ≺ N．別の言葉で言えば， σ が基本写像になっている．

Exercise 42 1. 基本部分構造の定義の (*) において，片側向きの矢印が成立すれば実は両側向きの矢印が成立する．

2. ≺ に対して推移性が成り立つことを示せ．

以下において M は濃度が無限の L-構造とする．

Lemma 43 κ を無限基数とするとき， M の基本拡大で濃度が κ 以上のものが存在する． Proof ： T^{∗} を M の基本設計図とする． L(M) に属さない新しい定数記号を κ 個容易する．それらを {c_{i} : i < κ} とする． L(M) ∪ {c_{i} : i < κ}-閉論理式の集合

T^{∗∗} = T^{∗} ∪ {c_{i} ≠ c_{j} : i < j < κ}

を考える．明らかに T^{∗∗} の有限部分はモデルを持つ．（有限個の c_{i} たちはすべて異なるように M の中で解釈してやることができる．）したがって， T^{∗∗} のモデル N が存在する． N ≻ M と考えることができる．また T^{∗∗} の条件から， N は κ 個の異なる元を有するので濃度は κ 以上である．

上の補題は，構造の大きさを大きい方に変えることができることを意味している．次に構造の大きさを小さくする方向を考える．その場合に重要になるのが，基本部分構造の判定条件である．

Lemma 44 (Tarski-Vaught の判定条件) M を L-構造とする． N ⊂ M に対して，次は同値である：

1. N ≺ M;

2. 勝手な L(N)-論理式 φ(x) に対して，

M ⊧ ∃φ(x) ⇒ M ⊧ φ(a) となる a ∈ N が存在する．

Proof ： 1 ⇒ 2 は易しいので省略（演習問題）． 2 ⇒ 1: L-論理式 φ(x_{1}, ..., x_{n}) の構成に関する帰納法で次を示す：

(*) M ⊧ φ(a_{1}, ..., a_{n}) ⟺ N ⊧ φ(a_{1}, ..., a_{n}) (∀a_{1}, ..., a_{n} ∈ N)

構造の定義から原子論理式 φ(x_{1}, ..., x_{n}) に対しては， (*) は成立する．問題は φ(x_{1}, ..., x_{n}) が ∃yψ(y, x_{1}, ..., x_{n}) の場合である．

M ⊧ ∃yψ(y, a_{1}, ..., a_{n}) ⟺ M ⊧ ψ(b, a_{1}, ..., a_{n}) (∃b ∈ N)
⟺ N ⊧ ψ(b, a_{1}, ..., a_{n}) (∃b ∈ N)
⟺ N ⊧ ∃ψ(y, a_{1}, ..., a_{n})

ここで，１行目の同値性は条件２による．また１行目と２行目の間の同値性は帰納法の仮定による．

以下では集合 A の濃度は |A| で表すことにする．

Lemma 45 M を L-構造とする． A ⊂ M に対して， N ≺ M で次の条件を満たすものが存在する．

1. A ⊂ N;

2. |M| ≤ |A| + |L| + ℵ_{0}

Proof ： A_{0} = A からはじめて， M の部分集合の上昇列 A_{i} (i < ω) を次の条件を満たすように帰納的に構成することができる：各 i > 0 に対して，

• L(A_{i−1})-論理式 φ(x) が M に解を持てばそのうち少なくとも一つは A_{i} の中にある；

• |A_{i}| ≤ |A| + |L| + ℵ_{0}.

実際， |A_{i}| ≤ |A| + |L| + ℵ_{0} のとき， L(A_{i})-論理式の数も |A| + |L| + ℵ_{0} 以下なので，それらの論理式の解を１つづつ A_{i} に付加したものを A_{i+1} とすればよい．

最終的にすべての A_{i} たちが定義された時点で， N = ⋃_{i∈ω} A_{i} とすれば，明らかに濃度の条件２は成立する． Tarski-Vaught の判定条件により， N ≺ M となる．

Theorem 46 （Löwenheim-Skolem の定理） T を L-閉論理式の一つの集合とする． T が無限モデルを持てば，任意の基数 κ ≥ |L| + ℵ_{0} に対して， T のモデル N で濃度が丁度 κ になるものが存在する．

Proof ： M を T の無限モデルとする．補題??により， M^{∗} ≻ M で濃度が κ 以上になるものが存在する． A ⊂ M^{∗} を濃度が丁度 κ の集合とする．補題??により， A を含む N ≺ M^{∗} で濃度が |A| + |L| + ℵ_{0}(= κ) 以下になるものが存在する．しかし， N ⊃ A だから |N| ≥ κ．よって， N の濃度は丁度 κ である．

二つの L-構造 M,N がまったく同じ L-閉論理式を満たすとき，それらは elementarily equivalent であるといい， M ≡ N とかく．

Corollary 47 L が可算言語とし， M を L-構造とする．勝手な無限基数 κ に対して， N ≡ M, |N| = κ となる N が存在する.

7 Elementary Chain Theorem とその応用

まず次の例からはじめよう．

Example 48 {M_{i} : i ∈ ω} を L-構造としての拡大列とする．各 M_{i} が T のモデルのとき， ⋃_{i∈ω} M_{i} も T のモデルになるだろうか？T が「群の公理」や「体の公理」のときは大丈夫である．しかし，一般には正しくない：各 i ∈ ω に対して， M_{i} = {n ∈ ℤ : n ≥ −i} とする． M_{i} に通常の順序を入れて， {<}-構造とみる．このとき，

• M_{0} ⊂ M_{1} ⊂ M_{2} ⊂ ⋯ ({<}-構造としての拡大列) ；

• M_{i} ⊧ “< は最小元を持つ全順序 ”

が成立する．しかし， ⋃_{i∈ω} M_{i} = ℤ は最小元は持たない．

Definition 49 α を順序数とする．長さ α の L-構造の列 (M_{i})_{i<α} が条件

(*) i < j < α ⇒ M_{i} ≺ M_{j}.

を満たすとき，基本鎖（elementary chain）と呼ばれる．

Theorem 50 (Elementary Chain Theorem) (M_{i})_{i<α} を基本鎖とする．このとき， M^{∗} = ⋃_{i<α} M_{i} は自然に L-構造となり，各 M_{i} は M^{∗} の基本部分構造になる．

Proof ： M^{∗} 上に定数記号，関数記号，述語記号の解釈を導入する． c^{M^{∗}} は一定の値 c^{M_{i}} とする．また， m 変数述語記号 P の解釈は P^{M^{∗}} = ⋃_{i<α} P^{M_{i}} とする． n 変数関数記号 F の解釈も（集合論的にかけば） F^{M^{∗}} = ⋃_{i<α} F^{M_{i}} とすればよい．

主張 M_{i} ≺ M^{∗}

次の命題を n ∈ ω に関する帰納法で示せばよい．

(∗)_{n} 任意の i < α と論理記号の数が n 以下の任意の L(M_{i})-閉論理式 φ に対して次が成立する： M^{∗} ⊧ φ ⇒ M_{i} ⊧ φ

n = 0 のとき，すなわち φ が原子論理式のときは明らか．帰納法のステージでは， φ が ∃xψ(x) の形のときが本質的である．（その他の論理記号については演習問題．） M^{∗} ⊧ ∃ψ(x) とする．このとき， ψ(x) の解 d ∈ M^{∗} が存在するが， M^{∗} はモデルの和の形をしているので， d ∈ M_{j} となる M_{j} がある． i < j としてよい．帰納法の仮定から M_{j} ⊧ ψ(d) である．よって， M_{j} ⊧ ∃xψ(x). M_{i} ≺ M_{j} だから M_{i} ⊧ φ．

Definition 51 （有限充足性とタイプ） 1. M を L 構造とし， A ⊂ M とする．列 x̄ = x_{1}, ..., x_{n} を自由変数として持つ

L(A)-論理式の集合 Φ(x̄) が M において有限充足的であるとは，任意有限個の φ_{1}(x̄), ..., φ_{n}(x̄) ∈ Φ(x̄) に対して，

M ⊧ ∃x̄[φ_{1}(x̄) ∧ ⋯ ∧ φ_{n}(x̄)]

が成立（共通解が存在）することである． Φ(x̄) が有限充足的でなおかつ完全（すなわち任意の L(A)- 論理式 φ(x̄) に対して， φ(x̄) ∈ Φ(x̄) または ¬φ(x̄) ∈ Φ(x̄) が成立）のとき， Φ(x̄) は M における A 上のタイプとよばれる．変数の数 n を強調したい場合は n 変数タイプという．

2. A 上のタイプ全体の集合を S_{M}(A) とかく． M が明らかなときは，省略して S(A) とかく．自由変数が n 個の A 上のタイプの集合を S^{n}(A) とかくことがある．

3. p ∈ S(A) のとき， A をタイプ p の領域（domain）とよび， dom(p) であらわす．

4. p(x) に属するすべての φ(x) を満たす元を p(x) の解という．（解は M の中に存在するとは限らない．）

Example 52 1. ℕ を {<, +, 1}-構造とみる． Φ(x) = {x > 1, x > 1 + 1, x > 1 + 1 + 1, … } は ℕ で有限充足的である．しかし， ℕ に解を持たない．

2. もう少し数学っぽい例． ℚ̄ を代数的数の全体とする．「x は ℚ 上の超越数である」という条件は

Φ(x) = {f(x) ≠ 0 : f は ℚ-係数の自明でない多項式}

という論理式の集合であらわされる．各多項式は有限個の解しか持たないので， Φ(x) は ℚ̄ で有限充足的である．しかし， Φ(x) の解は ℚ̄ にない．（拡大体の中には存在する．）

Lemma 53 M を L-構造として， L(A)-論理式の集合 Φ(x̄) は M で有限充足的とする． Φ(x̄) は A 上のタイプに拡大される．

Proof ： Φ(x) を拡大した有限充足的な集合のうち極大なものが存在する（Zorn の補題）．この極大集合がタイプになっている．

Exercise 54 p(x) を M におけるタイプとする． c を新しい定数記号として， T = T h(M, a)_{a∈M} ∪ p(c) を考える． T はモデルを持つことを示せ．（p(c) は {φ(c) : φ(x) ∈ p(x)} のことである．） Exercise 55 A ⊂ M ≺ M^{∗} とする． L(A)-論理式の集合 p(x̄) に対して， p(x̄) が M においてタイプになることと M^{∗} においてタイプになることは同値である．

次の補題はコンパクト性定理の簡単な応用である．

Lemma 56 M を L-構造とする． κ を無限基数とする．このとき，次の条件を満たす基本拡大 M^{∗} ≻ M が存在する：

(*) M^{∗} におけるタイプ p が dom(p) ⊂ M, |dom(p)| < κ を満たせば M^{∗} に解を持つ．

Proof ： S を M におけるタイプで条件 |dom(p)| < κ を満たすもの全体の集合とする． p ∈ S に対して，新しい定数記号 c_{p} を用意して，

T^{∗} = T h(M, a)_{a∈M} ∪ ⋃_{p∈S} p(c_{p})

なる閉論理式の集合を考える．右辺第２項は各 c_{p} が p の解になることを主張している． T^{∗} の各有限部分はモデルを持つので（M に定数記号 c_{p} たちの解釈を追加した形のモデルでよい），コンパクト性定理により T^{∗} 全体もモデル M^{∗} を持つ． M^{∗} は T h(M, a)_{a∈M} のモデルだから M^{∗} ≻ M である． c_{p} の解釈が p の解になっているから， M^{∗} は S に属する各タイプの解を少なくとも１つ持つ．

上で構成したモデル M^{∗} は domain が M に属するタイプのうち， domain の大きさが小さい（κ 未満の）ものに対する解を持っている．しかし， domain が小さくても M からはみ出るものについては解があるかどうかはわからない．

Definition 57 （飽和性） M を L-構造とし， κ は無限基数とする． M が |dom(p)| < κ なるすべてのタイプ p の解を持つとき， κ-飽和 (κ-saturated) であるといわれる．

Theorem 58 M を L-構造とし， κ は無限基数とする． M の拡大 M^{∗} ≻ M で κ^{+}-飽和なものが存在する．

Proof ： M_{0} = M から始まる elementary chain (M_{i})_{i<κ^{+}} を以下の条件が成り立つように作る：

1. A ⊂ M_{i}, |A| < κ^{+} ならば A 上のすべてのタイプは M_{i+1} に解を持つ．

2. δ が極限順序数のときは， M_{δ} = ⋃_{i<δ} M_{i}．補題??と elementary chain の性質??により，このような elementary chain は存在する． M^{∗} = M_{κ^{+}} が求める κ^{+}-飽和な構造である．実際， A ⊂ M^{∗} を濃度が κ 以下の集合とすれば， A ⊂ M_{i} となる M_{i} ≺ M^{∗} が存在する．したがって， A 上のすべてのタイプは M_{i+1} ≺ M^{∗} で解を持つ．（A 上のタイプの概念は M_{i+1} で考えても M^{∗} で考えても同じになることに注意．）

Remark 59 L が可算の場合を考える．可算構造 M からはじめることにより，上の命題による構成を行う．このとき， κ^{+}-飽和な M^{∗} ≻ M で濃度が 2^{κ} なものを作ることができる．

Definition 60 M を L-構造とする． ā = a_{1}, ..., a_{n} ∈ M および A ⊂ M に対して，

tp_{M}(a_{1}, ..., a_{n}/A) = {φ(x_{1}, ..., x_{n}) : φ(x_{1}, ..., x_{m}) は M ⊧ φ(a_{1}, ..., a_{n}) となる L(A)-論理式}

を（M における） ā の A 上のタイプという． M が明らかなときは省略する．

この表記のもとに， A 上のタイプ p(x̄) が M に解を持つということは tp(ā/A) = p(x̄) となる ā ∈ M が存在することと書きなおすことができる．また M が κ-飽和であることは，濃度が κ 未満の A ⊂ M 上のタイプはすべて tp(ā/A) (ā ∈ M) の形でかけることと同値になる．

Exercise 61 M ≡ N を ℵ_{0}-飽和な L-構造とする． tp_{M}(ā) = tp_{N}(b̄) なるとき，勝手な a ∈ M に対して，適当に b ∈ M を選べば， tp_{M}(ā, a) = tp_{N}(b̄, b) とできる．（ヒント： p(x̄, x) = tp_{M}(ā, a) とする．条件） tp_{M}(ā) = tp_{N}(b̄) から p(b̄, x) は N におけるタイプとなり，飽和性から解 b ∈ N を持つ．このとき， tp(ā, a) = tp(b̄, b) である． M と N が elementarily equivalent という仮定は， ā,b̄ が空列の場合に使われる．）

8 Omitting Types Theorem

この節では L は可算とし， T はモデルを持つ L-閉論理式の集合とする．この節での可算性の仮定は本質的である．特にタイプの排除定理はこの仮定なしには成り立たない．

前節では，なるべく多くのタイプが解を持つように構造を拡大することを考えてた．ここでは，その反対になるべくタイプが解を持たないように構造を作りたい．

Definition 62 Σ(x) を L-論理式の集合とする．

1. 次の条件を満たす L-論理式 φ(x) があるとき， Σ(x) は T で isolate されるという： (a) T ∪ {∃φ(x)} はモデルを持つ；

(b) 任意の T のモデル M において， φ(x) の解はすべて Σ(x) の解になる．（このことを T ⊧ ∀x[φ(x) → Σ(x)] とかく．）

2. Σ(x) が M に解を持たないとき， Σ(x) は M で排除（omit）されるという．

上の定義から直ちに， T が完全でなおかつ Σ(x) が T で isolate されるとき，任意の T のモデルは Σ(x) の解を持つことがわかる．

Theorem 63 （タイプの排除定理） T で Σ(x) が isolate されなければ， Σ(x) を排除する T のモデルが存在する．

Proof ： L に属さない可算個の新しい定数記号 {c_{i} : i ∈ ω} を用意する． L_{i} = L ∪ {c_{j} : j < i} とおく． L ∪ {c_{i} : i ∈ ω} に属する１変数論理式を一列にならべて φ_{i}(x) （i ∈ ω）とする．ただし， φ_{i} は L_{i}-論理式になるようにしておく． L_{i}-閉論理式の集合 T_{0} = T からはじめて T_{i} （i ∈ ω）を次のように定義してゆく：

(*) T_{i+1} = T_{i} ∪ {∃xφ_{i}(x) → φ_{i}(c_{i})} ∪ {¬σ_{i}(c_{i})},

ただし σ_{i}(x) ∈ Σ(x) は T_{i+1} がモデルを持つようにとる．

主張実際， T_{i+1} がモデルを持つように σ_{i} ∈ Σ はとれる．

σ_{i} ∈ Σ の取り方によらず， T_{i+1} がモデルを持たない（最小の） i があったとする．このとき， T_{i} の T 以外の部分をまとめて（∧ でつなげて） θ(c̄) とかけば，

T ⊧ ∀x[θ(x, c̄) ∧ (∃xφ_{i}(x) → φ_{i}(c_{i})) → Σ(x)]

を得る． c̄は T に属さない定数記号の列なので，

T ⊧ ∀x[∃ȳθ(x, ȳ) → Σ(x)].

これは Σ が T で isolate されることを意味するので矛盾．（主張の証明終わり）

以上から， T_{i} たちが構成された． T^{∗} = ⋃_{i∈ω} T_{i} とおいて， M^{∗} ⊧ T^{∗} をとる． M^{∗} の中の必要な部分 M = {c_{i}^{M^{∗}} : i ∈ ω} だけを抜き出す．条件 (*) から Tarski-Vaught の判定条件により， M ≺ M^{∗} がわかる．また各 c_{i} に対して， ¬σ_{i}(c_{i}) となる σ_{i} ∈ Σ があるので， M は Σ の解を持たない． Exercise 64 （拡張されたタイプの排除定理） Σ_{i}(x)(i ∈ ω) を T で isolate されない論理式の集合とする．このとき，すべての Σ_{i}(x) を排除する T のモデルが存在する．これを示せ．

Example 65 M を（論理式でかかれた）ペアノ公理系の可算モデルとする． N がM の elementary end extension であるとは， (i) M ≺ N, (ii) a ∈ M, b ∈ N, b < a ⇒ b ∈ M が成り立つことである．すなわち， N は M の基本拡大だが，増えている元は M の後ろだけに現れている． M の（真の） elementary end extension は存在する． Proof ： c を新しい定数記号として言語 L(M) に付加する．この新しい言語における理論 T^{∗} を

T^{∗} = T h(M, a)_{a∈M} ∪ {c > a : a ∈ M}

とする． T^{∗} のモデルは M の真の elementary extension となる．

Claim 1 φ(x) を L(M)-formula とする． T^{∗} ∪ {φ(c)} が consisitent になる必要十分条件は

M ⊧ ∃^{∞}yφ(y)

となることである．

T^{∗} ∪ {φ(c)} が consistent とすれば， T^{∗} のモデルで， M^{∗} ⊧ φ(c) となるものが存在する． a ∈ M が与えられたとき， M^{∗} ⊧ ∃y[y > a ∧ φ(y)] （c がその解）だから，

M ⊧ ∃y[y > a ∧ φ(y)].

a ∈ M は任意なので，このことは M ⊧ ∃^{∞}yφ(y) を意味する．

さて， b ∈ M に対して， (partial) type Σ_{b}(x) を

Σ_{b}(x) = {x < b} ∪ {x ≠ d : d ∈ M, d < b}

とする．次の主張がいえればよい（拡張されたタイプの排除定理）．

Claim 2 Σ_{b}(x) は T^{∗} において isolate されない．

Σ_{b}(x) が φ(x, c) によって isolate されたとする．すなわち，

1. T^{∗} ∪ {φ(x, c)} ⊢ x < b;

2. T^{∗} ∪ {φ(x, c)} ⊢ x ≠ d (∀d <_{M} b)

条件１より，特に ∃x < b φ(x, c) は T^{∗} と consistent．したがって， Claim 1 により，

M ⊧ ∃^{∞}y ∃x < b φ(x, y).

b 未満の M の元は（M の意味で）有限個なので，部屋割り論法により，

M ⊧ ∃x < b ∃^{∞}y φ(x, y).  (1)
M ⊧ ∃^{∞}y φ(d, y) (for some d ∈ M with d < b)  (2)

このことは，主張１により，次の集合が consisitent になるこを示す．

T^{∗} ∪ {φ(x, c)} ∪ {x = d}.

これは条件 2 に反する．

9 限量記号の消去

論理記号のうち ∀ と ∃ を限量記号という．与えられた命題が限量記号を使えば論理式で簡単にかけるが，使わないでも工夫をすればかける，という状況がある．たとえば

Example 66 実数構造の上で考えたとき，

• 「方程式ax+b = 0に実数解がある」という命題は，そのまま論理式∃x[ax+b = 0] で表現される．しかし，これは論理式 a ≠ 0 ∨ (a = 0 ∧ b = 0) と同値である．

• 「方程式 ax^{2} +bx+c = 0 に２つの実数解がある」という命題は論理式 ∃x∃y[x ≠ y ∧ ax^{2} + bx + c = 0 ∧ ay^{2} + by + c = 0] で表現されるが，中学生も知っているように，これは a ≠ 0 ∧ b^{2} − 4ac > 0 という論理式と同値である．

そこで，次の定義を与える．

Definition 67 T を L-閉論理式の一つの集合でモデルを持つと仮定する．

1. L-論理式 φ に限量記号が現れないとき， φ を限量記号のない論理式（quantifier free formula）とよぶ．（当たり前の話）

2. すべての L-論理式 φ(x̄) が T のもとで限量記号のない論理式 ψ(x̄) と同値（すなわち T の任意のモデル M において M ⊧ ∀x̄[φ(x̄) ↔ ψ(x̄)]）になるとき， T は限量記号の消去を許すという．

3. tp(ā/A) は ā によって満たされる L(A)-論理式全体の集合であった． ā によって満たされる限量記号のない L(A)-論理式全体の集合を qftp_{M}(ā/A) あるいは簡単に qftp(ā/A) とかくことにする．さらに， A = ∅ のときは単に qftp(ā) とかく． Remark 68 T が限量記号の消去を許すとき，勝手な M ⊧ T, ā ∈ M, A ⊂ M に対して， qftp(ā/A) ⊢ tp(ā/A)である．（すなわち，左辺の情報から右辺の情報がでる．今の場合， φ(x̄) ∈ tp(ā/A) に対して， ψ(x̄) ∈ qftp(ā/A) がとれて， M ⊧ ∀x̄[ψ(x̄) → φ(x̄)]．）

Exercise 69 T を完全として， M を T の ℵ_{0}-飽和なモデルとする．「qftp(ā) = qftp(b̄) ⇒ tp(ā) = tp(b̄)」が常に成立すれば， T は限量記号の消去を許す．ヒント：φ(x̄) が限量記号を持たない論理式とは同値にならないとする． Ψ(x̄) を M ⊧ ∀x̄[ψ(x̄) → φ(x̄)] となる限量記号を持たない論理式 ψ(x̄) 全体の集合とする． {φ(x̄)}∪{¬ψ(x̄) : ψ ∈ Ψ} は有限充足的である．したがって解 ā ∈ M がある．このとき， qftp(ā) ∪ {¬φ(x̄)} も有限充足的である．よって解 b̄ ∈ M がある．これは仮定「qftp(ā) = qftp(b̄) ⇒ tp(ā) = tp(b̄)」に反する．

Lemma 70 T は限量記号のない閉論理式に対しては完全とする．このとき， T に関する次の３条件は同値である．

1. T は完全でなおかつ限量記号の消去を許す．

2. M と N が ℵ_{0}-飽和な T の任意のモデルのとき，有限列 ā ∈ M, b̄ ∈ N が

qftp_{M}(ā) = qftp_{N}(b̄)

を満たせば，任意の a ∈ M に対して， b ∈ N を選ぶことにより

qftp_{M}(ā, a) = qftp_{N}(b̄, b)

とできる．

3. 条件２において， M,N を (|L|+ℵ_{0})^{+}-飽和， ā,b̄を有限列でなく，長さが (|L|+ℵ_{0}) 以下の列としたもの．

Proof ：最初に (|L| + ℵ_{0}) は L-論理式の個数を表していることに注意する．

1 ⇒ 2: T が限量記号の消去を許せば，「qftp_{M}(ā) = qftp_{N}(b̄) ⇒ tp_{M}(ā) = tp_{N}(b̄)」が成り立つ．このことに注意すれば明らか．（演習問題??参照のこと．）

2 ⇒ 3: 飽和性による． p(x̄, x) = qftp(ā, a) とおく． x̄ の中の有限個の変数 x_{1}, ..., x_{n} に注目する． p に属する論理式の中で自由変数が x_{1}, ..., x_{n}, x だけのものを集めて q(x_{1}, ..., x_{n}, x) とする．条件２から q(b_{1}, ..., b_{n}, x) は解 b を持つ．このことは p(b̄, x) の N における有限充足性を示す．よって， N の飽和性により p(b̄, b) となる b ∈ N が存在する．この b が求めるもの．

3 ⇒ 1: 簡単のために L は可算とする．３であるが１でないと仮定して矛盾を導く． T は完全でないか，または，限量記号の消去をしない．

最初に T は完全だが，限量記号を消去しない場合を扱う．限量記号のない論理式に対して完全な集合 q(x̄) と論理式 φ(x) を見つけて， T ∪ q(x̄) ∪ {φ(x̄)} と T ∪ q(x̄) ∪ {¬φ(x̄)} の両方がモデルを持つようにできる（演習問題??参照のこと）．したがって， ℵ_{1}-飽和な T のモデル M と N を選び， a ∈ M は q(x̄) ∪ {φ(x̄)} の解， b ∈ N は q(x̄) ∪ {¬φ(x̄)} の解とできる． M_{0} ≺ M を a_{0} ∈ M_{0} となる可算モデルとする． M_{0} の元を一列にならべて，順に条件３を用いることにより， N_{0} ⊂ N を b_{0} ∈ N でかつ， qftp(a, M_{0}) = qftp(b, N_{0}) となるように選ぶことができる．次に N_{1} ≺ N を N_{0} の拡大となる可算モデルとする．これに対して条件３を使って， M_{1} ≺ M を M_{0} の拡大で， qftp(a, M_{0}, M_{1}) = qftp(b, N_{0}, N_{1}) となるように選ぶ．以下同様に条件３を繰り返し使って，偶数番めは M から先に M_{i} をとり，奇数番めは先に N_{i} を選んで，

qftp_{M}(a, M_{0}, M_{1}, ...) = qftp_{N}(b, N_{0}, N_{1}, ...)

が成り立つようにする．偶数 i に対して， M_{i} ≺ M だから ⋃_{i∈ω} M_{i} ≺ M．同様に ⋃_{i∈ω} N_{i} ≺ N．またこれらの間には a を b におくる同型がある（qftp が等しい）から， tp_{M}(a) = tp_{N}(b) を得る．これは ā ∈ M, b̄ ∈ N の取り方に反する．

次に T が完全でない場合は， T ∪ {φ}, T ∪ {¬φ} がともにモデルを持つように閉論理式 φ をとる．後は上の場合と同じ証明で矛盾にいたる．注意すべきは，今回は ā, b̄ が空列の場合からはじめるので， T が限量記号のない閉論理式に対して完全である，という仮定が必要になる．

最後に実閉体の限量記号消去について述べる．実閉体の公理にはいくつかの同値なものが知られているが，我々は以下のかなり技術的なものを採用する：

Definition 71 体の言語を L_{field} = {0, 1, +, ·}, 順序体の言語を L_{of} = L_{field} ∪ {<} とする．

1. 順序体の公理は（１）体の公理および（２） < が算法と両立することを主張する公理からなる．

2. 実閉体の公理 RCF とは言語 L_{of} でかかれた次の閉論理式の集合のことである：（１）順序体の公理（２）任意の１変数多項式は１次式 x − a および２次式 x^{2} + bx + c （ただし D = b^{2} − 4c < 0）の形の因子の積で表わされる．

3. 実閉体（順序体）の公理を満たす L_{of}-構造を実閉体（順序体）という．

Remark 72 1. ℝ が実閉体になることは見やすい：実際，実係数の多項式が解 a+bi を持てば， a − bi も解である（a, b ∈ ℝ）．よって， x^{2} + 2ax + (a^{2} + b^{2}) で割れ

る．また， D = −4b^{2} < 0 である．

2. 実閉体では，奇数次の方程式は解を持つ：奇数次多項式 f(x) を分解すれば，必ず (x − a) の形の因子を持つ．

3. 実閉体では正の数は必ず平方数として表される： a > 0 として， x^{2} − a を考える． D = 4a > 0 だから， x^{2} − a は一次因子の積に表わされなければならない．すなわち， x^{2} − a = (x + b)(x − b) = x^{2} − b^{2} となる．

Fact 73 順序体 K は実閉体への拡大を持つ．また，それら実閉体への拡大の中で最小なもの（実閉包）が存在する．

Theorem 74 実閉体の公理 RCF は完全でなおかつ限量記号の消去を許す．

Proof ： RCF のモデルは標数が０である．したがって， RCF は限量記号のない論理式については完全である． M,N を RCF の ℵ_{1}-飽和なモデルとする．

可算無限列 ā ∈ M と b̄ ∈ N の qftp が等しいとする．したがって ā で生成される順序体 Kā ⊂ M と b̄ で生成される順序体 Lb̄ ⊂ N は L_{of}-同型になる．よって，さらにそれらの実閉包 K ⊂ M と L ⊂ N の間にも ā を b̄ に移す L_{of}-同型がある．すなわち qftp(ā, K) = qftp(b̄, L) である． a ∈ M を勝手にとる．

qftp(ā, K, a) = qftp(b̄, L, b)

となる b ∈ L の存在が示されれば，補題?? により定理が示されたことになる． a ∉ K と仮定してよい．このとき， qftp(a/ā, K) には自明でない方程式 f(x) = 0 は属さない．（もし自明でない方程式 f(x) = 0 を a が満たせば， f の因子に (x − a) が存在する．よって a ∈ K でなければならない．）したがって，

qftp(a/ā) = {f_{i}(x) ≠ 0 : i < ω} ∪ {g_{i}(x) > 0 : i < ω}

と考えてよい．しかし f(x) ≠ 0 は f(x) > 0 ∨ f(x) < 0 と同値なことと qftp(a/ā) は限量記号のない論理式に対して完全なことを考え合わせれば，

qftp(a/ā, K) = {g_{i}(x) > 0 : i < ω}

の形と思ってよい．実閉体の条件（２）を使って，各 g_{i}(x) を K[x] で分解する：

g_{i}(x) = d ∏_{j∈J_{1}}(x − a_{j}) ∏_{j∈J_{2}}(x^{2} − b_{j}x + c_{j}).

d ∏_{j∈J_{2}}(x^{2} − b_{j}x + c_{j}) の符号は一定である．よって， {a_{j} : j ∈ J_{1}} ∪ {±∞} の部分集合 {e_{1} < e^{1}, ⋯, e_{m} < e^{m}} を選んで， g_{i}(x) > 0 ↔ x ∈ ⋃_{j}(e_{j}, e^{j}). 各 g_{i} > 0 に対して，このような同値変形を行ない， qftp(a/ā) の完全性を再び考えると，両端が K の元で定義される開区間 I_{i} を使って，

qftp(a/ā, K) = {x ∈ I_{i} : i < ω}

と考えることができる．ここで注意すべき点がある．それは，上の等号は， T （と qftp(ā, K) の情報）のもとで同等という意味である．特に右辺の情報から左辺の情報が出てくるところが重要．仮定から K と L の間には ā を b̄ を移す L_{of}-同型がある．したがって， I_{i} に対応する L での区間 J_{i} がある． p(x, ā, K) = qftp(a/ā, K) とおいって， p(x, b̄, L) を考えると，上の注意から p(x, b̄, L) = {x ∈ J_{i} : i < ω} で，右辺は有限充足的． N の飽和性から {x ∈ J_{i} : i < ω} の解 b ∈ N がとれる．この b に対して， qftp(ā, K, a) = qftp(b̄, L, b) である．

Definition 75 体の言語 L_{field} = {0, 1, ∗+∗, −∗, ∗·∗, ∗^{−1}} でかかれた閉論理式の集合：

1. 体の公理，および

2. 各 n ∈ ω − {0} に対して， n 次代数方程式が解を持つことを主張する論理式 ∀a_{0} ⋯ ∀a_{n}[a_{0} ≠ 0 → ∃x(a_{0}x^{n} + ⋯ a_{n−1}x + a_{n} = 0)]

を代数閉体の公理とよび， ACF であらわす． ACF にその体の標数が p であることを付加した公理を ACF_{p} とかく．

Remark 76 標数が p > 0 であることは，論理式\underbrace{1 + 1 + ⋯ + 1}_{p} = 0 で表される．ま

た標数が 0 ということは，無限個の閉論理式\underbrace{1 + 1 + ⋯ + 1}_{n} ≠ 0 （n ∈ ω）で表さ

れる．

Theorem 77 （代数閉体の限量記号消去） ACF_{p} は完全でなおかつ限量記号の消去を許す．

Proof ：補題??を使う． M, N を ℵ_{0}-飽和な ACF_{p} のモデルとする． ā ∈ M と b̄ ∈ N が同じ qftp を持っていると仮定する． a ∈ M を勝手にとる．対応する b ∈ N がとれればよい．

Case 1. a が ā 上の超越元のとき． N は ℵ_{0}-飽和だから， b̄ 上の超越元 b ∈ N が存在する．このとき， qftp(ā, a) = qftp(b̄, b) である．実際 “f(x̄, x) = 0” ∈ qftp(ā, a) とすれば， a の超越性から f は x を真には含まない（x に関する多項式として係数はすべて０）．よって， qftp(ā) = qftp(b̄) により， f(b̄, x) の係数もすべて０．よって， f(b̄, b) = 0 である．（“f ≠ 0” ∈ qftp(ā, a) ならば “f ≠ 0” ∈ qftp(b̄, b) も同様に示される．） Case 2. a が ā 上代数的なとき． k を ā によって生成される部分体として， a の k 上の最小多項式を f(x) とする． f は何倍かすることにより，素体上の多項式 f(x̄, x) の x̄ に ā を代入した形と思ってよい（f(x) = f(ā, x)）． f の中の ā たちの項による係数部分を対応する b̄ たちによる項で置き換えた多項式を g(x) とする． g(x) = 0 は N で解を持つ．それを b ∈ N とすれば qftp(ā, a) = qftp(b̄, b) が成立する．（逆も同様なので）次を示せばよい：

Claim A h(x) を k 上の多項式とするとき， h(a) = 0 ならば hb̄(b) = 0 である．ただし， hb̄(x) は h の中に現れる ā を b̄ で置き換えてできる多項式．

f の最小性から， h(x) = f(x)q(x) となる k 上多項式がある．この式の係数部分に現れる ā をすべて b̄ で置き換えると， ā と b̄ の quantifier free type が等しいことから， hb̄(x) = g(x)qb̄(x) となる． b のとり方から， g(b) = 0．したがって， hb̄(b) = 0 を得る．

Definition 78 微分体の言語 L_{df} とは体の言語 L_{field} に１変数関数記号 D を付加した言語のことである． L_{df} = L_{field} ∪ {D}．

1. 微分体の公理とは，次の閉論理式の集合のことである：

(a) 標数０の体の公理および

(b) 微分に関する公理， ∀xy[D(x + y) = D(x) + D(y)], ∀xy[D(xy) = xD(y) + D(x)y]．

2. 変数 x に D を m 回ほどこしたものを D^{m}(x) あるいは x^{(m)} とかく．

3. g を L_{field}-多項式とする． g に現れる変数に D^{m}x_{i} たち（i ≤ n ; m ∈ ω）を代入してできる L_{df} の項 f(x_{0}, ..., x_{n}) を変数 x_{0}, ..., x_{n} を持つ微分多項式とよぶ． f(x_{0}, ..., x_{n}) = 0 の形の論理式を微分方程式とよぶ．

4. f(x_{0}, ..., x_{n}) が微分多項式のとき，その中に真に現れる D^{m}x_{i} の最大の m を f の階数という．階数が m のとき， f の（変数とみた） D^{m}x_{i} たちに関する次数を微分多項式 f の次数とよぶ．

Remark 79 体 K が与えられたとき，その上の微分を恒等的に０と定めれば微分体となる．

Definition 80 （微分閉体）微分体の公理にさらに次の公理を付加したものを微分閉体の公理（DCF）とよぶ： (*) 各微分方程式は generic な解を持つ：各 m 階微分多項式 f(x̄) と m − 1 階以下の

恒等的に０でない微分多項式 g(x̄) に対する，論理式 ∃x̄(f(x̄) = 0 ∧ g(x̄) ≠ 0). たち．（ただし， f,g は係数部分に x̄ 以外の変数を含んでいる．）

０階の微分方程式は単なる多項式である（また-1 階の微分方程式は存在しない）．したがって，上の (*) は特に「体が代数閉体であること」を含んでいる．また，与えられた有限個の微分方程式 g_{1}, ..., g_{n} の階にならない元の存在も (*) から言える．

Exercise 81 上の定義の (*) の部分を正確に閉論理式の集合として表わせ．

Fact 82 微分体は微分閉体に拡大される．

Theorem 83 （微分閉体の限量記号消去） DCF は完全でなおかつ限量記号の消去を許す．

Proof ：代数閉体の限量記号消去の議論とほぼ平行に行える．例によって， M ,N を DCF の ℵ_{0}-飽和なモデルとする． ā ∈ M と b̄ ∈ N を qftp が等しい有限列とする． a ∈ M を勝手にとる．対応する b ∈ N をさがす．

Case 1. a が ā 上の（自明でない）微分方程式を満たさない．（このとき a は ā 上微分超越的ということにする．） DCF の公理 (*) と N の飽和性により， b ∈ N で b̄ 上微分超越的なものが存在する．このとき qftp(ā, a) = qftp(b̄, b) である．

Case 2a が b̄ 上の（自明でない）微分方程式を満たす．（このとき a は ā 上微分代数的ということにする．） ā で生成される微分体を k とする． k 係数の微分方程式で， a によって満たされるもののうち，組（階数 m， x^{(m)} の次数）が最小になる f(x) をとる． f の中のパラメータを対応する N の元で置き換えたものを g とする． g(x) = 0 の generic な解を b とする．（すなわち， g(x) = 0 の解で g の階数未満の微分方程式の解にならないもの．） g よりも x^{(m)} に関する次数が低い h によって， b が満たされたとする．このような最小次数の h をとっておく．このとき， x^{(m)} の多項式としての g を h で割って， g = hk + r の形に分解すれば， h の最小性から， r = 0．よって g は因数分解される．このことは係数だけの問題なので，係数が同型である f も因数分解される．これは f の最小性に反する．後は代数閉体と同じ議論である．