Abstract Working toward showing the decidability of the $\forall \exists $ -theory of the ${\Sigma ^0_2}$ -enumeration degrees, we prove that no so-called Ahmad pair of ${\Sigma ^0_2}$ -enumeration degrees can join to ${\mathbf 0}_e'$ .

Abstract Recall that B is PA relative to A if B computes a member of every nonempty $\Pi ^0_1(A)$ class. This two-place relation is invariant under Turing equivalence and so can be thought of as a binary relation on Turing degrees. Miller and Soskova [23] introduced the notion of a $\Pi ^0_1$ class relative to an enumeration oracle A, which they called a $\Pi ^0_1{\left \langle {A}\right \rangle }$ class. We study the induced extension of the relation B is PA relative to A to enumeration oracles and hence enumeration degrees. We isolate several classes of enumeration degrees based on their behavior with respect to this relation: the PA bounded degrees, the degrees that have a universal class, the low for PA degrees, and the ${\left \langle {\text {self}\kern1pt}\right \rangle }$ -PA degrees. We study the relationship between these classes and other known classes of enumeration degrees. We also investigate a group of classes of enumeration degrees that were introduced by Kalimullin and Puzarenko [14] based on properties that are commonly studied in descriptive set theory. As part of this investigation, we give characterizations of three of their classes in terms of a special sub-collection of relativized $\Pi ^0_1$ classes—the separating classes. These three can then be seen to be direct analogues of three of our classes. We completely determine the relative position of all classes in question.

Abstract We give several new characterizations of the continuous enumeration degrees. The main one proves that an enumeration degree is continuous if and only if it is not half of a nontrivial relativized $\mathcal {K}$ -pair. This leads to a structural dichotomy in the enumeration degrees.

Abstract A structure is automatic if its domain, functions, and relations are all regular languages. Using the fact that every automatic structure is decidable, in the literature many decision problems have been solved by giving an automatic presentation of a particular structure. Khoussainov and Nerode asked whether there is some way to tell whether a structure has, or does not have, an automatic presentation. We answer this question by showing that the set of Turing machines that represent automata-presentable structures is ${\rm{\Sigma }}_1^1 $ -complete. We also use similar methods to show that there is no reasonable characterisation of the structures with a polynomial-time presentation in the sense of Nerode and Remmel.

Abstract A Turing degreedis the degree of categoricity of a computable structure ${\cal S}$ ifdis the least degree capable of computing isomorphisms among arbitrary computable copies of ${\cal S}$ . A degreedis the strong degree of categoricity of ${\cal S}$ ifdis the degree of categoricity of ${\cal S}$ , and there are computable copies ${\cal A}$ and ${\cal B}$ of ${\cal S}$ such that every isomorphism from ${\cal A}$ onto ${\cal B}$ computesd. In this paper, we build a c.e. degreedand a computable rigid structure ${\cal M}$ such thatdis the degree of categoricity of ${\cal M}$ , butdis not the strong degree of categoricity of ${\cal M}$ . This solves the open problem of Fokina, Kalimullin, and Miller [13]. For a computable structure ${\cal S}$ , we introduce the notion of the spectral dimension of ${\cal S}$ , which gives a quantitative characteristic of the degree of categoricity of ${\cal S}$ . We prove that for a nonzero natural numberN, there is a computable rigid structure ${\cal M}$ such that $0\prime$ is the degree of categoricity of ${\cal M}$ , and the spectral dimension of ${\cal M}$ is equal toN.

Abstract We study Turing degrees a for which there is a countable structure ${\cal A}$ whose degree spectrum is the collection {x : x ≰ a}. In particular, for degrees a from the interval [0′, 0″], such a structure exists if a′ = 0″, and there are no such structures if a″ > 0‴.

In the article, we study the behaviour of enumeration jumps of sets of low e-degrees in the Ershov hierarchy.

Journal Article Spectra of high n and non-low n degrees Get access Andrey Frolov, Andrey Frolov N. G. Chebotarev Research Inst. of Mechanics and Mathematics, Kazan Federal University, Universitetskaya St., 17, Kazan 420008, Russia.E-mail: [email protected]; [email protected] Search for other works by this author on: Oxford Academic Google Scholar Iskander Kalimullin, Iskander Kalimullin N. G. Chebotarev Research Inst. of Mechanics and Mathematics, Kazan Federal University, Universitetskaya St., 17, Kazan 420008, Russia.E-mail: [email protected]; [email protected] Search for other works by this author on: Oxford Academic Google Scholar Valentina Harizanov, Valentina Harizanov Department of Mathematics, George Washington University, Washington, DC 20052, USA. E-mail: [email protected] Search for other works by this author on: Oxford Academic Google Scholar Oleg Kudinov, Oleg Kudinov Sobolev Institute of Mathematics, Russian Academy of Sciences, Siberian Branch, 630090 Novosibirsk Russia. E-mail: [email protected] Search for other works by this author on: Oxford Academic Google Scholar Russell Miller Russell Miller Department of Mathematics, Queens College & C.U.N.Y. Graduate Center, 365 Fifth Avenue, New York, New York 10016, USA. E-mail: [email protected] Search for other works by this author on: Oxford Academic Google Scholar Journal of Logic and Computation, Volume 22, Issue 4, August 2012, Pages 755–777, https://doi.org/10.1093/logcom/exq041 Published: 30 November 2010 Article history Received: 16 October 2009 Published: 30 November 2010

We describe all possible relations between certain reducibities of algebraic structures which are based on the mass problems of structure presentability.

Abstract We prove that the degree structures of the d.c.e. and the 3-c.e. Turing degrees are not elementarily equivalent, thus refuting a conjecture of Downey. More specifically, we show that the following statement fails in the former but holds in the latter structure: There are degreesf>e>d>0such that any degreeu≤fis either comparable with botheandd, or incomparable with both.

We study the enumerability of families relative to the enumeration degrees. It is shown that if a family of finite sets is e-reducible to every non-zero e-degree, then the family is computably enumerable (c.e). On the another hand, we will find a non-c.e. family which is e-reducible to all non-zero e-degree. This allows to construct a model, whose (extended) degree spectrum coincides with the non-zero e-degrees.

Abstract It is proved that the (2p)-c. e. e-degrees are not elementarily equivalent to the (2p + 1)-c. e. e-degrees for each nonzero p ∈ ω. It follows that m-c. e. e-degrees are not elementarily equivalent to the n-c e. e-degrees if 1 <m < n.

Abstract It is proved that if 1 < m < 2p ≤ n for some integer p then the elementary theories of posets of m-c.e. and n-c.e. e-degrees are distinct. It is proved also that the structures 〈 2n, ≤, 〉 and 〈 2n, ≤. P〉 are not elementary equivalent where P is the predicate P(a) = “a is a e-degree”.