第8章コンパクト性とレーヴェンハイム–スコーレム

完全性が生む、二つの怪物

前章で $\vdash$ と $\models$ が一致しました。この一致から、意味論だけを見ていては信じがたい2つの定理が転がり出ます。コンパクト性定理——無限個の条件の充足可能性が、有限部分の充足可能性に還元される——と、 レーヴェンハイム–スコーレムの定理——理論はモデルの“サイズ”を制御できない。

これらは一階論理の限界を暴きます。「自然数はこういうものだ」といくら公理を並べても、まったく違う（無限に大きな数を含む）モデルが必ず紛れ込む。「実数は非可算だ」と証明できるのに、その理論には可算なモデルもある。一階論理は強力だが、狙ったモデルを一意に切り出すことはできない——この“無力さ”こそ、モデル理論（第9章以降）の豊かさの源泉になります。

コンパクト性とレーヴェンハイム–スコーレムは、一階論理がモデルのサイズや標準性を制御できないことを示す。

コンパクト性定理

定理コンパクト性定理

文の集合 $\Gamma$ がモデルをもつ $\iff$ $\Gamma$ のすべての有限部分集合がモデルをもつ。

証明

$\Rightarrow$ は自明（ $\Gamma$ のモデルは各有限部分のモデル）。 $\Leftarrow$ ：対偶で「 $\Gamma$ が充足不能なら、ある有限部分が充足不能」を示す。 $\Gamma$ が充足不能 $\Rightarrow$ （完全性の対偶＝モデル存在定理の対偶） $\Gamma$ は矛盾、すなわち $\Gamma\vdash\bot$ 。この導出は有限個の $\Gamma$ の要素 $\Gamma_0$ しか使わないので $\Gamma_0\vdash\bot$ 、健全性より $\Gamma_0$ は充足不能。∎

証明の心臓は第3章と同じ「証明は有限」。無限の意味論的条件（ $\Gamma$ 全体のモデル）が、有限の構文的事実（有限個の証明）に落ちる。これがコンパクト性の正体で、位相のコンパクト性と同じ「無限を有限に圧縮する」原理です。使い方の定石は「望む性質を有限では満たせるが全体では満たせない条件の集まりを作る」。

例超準モデル：無限大の自然数

自然数論 $\mathrm{Th}(\mathbb N)$ （ $\mathbb N$ で真な全文）に、新しい定数 $c$ と無限個の文 $c>0,\ c>1,\ c>2,\dots$ （各 $c>\underline n$ ）を加えた $\Gamma$ を考える。 $\Gamma$ の任意の有限部分は、現れる $\underline n$ の最大値より大きい自然数を $c$ とすれば $\mathbb N$ で充足できる。コンパクト性より $\Gamma$ 全体にモデル $\mathcal M$ がある。 $\mathcal M$ は $\mathbb N$ と同じ一階の文をすべて満たすのに、どの自然数より大きい元 $c$ （無限大の自然数）を含む。これが超準モデル。一階論理は「標準の自然数だけ」を切り出せない。

系有限性は一階で表現できない

「有限なモデルだけをもつ」文の集合で、任意有限の大きさのモデルをもつものは、必ず無限モデルももつ。（ $\exists^{\ge n}$ を全 $n$ で足せば、有限部分は大きな有限モデルで充足でき、コンパクト性で無限モデルが出る。）したがって「有限性」「連結性（グラフ）」などは一階では公理化できない。

上方レーヴェンハイム–スコーレム

コンパクト性から、モデルはいくらでも大きくできることが従います。

定理上方レーヴェンハイム–スコーレム

無限モデルをもつ理論 $T$ は、任意の無限濃度 $\kappa\ge|\mathcal L|$ のモデルをもつ。

証明

濃度 $\kappa$ の新定数 $\{c_\alpha:\alpha<\kappa\}$ を導入し、 $T'=T\cup\{c_\alpha\ne c_\beta:\alpha<\beta<\kappa\}$ を考える。 $T'$ の任意の有限部分は、 $T$ の無限モデル（無限個の相異なる元がある）で有限個の $c_\alpha$ を相異なる元に解釈すれば充足できる。コンパクト性より $T'$ にモデル $\mathcal M$ がある。 $\mathcal M$ は $\kappa$ 個の相異なる元 $c_\alpha^{\mathcal M}$ を含むので濃度 $\ge\kappa$ 。（下方 LS と合わせ、ちょうど $\kappa$ にできる。）∎

「無限モデルが1つでもあれば、どんなに巨大なモデルも作れる」。一階論理はモデルの上限サイズを縛れません。

下方レーヴェンハイム–スコーレム

逆に、モデルは小さくもできます。こちらは初等的部分構造を作る議論です。

定義初等的部分構造

$\mathcal N\subseteq\mathcal M$ が初等的部分構造（ $\mathcal N\preceq\mathcal M$ ）とは、 $\mathcal N$ のパラメータを込めた任意の論理式が、 $\mathcal N$ で真 $\iff$ $\mathcal M$ で真であること（ $\mathcal N$ から見た世界は $\mathcal M$ と一階では区別できない）。

定理下方レーヴェンハイム–スコーレム

可算言語 $\mathcal L$ の構造 $\mathcal M$ と部分集合 $A\subseteq M$ に対し、 $A$ を含み濃度 $\le\max(|A|,\aleph_0)$ の初等的部分構造 $\mathcal N\preceq\mathcal M$ が存在する。特に無限モデルをもつ可算理論は可算モデルをもつ。

証明

（タルスキ–ヴォートの判定法による。） $\mathcal M$ で $\exists x\,\varphi(x,\bar a)$ が真のたびに、それを満たす元 $\mathcal M$ の中から一つ選ぶ関数（スコーレム関数、選択公理を使う）を用意する。 $A$ から出発し、現れるすべての論理式の証人をスコーレム関数で補い続けて閉じた集合 $N$ を作る。 $|\mathcal L|=\aleph_0$ なので各段で補う証人は高々可算個、全体で濃度 $\le\max(|A|,\aleph_0)$ 。タルスキ–ヴォートの判定法（「 $\mathcal M$ で $\exists x\,\varphi$ が真なら、その証人が $N$ に取れる」が成り立てば $\mathcal N\preceq\mathcal M$ ）が、証人を補い続けた構成から満たされ、 $\mathcal N\preceq\mathcal M$ 。∎

スコーレムのパラドックス

上方・下方 LS を集合論に適用すると、有名な“逆説”が現れます。

注意スコーレムのパラドックス

ZFC集合論（第14章）は可算言語の一階理論なので、無矛盾なら下方 LS で可算モデル $\mathcal M$ をもつ。ところが ZFC は「非可算集合が存在する」（例： $\mathbb R$ は非可算）を証明する。可算なモデルの中に「非可算な集合」が居る——矛盾か？

逆説の解消：可算・非可算は「全単射が存在するか」で定義される（第1章的な話）。「 $X$ は非可算」とは「 $X$ と $\mathbb N$ の間の全単射が存在しない」という主張。 $\mathcal M$ の中の集合 $X$ が「 $\mathcal M$ 内で非可算」でも、 その全単射がたまたま $\mathcal M$ の外にあるだけかもしれない。実際、外から見れば $X$ は可算。「非可算性」はモデルに相対的な概念で、絶対的ではない——量化子 $\exists$ が「 $\mathcal M$ の中の対象」しか走らないことの帰結です。

スコーレムのパラドックスは矛盾ではなく、「集合論的概念のモデル相対性」という深い洞察です。この「モデルによって真偽・サイズが変わる」現象を積極的に研究するのが、次のモデル理論であり、第15章の強制法（連続体仮説の独立性）へと直結します。

つまずきポイント

注意よくある誤解

コンパクト性は「有限で充足 ⇒ 全体で充足」。 各有限部分にモデルがあれば全体にもモデルがある。逆は自明。使い方は「無限の要求を有限では満たせるように仕込む」。
一階は標準モデルを指定できない。 $\mathbb N$ の一階理論に超準モデルが必ずある。「標準の自然数」は一階では特徴づけ不能（二階論理なら可能、第10章）。
スコーレムのパラドックスは矛盾でない。 可算・非可算はモデル相対的。全単射が「モデルの外」にあり得る。絶対的な濃度は存在しない。

この章のまとめ

コンパクト性定理（有限充足 ⇒ 全体充足）は完全性＋「証明は有限」から出る。超準モデル・有限性の表現不能など、一階論理の限界を暴く。
上方 LS：無限モデルがあれば任意の巨大濃度のモデルがある（コンパクト性）。下方 LS：可算理論は可算モデルをもつ（スコーレム関数と初等的部分構造）。
スコーレムのパラドックスは、可算・非可算がモデル相対的であることを示す。この相対性がモデル理論・独立性証明の出発点。

ここまでで記号論理学（命題・述語・完全性・コンパクト性）が完成しました。次章から証明論——証明の構造そのものを解析するシークエント計算とカット除去へ進みます。

第8章 コンパクト性とレーヴェンハイム–スコーレム