Information Coded in Mathematical Structures

数学逻辑以内省的方式使用数学工具来研究数学本身。该项目将使用数学逻辑（特别是可计算性理论）的工具来研究将信息编码为数学所有领域中出现的类型的数学结构的方式。一般的范例是，如果信息总是能够以一种内在的方式从结构中恢复，而不受结构呈现方式的影响，那么信息就被编码到一个数学结构中。对于最简单的信息类型，比如由0和1组成的字符串，这种情况很好理解。但对于更复杂的信息，情况就不那么好理解了，有许多有趣的现象有待探索。理解信息的编码将有助于我们理解信息的本质和各种结构对信息编码的能力。这反过来又指导和指导其他数学家的数学实践。该项目包括对本科生和研究生的培训以及向高中的推广。更正式地说，我们说，如果从结构的每个副本中，我们可以以可计算的方式恢复信息a的副本，那么一条信息a被编码在结构B中。例如，如果B是一个可数无限群，那么B的副本就是该群的Cayley表，注意，对于一个无限群，有许多不同的Cayley表，通过列出该群的元素以不同的顺序获得。我们所说的一条信息，按照复杂度递增的顺序，是指一个二进制字符串（或自然数的子集），一个无限的二进制字符串族，一个无限的树，或其他一些结构。对于二进制字符串的第一种情况，当一个结构体对二进制字符串进行编码时，有一个很好的结构特征；我们可以这样解释：用结构对二进制字符串进行编码总是有一个很好的理由。对于任何更复杂的信息类型，情况都不是这样；似乎有一些结构碰巧编码了信息，但是没有一个好的结构原因来解释为什么。本项目旨在探索这些现象，并将其推向极限，目的之一是提供新的工具来解决当前技术难以解决的度谱难题。该奖项反映了美国国家科学基金会的法定使命，并通过使用基金会的知识价值和更广泛的影响审查标准进行评估，被认为值得支持。

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.