コンパクト性定理(一階論理)

どの有限部分集合 $T_0$ についても $T_0\not\models\varphi$ だと仮定する。すると各 $T_0$ に対し、$T_0$ のモデルで $\varphi$ が偽になるもの、すなわち $T_0\cup\{\lnot\varphi\}$ のモデルがある。$T\cup\{\lnot\varphi\}$ の有限部分集合は $T_0\cup\{\lnot\varphi\}$ の部分集合だから、$T\cup\{\lnot\varphi\}$ は有限充足可能である。thm-compactness-first-order によりモデル $M$ があり、$M\models T$ かつ $M\models\lnot\varphi$ となって $T\models\varphi$ に反する。$\square$

論理結合子は $\lnot,\land$、量化記号は $\exists$ だけを使うとしてよい（$\lor,\to,\forall$ はこれらで同値に書き換えられる）。右辺の添字集合を $S(\varphi(\bar f)):=\{i\in I: M_i\models\varphi(\bar f(i))\}$ と書き、論理式の構成に関する帰納法で示す。$M:=\prod_i M_i/U$ とおく。

項。 項 $t(\bar x)$ について $t^M([\bar f])=[\,i\mapsto t^{M_i}(\bar f(i))\,]$ が成り立つ。変数と定数記号では定義そのもの、$t=F(t_1,\ldots,t_m)$ では帰納法の仮定と $F^M$ の定義から従う。

原子論理式。 $t_1=t_2$ については、上の式から $M\models t_1=t_2$ は $[\,i\mapsto t_1^{M_i}(\bar f(i))\,]=[\,i\mapsto t_2^{M_i}(\bar f(i))\,]$ と同じで、$\sim_U$ の定義によりこれは $S(t_1=t_2)\in U$ と同値である。$R(t_1,\ldots,t_m)$ も $R^M$ の定義からそのまま従う。

否定。 $M\models\lnot\varphi([\bar f])$ は $M\not\models\varphi([\bar f])$ であり、帰納法の仮定により $S(\varphi(\bar f))\notin U$ と同値である。超フィルターの性質 (iv) により、これは $I\setminus S(\varphi(\bar f))=S(\lnot\varphi(\bar f))\in U$ と同値である。

連言。 $S((\varphi\land\psi)(\bar f))=S(\varphi(\bar f))\cap S(\psi(\bar f))$ であり、(ii)(iii) により「$A\cap B\in U$」と「$A\in U$ かつ $B\in U$」は同値である。これと帰納法の仮定を合わせればよい。

存在量化。 $\varphi(\bar x)=\exists y\,\psi(y,\bar x)$ とする。$M\models\varphi([\bar f])$ なら、ある $[g]$ で $M\models\psi([g],[\bar f])$ となる。帰納法の仮定により $S(\psi(g,\bar f))\in U$ であり、この集合は $S(\varphi(\bar f))$ に含まれるので (iii) より $S(\varphi(\bar f))\in U$ である。逆に $A:=S(\varphi(\bar f))\in U$ とする。各 $i\in A$ について $M_i\models\psi(b,\bar f(i))$ となる $b\in\lvert M_i\rvert$ を一つずつ選び（選択公理）、それを $g(i)$ とする。$i\notin A$ では $g(i)\in\lvert M_i\rvert$ を任意に選ぶ（台集合は空でない）。すると $S(\psi(g,\bar f))\supseteq A\in U$ なので、帰納法の仮定により $M\models\psi([g],[\bar f])$、したがって $M\models\varphi([\bar f])$ である。$\square$

$T$ を有限充足可能とする。$I$ を $T$ の有限部分集合全体とする（$\emptyset\in I$ なので $I\neq\emptyset$）。各 $s\in I$ について、仮定により $s$ のモデル $M_s$ を一つ選ぶ（選択公理）。

各 $s\in I$ に対し $J_s:=\{t\in I: s\subseteq t\}$ とおく。$s\in J_s$ なので $J_s\neq\emptyset$ であり、
$$ J_{s_1}\cap\cdots\cap J_{s_k}=J_{s_1\cup\cdots\cup s_k}\neq\emptyset $$
が成り立つ。すなわち族 $\{J_s: s\in I\}$ は有限交叉性をもつ。したがって
$$ \mathcal F:=\{A\subseteq I: \text{ある } s\in I \text{ について } J_s\subseteq A\} $$
は $\emptyset$ を含まないフィルターである（$J_s\cap J_{s'}=J_{s\cup s'}$ から有限交叉で閉じ、上に閉じていることは定義から明らか）。フィルターの記事の「超フィルターの補題」（選択公理から従う）により、$\mathcal F$ を含む超フィルター $U$ が存在する。

$M:=\prod_{s\in I}M_s/U$ とおき、$M\models T$ を示す。$\sigma\in T$ を任意にとる。$t\in J_{\{\sigma\}}$ なら $\sigma\in t$ で $M_t\models t$ だから $M_t\models\sigma$ である。よって
$$ \{t\in I: M_t\models\sigma\}\supseteq J_{\{\sigma\}}\in\mathcal F\subseteq U $$
であり、左辺は $U$ に属する。thm-compactness-los を文 $\sigma$（自由変数なし）に適用すれば $M\models\sigma$ を得る。$\sigma$ は任意なので $M$ は $T$ のモデルである。$\square$

有限交叉性をもつ閉集合族 $\{C_k\}$ の共通部分が空でないことを示せばよい。$[\sigma]$ の補集合は $[\lnot\sigma]$ なので、各閉集合は $[\sigma]$ の形の集合の共通部分である。そこで $\Sigma:=\{\sigma: \text{ある } k \text{ について } C_k\subseteq[\sigma]\}$ とおくと $\bigcap_k C_k=\bigcap_{\sigma\in\Sigma}[\sigma]$ である。$\sigma_1,\ldots,\sigma_m\in\Sigma$ がそれぞれ $C_{k_1},\ldots,C_{k_m}$ を含むとすると、$C_{k_1}\cap\cdots\cap C_{k_m}$ は空でないので、その元 $p=\operatorname{Th}(M)$ について $M\models\sigma_1,\ldots,\sigma_m$ である。よって $\Sigma$ は有限充足可能で、コンパクト性定理によりモデル $N$ をもつ。$\operatorname{Th}(N)\in\bigcap_{\sigma\in\Sigma}[\sigma]$ なので共通部分は空でない。$\square$

$T':=T\cup\{\theta_n:n\geq1\}$ を考える。有限部分集合 $T_0\subseteq T'$ に現れる $\theta_n$ の添字の最大値を $N$ とする（$\theta_n$ が現れなければ $N=1$）。仮定により $T$ の有限モデル $M$ で元が $N$ 個以上のものがあり、$M$ は $T$ のすべての文と $\theta_1,\ldots,\theta_N$ を満たすので $M\models T_0$ である。よって $T'$ は有限充足可能で、thm-compactness-first-order によりモデル $M'$ をもつ。$M'$ はすべての $\theta_n$ を満たすから無限であり、$T$ のモデルである。$\square$

1. そのような $T$ があれば、$T$ は任意に大きい有限モデルをもつので、prop-compactness-infinite-model により無限モデルももち、仮定に反する。
2. そのような $\sigma$ があれば、$\{\lnot\sigma\}$ のモデルはちょうど有限構造全体となり、(1) に反する。$\square$

そのような $T$ があると仮定する。新しい定数記号 $c_0,c_1,c_2,\ldots$ を加え、$T':=T\cup\{c_{n+1}< c_n:n\in\mathbb N\}$ とおく。有限部分集合 $T_0$ に現れる定数の添字の最大値を $N$ とし、整列順序集合 $(\mathbb N,<)$ で $c_k$ を $N-k$（$k\leq N$）、$c_k$ を $0$（$k>N$）と解釈する。$T_0$ に現れる $c_{n+1}< c_n$ は $n+1\leq N$ を満たすので $N-n-1< N-n$ となって真であり、$(\mathbb N,<)$ は整列順序なので $T$ も満たす。よって $T'$ は有限充足可能で、モデル $M$ をもつ。$M$ の $<$ だけへの制限は $T$ のモデルなので整列順序のはずだが、$c_0^M>c_1^M>c_2^M>\cdots$ は最小元をもたない空でない部分集合 $\{c_n^M\}$ を与え、矛盾する。$\square$

言語 $L$ を、各頂点 $v\in V$ に対応する定数記号 $c_v$ と一変数の関係記号 $P_1,\ldots,P_k$ からなるものとする（$V$ が非可算なら $L$ も非可算）。$T$ を次の文全体とする。

• 各 $v\in V$ について $P_1(c_v)\lor\cdots\lor P_k(c_v)$。
• 各 $v\in V$ と $j\neq j'$ について $\lnot(P_j(c_v)\land P_{j'}(c_v))$。
• 各辺 $\{u,v\}\in E$ と各 $j$ について $\lnot(P_j(c_u)\land P_j(c_v))$。

有限部分集合 $T_0\subseteq T$ に現れる頂点の集合を $V_0$ とし、$G[V_0]$ の $k$ 彩色 $\chi_0\colon V_0\to\{1,\ldots,k\}$ をとる。台集合 $V$、$c_v:=v$、$P_j:=\{v\in V_0:\chi_0(v)=j\}\cup\{v\notin V_0: j=1\}$ とした構造は、$T_0$ のすべての文を満たす（$T_0$ の辺の文は $V_0$ 内の辺についてのもので、$\chi_0$ が彩色だから真）。よって $T$ は有限充足可能で、モデル $M$ をもつ。$\chi(v):=$「$M\models P_j(c_v)$ となるただ一つの $j$」と定めると、最初の二種類の文により $\chi$ は well-defined であり、三種類目の文により隣接する頂点は異なる色をもつ。$\square$