Undecidable Theories and Global Properties of Structures

结构的不可判定理论和全局性质

• 批准号: 9803482
• 负责人: Andre Nies
• 金额: $ 6.25万
• 依托单位: University of Chicago
• 依托单位国家: 美国
• 项目类别: Standard Grant
• 财政年份: 1998
• 资助国家: 美国
• 起止时间: 1998-07-01 至 2001-12-31
• 项目状态: 已结题
• 来源: https://www.nsf.gov/awardsearch/showAward?AWD_ID=9803482&HistoricalAwards=false
• 关键词: Undecidable; Theories; Global; Properties; Structures

Nies intends to study a wide range of elementary theories and structures stemming from computability theory, complexity theory, algebra, and computable analysis. Ever since the work of Godel and Tarski, the question of whether a given elementary theory is decidable has been of central interest to logicians. Nies will study this question for the theories of nonabelian free groups and for the degree structure of recursively enumerable reals compared under Solovay's domination reducibility. As a main tool, he will use coding with first-order formulas. This method yields not only undecidability of the elementary theory of a structure, but also further global properties of the structure itself (rather than its theory). Typical results obtained by this method are definability results and limitations on automorphisms. Nies will study such properties, in particular for the central structure of recursively enumerable Turing degrees. Nies' work introduces a unifying aspect into the vast and diverging area of modern mathematics, by analyzing through common methods structures from such different domains as computability theory and analysis. These methods are called coding methods. They consist of representing an object of one kind in an object of a second kind (the structure under investigation) using first order formulas. First-order languages are central to mathematical logic and computer science. In a sense, they are a formalization of a fragment of natural language. The first-order theory of a structure is the collection of all facts about the structure which can be expressed in that language. For instance, the existence of infinitely many prime numbers is a first-order fact about the structure of natural numbers (with addition and multiplication). In part, Nies investigates the question whether first-order theories are decidable. Moreover, he uses coding methods to explore global properties of the structures, like the existence of symmetries. In several cases, the structures investigate d are considered central for the area in question (like free groups in algebra or the structure of recursively enumerable Turing degrees in computability theory).

NIE打算研究源于计算理论，复杂性理论，代数和可计算分析的广泛基础理论和结构。 自从Godel和Tarski的工作以来，对于逻辑学家来说，给定基本理论是否可以决定的问题一直是核心利益。 NIE将研究这个问题的非亚伯自由群体的理论，以及在Solovay的统治性降低性下比较的递归列举实时的理论结构。 作为主要工具，他将使用一阶公式使用编码。 该方法不仅产生了结构基本理论的不可证明，而且还产生了结构本身的进一步全球特性（而不是其理论）。通过这种方法获得的典型结果是对自动形态的确定性结果和局限性。 NIE将研究此类特性，特别是对于递归枚举的图灵程度的中心结构。 NIES的工作通过通过来自可计算性理论和分析等不同领域的常见方法结构进行分析，将统一的方面引入了现代数学的巨大和不同领域。这些方法称为编码方法。它们包括使用一阶公式在第二种对象（正在研究的结构）中代表一种对象。 一阶语言是数学逻辑和计算机科学的核心。 从某种意义上说，它们是对自然语言片段的形式化。结构的一阶理论是关于可以用该语言表达的结构的所有事实的集合。 例如，无限的许多质数的存在是关于自然数（加上和乘法）的一阶事实。在某种程度上，NIES调查了一阶理论是否可以决定的问题。此外，他使用编码方法来探索结构的全局特性，例如对称的存在。 在某些情况下，研究的结构被认为是该区域的核心（例如代数中的自由组或可计算理论中递归枚举的图灵程度的结构）。