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将研究数学现象的有效性，更普遍的定义方面，例如通用性，紧凑性和随机性。 Slaman与Veronica Becher和Pablo Heiber共同在布宜诺斯艾利斯大学，将使用可计算性和描述性集理论的方法到实数的正态性，这是其表示数字中数字的属性，其属性具有相等的渐近频率，尤其是在不同基础中考虑表示表示。 还将与洛朗·比恩维努（Laurent Bienvenu），巴黎大学迪德罗特·帕里斯大学（Diderot-Paris）7和与斯拉曼（Slaman）合作的高级研究生凯尔蒂·艾伦（Kelty Allen）合作，涉及布朗尼运动的有效理论。 同时，Slaman将研究一个更基本的问题：“熟悉的无限原则的理论后果是什么？”如一阶和二阶正式算术。 短语“一阶算术”是指自然数n = {0,1,2，...}的结构，加上和乘法的操作。 ``二阶算术''是指n的扩展，包括n的所有子集，并允许对无限集进行参考和定量。 更准确地说是，Slaman将调查二阶原则的程度，例如存在随机序列或断言经常应用的无限制组合原则，例如Ramsey定理，在第一顺序中具有不平凡的后果，在第一顺序中具有不平凡的后果。理解这些对象本身。 在提案的跨学科部分之一中，将调用此观点来研究构建实数的问题，以控制其表示相对于所有整数基础的行为。 一个目标是展示一种快速运行的算法以输出绝对正常的数字，这意味着，对于任何整数基础B，该数字的基本B表示中的数字随着时间的推移频率相等。 绝对正态性通常被解释为随机性的指标，但是这样一个可访问且可预测的例子会反驳该观点。 该项目的另一部分将数学逻辑放在前景中，要求提供有关自然数量无限亚集中的组合形式的实数的属性在有限集中产生后果的确切信息。