特殊篇章（数学定理）

紧致性定理与 Löwenheim-Skolem定理

我们从完全性定理的证明得到下面两个关于一阶语言语义性质的重要推论。

7.1 紧致性定理一阶公式集Φ

中是可满足的，当且仅当，Φ的任何有穷子集都是可满足的。

证明：Φ是可满足的，

当且仅当，Φ是一致的（定理

6.4)，

当且仅当，Φ的任何有穷子集都是一致的（引理2.8），

当且仅当，Φ的任何有穷子集都是可满足的（定理6.4）。

7.2 Löwenheim-Skolem定理设一阶公式集Φ是可数的。如果Φ是可满足的，那么它被一个可数的解释所满足。

证明：假设Φ是某个语言的公式集（可以是不可数语言)。既然Φ是可数的，而每个公式都是有穷长的-串，那么，Φ中所出现的的非逻辑符号一定是可数多的。设这些符号包含在一个可数语言里，则Φ也是公式集。我们知道，Φ作为-公式集是可满足的（一致的），当且仅当Φ作为-公式集是可满足的（一致的）。因此，我们不妨假定Φ是一个可数语言Ը的公式集。

设Φ是可满足的，那么Φ是一致的。给Ը增加新常项c ₀，c ₁，···，按定义5.4得到Ըᶜ和它的语句集Φ ᶜ。Ըᶜ仍然是可数语言。根据系理5.2的证明，存在Ըᶜ-解释σ，它满足Φ ᶜ，而且，它是Ըᶜ的项解释，其论域为{ [t] │t是Ըᶜ-项} 的基数 ≤ {t│t是Ըᶜ-项]的基数，而Ըᶜ-项只有可数多，因此，

σ的论域{ [t] │t是Ըᶜ-项]是可数的，即σ是一个可数解释。

按照可满足性定理（5.6）证明中的做法，将σ限制成一个Ը-解释σ´，其论域维持不变。由这个定理的证明，Ը-解释 σ´满足Ը-公式集Φ。

因此，Φ被一个可数的解释所满足。

170/231

这两个定理是一阶模型论的基础，其应用极其广泛。下面我们讨论一下它们所揭示的一阶语言在表达力方面的局限。

7.3定义 设Φ是一个Ը-语句集，K为一个Ը-结构类。

1）称Ը-结构类{│（Φ）＝T}为Φ的模型类，记为Mod（Φ）。

2)称Th (K) = {φ│φ 是Ը-语句，且对任何∈K，(φ)＝T}为K的理论。

3)如果存在Ը-语句集Ψ，使得K＝Mod(4)，则称K是可公理化的。若此时Ψ是有穷集，则称K为可有穷公理化的。

我们把 Mod ( {φ ₁，···，φₙ } ) 简记为Mod (φ₁，···，φₙ)。

Mod(φ)总括了语句φ的所有模型，可以看作φ的模型论「意义」，而Mod(Φ)则是语句集Φ的模型论「意义」。如果对某个语句集Ψ，K=Mod(Ψ)，那么K就被Ψ所「表达」和刻画，或者说，K被Ψ所公理化。能够被一阶语句集所公理化的K，又称初等类。

一般而言，所谓一种语言的表达力问题，就是问：哪些结构类能够被这种语言的语句集所公理化？或者，这种语言能够表达或刻画些什么？而一阶语言的表达力问题相当于：哪些结构类是初等类？一阶语言能辨别和区分结构的什么性质？

7.4.例 考虑一阶语句φ ≥₂ (φ ≥ₙ 的定义，见第四章第7.3节）。任给结构，

(φ ≥₂)＝T，当且仅当，的论域中至少有2个元素.

因此，

Mod(φ ≥₂)＝{│的论域中至少有2个元素}。

如果令K＝论域中至少有2个元素的结构的类，则K＝Mod (φ ≥₂)，即 K 被 φ ≥₂ 所(有穷)公理化。

把这推广一下。φ ≥₂ 表达「论域中至少有n个元素」，即

Mod(φ ≥ₙ)＝{│的论域中至少有n个元素}。

所以，论域中至少有n个元素的结构的类是初等类，它被 φ ≥₂ 所 (有穷) 公理化。

对于无穷大语句集Φ＝(φ ≥ₙ│n≥2}，则有

Mod(Φ)＝{│是无穷结构}。就是说，所有无穷结构组成的类是初等类，它被Φ所公理化。

另外，由第四章第7节知，等价关系结构、偏序结构、全序结构、无端点稠密全序结构等组成的类，都是初等类，而且都可有穷公理化。

7.5例 令P为一阶 Peano公理集，为算术标准结构 (见第四章第7.4节）。则我们由前面的内容知道，∈Mod(P)。

考虑在一阶算术语言中的理论Th( )，它是所有在中为真的-语句的集合 ( 但它不是一个形式理论，见第四章第7.4节的说明) 。它的模型类

Mod (Th ( ( ) 是什么样的呢？

任给结构，EMod (Th ( ( ) 当且仅当(Th( ( )＝T。因此，对任意语句φ，

(φ)＝T ⇒φ ∈ Th ( ) ⇒ (φ)＝T。

(φ)＝T ⇒φ ∉ Th ( ) ⇒ ￢φ∈Th ( ) ⇒ (￢φ)＝T ⇒ (φ)＝F。

这说明，Mod (Th( ) )中的结构，都与满足同样的一阶语句。满足同样的一阶语句的两个结构，称为初等等价 (或一阶等价) 的结构。因此，Mod (Th ( ) )中的结构，都与初等等价。

另外，因为是P的模型，所以P ⊆Th ()。由此可知：

Mod (Th( ) ) ⊆ Mod(P) (见下面习题7.6-2)。结构类Mod(P)可以叫作Peano类，它的理论 Th（Mod (P) )={φ│P￾φ}。根据经典逻辑的完全性，Th（Mod (P) )＝{φ│P ￾ ᴄ φ}，它是P所推出的语句的集合，称为一阶算术理论。

我们曾经希望是Mod (P) 的唯一元素，即 P (在同构的意义上）唯一地刻画标准模型，但下面的Skolem定理将表明，Mod (Th( ) )中已经有与「本质上」不同（即不同构）的结构，虽然它们与初等等价。文献上称它们为Th ( ) 的──因此是P的──非标准模型。

7.6 习题

1)对于公式φ₁，···，φₙ，证明：Mod (φ ₁，

···，φ ₙ)＝Mod(φ ₁，∧···∧φₙ)。

2)对于语句集Φ ₁、Φ ₂，

用Φ ₁，￾Φ ₂ 表达：对于任何φ∈Φ ₂，Φ ₁ ￾φ。证明：

Φ ₁，￾Φ ₂，当且仅当 Mod(Φ ₁)⊆Mod(Φ ₂)。

3)设K为一个Ը-结构类。证明：

i)K⊆Mod(Th (K))。

ii)K是可公理化的，当且仅当

K＝Mod(Th (K) )。

4)证明：如果K是初等类，则K中的所有无穷结构也组成一个初等类。

5)一个Ը-语句集Φ称为完全的，如果对任何Ը-语句φ，要么Φ￾ ᴄ φ 要么Φ ￾ ᴄ ￢φ。证明：

i)Th ( )是完全的。(但P不是完全的，见第四章第7.4节的说明。）

ii)Φ是完全的，当且仅当Mod（Φ）中的结构是初等等价的。

iii)Φ是完全的，当且仅当{φ│Φ￾ ᴄ φ}是极大一致的。

我们下面表明，有些普通的结构类，不能被一阶语言的语句集所公理化。

7.7引理 设Φ是Ը-语句集。如果Φ有任意大的有穷模型（即对任意自然数n，Φ有一个模型，其论域有穷，且至少含n个元素），则Φ也有无穷模型。

证明：令Ψ＝Φ∪{φ ≥ₙ│n≥2}，其中φ ≥ₙ表达「至少有n个元素」（见例7.4）。

如果Ψ可满足，则Ψ有模型，而这个既是Φ的模型，又是{φ≥ₙ│n≥2}的模型；由后者，是无穷模型(例7.4)。因此，如果Ψ可满足，则Φ有无穷模型。

我们证明Ψ可满足。根据紧致性定理（7.1），我们只要证明Ψ的任意有穷子集可满足。

设Θ是Ψ的一个有穷子集。Θ中只包含有穷多的φ ≥ₙ，因此，一定有自然数m，使得

Θ⊆Φ∪{φ ≥ₙ│2≤n≤m}。

因为Φ有任意大的有穷模型，所以，Φ有一个模型，其论域里至少有m个元素。显然这个模型是Θ的模型。

7.8定理 设Ը是一阶语言。所有有穷的Ը-结构组成的类不是初等类。

证明：令K＝{│是Ը-结构，且的论域有穷}。假设存在Ը-语句集Φ，使得K＝Mod(Φ)。那么，Φ只有有穷模型。但是，Φ既然有任意大的有穷模型，根据引理7.7，Φ也有无穷模型。矛盾。因此，不存在Ը-语句集Φ，使得K＝mod(Φ)，即K不是初等类。

所以，有穷结构类不可在一阶语言里公理化；换言之，一阶语言不能刻画「有穷」这个普通的数学概念。这个事实在一个侧面表明了一阶语言表达力的局限。由此我们又得到：

7.9系理 设Ը是一阶语言。所有无穷的Ը-结构组成的类不可有穷公理化。

证明：假设K是无穷的Ը-结构组成的类，而且K可以有穷公理化。那么，存在有穷的Ը-语句集Φ，使得K＝Mod(Φ)。

设Φ＝{φ ₁，···，φ ₙ}。由习题 7.6-1，Mod (Φ)＝Mod (φ ₁∧···∧φₙ)。因此，K＝Mod (φ ₁ ∧···∧φ ₙ)。

现在，任给Ը-结构，

是有穷的，

当且仅当，∉K，

当且仅当，(φ ₁ ∧···∧ φ ₙ)＝F，

当且仅当，(￢ (φ ₁∧···∧φ ₙ ) )＝T。

因此，Mod(￢(φ ₁∧···∧φ ₙ) )＝有穷的Ը-结构的类。

这与定理7.8矛盾。

所以，无穷结构类虽然可在一阶语言里公理化(例7.4)，但不可有穷公理化。

7.10 Skolem 定理 的理论Th ( ) 有可数的非标准模型。

证明：令一阶算术语言的公式集

Φ＝Th(𝔑)∪│￢x₀≡0，￢ x₀≡0＋1，

￢x₀ ≡ (0＋1)＋1，···│

首先证明Φ是可满足的。

设Ψ为Φ的一个有穷子集。记项0为0，0＋1为1，(0＋1)＋1为2，···。令n为最大的自然数，使得￢x₀≡n包含在Ψ中。定义-解释

σ＝〈，ρ〉，其中ρ (x₀)＝n＋1。

容易看出，σ(Ψ)＝T。

因此，根据紧致性定理，Φ是可满足的。

显然， Φ是可数集。由Löwenheim-Skolem定理(7.2) Φ被一个可数解释σ´＝〈，ρ´ 〉所满足。因此，σ´满足Th ( )，其中的可数结构是语句集 Th ( )的模型。

注意，对任意自然数

n，σ´(￢x₀≡n)＝T。所以，ρ´(x ₀)不是任何自然数。就是说，的论域里有「非自然数」，它不是0、1、2、···。这说明，与不同构，因为我们无法把中的非自然数与中的任何自然数对应起来，而仍然能够保持加法和乘法的运算关系。

另一方面，既然是Th ( ) 的模型，那么它与就是初等等价的(例7.5)。

Th ( ) 的这种非标准模型，是可数的（因此，根据例7.5的说明，一阶 Peano 公理集 P 也有可数非标准模型）。但是，Th ( ) 也有不可数的非标准模型。这牵涉到一阶语言的下面这个一般的性质。

7.11 升 Löwenheim-Skolem定理 设一阶语言Ը的公式集Φ可被一个有无穷论域的解释（无穷解释）所满足。那么，对任何集合A，存在一个解释满足Φ，其论域中至少有A中那么多元素。

证明：令指标集 I 与集合A等势。对每个i∈I，定义c ᵢ 为新常项（不在Ը中的常项），使得对于i，j∈I，如果i≠j，则C ᵢ ≠C ⱼ 。

设Ը´＝Ը∪{cᵢ │i∈I}。令Ը´-公式集

Ψ＝Φ∪{￢c ᵢ ≡c ⱼ │i，j∈I且i≠j}。

我们先证明Ψ是可满足的。对Ψ的任意有穷子集Θ，Θ中只有有穷多形如￢c ᵢ ≡ c ⱼ 的公式，设其中出现的新常项只有c ₁，c ₂，···，

c ₙ (它们互不相同，1，2，···，n为它们的重新编号)。

根据假设，有一个无穷Ը-解释σ＝〈，ρ〉满足Φ。因为的论域无穷，所以可以找到其中不同的个体a ₁，

a ₂，···，a ₙ 。将展开成Ը´-结构，使得

c 𝕶 ₁＝a₁，c 𝕶 ₂＝a₂，···，c𝕶 ₙ＝a ₙ (不在

c ₁，c ₂，···，C ₙ 中的新常项，可以任意解释)。

现在令Ը´-解释σ´＝〈，ρ〉。根据第四章系理 3.8，σ´ 满足Φ；再由的定义，σ´ 满足 Θ 中所有形如￢c ᵢ ≡c ⱼ 的公式。因此，σ´满足Θ。

由紧致性定理，Ψ是可满足的。但任何满足Ψ的解释，由于它满足{￢c ᵢ ≡c ⱼ │i，j∈I且i≠j}，所以其论域中至少有 I 中那么多元素(即A中那么多元素)。

将满足Ψ的Ը´-解释限制到Ը上，则这个解释就是满足Φ的、其论域中至少有A中那么多元素的Ը-解释。

这个定理说明，一阶公式集（语句集)只要被无穷解释所满足（有无穷模型），则它就被任意大的解释所满足（有任意大的模型)。因此，一阶语言不能区分无穷结构的大小，不能表达结构的无穷基数。

从这个定理马上得到：

7.12系理Th ( ) 有不可数的非标准模型。

证明：因为Th ( ) 有无穷模型，所以，根据定理7.11，它有任意大的模型，包括不可数模型。当然，不可数模型不能与同构（它们之间没有一一对应）。

根据例 7.5，Th ( ) 的不可数模型，也是P的模型，而且，它们与初等等价。容易看出，这个系理可以推广为：对任意无穷结构，Th ( ) 有任意大的与初等等价的模型。因此，任一无穷结构都不能用一阶语言唯一地刻画。

以上结果，都表明了一阶语言的表达力的局限。我们可以看出，克服这些局限的一种方法，是扩展一阶语言。比如，增加集合变项(二阶语言)，或允许无穷长公式，或增加其他量词（如「存在不可数多」)，等等。这些语言都有效地增强了表达力，但是，它们也同时丧失了一阶语言的一些好的性质。比如，我们在第四章末尾曾提到，与一阶Peano理论 P恰成对照，二阶Peano理论是范畴的：它在同构的意义上只有唯一的模型，即算术标准模型。另一方面，考虑二阶公式集：

二阶 Peano理论 ∪ {￢x ₀ ≡ 0，￢x₀ ≡0＋1，￢x ₀ ≡ (0＋1) ＋1，···} 。

…。

按照定理7.10的思路，我们同样可以证明这个公式集的每个有穷子集都是可满足的。但是，这个公式集本身却不可满足，因为二阶Peano理论的模型里没有「非自然数」。因此，对二阶语言，紧致性定理不成立。既然完全性定理蕴涵紧致性定理，从此又得出，二阶逻辑没有完全性；其中的语形推演不能实现全部语义上有效的推理。我们看到，二阶量化所收获的表达力，被推演力方面的损失「抵消」了。

Lindström证明，在一个比一阶语言表达力强的语言里，紧致性定理和 Löwenheim-Skolem定理不能同时成立。因此，一阶语言唯一具有这样两个性质，它在模型论的意义上被紧致性和 Löwenheim-Skolem性质所刻画。

7.13习题证明：

1)如果 φ 为一阶语句，且

Mod(φ)包含所有无穷结构，那么存在自然数

n＞0，使得Mod (φ)也包含所有基数大于 n 的结构。

2) 设 Φ ₁、Φ ₂为一阶语言Ը的语句集。如果Mod (Φ ₁ ) ∩ Mod (Φ ₂ )＝∅，那么，存在Ը-语句φ，使得

Mod (Φ ₁ ) ⊆Mod (φ)，且

Mod (Φ ₂ ) ⊆Mod (￢φ)。

3)设K为所有Ը-结构组成的类。如果K的子类

K ₁ 与K — K ₁ 都是初等类，则K ₁ 与K — K ₁ 都是可有穷公理化的。

4)一阶语言Ը的语句集Φ称为独立的，如果Φ中任意语句φ都不能由Φ— {φ}推出。

i)对Ը的任何有穷语句集Φ，存在Φ的独立子集Ψ，使得 Mod (Φ)＝Mod(Ψ)。

ii) (如果Ը是可数的) 对每个Ը-结构组成的初等类K，存在独立的Ը-语句集Φ，使得

K＝Mod (Φ)。

数学联邦政治世界观提示您：看后求收藏（笔尖小说网http://www.bjxsw.cc），接着再看更方便。