可靠性与完备性

关于本课程系统的两个问题

关于推演的单元确定了本课程的系统：卢卡西维茨的公理模式 A1、A2、A3 和两条规则，即分离规则（MP）和双重否定替换（双否替换）；后者是关于四种推演技巧的一课在证明双重否定之后加入的。从集合 $\Gamma$ 出发的推演是一个有穷的公式序列，其中每个公式或者是公理，或者是 $\Gamma$ 的元素，或者是对两个在前公式应用分离规则的结果，或者是对一个在前公式应用双重否定替换的结果；$\Gamma \vdash \varphi$ 表示存在一个从 $\Gamma$ 出发、最后一个公式为 $\varphi$ 的推演。关于语义的单元则在关于语义后承与语义等价的一课中定义了关系 $\Gamma \models \varphi$：每个满足 $\Gamma$ 中全部公式的赋值都满足 $\varphi$。两种关系的写法相同，左边是一个集合，右边是一个公式；但它们的性质截然相反。前者是语法的、存在性的：它断言存在某个有穷的东西，即一个推演，可以逐个符号地检查。后者是语义的、全称的：它断言关于全部赋值的某件事，而赋值有无穷多个，并且每个赋值都给无穷多个变元赋值。

于是，关于系统可以提出两个问题。第一，它是否只推演出应当推演出的东西？如果对每个集合 $\Gamma$ 和每个公式 $\varphi$，$\Gamma \vdash \varphi$ 蕴涵 $\Gamma \models \varphi$，就称系统是可靠的：由前提推演出的东西，在每个使前提为真的赋值下都为真。第二，它是否推演出所有应当推演出的东西？如果 $\Gamma \models \varphi$ 蕴涵 $\Gamma \vdash \varphi$，就称系统是完备的。按照所涵盖的前提集，完备性有三个等级：

• 弱完备性：若 $\models \varphi$，则 $\vdash \varphi$；每个重言式都是定理；
• 有穷前提集的完备性：若 $\{\gamma_{1}, \ldots, \gamma_{k}\} \models \varphi$，则 $\{\gamma_{1}, \ldots, \gamma_{k}\} \vdash \varphi$；
• 强完备性：若 $\Gamma \models \varphi$，则 $\Gamma \vdash \varphi$，其中 $\Gamma$ 是任意集合，即使是无穷集合。

本课证明可靠性和完备性的前两个等级。第三个等级在关于紧致性定理的一课中证明；为什么这样划分，本课最后会加以解释。

不应该说的话

在西班牙语中，可靠性有时被称为“solvencia”，这是英语 soundness 的仿译；西班牙语的术语是“corrección”，而本课程的中文术语是“可靠性”。也不应该把它定义为系统“从一组表达式推出一个表达式”的性质：那只是可推演性本身，而不是系统的性质。不过，实质性的错误是另外两个。

第一个错误是说可靠性和完备性“可以互相推出”。它们是相互独立的性质：卢卡西维茨系统（没有双重否定替换规则）是可靠的（本课的证明去掉一种情形即可证明这一点），却不是完备的（关于形式演绎系统的一课给出了一个它推演不出的重言式）；而以全部公式为公理的系统是完备的，却不是可靠的。例题 2 考察这两个例子。

第二个错误更严重，因为它把一个循环论证当成了完备性的证明。它的要点是：若 $\varphi \nvdash \psi$，则由演绎定理得 $\nvdash (\varphi \rightarrow \psi)$；“借助可靠性”得 $\not\models (\varphi \rightarrow \psi)$；再由语义演绎定理得 $\varphi \not\models \psi$。可是可靠性说的是可推演的东西是有效的，而它的逆否命题说的是不有效的东西不可推演：

论证中的那一步方向相反，是从 $\nvdash \chi$ 到 $\not\models \chi$，这是 $\models \chi \Rightarrow \vdash \chi$ 的逆否命题，也就是弱完备性。如果是这样，那么该论证预设了它想要证明的东西。由此可知，完备性并不能“以简单的方式推出”：它是本课程中最深刻的结果，它的证明占了本课的大部分篇幅。最后，把完备性概括为“所有真的表达式都有证明”是不确切的；有证明的是有效的公式，即在每个赋值下都为真的公式，而不是在某个赋值下为真的公式：变元 $v_{1}$ 在许多赋值下为真，却不是定理。