essential of Incompleteness

《数学女孩3-哥德尔不完备定理》

形式系统P

常量

• 0（零）是常量
• f（后继数）是常量
• ￢（非）是常量
• ∨（逻辑或）是常量
• ∀（任意的）是常量
• ( （开括号）是常量
• ) （闭括号）是常量

变量

变量的类型包括1,2,3......

• 第1型变量 x1，y1，z1...是用于数的变量，将其称为第1型变量。
• 第2型变量 x2，y2，z2...是用于数的集合的变量，将其称为第2型变量。
• 第3型变量 x3，y3，z3...是用于数的集合的集合的变量，将其称为第3型变量。

数项

数项用于在形式系统P中表示数

• 用数项0表示0
• 用数项f0表示1
• 用数项ff0表示2
• 用数项fff0表示3
  ......
  我们把0，f0，ff0，fff0，... 称作数项

符号

• 第1型符号：我们把0，f0，ff0，.......或是 x，fx，ffx，fffx，......称为第1型符号，此处设x是第1型变量
• 第2型符号：我们把第2型变量称为第2型符号
• 第3型符号：我们把第3型变量称为第3型符号

一直可以定义到第n型符号

基本逻辑公式

我们把呈a(b)这种形式的符号序列称为基本逻辑公式。这里假设a是第a+1型符号，b是第n型符号。
x2(0)，y2(ffx1)，z3(x2) 有点类似集合与元素的意思

逻辑公式

• 基本逻辑公式是逻辑公式
• 若a是逻辑公式，则￢(a) 也是逻辑公式
• 若a和b是逻辑公式，则(a)∨(b)也是逻辑公式
• 若a是逻辑公式且x为变量，则∀x(a)也是逻辑公式
• 只有满足以上条件的才是逻辑公式

省略形式

• 我们将(a)→(b) 定义为 (￢(a))∨(b)
• 我们将(a)∧(b) 定义为 ￢((￢(a))∨(￢(b)))
• 我们将(a)⇔(b) 定义为 ((a)→(b)) ∧((b)→(a))
• 我们将∃x(a) 定义为 ￢(∀x(￢(a)))
  为了看起来方便，后面会省略冗长的括号

公理

皮亚诺公理导入形式系统P

• 公理Ⅰ-1：
• 公理Ⅰ-2：
• 公理Ⅰ-3：

命题逻辑的公理导入形式系统P

• 公理Ⅱ-1：
• 公理Ⅱ-2：
• 公理Ⅱ-3：
• 公理Ⅱ-4：

导入谓词逻辑的公理

• 公理Ⅲ-1：
  注意，这里假设：
  subst(a,v,c)表示把a的所有自由的v用c代换后的逻辑公式
  c跟v是同一型的符号
  在a里，v只要是自由的，c中就没有受约束的变量
  例如：a是逻辑公式￢(x2(x1))，v是名为x1的第1型变量，c是名为f0的第1型符号（数项）此时subst(a,v,c)就是逻辑公式￢(x2(f0))

• 公理Ⅲ-2：
  这里假设v是任意变量，b中不出现自由的v。
  要是b里不出现变量v，那么就不会受∀v的影响。

集合的内涵公理

• 公理Ⅳ：
  u是第n+1型变量，v是第n型变量
  a中不出现自由的u
  即：逻辑公式a，能决定集合u

集合的外延公理

• 公理Ⅴ：
  我们把这个逻辑公式，以及将该逻辑公式形式提升后的逻辑公式定为公理。形式提升指的是让符号的类型都增加相同的数。
  
  
  ......
  等等

推理规则

• 推理规则1：根据a和a→b，得到b
• 推理规则2：根据a，得到∀v(a)
  此处v是任意的变量，既然没有条件的情况下都能得到a，那么即使增加任意的这个条件也能导出a。

哥德尔数

哥德尔数是分配给形式系统P的“符号，符号序列，符号序列的序列”的编号。
定义基本符号的哥德尔数，我们把不大于13的奇数作为哥德尔数分配给常量：

常量	0	f	￢	∨	∀	(	)
哥德尔数	1	3	5	7	9	11	13

把大于13的质数分配给第1型变量

第1型变量	x1	y1	z1
哥德尔数	17	19	23

把大于13的质数的平方分配给第2型变量

第2型变量	x2	y2	z2
哥德尔数	172	192	232

把大于13的质数的立方分配给第3型变量

第3型变量	x3	y3	z3
哥德尔数	173	193	233

ⅡⅢⅣⅤ ∨∧￢∀∃→