数理逻辑概要

逻辑是所有学科的基础，它那原始而又不言自明的特点却阻碍了研究的深入。直到19世纪后期，随着非欧几何的发现，以及要为各门分析学科提供一个严格理论基础的愿望，数学家们才对逻辑的研究有了一丝兴趣。在20世纪初，悖论的出现震惊了数学界！撒谎者悖论、理发师悖论、Cantor关于基数的悖论等等，让数学家们使出浑身解数去避免它们。

Russel注意到悖论中自我引用的特点，建议每个对象都应该有一个 “类型数”, 说 “X是Y的一个成员” 意味着Y的类型数比X的类型数大。Brouwer则拒绝接受 “排中律 “：P与非P二者必须且只能居其一；这对有限集是对的，但不能推广到无穷集。还有人提出，不能假设对于每种性质P(x)，都存在某些个体x满足该性质；必须要有确定的构造方法才行；人们只能相信直觉。依我看，集合基数相等的1对1原则，也只是对有限集成立，对无穷集是不对的，遗憾的是没有其它方法去定义基数相等。

Hilbert还想为所有的数学学科找到一个完备而又相容（不能推出相互矛盾的两个结论P与非P）的公理系统。一个数学系统指的是一种演绎机制，包含（1）一个对象集，包含数字、形状、关系、量词、标点等，甚至是集合（称为高阶逻辑）。（2）一套符号演算法则或函数关系，即对一个或多个对象进行变换或结合的法则（k元运算）以形成表达式或新的对象；如逻辑连接词、算子等。（3）一组公理，确定演算或关系所遵循的规则；比如，加法应当满足交换律、结合律；距离应当满足对称性、三角不等式、正定性（至少是可分离性，一致拓扑结构的要求）。（4）一组推导规则R，可以从公理推出新的定理。

现在关于逻辑学的定义是 “推理方法的分析”(Analysis of methods of reasoning)，它注重推理的形式，而不是对象的含义或内容。所谓形式推理，就是从前提S（命题或公式的集合）出发，按照一定的法则R（Rules of inferences），推出新的结论C（命题或公式）；简记为 S|--(R) C。可推导性（Deducibility）的衡量需要语义上的解释及真值赋值（truth valuation）。

一种真值赋值指的是从对象（命题符号）集到集合{0， 1}的一个函数。对于一个公式（表达式）A，其赋值由以下规则确定：v(~A) = 1 – v(A), v(A∧B) = v(A)v(B), v(A ∨ B) = v(A) + v(B) - v(A)v(B)，v(A→B) = v(~A ∨ B)，v(A↔B) = v(A→B) v(B→A)，v(AuB) = v(~B →A)，u指的是”unless”，也是一个逻辑连接词。这些规则其是就是集合运算的公理；蕴含→等价于集合的包含关系。一个公式（命题）A称为重言式（Tautology），如果对任何赋值v都有v(A) = 1。如果对任何赋值v都有v(A) = 0，则A是一个矛盾式。一个公式是可满足的，如果存在一种赋值v, 使得v(A) = 1; 也就是说，它的反公式~A不是重言式。

其实，表达式的合法形成也可以数值化。比如给左括号赋值-1，右括号赋值+1, 逗号赋值0；只有当整个表达式的总赋值为0时，才是有效的（valid）。在模糊逻辑中，一个式子还可以赋予一个分数值；只有递归求和的总值达到一定标准如1时，式子才是有效的。在赋值后的公式集上，还可以开展统计分析。

推断法则必须规定哪些行为是不被容许的。比如，不能用同音或者同形的字代替单词，不能有循环定义，不能自相矛盾。在命题逻辑中，有11条推理规则：（1）自反性A|-A, （2）可任意增加前提，（3）否定词的消去或引入，即S, A|-B, S, A|-~B, 那么S|-~A，（4）→的引入和消去，（5）且∧的引入和消去，（6）或∨的引入和消去，（7）等价↔的引入和消去。在谓词逻辑中，还有量词及等号=的引入和消去规则，共计17条。这其实就是集合运算的同一律、补、交、并、蕴含关系的反映。

对一个形式推演系统，通常有四种要求或性质：可靠性(Soundness)、兼容性（Consistency）、完备性（Completeness）、有效公理化(effectively axiomization)。所谓可靠性指的是，在这个演绎系统中任何可以形式化证明的命题，在所有释义以及这个理论所基于的真质赋值为真，即为重言式。

一个公式集S是兼容性的，指的是不能从它同时推出一个命题及其否命题。可以证明，如果S是可满足的(Satisfiable)，那么S一定是兼容的。一个公式集S是可满足的，要求存在一种真值的赋值方式v，使得对其中每个公式A，都有v(A) = 1。

一个系统的完备性（Completeness）指的是，任何重言式T都是可以证明的，即有一个形式推理的序列，T位于序列的最后。重言式可以认为是语义上完备的，而这里要求公理系统能够形式证明所有的重言式（Tautologies），是语法意义上完备的。

在分析学中，一个集合的完备性指的是，其中的任何收敛序列都有极限在集中，也就是对极限运算是封闭的。在逻辑学中，也可以要求所有算子的值域能够涵盖所有的表达式（公式），此时称为系统是归纳的（Inductive）。此外还有紧性的要求：任何闭集的每个开覆盖都有有限覆盖；在逻辑学中，紧性的要求则是，任何证明可以在有限步内完成; 也就是说，一个公式子集S是可满足的，当且仅当它的每个有限子集是可满足的。

一个系统可以有效地公理化，指的是其公式（定理、表达式）的集合是可数递归的；也就是说，在一个推断或者证明的过程中，或一个命题公式的序列F1，F2, …, Fn, … 中，每个公式Fn要么是一条公理，要么是前面某些公式、按照规则R推出的结论。Peano算术、Zermelo-Fraenkel集合论（ZFC）、Euclid几何都是可以递归生成的，分析学却不能。

哥德尔的不完备性定理说，包含Peano算术系统的形式系统不可能四条性质都具备。第一条不完备定理表明，任何一个允许定义自然数的体系必定是不完备的：它包含了不能在此系统内以一阶谓词逻辑形式证明的命题，并且该命题的否命题也不能在该体系内以一阶谓词逻辑的形式证明。在欧几里得几何中，如果把平行公设去掉，就得到一个不完备的体系。不完备的体系可能只意味着尚未找出所有必须的公理而已；但在多数情况下，例如在数论或者实分析中，永远不可能找出公理的完整集合。换句话说，每一次将一个命题作为公理加入，将总有另一个命题出现在所能形式证明的范围之外。

如果加入无穷条公理（例如，所有真命题）到公理列表中，确保所有命题都可证明为真或假，但得到的公理列表将不再是可数递归的。给出任意一条命题，将没有机械的方法判定它是否是系统的一条公理。即使给出一个证明，一般来说也无法检查它是否正确。

哥德尔第二定理说：如果一个（强度足以证明基本算术公理的）公理系统可以用来证明它自身的兼容性，那么它是不兼容的。于是，为了确立系统S的兼容性，就要构建另一个系统T，但是T中的证明并不是有效的，除非不使用S就能确立T的兼容性。比如，自然数上的皮亚诺公理的兼容性可以在ZFC集合论中证明，但不能单独在自然数理论范围内证明。ZFC也不能在自身内证明其兼容，但如果增加一条“存在一个无法达到的基数”，则可以证明兼容性。

物理学家们说，任何公式都是有用的，哪管它什么完备性；不兼容的系统随处可见，不能可数递归生成又如何。发散的、连续求和的式子，也是随手写来，不能积分化也行啊！物理学科尚且难以统一（Grand Unification），何况数学。玩玩逻辑推理，以防大脑衰退，诡辩也是可以的；这才是逻辑的有用性。