Generic muchnik reducibility and presentations of fields
Generic muchnik reducibility and presentations of fields
复制标题
通用的 muchnik 可归约性和域的表示
DOI：
10.1007/s11856-016-1413-7
复制
发表时间：
2016
影响因子：
1
通讯作者：
Joseph S. Miller
中科院分区：
文献类型：
--
作者：
R. Downey;Noam Greenberg;Joseph S. Miller
我们证明了如果I是图灵度中的可数理想，则I中的真实的数域RI可以从列出函数的度精确计算（即，ωω的元素）在I.例如，这意味着可计算真实的数域的度谱恰好由高次组成。我们还证明了，如果I是可数Scott理想，那么列出集合严格更容易（即，2ω的元素），而不是列出I中的函数。这使我们能够回答奈特、蒙塔尔班和施韦伯的一个问题。他们引入了泛型Muchnik可约性，将可数结构之间的Muchnik可约性扩展到任意结构。他们问R是否一般地Muchnik可约化为由所有自然数集合组成的结构。我们对Scott理想的结果表明事实并非如此。最后，我们考虑了可数结构A到任意结构B的一般Muchnik可约性。我们与此相关的一对夫妇的条件断言的无处不在的可数基本子结构的B是Muchnik以上A，我们证明了这些条件之一是严格的更强，另一个是严格弱于通用Muchnik约简。
We prove that ifIis a countable ideal in the Turing degrees, then the fieldRIof real numbers inIis computable from exactly the degrees that list the functions (i.e., elements ofωω) inI. This implies, for example, that the degree spectrum of the field of computable real numbers consists exactly of the high degrees. We also prove that ifIis a countable Scott ideal, then it is strictly easier to list the sets (i.e., elements of 2ω) inIthan it is to list the functions inI. This allows us to answer a question of Knight, Montalbán, and Schweber. They introducedgeneric Muchnik reducibilityto extend the idea of Muchnik reducibility between countable structures to arbitrary structures. They asked if R is generically Muchnik reducible to the structure that consists of all sets of natural numbers. Our result for Scott ideals shows that this is not the case.We finish by considering generic Muchnik reducibility of a countable structureAto an arbitrary structureB. We relate this to a couple of conditions asserting the ubiquity of countable elementary substructures ofBthat are Muchnik aboveA; we prove that one of these conditions is strictly stronger and the other is strictly weaker than generic Muchnik reducibility.