Henkin定理

现在我们前进到一阶语言里，考虑整个经典逻辑的完全性。

首先简化一下语言。由第四、五章的相关内容我们知道，在经典逻辑中，可以把∀xφ 看作

￢∃x￢φ的缩写，从而在语言的初始符号中去除∀。这样改变的语言，与原来的语言有相同的表达力，相同的（经典）语义与语形后承关系。因此，在新语言里证明的经典完全性，对原来的语言同样成立。为了简化证明步骤，我们假定本节的Ը不含∀，其中的量词只有∃一个。

然后我们梳理证明的总体思路。

同命题逻辑的情形一样，完全性证明的关键步骤是得到可满足性引理；同前面的区别是，这里的可满足性引理是针对一阶公式集的，因此还要处理谓词、等词和量词带来的问题。按照前面描述的 Henkin方法，我们既然已经有了把一致集扩充为极大一致集的办法，那么目前的任务就是对于给定的极大一致集，找到一个满足其中的素公式的解释。就是说，给定极大一致Ը-公式集Φ，我们要定义一个Ը-解释σ＝〈，ρ〉，使得：

第一，对于Ը的原子公式φ，

σ (φ)＝T当且仅当φ∈Φ。

第二，对于Ը的量化式∃xφ，

σ (∃xφ)＝T当且仅当∃xφ∈Φ。按照满足概念的定义，这相当于要求：

1)对于Ը-原子公式Pt ₁，···，t ₙ，Pt ₁ ··· t ₙ ∈Φ当且仅当σ (t ₁)，···，σ (t ₙ) )。

2)对于Ը-等式t≡s，t≡s∈Φ中当且仅当σ (t)＝σ (s)。

3)对于Ը-量化式 ∃xφ，∃xφ∈Φ，当且仅当，存在a∈A，使得σ (a/x) (φ)＝T。

我们逐条分析这些要求。

1) 是针对σ的论域和其中的基本关系的，它要求，一旦 Φ「规定」了Pt ₁，···t ₙ，那么这些项对应的个体在论域中就恰好具有P表达的关系。我们如何找到一个这样一个论域呢？显然不能凭空造出一个论域。可我们有什么东西可资利用呢？我们现在仅有的资源是语言Ը及其中的项与公式，它们是一些语形对象（符号串），我们曾经说过，语形对象需要跟语义对象区别开来，一边是语言符号，一边是世界里的个体、关系和命题，前者表达后者，但不能混同于后者。

但是，Ը的符号串毕竟也是对象，因此我们能够使用某个语言Ը´谈论它们。在这个意义上，被谈论的Ը-串构成语言Ը´的论域。特别是，没有什么阻碍我们，让Ը´直接等于Ը，即让Ը述说自身。这不意味着我们混同了Ը的语形和语义，我们只是让符号串身兼二任。比如，我们可以令个体常项a指称a本身。作为语形对象，a是一个名字，而作为语义对象，a是某个名字的指称。同一个符号，扮演的角色不同，两个角色，没有在这里混淆。实际上，这只是定义了结构中的解释函数ŋ，使得ŋ(a)＝a。

回到1）的问题。既然1）要求项的语形「表现」跟语义「表现」相同，那么，一个自然的想法是：我们把项的语形「表现」直接「搬」到语义中去。具体而言，我们让语言Ը中的项直接充当个体而组成Ը的一个论域，然后定义解释σ，使得每个Ը-项t对应于论域中的个体t，即

(*) σ (t) ＝t。

进一步，对Ը的每个n元谓词P，我们如下定义它在这个论域中的解释：

(σ(t ₁)，···，σ (t ₙ ) )，当且仅当，Pt ₁，···t ₙ，∈Φ。

这满足了1）的要求，其中的关键思想是：让语言中的项「指称」它们本身。

但是，2）对上面的想法提出了一个疑问：对于不同的项t和s，有可能t≡s∈Φ，而2）要求这时候σ (t) 与 σ (s) 是同一个体。因此，(在有等词的语言中）仅仅把项当作论域中的个体还不行，因为这会使得不同的项充当不同的个体。可是，这个困难并不严重，我们可以通过取项的等价类的办法来避免它。就是说，我们可以稍微改变一下原初的想法，不直接用项充当个体，而把Φ规定它们「相等」的那一类项当作一个个体。具体而言，我们可以这样定义一个项之间的等价关系∼：

t∼s，当且仅当，t≡s∈Φ。

然后把项t的指称定义为t所对应的∼ 等价类。这样，(*) 就改变为：

(**) σ (t)＝{s│t∼s}。

这没有改变「项『指称』自身」的思想，因为这样定义的t的等价类与这个类的代表元t，对Φ而言，实质上是一个对象。我们稍后验证，∼ 的确是等价关系，而这样改变的解释仍然满足 1) 和2 ) 。

3) 的要求是，对Φ所肯定的每个存在式 ∃xφ，有σ的论域中的个体 a （「证据」），使得 a 具有 φ 所表达的性质。如何满足这个要求呢？为方便计，我们暂且只考虑简单的存在式∃xPx，其中 P 为一元谓词。现在，σ 的论域中的全部个体都是Ը-项的解释，因此，这个要求就成为：

∃xPx∈Φ，当且仅当，存在Ը-项t，

使得σ (σ (t) /x) (Px)＝T。

根据代入引理（第四章引理

6.1)，这相当于说：

∃xPx∈Φ，当且仅当，存在Ը-项t，

使得σ (Pt)＝T。

而根据1)，σ (Pt)＝T等价于Pt∈Φ。因此，∃xPx 所要求的语义上的证据a，变为语形上的证据t。这提示我们，要达到3）的要求，只要做到：

对每个，Ը-存在式 ∃xφ，∃xφ∈Φ中，当且仅当，存在Ը-项t，使得φ (t / x) ∈Φ。满足这个性质的公式集Φ，称为包含证据的。因此，3) 的语义要求，可以转化为对Φ的语形要求，即要求它包含证据。如何使Φ包含证据，我们准备在下一节讨论。本节里面，我们只证明，对任何包含证据的极大一致集，都可以找到上面描述的这样一个解释来满足它。

下面我们处理这个总体思路中的细节问题。

4.1定义 设Φ为极大一致的Ը-公式集，t、s是Ը-项。定义Ը-项之间关系∼如下：

t∼s，当且仅当，t≡s∈Φ。

4.2引理

1）∼是一个等价关系。

2）如果t ₁，∼ s ₁，···，t ₙ ∼ s ₙ，那么，对Ը的任何n元函数符号f，

ft ₁ ···t ₙ ∼ fs ₁ ···s ₙ ；

并且对Ը的任何n元谓词 P，

Pt ₁，···t ₙ ∈Φ，当且仅当，Ps ₁，···s ₙ ∈Φ。

证明：

1) ∼ 是自反的：显然有Φ￾ c t≡t。因此据引理 2.11-1，t≡t∈Φ，即t∼t。

∼是对称的：如果t∼s，则t≡s∈Φ，所以Φ￾ ᴄ t≡s。但由第五章例 5.13-2，Φ￾ ᴄ t≡s→s≡t。故Φ￾ ᴄ s≡t。因此s≡t∈Φ，即s∼t。

∼是传递的：留作习题。

2) 根据前提，t ₁ ≡s ₁，∈Φ，···，t ₙ≡s ₙ ∈Φ。因此，Φ￾ ᴄ t ₁≡s ₁ ∧···∧t ₙ≡s ₙ 。由第五章习题5.14，Φ￾t ₁≡s ₁，∧···∧t ₙ≡s ₙ →ft ₁ ···t ₙ≡fs ₁ ··· s ₙ。所以，Φ￾ᴄ ft ₁ ··· t ₙ ≡fs ₁ ···s ₙ ，即ft ₁ ···t ₙ ∼ fs ₁···s ₙ 。

第二条的验证留作习题。

4.3 习题 完成上面引理的证明。

对于Ը-项t，记其等价类{s│s是Ը-项且t∼s]为［t］。我们用全部的[t]组成一个论域(注意它是非空的)，如下建立项结构与项解释：

4.4定义令Φ为极大一致的-公式集。与Φ对应的项结构=〈A，ŋ〉由如下条件定义：

1)论域A＝{［t］│t是Ը-项}。

2)对Ը的每个个体常项c，

=［c］。

3)对Ը的每个n元谓词P，

( ［t ₁］，···，［t ₙ］ )，当且仅当，Pt ₁，···t ₙ ∈Φ。

4)对Ը的每个n元函数符号f，

( ［t ₁］，···，［t ₙ］ )＝［ft ₁ ···t ₙ］。

再定义赋值 ρ 为：

5) 对每个个体变项x，

ρ(x)＝［x］。

令σ＝〈，ρ〉。称σ为与Φ对应的项解释，记为σ Φ。

根据引理 4.2，上面定义3) 和

4) 中的条件与代表元t ₁，···，t ₙ的选择无关，因而我们的定义是合理的：

只要t ₁ ∼ s ₁，···，t ₙ ∼ S ₙ，就有ft ₁ ···t ₙ ∼fs ₁ ··· s ₙ，因此 ( ［t ₁］，···，［t ₙ］ ) 的值是唯一的；

只要t ₁ ∼ s ₁，···，t ₙ ∼ s ₙ，就有Pt ₁，···t ₙ ∈Φ当且仅当Ps ₁ ···s ₙ ∈Φ，因此 ( ［t ₁］，···，［t ₙ］ ) 是否成立总是确定的。

容易验证，σ Φ 把每一个Ը-项t解释为［t］：

4.5 引理 对每个Ը-项t，

σ Φ (t)＝［t］：

证明：施归纳于项t。

1）t是个体常项或变项的情况，直接由定义4.4-2、5得到。

t＝ft₁…tₙ。σ Φ （t）＝f𝕶(σΦ (t₁)，···，σΦ (tₙ) )

2) = f𝕶 ( ［t₁］，···，［tₙ］ ) ( 归纳假设 )

＝［ft₁ ··· tₙ］ (定义4.4-4)。

项解释σΦ。就是我们所需要的Ը-解释。下面我们证明，对于包含证据的极大一致集Φ，项解释σΦ恰好满足Φ。

4.6Henkin定理 设Φ是包含

证据的极大一致Ը-公式集。对于任何对任何Ը-公式φ，

σ Φ (φ)＝T，当且仅当，φ∈Φ。

证明：施归纳于φ的秩，即

r (φ)。

1) r (φ)＝0。此时φ为原子公式。

i)φ＝Pt ₁ ···t ₙ 。σ Φ (φ)＝T,

当且仅当，( σΦ (t ₁)，···，σΦ(t ₙ))，

当且仅当，( ［t ₁］，···，［t ₙ］ ) (引理4.5)，

当且仅当，Pt ₁，··· t ₙ ∈Φ (定义

4.4-3)。

ii) φ＝t≡s。σΦ (φ)＝T，

当且仅当，σΦ (t)＝σΦ (s)，

当且仅当，［t］＝［s］ ( 引理4.5 )，

当且仅当，t∼s，

当且仅当，t≡s∈Φ。

2) r (φ)＞0。此时φ为布尔式或量化式∃xψ。

i)φ为布尔式情形，证明同引

理3.1。

ii)φ＝∃xψ。σΦ (φ)＝T，

当且仅当，存在Ը-项t，使得σΦ ( ［t］/x) (ψ) ＝T，

当且仅当，存在Ը-项t，使得σΦ ( σΦ (t) /x)(ψ)＝T（引理4.5)，

当且仅当，存在Ը-项t，使得σΦ ( ψ (t/x) )＝T（代入引理），

当且仅当，存在Ը-项t，使得 ψ (t/x)∈φ (归纳假设，r (ψ (t/x) ＝r (ψ)＜r (∃xψ)，第三章习题6.7-3)，

当且仅当，∃xψ∈Φ (Φ包含证据)。

4.7 习题 设语言Ը不含全称量词∀，Φ是包含证据的i-极大一致Ը-公式集。证明：存在Ը-解释σ，使得对任何Ը-公式φ，

σ (φ)＝T，当且仅当，φ∈Φ。

(提示：按4.1—4.6的思路，在「Φ是i-极大一致集」的前提下，证明对应的结果。)

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