コンパクト性定理 | 数理論理 | 天游ヶ丘数理学院

1 充足可能性に関するコンパクト性

$T_0\subseteq_{\mathrm{fin}}T$ は、 $T_0$ が $T$ の有限部分集合であることを表す。

定理 1.1 (一階論理のコンパクト性定理). 集合サイズの有限項言語 $L$ と理論 $T\subseteq\operatorname{Sent}(L)$ について、次は同値である。

$T$ は充足可能である。
すべての有限部分集合 $T_0\subseteq_{\mathrm{fin}}T$ は充足可能である。

証明の方針は、有限充足可能性から $T$ の構文的無矛盾性を示すことである。 $T$ が矛盾を証明するなら、その有限証明で用いた有限個の前提だけでも矛盾を証明する。

証明.条件 (a) $\Rightarrow$ (b)を示す。 $T$ が充足可能なら、そのモデルはすべての $T_0\subseteq T$ を満たす。

条件 (b) $\Rightarrow$ (a)を示す。逆に、すべての有限部分集合 $T_0\subseteq_{\mathrm{fin}}T$ が充足可能であるとする。 $T$ が構文的に矛盾すると仮定する。すると $T\vdash\bot$ である。§E16.10 系 5.2により、ある有限部分集合 $T_0\subseteq_{\mathrm{fin}}T$ が存在して $T_0\vdash\bot$ となる。一階 Hilbert 系の健全性から $T_0\models\bot$ である。 $\bot$ はどの構造でも偽なので、 $T_0$ は充足不可能であり、有限充足可能性の仮定に反する。

したがって $T$ は構文的に無矛盾である。§E16.12 定理 4.1により $T$ はモデルをもち、充足可能である。▨

注意 1.2 (個別の充足可能性では足りない). 定数記号 $c$ と一項関係記号 $P$ をもつ言語で、 $P(c)$ と $\neg P(c)$ はそれぞれ単独では充足可能である。しかし、二つを合わせた有限集合 $\{P(c),\neg P(c)\}$ は充足不可能である。したがって、各文の個別の充足可能性はコンパクト性定理の仮定ではない。

2 帰結に関するコンパクト性

定理 2.1. $T\subseteq\operatorname{Sent}(L)$ と $\varphi\in\operatorname{Sent}(L)$ について、 $T\models\varphi$ なら、ある有限部分集合 $T_0\subseteq_{\mathrm{fin}}T$ が存在して $T_0\models\varphi$ である。

証明. $T\models\varphi$ とする。強完全性定理により $T\vdash\varphi$ である。§E16.10 系 5.2により、ある有限部分集合 $T_0\subseteq_{\mathrm{fin}}T$ が存在して $T_0\vdash\varphi$ である。健全性により $T_0\models\varphi$ を得る。▨

命題 2.2.定理 1.1の充足可能性版と定理 2.1の帰結版は、健全性や完全性を改めて用いなくても互いに導くことができる。

証明. まず帰結版を仮定する。 $T$ の各有限部分集合が充足可能であるにもかかわらず $T$ が充足不可能であるとする。充足不可能な理論は任意の文を意味論的に帰結するので、特に $T\models\bot$ である。帰結版により、 $T_0\models\bot$ を満たす有限集合 $T_0\subseteq T$ が存在する。この帰結は $T_0$ が充足不可能であることを意味し、有限部分集合に関する仮定に反する。したがって充足可能性版が従う。

逆に充足可能性版を仮定し、 $T\models\varphi$ とする。 $T\cup\{\neg\varphi\}$ は充足不可能である。充足可能性版の対偶により、充足不可能な有限部分集合 $S\subseteq T\cup\{\neg\varphi\}$ が存在する。 $T_0=S\cap T$ とおく。 $T_0$ は有限である。 $\neg\varphi\in S$ なら、 $T_0\cup\{\neg\varphi\}$ が充足不可能なので $T_0\models\varphi$ である。 $\neg\varphi\notin S$ なら $T_0=S$ 自身が充足不可能であり、この場合も空虚に $T_0\models\varphi$ である。したがって帰結版が従う。▨

3 無限モデルの存在

有限個の一階文だけでは、構造が指定した有限の大きさ以上であるという条件を有限個しか要求することができない。この性質を用いて、任意に大きい有限モデルから一つの無限モデルを構成する。

正の整数 $n$ に対して、 $\eta_n$ を

\exists x_0\cdots\exists x_{n-1} \bigwedge_{0\le i<j<n}x_i\ne x_j

とする。 $\eta_n$ は台集合に相異なる $n$ 個の要素が存在することを述べる。

定理 3.1. $T$ を $L$ 理論とする。すべての正の整数 $n$ について、濃度が $n$ 以上である有限モデル $M_n\models T$ が存在すると仮定する。このとき $T$ は無限モデルをもつ。

証明.

T^*=T\cup\{\eta_n\mid 1\le n<\omega\}

とおく。 $T^*$ の任意の有限部分集合 $S$ を取る。 $S$ に現れる $\eta_n$ の添字の最大値を $N$ とする。 $S$ に $\eta_n$ が現れない場合は $N=1$ とする。仮定により、濃度が $N$ 以上である有限モデル $M_N\models T$ が存在する。 $M_N$ は $S\cap T$ と、 $S$ に現れるすべての $\eta_n$ を同時に満たす。したがって $T^*$ の各有限部分集合は充足可能である。

定理 1.1により $T^*$ はモデル $M$ をもつ。 $M$ はすべての $\eta_n$ を満たすため、任意の正の整数 $n$ に対して相異なる $n$ 個の要素をもつ。したがって $M$ は無限であり、 $M\models T$ である。▨

例 3.2 (有限線形順序から無限線形順序へ). 線形順序の公理からなる理論を $T_{\mathrm{lo}}$ とする。各正の整数 $n$ について $n$ 要素の線形順序が存在するので、定理 3.1により $T_{\mathrm{lo}}$ は無限モデルをもつ。この応用は無限線形順序を具体的に構成しないが、すべての有限下界を一つのモデルで同時に満たす。

4 有限構造全体は一階理論のモデル類ではない

定理 4.1. $L$ を集合サイズの有限項言語とする。 $L$ の有限構造全体をモデル類としてもつ一階理論 $T\subseteq\operatorname{Sent}(L)$ は存在しない。

証明. そのような理論 $T$ が存在すると仮定する。

T^*=T\cup\{\eta_n\mid 1\le n<\omega\}

とおく。 $T^*$ の有限部分集合 $S$ を任意に取る。 $S$ に現れる $\eta_n$ の添字より大きい正の整数 $N$ を選ぶ。 $N$ 要素集合上には $L$ 構造を定めることができる。各定数記号には一つの要素を割り当て、正の項数の各関数記号は一つの固定要素を返す関数として解釈し、各関係記号は空関係として解釈すればよい。得られた構造は有限なので、仮定により $T$ のすべての文を満たす。また、台集合が $N$ 要素をもつため、 $S$ に現れるすべての $\eta_n$ を満たす。したがって $S$ は充足可能である。

定理 1.1により $T^*$ はモデル $M$ をもつ。 $M$ はすべての $\eta_n$ を満たすので無限である。一方 $M\models T$ なので、 $T$ のモデルはすべて有限であるという仮定に反する。したがって有限 $L$ 構造全体を一階理論のモデル類として指定することができない。▨

注意 4.2 (各有限濃度を一文で指定することとの違い). 固定した正の整数 $n$ について、台集合の濃度がちょうど $n$ であることは一つの一階文で表すことができる。相異なる $n$ 個の要素の存在に加え、すべての要素がそのいずれかに等しいと述べればよい。不可能なのは、有限な濃度のどれかであるという無限選言を、一階理論のモデル類として一括して指定することである。

5 演習

問題 5.1.

各文が個別に充足可能であることと、各有限部分理論が充足可能であることの違いを例で説明せよ。
$T\models\varphi$ の証明が実際に用いる前提を有限個へ減らす論証を書け。
定理 3.1で、 $T$ の各有限部分だけでなく $T$ 全体の大きい有限モデルを仮定した理由を説明せよ。
「無限構造全体」は一階理論のモデル類になることを示し、「有限構造全体」と比較せよ。

解答 (確認問題の解答).

$P(c)$ と $\neg P(c)$ はそれぞれ単独では充足可能であるが、二文からなる有限集合は充足不可能である。
強完全性により $T\vdash\varphi$ である。一つの導出は有限列なので、その中で前提として使う $T$ の文は有限個である。導出で用いた前提の集合を $T_0$ とすれば $T_0\vdash\varphi$ であり、健全性から $T_0\models\varphi$ となる。
有限部分 $S$ を満たすとき、 $S\cap T$ と最大の濃度下界 $\eta_N$ を同時に満たす一つのモデルが必要である。 $T$ 全体の大きい有限モデルがあれば、この同時充足可能性が直ちに従う。
無限構造全体は文集合 $\{\eta_n\mid1\le n<\omega\}$ のモデル類である。各有限構造 $\mathcal M$ には、 $\mathcal M\not\models\eta_n$ を満たす正整数 $n$ が存在するため、その構造は除かれ、各無限構造はすべてを満たす。有限構造全体を指定しようとすると、コンパクト性がすべての有限下界を満たす無限モデルを生じさせる。

▨

§E16.13コンパクト性定理

1 充足可能性に関するコンパクト性

2 帰結に関するコンパクト性

3 無限モデルの存在

4 有限構造全体は一階理論のモデル類ではない

5 演習

参考文献

前提記事