直觉主义完全性（逻辑论文） (11-7)

n是奇数时，Ψ ₙ₊₁＝Ψ ₙ ∪ {ψ ₁} 或 Ψ ₙ₊₁＝Ψ ₙ ∪ {ψ ₁}。由定义知，二种情形下都有：并非

Ψ ₙ₊₁ ￾ ᵢ φ。

n是偶数时，Ψ ₙ₊₁＝Ψ ₙ ∪ {ψ (c / x) }。如果

Ψ ₙ ∪{ψ (c / x) } ￾ ᵢ φ，则由于 Ψ ₙ ￾ ᵢ ∃xψ，据我们新的存在消去规则 (见定理8.3.2)，有

Ψ ₙ ￾ ᵢ φ。这与归纳假设矛盾。

总之，并非 Ψ ₙ₊₁ ￾ ᵢ φ。归纳证明完毕。

2) Ψ 是 (相对于语言的) 素理论。

a) 因为并非 Ψ￾ ᵢ φ，所以 Ψ 是i-一致的。

b)设 ∃xψ∈Ψ。因此，Ψ￾ ᵢ ∃xψ。令 n 是使得Ψ ₙ ￾ ᵢ ∃xψ 的最小的数。那么，在第n步之前，∃xψ 的证据式未得到添加。但是，对某个m≥n，∃xψ 在第 m 步得到处理。因此，对某个c，ψ(c / x)∈Ψ ₘ₊₁，故ψ (c / x) ∈Ψ。

c) 设ψ ₁ ∨ψ ₂ ∈Ψ。令 n 是使得 Ψ ₙ ￾ ᵢ ∨ψ ₂

的最小的数。那么，对某个m≥n，ψ ₁，∨ψ ₂在第 m 步得到处理。因此，ψ ₁ ∈Ψ ₘ₊₁，或

φ ₂ ∈Ψ ₘ₊₁，故ψ ₁，∈Ψ 或ψ ₂ ∈Ψ。

d) Ψ 对直觉主义推演是封闭的。

如果 Ψ￾ ᵢ ψ，则 Ψ￾ ᵢ ψ∨ψ。有最小的 n，使得Ψ ₙ ￾ ᵢ ψ∨ψ。根据 c)，ψ∈Ψ。

在目前的阶段，我们得到了语句集的素理论扩张，这相当于获得了经典情形下的包含证据的极大一致集。下一阶段的任务是建立由这样的集合决定的「项结构」，从而证明「可满足性引理」。但是，对于一个Kripke模型𝕶来说，其中每个状态i下的D(i)和A(i)都对应一个经典项结构。因此，我们需要的不是一个，而是一组素理论，来建立Kripke「项模型」。

8.4.3 定义 𝕶ₚ是如下定义的

Kripke模型（I ₚ ，⊆，D，A）：

1) lₚ＝{Φ│Φ是素理论}；

2) ⊆ 是子集关系；

3) 对每个Φ∈l ₚ，D(Φ)是Φ中闭项的集合；

4) 对每个Φ∈l ₚ，A(Φ)＝{φ│φ 是原子语句，且Φ￾ ᵢ φ}。

由引理 8.4.2，存在素理论，因此 l ₚ 是非空的，D (Φ)也是非空的。⊆ 显然是一个偏序。如果Φ⊆Ψ，那么A(Φ) ⊆A(Ψ)，且D (Φ)⊆ D (Ψ)。因此，𝕶ₚ的确是一个 Kripke 模型。

因此，给定一个素理论Φ，我们就有𝕶ₚ中的一个状态Φ，或者说，一个「经典结构」，其论域为项集D (Φ)，论域中的基本关系由A (Φ)决定。按照Henkin方法，我们需要证明，理论Φ 恰好被状态Φ所「满足」，即理论Φ中的语句恰好是状态Φ中的真语句。

下面证明 Henkin定理的这个直觉主义版本。

8.4.4 直觉主义可满足性引理对于𝕶ₚ中的每个

Φ∈l ₚ，Φ＝Th (Φ)。

证明：我们要证，对任意语句φ，φ∈Φ当且仅当𝕶ₚ(Φ，φ)＝T。施归纳于 φ 的秩。

1)φ是原子句。

φ∈Φ

⇔Φ├ ᵢ φ(Φ 对直觉主义推演封闭)

⇔φ∈A(Φ)(A(Φ)定义)

⇔ 𝕶 ₚ (Φ，φ)＝T(定义8.2.2)。

2)φ是合取式。易证。

3)φ是ψ ₁ ∨ψ ₂ 。

ψ₁∨ψ₂∈Φ

⇔ψ₁∈Φ或ψ₂∈Φ (素理论性质)

数学联邦政治世界观提示您：看后求收藏（同人小说网http://tongren.me），接着再看更方便。