《数学女孩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 |
ⅡⅢⅣⅤ ∨∧￢∀∃→
网友评论