可靠性定理

维基百科，自由的百科全书

可靠性定理是数理逻辑的最基本结果。它们有关于某个形式逻辑语言与这个语言的形式演绎系统的特定语义理论。可靠性定理有两种主要变体: 弱可靠性的和强可靠性的。

演绎系统的弱可靠性定理声称，在这个演绎系统中任何可证明的句子，在所有释义或这个理论所基于的语言的语义理论的模型上为真。用符号表示，这里的 S 是演绎系统，而 L 是语言和它的语义理论在一起，而 P 是 L 的句子: 若 $\vdash _S P$ ，则 $\vDash _L P$ 。

演绎系统的强可靠性定理声称，演绎系统所基于的语言的任何句子 P，可以同这个语言的一个句子集合 Γ 推导出来，则它也是这个集合 Γ 的语义推论，在使 Γ 的所有成员为真的任何模型也使 P 为真的意义上。用符号表示，这里的 Γ 是 L 句子的一个集合: 若 $\Gamma \vdash _S P$ , 则 $\Gamma \vDash _L P$ 。

“强”与“弱”的意义在于，强可靠性考虑句子的任意集合，而与弱可靠性有关的句子的空集是这种集合之一。大多数但不是全部演绎系统，强可靠性和弱可靠性都成立。

可靠性定理的逆命题是语义完备性定理。在强形式下，它声称对于一个演绎系统和语义理论，是一个句子集合的语义推论的任何句子可以在这个演绎系统中从这个集合推导出来。(在一阶完备性定理的情况下常叫做哥德尔完备性定理)。用符号表示: 若 $\Gamma \vDash _L P$ ，则 $\Gamma \vdash _S P$ 。

非形式的，演绎系统的可靠性定理告诉我们用这个演绎系统可以推导或证明的任何东西都是你希望能够推导或证明的东西。因此，没有你不想推导出的东西可以被推导出来。所以，推导关于语义可以被信任。完备性告诉我们你希望能被推导或证明的所有东西都可以被推导出来。

哥德尔第一不完备定理保证对于有充分表达力的语言，可能没有演绎系统关于经典语义是完备的，在其中所有句子是要么为真要么为假。因此，不是所有可靠的演义系统都是完备的。

而完备性定理一般被认为是对有价值的演绎系统根本上的最小要求。这是因为如果演绎系统是不可靠的，在这个系统中可以被推导或证明的一个句子不告诉我们关于这个句子的语义性质的任何事情。