Recursion Theory, Randomness, and Subsystems of Second Order Arithmetic

递归理论、随机性和二阶算术子系统

• 批准号: 1301659
• 负责人: Theodore Slaman
• 金额: $ 36万
• 依托单位: University of California-Berkeley
• 依托单位国家: 美国
• 项目类别: Continuing Grant
• 财政年份: 2013
• 资助国家: 美国
• 起止时间: 2013-08-15 至 2016-07-31
• 项目状态: 已结题
• 来源: https://www.nsf.gov/awardsearch/showAward?AWD_ID=1301659&HistoricalAwards=false
• 关键词: Recursion; Theory; Randomness; Subsystems; Second

Slaman will investigate the effective, and more generally definable, aspects of mathematical phenomena such as genericity, compactness, and randomness. Jointly with Veronica Becher and Pablo Heiber, both at the University of Buenos Aires, Slaman will apply methods from Computability and Descriptive Set Theory to normality of real numbers, the property that the digits in their representations occur with equal asymptotic frequency, especially considering representations in varying bases. Will also collaborate with Laurent Bienvenu, University of Paris Diderot-Paris 7, and Kelty Allen, an advanced graduate student working with Slaman, on the effective theory ofBrownian motion. In parallel, Slaman will investigate the more foundational question, "What are the number theoretic consequences of familiar infinitary principles?" as formalized in first and second order arithmetic. The phrase "first order arithmetic" refers to the structure of the natural numbers N={0,1,2,...} with the operations of addition and multiplication. ``Second order arithmetic'' refers to the expansion of N to include all of the subsets of N and allowing for reference to and quantification over infinite sets. Stated more precisely, Slaman will investigate the extent to which second order principles, such as the existence of a random sequence or the assertion of a frequently applied infinitary combinatorial principle such as Ramsey's Theorem, have non-trivial consequences in first order arithmetic.This project comes from the perspective of Mathematical Logic, that understanding the means by which one can work with mathematical objects can be as important as, or even equivalent to, understanding those objects themselves. In one of the more interdisciplinary parts of the proposal, this point of view will be invoked to study the problem of constructing real numbers so as to control the behaviors of their representations relative to all integer bases. One goal is to exhibit a fast-running algorithm to output an absolutely normal number, which means that for any integer base b the digits in the base b representation of this number occur with equal frequency over time. Absolute normality is often interpreted as an indicator of randomness, but such an accessible and predictable example would refute that view. Another part of the project puts Mathematical Logic in the foreground by asking for exact information concerning the extent that the properties of the real numbers, in the form of combinatorics seen within infinite subsets of the natural numbers, have consequences among the finite sets.

斯拉曼将研究数学现象的有效且更普遍可定义的方面，例如通用性、紧凑性和随机性。 Slaman 与布宜诺斯艾利斯大学的 Veronica Becher 和 Pablo Heiber 合作，将可计算性和描述性集合论的方法应用于实数的正态性，即其表示中的数字以相同渐近频率出现的属性，特别是考虑到不同的基地。 还将与巴黎第七大学狄德罗分校的 Laurent Bienvenu 以及与 Slaman 合作的高级研究生 Kelty Allen 合作研究布朗运动的有效理论。 与此同时，斯拉曼将研究更基本的问题，“熟悉的无限原理的数论后果是什么？”正如一阶和二阶算术形式化的那样。 短语“一阶算术”是指具有加法和乘法运算的自然数N={0,1,2,...}的结构。 “二阶算术”是指将 N 扩展为包括 N 的所有子集，并允许对无限集进行引用和量化。 更准确地说，斯拉曼将研究二阶原理（例如随机序列的存在或频繁应用的无限组合原理（例如拉姆齐定理）的断言）在一阶算术中产生不平凡的后果的程度。该项目从数理逻辑的角度来看，理解处理数学对象的方法与理解这些对象本身一样重要，甚至等同于理解这些对象本身。 在该提案的跨学科部分之一中，将引用这一观点来研究构造实数的问题，以控制其表示相对于所有整数基的行为。 一个目标是展示一种快速运行的算法来输出绝对正常的数字，这意味着对于任何整数基数 b，该数字的基数 b 表示中的数字随着时间的推移以相同的频率出现。 绝对正态性通常被解释为随机性的指标，但这样一个易于理解且可预测的例子会反驳这种观点。 该项目的另一部分将数理逻辑置于前台，要求提供有关实数属性（以自然数的无限子集中的组合数学形式）在有限集合中产生影响的程度的准确信息。