紧致性定理

维基百科,自由的百科全书
跳转至: 导航搜索

紧致性定理符号逻辑模型论中的基本事实,它断言一阶句子的(可能无限的)集合是可满足的(就是说有一个模型),当且仅当它的所有有限子集是可满足的。

命题演算的紧致性定理是吉洪诺夫定理(它声称紧致空间的积是紧致的)应用于紧致Stone空间的结果。

应用[编辑]

从这个定理可以得出,如果某个一阶句子对于特征值为零的所有都成立,则存在着一个常量p,使得这个句子对特征值大于p的所有域都成立。这可以被看作为如下:假定S是要考虑的句子。那么它的否定~S,和域公理与句子的无限序列1+1 ≠ 0, 1+1+1 ≠ 0, ...一起,不能被假定所满足。所以这些句子的有限子集是不可满足的,意味着S在有足够大特征值的这些域中成立。

从这个定理还得出,有一个无限模型的任何理论都有任意大基数的模型。所以,有着带有不可数多个自然数的皮亚诺算术有非标准模型。非标准分析是出现无限个自然数的另一个例子,是不能被任何公理化所排除的可能事物,也是紧致性定理的一个推论。

证明[编辑]

紧致性定理可以使用哥德尔完备性定理来证明,它确立了一组句子是可满足的,当且仅当没有矛盾可以证明自它们。事实上,紧致性定理等价于哥得尔完备性定理,并且二者都等价于超滤子引理,它是弱形式的选择公理。因为证明总是有限的,所以只涉及有限多个给定句子,就得出了紧致性定理。

哥德尔最初就是以这种方式证明紧致性定理的,但是后来又找到了紧致性定理的一些“纯语义”证明,就是说提及“真理”但不提及“可证明性”的证明。这些证明倚赖于依仗选择公理的超乘积

证明:固定一个一阶语言L,并设Σ为L-句子的搜集,使得所有L-句子的子搜集i ⊆ Σ都有模型\mathcal{M}_i。还设\prod_{i \subseteq \Sigma}\mathcal{M}_i是这些结构的直接乘积,和I是Σ的有限子集的搜集。对于I中每个i设Ai := { jI : ji}。所有这些集合Ai的家族形成一个滤子(filter),所以有一个超滤子(ultrafilter)U包含形如Ai的所有集合。

现在对于Σ中任何公式φ我们有:

  • 集合A{φ}U
  • 只要j ∈ A{φ},则φ ∈ j,因此φ在\mathcal M_j中成立
  • 带有φ在\mathcal M_j中成立的性质的所有j的集合是A{φ}的超集,因此也在U

使用Łoś定理我们看到φ在超乘积\prod_{i \subseteq \Sigma}\mathcal{M}_i/U中成立。所以这个超乘积满足Σ中所有的公式。

紧致性定理(版本2)[编辑]

紧致性定理的定义[编辑]

紧致性定理定义:

1)在一阶逻辑中,如果我们有一个公式集合(记作) \Delta 并且 \Delta 是一个不满足式的公式集合,那么 \Delta 至少有一个有限个数元素的子集(记作) \Delta^\prime  \Delta^\prime \subseteq \Delta  )并且 \Delta^\prime 也是不满足式的集合
我们注意到:
2)(换一句话说),如果我们有一个公式集合(记作) \Delta 并且 \Delta 是一个可满足式的公式集合,那么对于所有 \Delta 有限个数元素的子集(记作) \Delta^\prime ( \Delta^\prime \subseteq \Delta  ) ,  \Delta^\prime 也是可满足式的集合
3)(换一句话说),前提假设我们有一个子句(Clause)集合(记作)S,并且S中的所有子句是封闭的(Clause Fermee,也就是说子句中不含有变量),如果S是不可满足式的子句集合,当且仅当S至少有一个子集合S',S'是有限集合并且S'是不可满足的集合
我们注意到:
在3)中我们把公式集合 \Delta 转化成子句集合S,(根据定理: \Delta SAT \Leftrightarrow Clause(\Delta) SAT),我们说 \Delta 的可满足性和转化成的子句集合S的可满足性是等价的

紧致性定理的证明[编辑]

我们对1)的证明如下: 在证明前,我们需要知道如下定义:

a)完备性(Completude)定理的定义:前提假设我们有一个有限个数元素的子句集合(记作)S并且S中不含有变量(符号),如果S是不可满足的集合,那么S必定拥有一个驳斥(Refutation)
b)驳斥(Refutation)的定义:一个子句集合S的驳斥是一个通过应用衍生方法产生的一系列子句 C_1,C_2,......C_n并且最后的C_n是一个空子句,我们叫做S拥有(或接受)一个驳斥,记作S \vdash \Box
我们注意到当S拥有一个驳斥时,那么很显然集合S是有限的,产生的子句 C_1,C_2,......C_n也是有限的,这是因为我们不能再运用衍生规则产生其它新的子句
c)衍生(Derivation)的定义:从一个子句集合S,通过应用解决规则(regle de resolution)或因式分解规则(regle de factorisation)产生得到的一系列子句C_1,C_2,......C_n叫做衍生
d)正确性(Correction)定理的定义:前提S是一个不含变量符号的子句集合,如果子句C是子句集合S通过应用解决规则或因式分解规则所的到的子句,那么子句C是子句集合S的逻辑子序列(Consequence Logique),记作 S \models C ,也就是说集合S的所有模型(或称解释,指派)也是子句C的模型
e)逻辑子序列(Consequence Logique)的定义:一个公式(或公式集合)\phi是另一个公式(或公式集合) \psi 的逻辑子序列,当且仅当所有 \psi 的模型(或称解释,指派)是\phi的模型,记做\psi \models \phi
证明:
根据完备性定理我们可以知道子句集合S拥有一个驳斥,那么对应的集合\Delta也拥有驳斥,那么这两个集合都是有限的,所以一个S的子集合S'在衍生驳斥中也是有限的,我们根据正确性定理可以知道,通过应用衍生规则,S'也是不可满足的,那么很显然存在对应于S'的公式集合\Delta^'\Delta^'\subseteq \Delta)来说,由于\Delta含有以子句形式的集合S',那么集合\Delta^'必定是不可满足的
\Box

参见[编辑]