马琦 2010.12.18 maqi08@


考察形式系统及其扩张的递归可判定性。

考察形式系统及其扩张的递归可判定性。

可对任何形式系统提出可判定性和不可判定性问题， 因为哥德尔编码对它们都适用。

而这个问题正是DN中 一个特殊的子集的递归性或非递归性的问题。

命题 2.24 可判定的 即有一种能行的方法， L 是可判定的，即有一种能行的方法， 用它可判定， 用它可判定，L 的任意给出的 wf. 是否是 L 的定理。

的定理。

第二章的命题2.24说明命题演算的形 式系统L是可判定的。

可以证明
命题7.41 命题 L的定理的哥德尔数的集合是一个递归集。

的定理的哥德尔数的集合是一个递归集。

的定理的哥德尔数的集合是一个递归集


谓词演算系统KL是否为递归不可判定的，这 依赖于语言L。

取一个特殊情形，设L1 是不含函数字母，不 含个体常项，而只有一个谓词字母的一阶语言。

命题7.42 命题 KL1是递归可判定的。

是递归可判定的。

命题7.43 命题 设L是不包含函数字母和个体常项而只包含一元谓 词字母(可能有无穷个)的一阶语言，则KL 是递归可判定 的。

一阶语言 L
变元 个体常项 谓词字母 函数字母 x1,x2,… a1,a2,… Ain fin


命题7.44 命题 系统N 是递归不可判定的（在它是相容的假定下）。

系统N 是递归不可判定的 因为一个递归集可以有非递归的子集，而一个非递归集 可以有递归的子集，所以已知一个系统是递归可判定(或不可 判定)的，无法判定其扩张的递归可判定性。

但在某些情况下， 可以找出一种联系。

命题7.45 命题 设S和 S+是有相同语言的一阶系统，又S+是S的有穷扩张 有穷扩张， 有穷扩张 即存在wf.的有穷集A1,…,An ，当这个wf.的有穷集增加到S中去 作为S的公理后，我们就得到S+ 的公理集。

若S+ 是递归不可判 若 定的， 也是递归不可判定的。

定的，则S也是递归不可判定的。

也是递归不可判定的


不完全性 • 定理集与真语句集是不同的。

递归不可判定性 • 不存在判定哪些语句对应于N 定理的算法。

N
算术的形式系统因这两种局限而受到损害。

成书为止，还没有找到其他的解决办法。

一个谓词演算的系统是递归可 判定或递归不可判定与语言L有关。

而且，不可判定是常规，不是例外。

命题7.46 命题 存在一阶语言L 使得K 是递归不可判定的。

存在一阶语言L ，使得 L是递归不可判定的。

推论7.47 推论 全一阶谓词演算（具有第3章给出的所有符号）是递归不可判定的。

是递归不可判定的。

全一阶谓词演算 是递归不可判定的


命题7.48 命题
下列系统是递归不可判定的。

▪ 一阶群论。

▪ 一阶环论。

▪ 一阶域论。

▪ 一阶半群理论。

▪ 系统ZF。

下列系统是递归可判定的。

▪ 一阶Abel群理论。

▪ 没有乘法的一阶算术 （类似N ，不包括符号f22，而且删去公理(N5)和(N6)）。

。