Information Coded in Mathematical Structures

数理逻辑以一种内省的方式使用数学工具来研究数学本身。这个项目将使用数理逻辑(特别是可计算性理论)的工具来研究如何将信息编码成在所有数学领域中出现的类型的数学结构。一般的范例是，如果信息总是可以从结构中以内在的方式恢复，而不是结构呈现方式的人工产物，那么信息就被编码到数学结构中。对于最简单的信息，比如一串0‘S和1’S，情况是很容易理解的。但对于更复杂的信息类型，情况还不太清楚，有许多有趣的现象需要探索。理解信息的编码将有助于我们理解信息的性质和各种结构对信息进行编码的能力。这反过来又为其他数学家的数学实践提供了信息和指导。这个项目包括培养本科生和研究生以及推广到高中。更正式地说，我们说一条信息A被编码在结构B中，如果从结构的每个副本中，我们可以用可计算的方式恢复信息A的副本。例如，如果B是可数无限群，则B的副本是该群的Cayley表，注意对于无限群，有许多不同的Cayley表是通过以不同的顺序列出群的元素而获得的。按照复杂性递增的顺序，我们所说的信息指的是二进制字符串(或自然数的子集)、二进制字符串的无穷族、无穷树或一些其他结构。对于二进制字符串的第一种情况，结构何时对二进制字符串进行编码有一个很好的结构特征；人们可以将其解释为总是有很好的理由让二进制字符串由结构编码。对于更复杂的信息类型来说，情况并非如此；似乎有一些结构恰好对信息进行了编码，但没有很好的结构原因来解释原因。该项目旨在探索这些现象并将其推向极限，目的之一是提供新的工具来解决学位谱上对当前技术具有抵抗力的难题。该奖项反映了NSF的法定使命，并通过使用基金会的智力优势和更广泛的影响审查标准进行评估，被认为值得支持。

Mathematical logic uses mathematical tools in an introspective way to study mathematics itself. This project will use the tools of mathematical logic (and computability theory in particular) to study the way that information can be coded into mathematical structures of the types that arise in all areas of mathematics. The general paradigm is that information is encoded into a mathematical structure if it can always be recovered in an intrinsic way from the structure, without artifacts from the way that the structure is presented. For the simplest kinds of information, like a string of 0's and 1's, the situation is well-understood. But for more complex kinds of information, the situation is much less well-understood and there are many interesting phenomena to explore. Understanding the coding of information will help us understand both the nature of information and the ability of structures of various kinds to code information. This, in turn, informs and guides the mathematical practice of other mathematicians. This project includes the training of undergraduate and graduate students and outreach to high schools.More formally, we say that a piece of information A is coded in a structure B if from every copy of the structure, we can recover in a computable way a copy of the information A. For example if B is a countably infinite group then a copy of B is a Cayley table for the group, noting that for an infinite group there are many different Cayley tables obtained by listing the elements of the group in different orders. By a piece of information we mean, in order of increasing complexity, a binary string (or subset of the natural numbers), an infinite family of binary strings, an infinite tree, or some other structure. For the first case of a binary string, there is a good structural characterisation of when a structure codes a binary string; one can interpret this as saying that there is always a good reason for a binary string to be coded by a structure. This is not the case for any more of the more complicated types of information; it seems that there are structures which happen to code information, but there is no good structural reason as to why. This project aims to explore these phenomena and push them to their limit with one aim being to give new tools to attack difficult open problems on degree spectra which have been resistant to current techniques.This award reflects NSF's statutory mission and has been deemed worthy of support through evaluation using the Foundation's intellectual merit and broader impacts review criteria.