essential of Incompleteness

作者: little_wang | 来源:发表于2018-12-08 13:30 被阅读0次

《数学女孩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： $\small \neg (fx_1 = 0)$
公理Ⅰ-2： $\small (fx_1 = fy_1) \to (x_1 = y_1)$
公理Ⅰ-3： $\small x_2(0) \land \forall x_1(x_2(x_1) \to x_2(fx_1)) \to \forall x_1(x_2(x_1))$

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

公理Ⅱ-1： $\small p \lor p \to p$
公理Ⅱ-2： $\small p \to p \lor q$
公理Ⅱ-3： $\small p\lor q \to q \lor p$
公理Ⅱ-4： $\small (p \to q) \to (r\lor p \to r \lor q)$

导入谓词逻辑的公理

公理Ⅲ-1： $\small \forall v(a) \to subst(a, v, c)$
注意，这里假设：
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： $\small \forall v (b \lor a) \to b\lor \forall v(a)$
这里假设v是任意变量，b中不出现自由的v。
要是b里不出现变量v，那么就不会受∀v的影响。

集合的内涵公理

公理Ⅳ： $\small \exists u (\forall v(u(v) \rightleftarrows a))$
u是第n+1型变量，v是第n型变量
a中不出现自由的u
即：逻辑公式a，能决定集合u

集合的外延公理

公理Ⅴ： $\small \forall x_1(x_2(x_1) \rightleftarrows y_2(x_1)) \to (x_2 = y_2)$
我们把这个逻辑公式，以及将该逻辑公式形式提升后的逻辑公式定为公理。形式提升指的是让符号的类型都增加相同的数。
$\small \forall x_1(x_2(x_1) \rightleftarrows y_2(x_1)) \to (x_2 = y_2)$
$\small \forall x_2(x_3(x_2) \rightleftarrows y_3(x_2)) \to (x_3 = y_3)$
......
等等

推理规则

推理规则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
哥德尔数	17²	19²	23²

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

第3型变量	x3	y3	z3
哥德尔数	17³	19³	23³

ⅡⅢⅣⅤ ∨∧￢∀∃→

网友评论

本文标题：essential of Incompleteness

本文链接：https://www.haomeiwen.com/subject/auxqhqtx.html

延伸阅读

深度阅读

您也可以注册成为美文阅读网的作者，发表您的原创作品、分享您的心情！