J. 巴克利·罗瑟(1907年12月6日—1989年9月5日)是美国数学家,研究领域涵盖数理逻辑、计算基础和数论。他尤以通过减弱一致性假设来加强哥德尔第一不完备定理,以及与阿隆佐·丘奇共同证明丘奇—罗瑟定理而闻名。他的研究还包括关于素数分布的显式估计。
生平与学术生涯
约翰·巴克利·罗瑟出生于佛罗里达州杰克逊维尔。他先在佛罗里达大学求学,随后前往普林斯顿大学攻读研究生,并于1934年在阿隆佐·丘奇的指导下获得博士学位。他的博士论文《不含变量的数理逻辑》研究了不使用约束变量的逻辑形式化方法。
罗瑟于1936年加入康奈尔大学,任职至1963年。此后,他转赴威斯康星大学麦迪逊分校,担任数学研究中心主任,并继续从事研究和教学工作。他于1978年退休,1989年在威斯康星州麦迪逊去世。
他的学术生涯将关于形式推理的基础性问题,与数论及应用数学中更侧重计算的研究结合在一起。
加强哥德尔不完备定理
罗瑟在逻辑领域最著名的成果发表于他1936年的论文《哥德尔与丘奇若干定理的推广》。这一成果加强了哥德尔不完备定理中的第一定理,该定理最初由库尔特·哥德尔于1931年证明。
第一不完备定理讨论的是这样一种形式系统:其公理可以有效枚举,且能够表达足够多的初等算术内容。哥德尔构造了一个语句,在适当假设下,系统既不能证明它,也不能否证它。在哥德尔最初的论证中,一致性足以保证该语句不可证明,而要保证其否定也不可证明,则使用了更强的 ω一致性条件。
罗瑟证明,普通的一致性就足以得出这两个结论。按照一种标准的现代表述,任何一致的、可有效公理化且包含足够多初等算术内容的理论都是不完备的:在该理论的语言中,存在某个语句,在该理论内既不可证明,也不可否证。
罗瑟语句
关键在于用一个经过更精巧权衡的自指语句来替代哥德尔语句。非形式化地说,罗瑟语句表达的是:
对于这个语句的每一个证明,都存在一个证明其否定的证明,且后者的数值编码不大于前者。
这一构造使用了对公式和形式证明的算术编码。如果理论证明了该语句,那么一致性就会排除其否定的任何证明,这与该语句所断言的内容矛盾。如果理论证明了该语句的否定,那么利用证明编码的有限次序关系,理论便能核实关于较小编码的候选证明的足够信息,从而推导出该语句本身,再次与一致性矛盾。
要将这些非形式化的说明化为严格论证,就需要对理论表达证明检验过程的能力作出精确假设。其意义在于,论证比较的是有限的证明编码,而不依赖ω一致性。由此得到的加强结果通常称为罗瑟定理或哥德尔—罗瑟定理。
该定理并不声称所有形式理论都是不完备的。它的适用范围取决于理论是否可有效公理化、是否一致,以及是否具有足够强的算术表达能力。
丘奇—罗瑟定理
罗瑟还与丘奇合作研究了λ演算,这是一种用于描述函数及其应用的形式语言。他们于1936年发表的论文《转换的若干性质》证明了如今称为丘奇—罗瑟定理的结果。
按照常见的表述,该定理指出,λ演算中的β归约具有合流性。如果一个项 通过不同的归约序列分别归约为项 和 ,那么存在一个项 ,使得 和 都可以进一步归约为它:
这里, 表示零次或多次β归约步骤。
一个重要推论是:如果范式存在,那么在不计约束变量重命名差异的意义下,它是唯一的。不同的归约路径不可能为同一个项产生实质上不同的范式。合流性并不意味着每个归约序列都会终止,也不意味着每个项都有范式。
该定理成为程序设计语言语义学和符号计算研究的基础。它有助于区分计算的数学含义与其中间运算的具体执行顺序。
素数研究
罗瑟对素数的估计作出了重要贡献,尤其是在适用于显式计算的不等式方面。
用 表示第 个素数,用 表示自然对数,与他相关的一个经典结果是
这样的不等式补充了素数定理,后者蕴含渐近关系 。渐近命题描述的是极限行为,而显式不等式则给出在指定范围内成立的界。
罗瑟与洛厄尔·舍恩菲尔德合作,进一步建立了涉及素数的函数的显式估计。他们1962年的论文《关于若干素数函数的近似公式》给出了素数计数函数及相关函数的界。这些估计成为计算数论和解析数论中的实用工具,因为这些领域中的论证有时不仅需要极限行为,还需要具体的常数和阈值。
著作与阐释
罗瑟的著作包括《面向数学家的逻辑》(1953年)和《简化的独立性证明:集合论的布尔值模型》(1969年)。前者面向数学读者介绍形式逻辑;后者利用布尔值模型讨论集合论中的独立性方法。
他的著述将几种不同类型的数学推理联系起来:形式可证明性的局限、计算的结构性质,以及算术函数的定量估计。