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.

斯拉曼将研究有效的，更普遍的定义，数学现象的方面，如通用性，紧凑性和随机性。 与维罗妮卡Becher和巴勃罗海伯，无论是在布宜诺斯艾利斯大学，Slaman将适用于方法从可计算性和描述集理论的正规性真实的数字，财产的数字在他们的陈述发生以相等的渐近频率，特别是考虑表示在不同的基地。 还将与劳伦特Bienvenu，巴黎狄德罗-巴黎7大学，和Kendy艾伦，一个先进的研究生与Slaman合作，对布朗运动的有效理论。 与此同时，斯拉曼将研究更基本的问题，“什么是熟悉的无穷大原则的数论后果？“在一阶和二阶算术中形式化。 短语“一阶算术”是指自然数N={0，1，2，.}的结构。用加法和乘法运算。 “二阶算术”是指N的扩展，包括N的所有子集，并允许引用和量化无限集。 更准确地说，Slaman将研究二阶原理，如随机序列的存在或经常应用的无穷组合原理（如Ramsey定理）的断言，在一阶算术中具有非平凡后果的程度。该项目来自数理逻辑的角度，即理解人们可以与数学对象一起工作的方法可能与，甚至等同于理解这些物体本身。 在该提案的一个更跨学科的部分，这一观点将被调用来研究构造真实的数的问题，以便控制它们的表示相对于所有整数基的行为。 一个目标是展示一个快速运行的算法来输出一个绝对正常的数字，这意味着对于任何以B为基的整数，该数字的以B为基的表示中的数字随着时间的推移以相等的频率出现。 绝对常态通常被解释为随机性的指标，但这样一个可访问和可预测的例子将反驳这种观点。 该项目的另一部分将数理逻辑置于前台，要求提供有关真实的数的性质的确切信息，这些性质以自然数的无限子集中的组合形式出现，在有限集合中产生后果。