数学联邦政治世界观
超小超大

直觉主义完全性(逻辑论文) (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),接着再看更方便。

相关小说

待我归来再爱 连载中
待我归来再爱
幺烽
我做了一个梦,醒来之后我是谁?十七?拾柒?还是瑶戚?
0.7万字9个月前
修仙:小小炮灰她拿捏世界 连载中
修仙:小小炮灰她拿捏世界
白皖烟
0.1万字9个月前
攻略系统1 连载中
攻略系统1
99_06403992154430976
0.1万字9个月前
我终究是负了你 连载中
我终究是负了你
凤柒玖
前世,她知晓他的一切,却一生欢喜未能如愿。今世,她知晓他的欢喜,却终究是负了他。
11.5万字9个月前
《重塑之魔尊的女人》 连载中
《重塑之魔尊的女人》
二雨田
在满地尸体的阶梯上,一个黑衣男子抱着一个满身鲜血的红衣女子阿忱,我替你守住了对不起,我来晚了,对不起……甜虐第一次写文,写的不好多多指点
8.8万字9个月前
阁宝 连载中
阁宝
喜慕
打小住在天虚阁的孟月天,以为天虚阁就是她的家,天虚阁的街坊四邻是自己的家人,从小到大一起长大的何九,是自己最信赖的朋友,一次外人的闯入,打破......
14.2万字9个月前