Problems of Definability and Decidability over Algebraic Fields

与本提案中讨论的问题相关的一般性问题可以表述如下：什么是可以用环的语言来确定和定义的？目前的研究方向起源于希尔伯特的第十个问题及其由戴维斯、普特南、罗宾逊和马蒂亚塞维奇提出的解决方案。当Yurii Matiyasevich证明有理整数上的丢番图集与可计算可枚举集相同时，他证明了起源于数学的两个不同分支的对象是相同的。这一结果开启了对代数和逻辑共同根的搜索，一次围绕两个最重要的对象：整数和有理数的搜索。虽然在搜索中使用的方法大部分是代数或几何的，但提出的问题源于模型理论或可计算性理论。Mazur的猜想、它们的推广以及它们对丢番图定义和丢番图模型存在的后果是可计算性理论/模型理论中的问题产生代数几何问题的一个很好的例子，这反过来又产生了可计算性理论/模型理论中的结果。由这一研究线路引起的域之间相互作用的另一个例子是Mazur和Rubin最近关于数域上的椭圆曲线的秩的结果，这些结果是为了回答一些丢番图可定义性问题而产生的。在这项建议中，作者计划继续她对有理数和所有特征有理函数域的代数扩张的可定义性和可判断性的研究。特别地，我们计划探索全局域的无限代数扩张上的一阶可定性和一大类正特征函数域的存在不可定性。这项建议调查了以下类型的问题：给定一个多变量多项式方程，是否有一个算法(或计算机程序)可以告诉我们这个方程在特定集合中是否有解。这类问题可以追溯到德国数学家大卫·希尔伯特，他在二十世纪初问道，我们是否可以用算法来决定一个具有整数系数的多元多项式方程何时有整数解。事实证明，这样的算法并不存在，戴维斯、普特南、罗宾逊和马蒂亚塞维奇的解决方案花了好几年的时间。不幸的是，我们仍然不知道是否有一种算法可以确定有理数(分数)解的存在性，而不是整数。事实证明，这个问题比最初的问题更难。就像难题通常是这样，为了解决它，甚至只是为了更好地理解困难，一个数学领域被创造了出来。这个领域将多项式视为一种特殊的数学语言的一部分(被许多数学领域和许多科学使用)，并试图确定一个人可以用这种语言说什么，以及一个人是否可以用算法来决定这种语言中的句子是否为真。目前的项目在各种情况下考虑这些问题，例如“大环”(所有有理数(分数)的子集)和函数域(通过考虑多项式的比率形成的对象)。

The general questions associated with the problems discussed in this proposal can be stated as follows: what is decidable and definable in the language of rings? The current line of research has its origins in Hilbert's Tenth Problem and its solution by Davis, Putnam, Robinson and Matiyasevich. When Yurii Matiyasevich showed that over rational integers, Diophantine sets were the same as computably enumerable sets, he showed that objects originating in two different branches of Mathematics were the same. This result initiated a search for common roots of algebra and logic, a search centered on the two most important objects: integers and rational numbers. While the methods employed in the search are for the most part algebraic or geometric, the questions asked originate in Model Theory or Computability Theory. Mazur's conjectures, their extensions and their consequences for existence of Diophantine definitions and Diophantine models are a fine example of a question in Computability Theory/ Model Theory generating a question in Algebraic Geometry which in turn produces a consequence in Computability Theory/Model Theory. Another example of interaction between the fields spurred by this line of research are the recent results by Mazur and Rubin concerning ranks of elliptic curves over number fields which were produced to answer some questions of Diophantine definability. In this proposal the author plans to continue her investigation of definability and decidability over algebraic extensions of rational numbers and rational function fields of all characteristics. In particular, we plan to explore first-order definability over infinite algebraic extensions of global fields and existential undefinability of a large class of function fields of positive characteristic. This proposal investigates questions of the following sort: given a polynomial equation in several variables, is there an algorithm (or a computer program) that can tell us if this equation has solutions in a particular set. These kinds of questions go back to a German Mathematician David Hilbert who asked at the beginning of the XX century whether we could algorithmically decide when a polynomial equation in several variables with integer coefficients has integer solutions. It turned out that such an algorithm does not exist and the solution by Davis, Putnam, Robinson and Matiyasevich took quite a few years. Unfortunately, we still don't know whether there is an algorithm to determine existence of solutions in rational numbers (fractions) as opposed to integers. That problem turned out to be even harder than the original one. As it is often the case with difficult problems, in order to solve it or even just to understand better the difficulties, an area of Mathematics has been created. This area considers polynomials as a part of a special Mathematical language (used by many areas of Mathematics and many sciences) and tries to determine what one can say in this language and whether one can decide algorithmically whether a sentence in this language is true. The current project considers these questions in various settings such as ``big rings'' (subsets of all rational numbers (fractions)) and function fields (objects formed by considering ratios of polynomials).