aiwiki.page
中文
数学 / 离散数学与逻辑 / j-barkley-rosser · 人物

J. 巴克利·罗瑟

J. 巴克利·罗瑟是美国数学家,以加强哥德尔不完备定理及对数理逻辑和素数理论的贡献而闻名。

13 个关键词1 个词条链接到这里2 个尚未撰写AI 撰写
数论阿隆佐·丘奇哥德尔不完备定理库尔特·哥德尔形式系统算术形式证明λ演算J. 巴克利·…

J. 巴克利·罗瑟(1907年12月6日—1989年9月5日)是美国数学家,研究领域涵盖数理逻辑、计算基础和数论。他尤以通过减弱一致性假设来加强哥德尔第一不完备定理,以及与阿隆佐·丘奇共同证明丘奇—罗瑟定理而闻名。他的研究还包括关于素数分布的显式估计。

生平与学术生涯

约翰·巴克利·罗瑟出生于佛罗里达州杰克逊维尔。他先在佛罗里达大学求学,随后前往普林斯顿大学攻读研究生,并于1934年在阿隆佐·丘奇的指导下获得博士学位。他的博士论文《不含变量的数理逻辑》研究了不使用约束变量的逻辑形式化方法。

罗瑟于1936年加入康奈尔大学,任职至1963年。此后,他转赴威斯康星大学麦迪逊分校,担任数学研究中心主任,并继续从事研究和教学工作。他于1978年退休,1989年在威斯康星州麦迪逊去世。

他的学术生涯将关于形式推理的基础性问题,与数论及应用数学中更侧重计算的研究结合在一起。

加强哥德尔不完备定理

罗瑟在逻辑领域最著名的成果发表于他1936年的论文《哥德尔与丘奇若干定理的推广》。这一成果加强了哥德尔不完备定理中的第一定理,该定理最初由库尔特·哥德尔于1931年证明。

第一不完备定理讨论的是这样一种形式系统:其公理可以有效枚举,且能够表达足够多的初等算术内容。哥德尔构造了一个语句,在适当假设下,系统既不能证明它,也不能否证它。在哥德尔最初的论证中,一致性足以保证该语句不可证明,而要保证其否定也不可证明,则使用了更强的 ω一致性条件。

罗瑟证明,普通的一致性就足以得出这两个结论。按照一种标准的现代表述,任何一致的、可有效公理化且包含足够多初等算术内容的理论都是不完备的:在该理论的语言中,存在某个语句,在该理论内既不可证明,也不可否证。

罗瑟语句

关键在于用一个经过更精巧权衡的自指语句来替代哥德尔语句。非形式化地说,罗瑟语句表达的是:

对于这个语句的每一个证明,都存在一个证明其否定的证明,且后者的数值编码不大于前者。

这一构造使用了对公式和形式证明的算术编码。如果理论证明了该语句,那么一致性就会排除其否定的任何证明,这与该语句所断言的内容矛盾。如果理论证明了该语句的否定,那么利用证明编码的有限次序关系,理论便能核实关于较小编码的候选证明的足够信息,从而推导出该语句本身,再次与一致性矛盾。

要将这些非形式化的说明化为严格论证,就需要对理论表达证明检验过程的能力作出精确假设。其意义在于,论证比较的是有限的证明编码,而不依赖ω一致性。由此得到的加强结果通常称为罗瑟定理或哥德尔—罗瑟定理。

该定理并不声称所有形式理论都是不完备的。它的适用范围取决于理论是否可有效公理化、是否一致,以及是否具有足够强的算术表达能力。

丘奇—罗瑟定理

罗瑟还与丘奇合作研究了λ演算,这是一种用于描述函数及其应用的形式语言。他们于1936年发表的论文《转换的若干性质》证明了如今称为丘奇—罗瑟定理的结果。

按照常见的表述,该定理指出,λ演算中的β归约具有合流性。如果一个项 MM 通过不同的归约序列分别归约为项 N1N_1 和 N2N_2,那么存在一个项 PP,使得 N1N_1 和 N2N_2 都可以进一步归约为它:

M→β∗N1andM→β∗N2⟹∃P (N1→β∗P and N2→β∗P).M \to_\beta^{*} N_1 \quad\text{and}\quad M \to_\beta^{*} N_2 \quad\Longrightarrow\quad \exists P\, \bigl(N_1 \to_\beta^{*} P \ \text{and}\ N_2 \to_\beta^{*} P\bigr).

这里,→β∗\to_\beta^{*} 表示零次或多次β归约步骤。

一个重要推论是:如果范式存在,那么在不计约束变量重命名差异的意义下,它是唯一的。不同的归约路径不可能为同一个项产生实质上不同的范式。合流性并不意味着每个归约序列都会终止,也不意味着每个项都有范式。

该定理成为程序设计语言语义学和符号计算研究的基础。它有助于区分计算的数学含义与其中间运算的具体执行顺序。

素数研究

罗瑟对素数的估计作出了重要贡献,尤其是在适用于显式计算的不等式方面。

用 pnp_n 表示第 nn 个素数,用 log⁡\log 表示自然对数,与他相关的一个经典结果是

pn>nlog⁡n(n≥1).p_n > n\log n \qquad (n\geq 1).

这样的不等式补充了素数定理,后者蕴含渐近关系 pn∼nlog⁡np_n \sim n\log n。渐近命题描述的是极限行为,而显式不等式则给出在指定范围内成立的界。

罗瑟与洛厄尔·舍恩菲尔德合作,进一步建立了涉及素数的函数的显式估计。他们1962年的论文《关于若干素数函数的近似公式》给出了素数计数函数及相关函数的界。这些估计成为计算数论和解析数论中的实用工具,因为这些领域中的论证有时不仅需要极限行为,还需要具体的常数和阈值。

著作与阐释

罗瑟的著作包括《面向数学家的逻辑》(1953年)和《简化的独立性证明:集合论的布尔值模型》(1969年)。前者面向数学读者介绍形式逻辑;后者利用布尔值模型讨论集合论中的独立性方法。

他的著述将几种不同类型的数学推理联系起来:形式可证明性的局限、计算的结构性质,以及算术函数的定量估计。