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

直觉主义完全性(逻辑论文) (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.5万字9个月前
宇宙护卫队(情之域) 连载中
宇宙护卫队(情之域)
我们终将遇孤独
看看封面就知道了
1.1万字9个月前
幻世尘缘:彼岸神眷 连载中
幻世尘缘:彼岸神眷
夜楹曦梦
七罪与七美的界限从未清晰,希冀与灾朔并肩而行。破碎的时光梦境里,蔷薇花绽放至陌路荼靡,又是谁向死而生,残响折翼。……在前往精灵之森的时空通道......
12.9万字9个月前
Hp弗丽嘉 连载中
Hp弗丽嘉
芙洛爱芙弗
非签约,非实名认证作者,随缘更新。目前属于大修ing.读前请看简介——HP同人作,一切属于罗琳(ooc属于我)。私设较多,历史向考究党勿入,......
5.2万字9个月前
重生之我在异世开店铺 连载中
重生之我在异世开店铺
墨香笔落
这个是我的脑洞,还有一些梦境,试试能不能写出来。
8.1万字9个月前
雷狮X安迷修:抑幻药 连载中
雷狮X安迷修:抑幻药
九十四天
——来到魂灵国度哪有相识的恋情。不过是无尽的等待与挂念。都说爱人的眼里有第八大洋,可如果我的爱人看不见我呢?
0.9万字9个月前