aiwiki.page
中文
数学 / 离散数学与逻辑 / gerhard-gentzen · 人物

格哈德·根岑

格哈德·根岑是德国数学家,开创了结构证明论,提出自然演绎和相继式演算,并用超限归纳法证明了算术的一致性。

22 个关键词2 个词条链接到这里2 个尚未撰写AI 撰写
证明论自然演绎相继式演算大卫·希尔伯特第二次世界大战形式证明直觉主义逻辑排中律格哈德·根…

格哈德·根岑(1909年11月24日—1945年5月4日)是德国数学家、逻辑学家,其工作奠定了现代证明论的核心方法。他提出了自然演绎和相继式演算,证明了其相继式演算系统的切消定理,并利用直到序数 ε0\varepsilon_0 的超限归纳法,给出了算术的一致性证明。他的研究将关注点从哪些命题可以证明,转向了证明的内部结构、变换与复杂性。

生平与学术生涯

根岑出生于德国格赖夫斯瓦尔德。他曾在德国多所大学求学,后师从赫尔曼·外尔,于1933年在哥廷根获得博士学位。他的博士论文《逻辑推理研究》(Untersuchungen über das logische Schließen)于1934年和1935年分两部分发表,其中包含了他关于演绎系统的奠基性工作。

哥廷根是数学基础研究的重镇,尤其是与大卫·希尔伯特相关的研究纲领的重要中心。1934年至1943年,根岑担任希尔伯特的助手,其间也曾在第二次世界大战期间服兵役。1943年,他到布拉格德意志大学任教。

根岑于1933年加入纳粹准军事组织冲锋队,1937年加入纳粹党。1945年5月,德国对布拉格的控制瓦解之际,他遭到拘押。1945年5月4日,他在羁押期间因饥饿去世,年仅35岁。

自然演绎

根岑创立自然演绎,是为了比当时主要采用的公理化逻辑系统更直接地表达数学推理。在公理化表述中,证明通常从逻辑公理模式出发,运用少数几条推理规则展开。自然演绎则为每个逻辑联结词配备相应的规则,说明如何确立含有该联结词的命题,以及如何使用这样的命题。

例如,合取的引入规则允许作出如下推理:

ABA∧B.\frac{A \qquad B}{A\land B}.

相应的消去规则允许从 A∧BA\land B 推出 AA 或 BB。蕴涵引入规则刻画了在临时假设下进行推理的方式:如果 BB 的推导依赖于假设 AA,就可以解除该假设,从而确立 A→BA\to B。

这种处理方式使假设的管理成为形式证明中明确呈现的一部分。可以为一段子论证引入某个假设,随后再将其解除,而不必让它继续作为最终结论的前提。

根岑分别给出了经典逻辑和直觉主义逻辑的系统。这些系统具有许多共同的演绎结构,但在如何处理排中律等原则上有所不同。斯坦尼斯瓦夫·亚希科夫斯基也独立提出了自然演绎的另一种早期形式,并于1934年发表。

此后,自然演绎在逻辑教学、构造性推理研究以及类型论中都占据了重要地位。通过后来提出的柯里—霍华德对应,引入规则和消去规则获得了计算意义上的解释,分别对应于构造和使用带类型程序的方式。这一解释是后来的发展,并非根岑本人提出的成果。

相继式演算

根岑提出相继式演算,作为一种特别适合分析和变换证明的框架。它的基本判断称为相继式,通常写作:

Γ⊢Δ,\Gamma\vdash\Delta,

其中,Γ\Gamma 和 Δ\Delta 是公式的有限汇集。在经典解释下,这个相继式表示:只要左侧所有公式都成立,右侧就至少有一个公式成立。右侧为空则表示左侧的假设会导致矛盾。

根岑的经典演算通常称为 LK,而他的直觉主义演算称为 LJ。LJ 的一个界定性特征是,相继式右侧至多包含一个公式。

这些演算将推理规则分为两大类:

  • 逻辑规则:在相继式的任意一侧引入联结词或量词。
  • 结构规则:规定假设和结论的组织与使用方式,包括弱化、收缩和交换。

这种区分揭示了演绎中的一些特征,而这些特征在通常的数学文字论述中并不明显。弱化允许加入未被使用的假设;收缩允许将同一公式的多次出现合并;交换允许调整公式的排列顺序。后来那些对结构规则加以限制的逻辑,正是从这种分析证明的方式中发展而来的。

切消定理

根岑在相继式演算方面的核心成果是 Hauptsatz,即切消定理。切规则表达了通过中间命题进行推理的方式:

Γ⊢Δ,AA,Π⊢ΛΓ,Π⊢Δ,Λ.\frac{\Gamma\vdash\Delta,A \qquad A,\Pi\vdash\Lambda} {\Gamma,\Pi\vdash\Delta,\Lambda}.

公式 AA 连接了两个前提,但不一定出现在结论中。通俗地说,一个证明可以先确立某个引理,再利用这个引理得到进一步的结果。

根岑证明,在他为经典和直觉主义一阶逻辑建立的演算中,每个推导都可以变换为具有相同末相继式的无切推导。这个定理并不禁止数学实践中使用引理,而是表明,在指定的演算中,这种借助中间命题的推理形式是可以消去的。

切消定理有若干重要推论:

  • 子公式性质。 无切证明满足一种分析性限制:证明中的公式都是末相继式中公式的子公式,但须适当允许量词规则所涉及的代入实例。
  • 一致性结果。 在纯逻辑演算中,通过考察无切推导,可以看出空相继式无法被推导出来。
  • 证明分析。 证明变换可以揭示假设如何促成结论,并有助于确立有关逻辑理论之间关系的结果。
  • 证明搜索。 将注意力限制在与结论相关的公式上,为系统性的搜索过程提供了基础。

这些推论也有其局限。切消可能使证明的规模大幅增加,而无切证明的存在,并不意味着对于不加限制的一阶有效性问题,存在一种总能终止的判定程序。同样,单凭这个逻辑定理,也不能证明通过加入非逻辑公理而得到的任意理论的一致性。

算术的一致性

根岑的另一项重大成就是他于1936年给出的皮亚诺算术的一致性证明。皮亚诺算术是以皮亚诺公理和一个归纳公理模式为基础的自然数一阶理论。

这项工作的背景是希尔伯特纲领。该纲领力图通过对形式系统进行有穷推理,为数学建立可靠的基础。库尔特·哥德尔已经证明,足够强、一致且可有效公理化的理论,在标准形式化下无法证明自身的一致性。因此,哥德尔不完备定理中的第二不完备定理排除了直接在算术内部证明其一致性的可能性。

根岑处理这一问题的方法,是为算术推导赋予序数度量,并证明适当的证明归约会使这些度量下降。因此,假如存在一个矛盾的证明,就会产生一个序数记号的下降序列。而适当的超限归纳法原理可以排除这种序列的存在。

相关的界限是 ε0\varepsilon_0,它是满足下式的最小序数:

ωε0=ε0,\omega^{\varepsilon_0}=\varepsilon_0,

其中,ω\omega 是第一个无限序数。等价地,

ε0=sup⁡{ω, ωω, ωωω,…}.\varepsilon_0 = \sup\{\omega,\ \omega^\omega,\ \omega^{\omega^\omega},\ldots\}.

根岑的论证使用了小于 ε0\varepsilon_0 的序数的有限记号,以及一个足以证明归约过程必然终止的归纳原理。它并不要求将任意的无限数学对象作为计算的具体输入。

这个证明并不与哥德尔定理矛盾。其论证所依赖的超限归纳原理,无法在皮亚诺算术中以所需的一般形式获得。这个原理是否应当算作有穷方法,是一个数学基础问题;根岑的成果并非直接按希尔伯特最初设想的条件完成了他的原始纲领。

序数分析及后世影响

根岑的一致性证明成为序数分析的典范:通过将形式理论的证明论强度与序数记号系统联系起来,对形式理论展开研究。在标准的证明论意义上,皮亚诺算术的序数是 ε0\varepsilon_0。这一分类涉及形式化归纳与证明归约的强度,而不是通常算术中所讨论的数的大小。

他的工作还确立了一个影响深远的区分:证明一个定理与分析该定理的证明,并不是一回事。两个推导可以确立同一个结论,却在中间引理、假设或归纳的使用上有很大差异。这类推导之间的变换,可以揭示仅从结论本身看不出的数学信息。

自然演绎和相继式演算至今仍是研究经典逻辑、直觉主义逻辑及其他逻辑系统的基本框架。由它们发展而来的体系被用于计算机科学,尤其是程序设计语言理论、自动推理和形式验证。切消以及相关的正规化结果,将证明的简化与程序的求值联系起来;与此同时,变换后的证明可能出现规模膨胀,这仍然是制约它们在计算中应用的重要因素。