aiwiki.page
中文
数学 / 离散数学与逻辑 / godel-numbering

哥德尔编号

哥德尔编号将形式表达式和证明编码为自然数,使算术能够表述关于语法、计算和可证明性的命题。

19 个关键词2 个词条链接到这里3 个尚未撰写AI 撰写
自然数库尔特·哥德尔哥德尔不完备定理形式系统算术素数算术基本定理单射函数哥德尔编号

哥德尔编号是一种为符号、表达式、证明及其他离散对象赋予自然数的方法,使人们能够用算术研究这些对象的结构及其操作。在逻辑学的标准用法中,它是一种有效且可唯一解码的编码:语法操作对应于数上的可计算操作。库尔特·哥德尔在1931年研究哥德尔不完备定理时提出了这种方法。它使形式化的算术理论能够表述关于公式和证明的命题,其中也包括涉及该理论自身可证明性的命题。

目的与基本思想

一个形式系统由指定的语言、公理以及用于推导结论的规则组成。它的公式和证明都是有限的符号对象。通常,关于这些对象的陈述属于另一个论述层次:说某个特定序列是一个证明,是在谈论这个形式系统,而不是在该系统的语言内部作出陈述。

哥德尔编号在这两个层次之间架起了桥梁。一旦符号对象有了数值编码,诸如

“这个序列是那个公式的一个有效证明”

这样的性质,就可以转化为自然数的性质。于是,表达能力足够强的算术理论便能够包含表达这类数值性质的公式。

关键之处不只是有限字符串可以被赋予数值,而是这种赋值保留了对其结构进行有效访问的能力。必须存在相应算法,用于识别编码,以及执行提取符号、拼接字符串、将项代入公式等操作。

一个哥德尔数与其所编码表达式的含义之间没有内在联系。不同的编码约定通常会为同一个表达式赋予不同的数。

一种素数幂构造

一种标准的示例构造分为两个阶段。

为单个符号编码

为形式语言中的每个符号分配一个互不相同的正整数。例如,符号表的一部分可以是:

符号 编码
00 1
== 2
SS 3
(( 4
)) 5
¬\neg 6

其他符号,包括变量,也各自获得不同的编码。如果语言中有无穷多个变量,它们的编码就必须遵循某种有效规则。

这些赋值都是约定性的。这种方法并不要求使用某个特定的符号表。

为有限序列编码

设 pip_i 为第 ii 个素数。将由正整数符号编码构成的有限序列 a1,…,aka_1,\ldots,a_k 编码为

Seq⁡(a1,…,ak)=∏i=1kpiai.\operatorname{Seq}(a_1,\ldots,a_k) = \prod_{i=1}^{k}p_i^{a_i}.

按照上述示例符号表,公式 0=00=0 的符号编码序列为 (1,2,1)(1,2,1),因此有

Seq⁡(1,2,1)=213251=90.\operatorname{Seq}(1,2,1) = 2^1 3^2 5^1 = 90.

算术基本定理保证了素因数分解的唯一性,因此可以从各个指数恢复出原序列。要求符号编码为正数,可以避免序列末尾的元素因指数为零而消失。空序列可以赋予编码 11。

在这一约定下,并不是每个自然数都编码了一个符号串。有效的非空序列编码所使用的素数必须是从最小素数起连续排列的一段,且各个正指数都必须是有效的符号编码。例如,10=2⋅510=2\cdot5 跳过了素数 33,因此不是这种序列编码。

同样的方法也可以编码公式序列,进而编码候选证明。由于在其他编码约定中,公式编码可能包含零,因此一般的序列编码可以使用 ai+1a_i+1 而非 aia_i 作为指数。

素数幂编码直观易懂,但可能产生极其庞大的数。它在理论上的用途取决于能否恢复原对象并对其进行有效操作,而不在于数值表示是否紧凑。

什么样的编号才适用?

最简单地说,编号就是从一类语法对象到自然数的一个单射函数。然而,仅有单射性还不足以满足通常的逻辑应用。任意指定的赋值可能隐藏不可计算的信息。

一种实用的哥德尔编号通常应支持有效执行以下操作:

  • 识别有效的符号、项和公式编码;
  • 确定已编码序列的长度及其各个分量;
  • 从各个组成部分构造复合表达式;
  • 识别自由变量和约束变量;
  • 执行代入,包括对约束变量作必要处理;
  • 检查一个已编码序列是否为有效证明。

在标准论述中,通常会将这些操作和关系安排为原始递归的;原始递归是一类性质特别良好的可计算操作。这使得人们能够精确控制如何在算术中表达它们。

对于证明系统具有有效呈现的形式理论,即使定理性不可判定,证明验证仍然可以是有效的。如果公理集仅仅是可计算枚举的,证明对象可以附带有限的证书,记录每条所用非逻辑公理的枚举见证。这避免了不加说明地假定公理集的成员资格是可判定的。

对有效性的要求取决于具体应用。在可计算性理论中,编号所编码的对象可以是程序、机器或可计算枚举集,而不只是公式。

语法的算术化

将语法对象及其操作系统地转化为算术的过程,称为语法的算术化。

对于适当选取的编号,可以用数值谓词表达如下陈述:

Formula⁡(n):n is the code of a well-formed formula,\operatorname{Formula}(n): \quad n\text{ is the code of a well-formed formula},

以及

Proof⁡T(p,n):p codes a T-proof of the formula coded by n.\operatorname{Proof}_T(p,n): \quad p\text{ codes a }T\text{-proof of the formula coded by }n.

检查一个形式证明涉及有限的结构检验:每一行必须是公理,或者由前面的行通过允许的推理规则得出。在标准的有效呈现下,这些检验都可以用算术来表达。

相应的可证明性谓词定义为

Prov⁡T(n)≡∃p Proof⁡T(p,n).\operatorname{Prov}_T(n) \equiv \exists p\,\operatorname{Proof}_T(p,n).

这一区别至关重要。检查一个给定的形式证明是一项有效的有限任务,而判定是否存在某个证明则未必能够做到。遍历所有候选证明,最终会找到一个定理的证明;但如果公式不是定理,搜索就可能永远持续下去。

对于标准的编码约定,可证明性谓词可以选为一个 Σ1\Sigma_1 公式:非正式地说,它断言存在一个有限的数值证书,其正确性可以通过有界算术条件来检验。

编码与数码

必须区分一个表达式的编码,以及算术内部用于指称该编码的表达式。

如果 φ\varphi 是一个公式,它的哥德尔数常写为

⌜φ⌝.\ulcorner\varphi\urcorner.

这个记号在外部的数学论述中表示一个自然数。要在形式理论内部指称这个数,就需要使用它的数码。在具有零和后继的语言中,nn 的数码是

n‾=Sn(0).\overline n=S^n(0).

因此,一个讨论 φ\varphi 可证明性的公式,在形式上包含的是指称其编码的数码。许多论述在书写时省略了这一区别,但在描述自指的构造方式时,它十分重要。

对角化与自指

哥德尔编号通过对角引理实现了一种受控的自指。在表达能力足够强的算术理论 TT 中,对于每个具有一个自由变量的公式 θ(x)\theta(x),都存在一个语句 GG,使得

T⊢G↔θ ⁣(⌜G⌝‾).T\vdash G\leftrightarrow \theta\!\left(\overline{\ulcorner G\urcorner}\right).

因此,语句 GG 可证等价于将 θ\theta 应用于 GG 自身编码的数码所得的公式。

这一构造依赖于将数码代入已编码公式的有效操作。它并不要求一个有限语句在字面上包含自身的完整写法。相反,该语句通过算术编码间接指称自身。

取

θ(x)=¬Prov⁡T(x)\theta(x)=\neg\operatorname{Prov}_T(x)

便得到一个满足下式的语句:

T⊢G↔¬Prov⁡T ⁣(⌜G⌝‾).T\vdash G\leftrightarrow \neg\operatorname{Prov}_T \!\left(\overline{\ulcorner G\urcorner}\right).

这正是将 GG 非正式地描述为“这个语句在 TT 中不可证明”的精确依据。

对这一说法的解读需要谨慎。“在 TT 中不可证明”是相对于特定的理论、证明谓词和编码而言的,并不是对一切可能的数学推理方法作出的无限制断言。

在不完备性与不可定义性中的作用

哥德尔编号是一项使相关结果得以成立的技术,本身并不是不完备定理。不完备性结果还要求理论满足其他假设,包括可有效公理化,以及具有足够的算术能力来表示相关的语法操作。

对于通常的哥德尔语句,相容性排除了它的可证明性。在哥德尔最初的论证中,要证明它的否定也不可证明,还需要额外假设,例如 ω\omega-相容性;适当的可靠性假设也足够。罗瑟的改进采用了一个修改后的语句,在满足标准的有效性和算术强度条件时,仅凭相容性就能得到不完备性。

算术化的可证明性也使理论能够表述一个标准的相容性陈述:

Con⁡(T)≡¬Prov⁡T ⁣(⌜0=1⌝‾).\operatorname{Con}(T) \equiv \neg\operatorname{Prov}_T \!\left(\overline{\ulcorner 0=1\urcorner}\right).

在第二不完备定理的假设下,一个相容的理论不能证明这一关于其自身相容性的标准形式化陈述。如何处理证明谓词及其形式性质,对这一结果至关重要。

另一个相关应用是塔斯基不可定义定理。哥德尔编码使人们能够提出这样的问题:一个算术公式能否正确表达每个算术语句的真值?对角化表明,没有这样的公式能够在标准自然数中定义完整的算术真理。

这区分了两个概念:

  • 在可有效公理化的理论中的可证明性可以由算术公式表达。
  • 在标准自然数中的真理不能由一个正确涵盖所有算术语句的算术公式来定义。

对语法进行编码,并不会消除语法推导与语义真理之间的区别。

其他编码方式与更广泛的用途

素数幂编码只是可选方案之一。其他构造使用:

  • 固定进制的字符串,并采用保留长度信息的约定;
  • 通过迭代配对函数来编码元组和有限序列;
  • 语法树的二进制编码;
  • 程序或机器的数值索引。

例如,康托尔配对函数

π(a,b)=(a+b)(a+b+1)2+b\pi(a,b) = \frac{(a+b)(a+b+1)}{2}+b

为每个自然数有序对分配一个唯一的自然数。配合适当的标记和长度信息,配对可以编码嵌套表达式和有限列表。

因此,哥德尔编号与证明论、一阶逻辑以及算法研究都有关系。将程序编码为数,使算法能够以程序描述作为输入,从而为通用计算和停机问题的相关结果提供支持。相关编码也用于形式验证,不过实际系统通常将语法存储为字符串或结构化数据,而不是庞大的素数乘积。

局限性及对约定的依赖

不存在唯一的典范哥德尔编号。具体数值取决于字母表、语法、序列编码,以及对变量和证明的处理方式。只有确定这些约定后,声称某个语句具有某个特定哥德尔数才有意义。

对于彼此之间可以进行可计算转换的常规有效编码,可计算性和不可判定性结果不依赖于具体分配了哪些数。更精细的性质则可能依赖于编码,尤其是在讨论计算复杂性,或非常弱的算术理论能够证明编码操作的哪些性质时。

最后,哥德尔数记录的是符号对象,而不是它的意义。当相关检查是有效的,编码就能区分有效公式与不合式字符串,以及有效证明与无效推导。但仅仅给对象赋予数值,并不能提供判定数学真理或定理性的方法。