紧致性定理 · aiwiki.page

紧致性定理是一阶逻辑中的一项基本结果：如果一个语句集的每个有限子集都能被同时满足，那么整个语句集也能被同时满足。它将有限组逻辑要求与可能包含无穷多个语句的理论联系起来，是模型论的核心工具。该定理讨论的是模型的存在性，而不是模型的唯一性，也不提供构造模型的有效程序。(math.berkeley.edu)

表述与解释

设 $L$ 为一阶语言， $T$ 为一组 $L$ -语句，称为一个理论。语句是没有自由变量的公式。 $T$ 的模型是一个 $L$ -结构，其中 $T$ 中的每个语句都为真。紧致性定理断言：

T\text{ 有模型} \quad\Longleftrightarrow\quad \text{每个有限子集 }T_0\subseteq T\text{ 都有模型}.

右侧的条件称为有限可满足性。满足某个有限子集的模型不一定满足另一个有限子集；紧致性保证存在一个满足整个理论的模型。正向蕴涵是显然的，反向蕴涵才是定理的实质内容。该定理适用于任何以集合为规模的语言，包括不可数语言。(math.berkeley.edu)

以下两种等价表述尤其有用：

如果一个理论没有模型，那么它的某个有限子集就已经没有模型。
如果 $T\models\varphi$ ，那么存在有限子集 $T_0\subseteq T$ ，使得 $T_0\models\varphi$ 。

这里， $T\models\varphi$ 表示语义后承关系，即 $T$ 的每个模型都满足 $\varphi$ 。因此，即使某个结论是无穷多个假设的语义后承，它也已是其中有限多个假设的语义后承。将紧致性应用于 $T\cup\{\neg\varphi\}$ ，即可得到这一等价关系。(math.berkeley.edu)

证明方法

由完备性定理推出

哥德尔完备性定理表明，语义后承与形式可推导性相一致。假设 $T$ 不可满足。由完备性可知，存在一个从 $T$ 推出矛盾的形式证明。由于证明是有限的，它只使用有限多个假设，这些假设构成一个子集 $T_0$ 。根据可靠性（逻辑学），这个子集本身也是不可满足的。取其逆否命题，便得到紧致性定理。(math.berkeley.edu)

这一论证区分了两种有限性：每个一阶公式都是有限的表达式，而通常的形式证明只包含有限多个步骤。然而，一个理论可以包含无穷多个语句。(math.berkeley.edu)

亨金构造

一种直接证明使用亨金构造。首先扩充语言，加入为存在性断言提供见证的常量。然后扩展这个有限可满足的理论，使其以一致的方式判定各个语句，并为存在性断言提供见证。接着用闭项构造模型；如果扩展后的理论断言两个项相等，就将它们视为同一个元素。最后，通过对公式的归纳证明，说明这个项模型满足原理论。(math.berkeley.edu)

超积证明

一种模型论证明使用超积和沃希定理。以有限子集 $F\subseteq T$ 为指标选取结构 $M_F$ ，使每个 $M_F$ 都满足 $F$ 。对于每个语句 $\sigma\in T$ ，考虑集合

I_\sigma=\{F\subseteq T:F\text{ 有限且 }\sigma\in F\}.

这些集合具有有限交性质，因此可以包含在某个超滤子 $U$ 中。于是，沃希定理说明

\prod_F M_F/U

满足 $T$ 中的每个语句：对于每个语句，使其成立的指标所构成的集合都属于 $U$ 。(personalpages.manchester.ac.uk)

主要应用

无限模型与更大规模的模型

假设理论 $T$ 有任意大的有限模型。引入常量 $c_0,c_1,\ldots$ ，并加入所有如下语句：

c_i\ne c_j\qquad(i\ne j).

扩充后理论的每个有限子集，都能在 $T$ 的某个足够大的有限模型中得到满足。紧致性给出一个模型，其中所有这些常量都被解释为互不相同的元素，因此它的论域是无限的。(people.math.sc.edu)

更一般地，如果 $T$ 有无限模型，就可以引入以任意指定的无限基数为指标的常量，并要求它们两两不同。紧致性给出一个基数至少达到指定大小的模型。结合勒文海姆—斯科伦定理，便可得到模型，其基数可以是任何不小于语言规模的无限基数。(people.math.sc.edu)

非标准算术

一个经典应用是构造算术的非标准模型。在皮亚诺公理中加入一个新常量 $c$ ，以及以下语句：

c>\overline{0},\quad c>\overline{1},\quad c>\overline{2},\quad\ldots,

其中， $\overline n$ 是表示通常的自然数 $n$ 的数码。只要将 $c$ 解释为一个足够大的数，任何有限组这样的语句都能在通常的算术结构中得到满足。因此，紧致性给出一个模型，其中存在一个比每个标准数码所表示的数都大的元素。这样的模型不可能与通常的自然数结构同构。同样的论证也适用于该结构的完备一阶理论，而不只是皮亚诺公理。(plato.stanford.edu)

图着色

在图论中，紧致性确立了一条从有限情形推广到无限情形的着色原理：对于固定的正整数 $k$ ，如果一个图的每个有限子图都可用 $k$ 种颜色着色，那么整个图也可用 $k$ 种颜色着色。用命题逻辑语句编码每个顶点的可能颜色，要求每个顶点恰有一种颜色，且相邻顶点的颜色不同。每组有限的约束只涉及有限多个顶点，根据假设，它们可以得到满足。命题逻辑的紧致性于是给出整个图的着色。(math.berkeley.edu)

与拓扑紧致性的联系

定理的名称反映了它与拓扑学的联系。对于命题变元集 $P$ ，所有真值赋值构成空间

\{0,1\}^{P},

并赋予它积拓扑，其中 $\{0,1\}$ 取离散拓扑。一个公式只涉及有限多个变元，因此满足该公式的赋值构成一个既开又闭的集合。有限可满足性意味着这些集合具有有限交性质。赋值空间的紧致性进而说明，它们的总交集非空。这正是命题逻辑的紧致性定理。(iep.utm.edu)

一阶逻辑中一个相关的表述使用完备理论构成的空间：语句确定基本的开闭集，而逻辑紧致性对应于所得拓扑空间是紧空间。(pages.jh.edu)

适用范围与局限

紧致性适用于采用通常语义的一阶逻辑；它并不意味着每个更强的逻辑系统都具有紧致性。例如，采用完全语义的二阶逻辑能够表达论域是有限的。将这样的语句与“至少有 $n$ 个元素”的断言合在一起，其中 $n$ 遍历所有正整数，就会得到一个有限可满足但整体不可满足的语句集。(iep.utm.edu)

即使在一阶逻辑内部，将考察范围限制为有限模型也会破坏紧致性。所有断言“至少有 $n$ 个元素”的语句，其每个有限子集都有有限模型，但整个语句集只有无限模型。因此，不存在一个一阶理论，其模型恰好是所有有限结构；不过，无限性可以用这组无穷多个语句来公理化。(math.berkeley.edu)

该定理也不保证能在某个指定结构内部得到模型。在算术的例子中，每组有限的语句都能在通常的自然数结构中得到满足，但整个语句集需要一个不同的结构。(plato.stanford.edu)

历史发展

库尔特·哥德尔在与其1929年博士论文相关的研究中，得到了可数语言的紧致性结果，并于1930年将其与完备性定理一同发表。阿纳托利·马尔采夫于1936年将紧致性推广到任意语言，并发展了它在代数中的应用。此后，莱昂·亨金提出了一种构造模型的证明，成为证明完备性和紧致性的标准方法。这些进展推动紧致性成为模型论的一项主要方法。(people.math.sc.edu)

参考来源

Math 225A – Model Theory, Lecture 16: Compactnessmath.berkeley.edu
Mathematical Logic for Mathematicians, Part Imath.berkeley.edu
Model Theory — George F. McNultypeople.math.sc.edu
The Compactness Theorem and Ultraproducts — Mike Prestpersonalpages.manchester.ac.uk
Math 225A – Model Theory, Lecture 17: Compactness Continuedmath.berkeley.edu
Kurt Gödel — Stanford Encyclopedia of Philosophyplato.stanford.edu
The Compactness Theorem — Internet Encyclopedia of Philosophyiep.utm.edu