专门做qq小工具的网站,广州一建建设集团,公司网站建设站酷,网站创建需要什么前言
前两节主要阐述了公理系统的发展历史#xff0c;一致性问题的提出#xff0c;以及希尔伯特的洞见#xff0c;本节将给出哥德尔证明所需的最后一次具体背景阐述#xff0c;包含两个问题#xff1a;一是罗素所著的《数学原理》是为何而写#xff1f;二是从数学原理中…前言
前两节主要阐述了公理系统的发展历史一致性问题的提出以及希尔伯特的洞见本节将给出哥德尔证明所需的最后一次具体背景阐述包含两个问题一是罗素所著的《数学原理》是为何而写二是从数学原理中截取一段示范对初等命题逻辑系统给出希尔伯特所设想的那种一致性的绝对证明。
《数学原理》的背景
就我们日常所接触的数学证明而言几乎任何一个证明中都包含大量默认的推理规则和逻辑定理。 比如证明素数有无穷多个其过程简述如下 假定素数有有穷个将最大的素数命名为 p p p。 那么考虑一个自然数 y ( 2 × 3 × 5 × 7 × ⋯ × p ) y(2\times3\times5\times7\times \cdots\times p) y(2×3×5×7×⋯×p)。 如果 y y y是素数那么 p p p就不是最大的素数 如果 y y y是合数那么它必定有素因子且素因子不属于 { 2 , 3 , 5 , 7 , ⋯ , p } \{2,3,5,7,\cdots ,p\} {2,3,5,7,⋯,p}中任何一个同样 p p p仍不是最大的素数。 y y y要么是素数要么是合数。 所以 p p p不是最大的素数不存在最大的素数。 以上推论可以说足够严谨了但较真的话能观察到其中包含了一些默认的规则比如为什么 y y y要么是素数要么是合数这其实是必然原理即 p ∨ ∼ p p\lor \sim p p∨∼p一个陈述或其非是必然的。我们日常使用这些逻辑原理而不自知事实上我们这种传统的逻辑演绎是严重不完整的。
逻辑的研究在近代复苏始于布尔的《逻辑的数学分析》他发明了布尔代数为传统逻辑原理提供了精准记法扩展了逻辑原理的研究。之后数学家尝试将纯数学变成形式逻辑的一部分这一思路的集大成这就是罗素的《数学原理》这一工作的目的是将所有数论和分析的概念用纯逻辑真理的基本命题演绎出来。虽然这个过程很复杂三卷数学原理中花费了几百页才从逻辑真理证明出112几乎没有人想用这样的系统做数论研究但《数学原理》实质上将数论系统的一致性化为形式逻辑本身一致性的问题就意义上数论的公理都是形式逻辑的定理它的另一个意义是把纯数学中所有陈述用一种标准方式进行编码明确了数学证明中推论规则。
初等命题逻辑一致性的绝对证明
初等命题逻辑系统形式化
形式化的一般步骤
首先我们要明晰一般系统是如何形式化的这里以几条原则说明。
指号目录此系统需要建立一个指号目录只允许用此目录中的指号构成串。可以理解为英文中的词汇表。形成规则表示指号形成串的规则这个按规则形成的串可以称为公式或者良构串或者叫句子。后面可能混用这些名词。形成规则只是指串是否合法和真假无关。转换规则实际上就是推论规则描述了公式的精细结构从某些公式推导其他具有既定结构公式的方法。初始公式即选择一些公式作为公理。
一般记号
这里额外补充一些书中的记法虽然下面列出了这些符号在命题逻辑系统中的含义但应当理解的是在完全形式化的系统中这些意义是抽离的本文中所有证明不需要默认这些符号有这些含义而是把这些符号当成完全无意义的指号 ∼ \sim ∼是非的缩写 ∨ \lor ∨是或的缩写 ⊃ \supset ⊃是“如果…那么…”的缩写或者理解为推导出或者叫做蕴涵。 ∧ \land ∧是与的缩写
初等命题逻辑系统的形式化
指号目录的选择包含变元和常项两种指号变元即可以使用句子替换的记号常项有句子连接词和标点符号。举例来说 ( p ∨ q ) ⊃ ( p ∨ q ) (p\lor q)\supset(p\lor q) (p∨q)⊃(p∨q)就是一个句子其中 p p p和 q q q是变元它们可以用另一个句子替换掉 ∨ ∧ ∼ ⊃ ( ) \lor\land\sim\supset () ∨∧∼⊃()等都是句子连接词或符号。形成规则 句子变元单独可视为一个句子公式、良构串。如果 S S S代表一个公式那么 ∼ ( S ) \sim(S) ∼(S)也是一个公式。如果 S 1 S_1 S1和 S 2 S_2 S2都是公式那么 ( S 1 ) ∧ ( S 2 ) (S_1)\land(S_2) (S1)∧(S2)、 ( S 1 ) ∨ ( S 2 ) (S_1)\lor(S_2) (S1)∨(S2)、 ( S 1 ) ⊃ ( S 2 ) (S_1)\supset(S_2) (S1)⊃(S2)都是公式。 转换规则有两条分别是 替换规则对于一个包含句子变元的公式总可以将其中某个变元的每一次出现都替换为一个公式从而得到一个新的公式。比如 p ⊃ p p\supset p p⊃p可以将 p p p替换为 p ∨ q p\lor q p∨q从而得到 ( p ∨ q ) ⊃ ( p ∨ q ) (p\lor q)\supset (p\lor q) (p∨q)⊃(p∨q)。分离规则如果有形式上是 S 1 S_1 S1和 S 1 ⊃ S 2 S_1\supset S_2 S1⊃S2的两个公式总可以推出公式 S 2 S_2 S2。例如有 p ∨ ∼ p p\lor\sim p p∨∼p和 ( p ∨ ∼ p ) ⊃ ( p ⊃ p ) (p\lor \sim p)\supset (p\supset p) (p∨∼p)⊃(p⊃p)那么有 p ⊃ p 。 p\supset p。 p⊃p。 初始公式公理选择这个演算的公理如下 ( p ∨ p ) ⊃ p (p\lor p)\supset p (p∨p)⊃p p ⊃ ( p ∨ q ) p\supset (p\lor q) p⊃(p∨q) ( p ∨ q ) ⊃ ( q ∨ p ) (p\lor q)\supset (q\lor p) (p∨q)⊃(q∨p) ( p ⊃ q ) ⊃ ( ( r ∨ p ) ⊃ ( r ∨ q ) ) (p\supset q)\supset ((r\lor p)\supset (r\lor q)) (p⊃q)⊃((r∨p)⊃(r∨q))
系统一致性的绝对证明
以下将分步骤给出此命题逻辑系统中一致性的绝对证明证明步骤中在《哥德尔证明》书中没有给出的部分大部分来自于罗素的《数学原理》。 Step1首先此系统中可推导出一个定理 p ⊃ ( ∼ p ⊃ q ) p\supset (\sim p\supset q) p⊃(∼p⊃q)证明过程如下。 必须先声明《哥德尔证明》这本书有漏掉的地方在罗素原版的《数学原理》明确给出了 p ⊃ q def ∼ p ∨ q p\supset q\overset{\text{def}}{}\sim p\lor q p⊃qdef∼p∨q此处证明需要用到这个定义。 根据公理2 p ⊃ ( p ∨ q ) p\supset (p\lor q) p⊃(p∨q)根据替换规则用 ∼ p \sim p ∼p取代 p p p可得 ∼ p ⊃ ( ∼ p ∨ q ) \sim p\supset(\sim p\lor q) ∼p⊃(∼p∨q) 根据定义上式子可重写为 ∼ p ⊃ ( p ⊃ q ) \sim p\supset(p\supset q) ∼p⊃(p⊃q) 再次运用替换规则用 ∼ p \sim p ∼p取代 p p p可得 ∼ ∼ p ⊃ ( ∼ p ⊃ q ) \sim\sim p\supset(\sim p\supset q) ∼∼p⊃(∼p⊃q) 到这一步证明还要继续因为这个形式系统中抽离了现实意义不能有“把 ∼ \sim ∼看做否定双重否定抵消”的想法。第二步需要证明一个重要的性质传递律。即若 a ⊃ b a\supset b a⊃b且 b ⊃ c b\supset c b⊃c则 a ⊃ c a\supset c a⊃c。由公理4出发 ( p ⊃ q ) ⊃ ( ( r ∨ p ) ⊃ ( r ∨ q ) ) (p\supset q)\supset ((r\lor p) \supset(r\lor q)) (p⊃q)⊃((r∨p)⊃(r∨q))将 p p p取代为 b b b将 q q q取代为 c c c则由分离规则通过 b ⊃ c b\supset c b⊃c和 ( b ⊃ c ) ⊃ ( ( r ∨ b ) ⊃ ( r ∨ c ) ) (b\supset c)\supset((r\lor b)\supset(r\lor c)) (b⊃c)⊃((r∨b)⊃(r∨c))立刻得出 ( r ∨ b ) ⊃ ( r ∨ c ) (r\lor b)\supset(r\lor c) (r∨b)⊃(r∨c)将 r r r用 a a a取代得到 ( a ∨ b ) ⊃ ( a ∨ c ) (a\lor b)\supset (a\lor c) (a∨b)⊃(a∨c)再将 a a a用 ∼ a \sim a ∼a取代得到 ( ∼ a ∨ b ) ⊃ ( ∼ a ∨ c ) (\sim a\lor b)\supset (\sim a\lor c) (∼a∨b)⊃(∼a∨c)即 ( a ⊃ b ) ⊃ ( a ⊃ c ) (a\supset b)\supset (a\supset c) (a⊃b)⊃(a⊃c)再用一次分离规则就可以得出 a ⊃ c a\supset c a⊃c故传递律得证。第三步需要证明 p ⊃ p p\supset p p⊃p。通过公理2和公理1 p ⊃ ( p ∨ p ) p\supset(p\lor p) p⊃(p∨p)和 ( p ∨ p ) ⊃ p (p\lor p)\supset p (p∨p)⊃p再根据传递律即可证明 p ⊃ p p\supset p p⊃p。接下来需要证明 p ⊃ ∼ ∼ p p\supset\sim\sim p p⊃∼∼p。对公理3运用两次替换规则可得 ( ∼ p ∨ ∼ q ) ⊃ ( ∼ q ∨ ∼ p ) (\sim p\lor\sim q)\supset(\sim q\lor\sim p) (∼p∨∼q)⊃(∼q∨∼p)再根据定义可将其重写为 ( p ⊃ ∼ q ) ⊃ ( q ⊃ ∼ p ) (p\supset\sim q)\supset(q\supset\sim p) (p⊃∼q)⊃(q⊃∼p)此时再进行两次取代将 p p p取代为 ∼ p \sim p ∼p将 q q q取代为 p p p可得 ( ∼ p ⊃ ∼ p ) ⊃ ( p ⊃ ∼ ( ∼ p ) ) (\sim p\supset\sim p)\supset(p\supset\sim(\sim p)) (∼p⊃∼p)⊃(p⊃∼(∼p))对步骤3得出的 p ⊃ p p\supset p p⊃p用替换规则得到 ∼ p ⊃ ∼ p \sim p\supset \sim p ∼p⊃∼p再用分离规则可得 p ⊃ ∼ ( ∼ p ) p\supset\sim(\sim p) p⊃∼(∼p)。综合1中的结果和4中的结果 p ⊃ ∼ ( ∼ p ) p\supset\sim(\sim p) p⊃∼(∼p)和 ∼ ∼ p ⊃ ( ∼ p ⊃ q ) \sim\sim p\supset(\sim p\supset q) ∼∼p⊃(∼p⊃q)运用传递律可得 p ⊃ ( ∼ p ⊃ q ) p\supset(\sim p\supset q) p⊃(∼p⊃q) Step2在此定理的前提下如果 S S S即其形式否定 ∼ S \sim S ∼S都可以从此命题系统中推导出来用替换规则让 S S S代替 p p p可得 S ⊃ ( ∼ S ⊃ q ) S\supset (\sim S\supset q) S⊃(∼S⊃q)运用分离规则可得 ∼ S ⊃ q \sim S\supset q ∼S⊃q再用一次分离规则即可得到 q q q。
由于 q q q可以通过替换规则带入任何公式那么任何公式都能通过这组公理推导出来实际上是不可能的。这个结论的内涵是如果 S S S和 ∼ S \sim S ∼S都可以由这组公理推导出来那么任何公式都可以推导出来也就是我们常说的假命题可以推出任何命题。
当然为了严谨性不能轻易否定证明还要继续下去这个公理系统允许推导出任何公式吗如果找到一个公式是确信无法由公理系统推导的那么我们最初的前提 S S S和 ∼ S \sim S ∼S都可由这组公理推导出来就是错误的那么系统就是一致的。
Step3现在的任务是证明存在一个公式无法由公理推导出来即某个公式不是定理。完成这个任务的方式是进行元数学方面的推理。基本思路是这样的
找到公理的一致属性。确认转换规则将遗传这个属性所以任何公理推导出的定理都具备此属性。写出一个不具备此属性的公式那么此公式就不是定理。
重言属性
罗素这套公理系统中可以选择“重言属性”在非形式化的常见的命题逻辑解释下重言属性即排除没有逻辑可能性的属性在任意可能的世界为真比如非 p p p或 p p p。当然这种解释有悖我们形式化的初衷还是用现实中的模型用真假来解释。那么更抽象的重言属性的描述在此展开。
我们创建两个类 K 1 K_1 K1和 K 2 K_2 K2同时我们将所有公式分类分为基本公式和非基本公式基本公式就是用作句子变元的字母非基本公式就是排除了基本公式外的其他。
首先我们将基本公式任意放在两个类中。
非基本公式按以下规则放入两个类中
如果 S 1 S_1 S1和 S 2 S_2 S2都在 K 2 K_2 K2中那么具有 S 1 ∨ S 2 S_1\lor S_2 S1∨S2的公式也放在 K 2 K_2 K2中否则放在 K 1 K_1 K1中。如果 S 1 S_1 S1在 K 1 K_1 K1中 S 2 S_2 S2在 K 2 K_2 K2中那么形式为 S 1 ⊃ S 2 S_1\supset S_2 S1⊃S2的公式放在 K 2 K_2 K2中否则它放在 K 1 K_1 K1中。如果 S 1 S_1 S1和 S 2 S_2 S2都在 K 1 K_1 K1中形式为 S 1 ∧ S 2 S_1\land S_2 S1∧S2的公式被置于 K 1 K_1 K1中否则放在 K 2 K_2 K2中。如果 S S S在 K 1 K_1 K1中那么具有 ∼ S \sim S ∼S形式的公式放于 K 2 K_2 K2中否则置于 K 1 K_1 K1中。
此时可以定义重言式为一个当且仅当它属于 K 1 K_1 K1类的公式。
可以考察四条公理 ( p ∨ p ) ⊃ p (p\lor p)\supset p (p∨p)⊃p如果基本公式句子变元 p p p被分到 K 1 K_1 K1那么根据规则1 ( p ∨ p ) (p\lor p) (p∨p)也属于 K 1 K_1 K1根据规则2 ( p ∨ p ) ⊃ p (p\lor p)\supset p (p∨p)⊃p仍应放到 K 1 K_1 K1中如果基本公式句子变元 p p p被分到了 K 2 K_2 K2那么根据规则1 ( p ∨ p ) (p\lor p) (p∨p)属于 K 2 K_2 K2根据规则2 ( p ∨ p ) ⊃ p (p\lor p)\supset p (p∨p)⊃p仍应放到 K 1 K_1 K1中。 这里以表格的形式列出第二公理的分析。 p p p q q q ( p ∨ q ) (p\lor q) (p∨q) p ⊃ ( p ∨ q ) p\supset(p\lor q) p⊃(p∨q) K 1 K_1 K1 K 1 K_1 K1 K 1 K_1 K1 K 1 K_1 K1 K 1 K_1 K1 K 2 K_2 K2 K 1 K_1 K1 K 1 K_1 K1 K 2 K_2 K2 K 1 K_1 K1 K 1 K_1 K1 K 1 K_1 K1 K 2 K_2 K2 K 2 K_2 K2 K 2 K_2 K2 K 1 K_1 K1 第三公理的分析如下。 p p p q q q ( p ∨ q ) (p\lor q) (p∨q) ( q ∨ p ) (q\lor p) (q∨p) ( p ∨ q ) ⊃ ( q ∨ p ) (p\lor q)\supset(q\lor p) (p∨q)⊃(q∨p) K 1 K_1 K1 K 1 K_1 K1 K 1 K_1 K1 K 1 K_1 K1 K 1 K_1 K1 K 1 K_1 K1 K 2 K_2 K2 K 1 K_1 K1 K 1 K_1 K1 K 1 K_1 K1 K 2 K_2 K2 K 1 K_1 K1 K 1 K_1 K1 K 1 K_1 K1 K 1 K_1 K1 K 2 K_2 K2 K 2 K_2 K2 K 2 K_2 K2 K 2 K_2 K2 K 1 K_1 K1 第四公理分析如下。 p p p q q q r r r ( p ⊃ q ) (p\supset q) (p⊃q) ( r ∨ p ) (r\lor p) (r∨p) ( r ∨ q ) (r\lor q) (r∨q) ( r ∨ p ) ⊃ ( r ∨ q ) (r\lor p)\supset (r\lor q) (r∨p)⊃(r∨q) ( p ⊃ q ) ⊃ ( ( r ∨ p ) ⊃ ( r ∨ q ) ) (p\supset q)\supset ((r\lor p)\supset (r\lor q)) (p⊃q)⊃((r∨p)⊃(r∨q)) K 1 K_1 K1 K 1 K_1 K1 K 1 K_1 K1 K 1 K_1 K1 K 1 K_1 K1 K 1 K_1 K1 K 1 K_1 K1 K 1 K_1 K1 K 1 K_1 K1 K 1 K_1 K1 K 2 K_2 K2 K 1 K_1 K1 K 1 K_1 K1 K 1 K_1 K1 K 1 K_1 K1 K 1 K_1 K1 K 1 K_1 K1 K 2 K_2 K2 K 1 K_1 K1 K 2 K_2 K2 K 1 K_1 K1 K 1 K_1 K1 K 1 K_1 K1 K 1 K_1 K1 K 1 K_1 K1 K 2 K_2 K2 K 2 K_2 K2 K 2 K_2 K2 K 1 K_1 K1 K 2 K_2 K2 K 2 K_2 K2 K 1 K_1 K1 K 2 K_2 K2 K 1 K_1 K1 K 1 K_1 K1 K 1 K_1 K1 K 1 K_1 K1 K 1 K_1 K1 K 1 K_1 K1 K 1 K_1 K1 K 2 K_2 K2 K 1 K_1 K1 K 2 K_2 K2 K 1 K_1 K1 K 2 K_2 K2 K 1 K_1 K1 K 1 K_1 K1 K 1 K_1 K1 K 2 K_2 K2 K 2 K_2 K2 K 1 K_1 K1 K 1 K_1 K1 K 1 K_1 K1 K 1 K_1 K1 K 1 K_1 K1 K 1 K_1 K1 K 2 K_2 K2 K 2 K_2 K2 K 2 K_2 K2 K 1 K_1 K1 K 2 K_2 K2 K 2 K_2 K2 K 1 K_1 K1 K 1 K_1 K1
由此可见四条公理都具有重言属性。接下来还需要考察重言属性在转换规则下会传递。 对于替换规则其实替换规则不改变重言属性已经隐含在 K K K的定义里了基本公式即用作句子变元的字母也是替换规则允许替换的项而 K K K的分类中基本公式允许任意分布在 K 1 K_1 K1或 K 2 K_2 K2中不改变公式的重言属性。 对于分离规则 S 1 S_1 S1和 S 1 ⊃ S 2 S_1\supset S_2 S1⊃S2如果都具有重言属性必须证明 S 2 S_2 S2具有重言属性假定 S 2 S_2 S2不具有重言属性即 S 2 S_2 S2属于 K 2 K_2 K2这立即引起了矛盾因为 S 1 S_1 S1位于 K 1 K_1 K1意味着根据重言属性规则2 S 1 ⊃ S 2 S_1\supset S_2 S1⊃S2也属于 K 2 K_2 K2前面以及假定了 S 1 ⊃ S 2 S_1\supset S_2 S1⊃S2具有重言属性它位于 K 1 K_1 K1。
Step 4现在可以总结前面几个步骤给出整个证明脉络了首先我们推出了如果此系统允许 S S S和 ∼ S \sim S ∼S都作为定理那么我们可以推出的所有公式都是定理然后我们又推出系统所有的定理都是重言式现在只要找出一个公式不是重言式那么我们的前提就不成立。这样的公式大量存在比如 p ∨ q p\lor q p∨q就可以不是重言式那两个基础句子变元都可以放在 K 2 K_2 K2类中。至此我们完成了初等命题逻辑系统一致性的绝对证明。
