Recursion Theory, Randomness, and Subsystems of Second Order Arithmetic

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

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.