第3节自然推演系统的可靠性和完全性 第6章哥德尔完全性定理 重复上述过程,我们就得到一个序列I,r’,r",…,并且可以排成树状,将r排在最 下面,然后自下而上,依次添加r,r",…等等。例如,它有可能是 注意到我们的生成规则恰好是把推理规则倒过来,因此在这棵树上,排在下面的r可以 视为从排在它上面的r*按照自然推演规则导出的,(在(∧)情形中则是从r*和I中导 出的)。如果发现树的某个节点上的公式集是一个公理,则停止这一支的构造。根据r不 可证的假定,这棵树至少有一支,记为p,或者(a)终结于一个由原子公式组成的但不是 公理的序列;或者(b)永不终结,即形成一个无穷支。 从分支p中我们定义一个r的“反模型”a如下:论域||为自然数集N;对每个 谓词符号P定义 (1,12,…,in)∈P当且仅当原子公式P(vn1,v2,…,tn)不在分支p中出现。 引理65.令赋值函数s为s(v2)=i对任意在分支p中出现的公式a,都有(2,s)长ao 证明:对公式a施行归纳 初始情形:a为原子公式P(v1,2,…,vn),则根据定义,(Ql,s)a 归纳情形:我们分成如下子情形来讨论: 子情形1:a为P(v1,2,…,vn)。由于P中不含公理,因此公式P(12,t2…,tn) 在p中不出现,所以(2,s)=P(vn1,tv2,…,tn),因而(,s)≠a 子情形2:α为ao∨a1。当我们处理a时,ao和a1都被添进p中。根据归纳假定 我们有(,s)长a和(,s)长a1。所以(,s)≠长ao 子情形3:α为ao∧a1。当我们处理a时,a0和α1至少有一个被添进p中。根据归 纳假定,我们至少有(,s)长a或(,s)长a1所以(,s)ka 子情形4:α为vrβ(x)。当我们处理α时,某个β(υ)被添进p中。根据归纳假定, 我们有(,s)≠B(vy)。所以(,s)长a 子情形5:α为彐rβ(x)。根据构造,我们会处理a无穷多次,在每次处理它时,j最 小的那个还不在p中的β(v)被添进p中。所以,对每一个自然数i,B(v)都在p中出现。 根据归纳假定,对每一个自然数,我们有(,s)≠B(v)。所以(,s)≠a 这就完成了引理的归纳证明。 推论63(甘岑1936).如果r是自然推演系统的一个定理,则有一个r的证明树其中没有 用到切割规则。 证明:假定}r。根据可靠性定理,}I。所以如果我们用完全性定理证明中的方法来搜 索,结果一定找不到r的反模型。因此一定得到r的一个证明树。根据构造,这棵证明 树显然没有用到切割规则。第 3 节 自然推演系统的可靠性和完全性 第 6 章 哥德尔完全性定理 重复上述过程，我们就得到一个序列 Γ, Γ ′ , Γ ′′ , · · · ，并且可以排成树状，将 Γ 排在最 下面，然后自下而上，依次添加 Γ ′ , Γ ′′ , · · · 等等。例如，它有可能是： Γ ′′ 0 Γ ′′ 1 Γ ′ Γ 。 注意到我们的生成规则恰好是把推理规则倒过来，因此在这棵树上，排在下面的 Γ ∗ 可以 视为从排在它上面的 Γ ∗∗ 按照自然推演规则导出的，（在 (∧) 情形中则是从 Γ ∗∗ 0 和 Γ ∗∗ 1 中导 出的）。如果发现树的某个节点上的公式集是一个公理，则停止这一支的构造。根据 Γ 不 可证的假定，这棵树至少有一支，记为 p，或者 (a) 终结于一个由原子公式组成的但不是 公理的序列；或者 (b) 永不终结，即形成一个无穷支。 从分支 p 中我们定义一个 Γ 的“反模型”A 如下：论域 | A | 为自然数集 N；对每个 谓词符号 Pj 定义： (i1, i2, · · · , in) ∈ P A j 当且仅当 原子公式 Pj (vi1 , vi2 , · · · , vin ) 不在分支 p 中出现。 引理 6.5. 令赋值函数 s 为 s(vi) = i。对任意在分支 p 中出现的公式 α，都有 (A, s) ̸|= α。 证明: 对公式 α 施行归纳。 初始情形：α 为原子公式 Pj (vi1 , vi2 , · · · , vin )，则根据定义，(A, s) ̸|= α。 归纳情形：我们分成如下子情形来讨论： 子情形 1：α 为 Pj (vi1 , vi2 , · · · , vin )。由于 p 中不含公理，因此公式 Pj (vi1 , vi2 , · · · , vin ) 在 p 中不出现，所以 (A, s) |= Pj (vi1 , vi2 , · · · , vin )，因而 (A, s) ̸|= α。 子情形 2：α 为 α0 ∨ α1。当我们处理 α 时，α0 和 α1 都被添进 p 中。根据归纳假定， 我们有 (A, s) ̸|= α0 和 (A, s) ̸|= α1。所以 (A, s) ̸|= α。 子情形 3：α 为 α0 ∧ α1。当我们处理 α 时，α0 和 α1 至少有一个被添进 p 中。根据归 纳假定，我们至少有 (A, s) ̸|= α0 或 (A, s) ̸|= α1。所以 (A, s) ̸|= α。 子情形 4：α 为 ∀xβ(x)。当我们处理 α 时，某个 β(vj ) 被添进 p 中。根据归纳假定， 我们有 (A, s) ̸|= β(vj )。所以 (A, s) ̸|= α。 子情形 5：α 为 ∃xβ(x)。根据构造，我们会处理 α 无穷多次，在每次处理它时，j-最 小的那个还不在 p 中的 β(vj ) 被添进 p 中。所以，对每一个自然数 i，β(vi) 都在 p 中出现。 根据归纳假定，对每一个自然数 i，我们有 (A, s) ̸|= β(vi)。所以 (A, s) ̸|= α。 这就完成了引理的归纳证明。 推论 6.3 (甘岑 1936). 如果 Γ 是自然推演系统的一个定理，则有一个 Γ 的证明树其中没有 用到切割规则。 证明: 假定 ⊢ Γ。根据可靠性定理，|= Γ。所以如果我们用完全性定理证明中的方法来搜 索，结果一定找不到 Γ 的反模型。因此一定得到 Γ 的一个证明树。根据构造，这棵证明 树显然没有用到切割规则。 10