Abstract We improve on and generalize a 1960 result of Maltsev. For a field F, we denote by $H(F)$ the Heisenberg group with entries in F. Maltsev showed that there is a copy of F defined in $H(F)$ , using existential formulas with an arbitrary non-commuting pair of elements as parameters. We show that F is interpreted in $H(F)$ using computable $\Sigma _1$ formulas with no parameters. We give two proofs. The first is an existence proof, relying on a result of Harrison-Trainor, Melnikov, R. Miller, and Montalbán. This proof allows the possibility that the elements of F are represented by tuples in $H(F)$ of no fixed arity. The second proof is direct, giving explicit finitary existential formulas that define the interpretation, with elements of F represented by triples in $H(F)$ . Looking at what was used to arrive at this parameter-free interpretation of F in $H(F)$ , we give general conditions sufficient to eliminate parameters from interpretations.

Abstract For a ring R, Hilbert’s Tenth Problem $HTP(R)$ is the set of polynomial equations over R, in several variables, with solutions in R. We view $HTP$ as an enumeration operator, mapping each set W of prime numbers to $HTP(\mathbb {Z}[W^{-1}])$ , which is naturally viewed as a set of polynomials in $\mathbb {Z}[X_1,X_2,\ldots ]$ . It is known that for almost all W, the jump $W'$ does not $1$ -reduce to $HTP(R_W)$ . In contrast, we show that every Turing degree contains a set W for which such a $1$ -reduction does hold: these W are said to be HTP-complete. Continuing, we derive additional results regarding the impossibility that a decision procedure for $W'$ from $HTP(\mathbb {Z}[W^{-1}])$ can succeed uniformly on a set of measure $1$ , and regarding the consequences for the boundary sets of the $HTP$ operator in case $\mathbb {Z}$ has an existential definition in $\mathbb {Q}$ .

Abstract We introduce the notion of infinitary interpretation of structures. In general, an interpretation between structures induces a continuous homomorphism between their automorphism groups, and furthermore, it induces a functor between the categories of copies of each structure. We show that for the case of infinitary interpretation the reversals are also true: every Baire-measurable homomorphism between the automorphism groups of two countable structures is induced by an infinitary interpretation, and every Baire-measurable functor between the set of copies of two countable structures is induced by an infinitary interpretation. Furthermore, we show that the complexities are maintained in the sense that if the functor is ${\bf{\Delta }}_\alpha ^0$ , then the interpretation that induces it is ${\rm{\Delta }}_\alpha ^{in}$ up to ${\bf{\Delta }}_\alpha ^0$ equivalence.

Abstract Fried and Kollár constructed a fully faithful functor from the category of graphs to the category of fields. We give a new construction of such a functor and use it to resolve a longstanding open problem in computable model theory, by showing that for every nontrivial countable structure ${\cal S}$ , there exists a countable field ${\cal F}$ of arbitrary characteristic with the same essential computable-model-theoretic properties as ${\cal S}$ . Along the way, we develop a new “computable category theory”, and prove that our functor and its partially defined inverse (restricted to the categories of countable graphs and countable fields) are computable functors.

Abstract Our main result is the equivalence of two notions of reducibility between structures. One is a syntactical notion which is an effective version of interpretability as in model theory, and the other one is a computational notion which is a strengthening of the well-known Medvedev reducibility. We extend our result to effective bi-interpretability and also to effective reductions between classes of structures.

Abstract The degree spectrum of a countable structure is the set of all Turing degrees of presentations of that structure. We show that every nonlow Turing degree lies in the spectrum of some differentially closed field (of characteristic 0, with a single derivation) whose spectrum does not contain the computable degree 0. Indeed, this is an equivalence, for we also show that if this spectrum contained a low degree, then it would contain the degree 0. From these results we conclude that the spectra of differentially closed fields of characteristic 0 are exactly the jump-preimages of spectra of automorphically nontrivial graphs.

Abstract We introduce the notion of finitary computable reducibility on equivalence relations on the domainω. This is a weakening of the usual notion of computable reducibility, and we show it to be distinct in several ways. In particular, whereas no equivalence relation can be ${\rm{\Pi }}_{n + 2}^0$ -complete under computable reducibility, we show that, for everyn, there does exist a natural equivalence relation which is ${\rm{\Pi }}_{n + 2}^0$ -complete under finitary reducibility. We also show that our hierarchy of finitary reducibilities does not collapse, and illustrate how it sharpens certain known results. Along the way, we present several new results which use computable reducibility to establish the complexity of various naturally defined equivalence relations in the arithmetical hierarchy.

Abstract We study the relative complexity of equivalence relations and preorders from computability theory and complexity theory. Given binary relationsR,S, a componentwise reducibility is defined by R≤S⇔ ∃f∀x, y[x R y↔f(x)S f(y)]. Here,fis taken from a suitable class of effective functions. For us the relations will be on natural numbers, andfmust be computable. We show that there is a ${\rm{\Pi }}_1^0$ -complete equivalence relation, but no ${\rm{\Pi }}_k^0$ -complete fork≥ 2. We show that ${\rm{\Sigma }}_k^0$ preorders arising naturally in the above-mentioned areas are ${\rm{\Sigma }}_k^0$ -complete. This includes polynomial timem-reducibility on exponential time sets, which is ${\rm{\Sigma }}_2^0$ , almost inclusion on r.e. sets, which is ${\rm{\Sigma }}_3^0$ , and Turing reducibility on r.e. sets, which is ${\rm{\Sigma }}_4^0$ .

We continue recent work on computable structure theory in the setting of ω1. We prove the analogue of a result from Fokina et al. (2012 J. Symbolic Logic, 77, 122–132) saying that isomorphism of computable structures lies ‘on top’ among Σ11 equivalence relations on ω. Our equivalence relations are on ω1. In the standard setting, Σ11 sets are characterized in terms of paths through trees. In the setting of ω1, we use a new characterization of Σ11 sets that involves clubs in ω1. Finally, we present some new results about ω1-computable categoricity for fields.

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

Abstract Fraïssé studied countable structures through analysis of the age of , i.e., the set of all finitely generated substructures of . We investigate the effectiveness of his analysis, considering effectively presented lists of finitely generated structures and asking when such a list is the age of a computable structure. We focus particularly on the Fraïssé limit. We also show that degree spectra of relations on a sufficiently nice Fraïssé limit are always upward closed unless the relation is definable by a quantifier-free formula. We give some sufficient or necessary conditions for a Fraïssé limit to be spectrally universal. As an application, we prove that the computable atomless Boolean algebra is spectrally universal.

Abstract It is known that the spectrum of a Boolean algebra cannot contain a low4 degree unless it also contains the degree 0; it remains open whether the same holds for low5 degrees. We address the question differently, by considering Boolean subalgebras of the computable atomless Boolean algebra . For such subalgebras , we show that it is possible for the spectrum of the unary relation on to contain a low5 degree without containing 0.

We examine the relation of BSS-reducibility on subsets of the real numbers. The question was asked recently (and anonymously) whether it is possible for the halting problem H in BSS-computation to be BSS-reducible to a countable set. Intuitively, it seems that a countable set ought not to contain enough information to decide membership in a reasonably complex (uncountable) set such as H. We confirm this intuition, and prove a more general theorem linking the cardinality of the oracle set to the cardinality, in a local sense, of the set which it computes. We also mention other recent results on BSS-computation and algebraic real numbers.

Abstract We use the Low Basis Theorem of Jockusch and Soare to show that all computable algebraic fields are d-computably categorical for a particular Turing degree d with d′ = 0″, but that not all such fields are 0′-computably categorical. We also prove related results about algebraic fields with splitting algorithms, and fields of finite transcendence degree over ℚ.

Abstract We consider embeddings of structures which preserve spectra: if g : ℳ → with computable, then ℳ should have the same Turing degree spectrum (as a structure) that g(ℳ) has (as a relation on ). We show that the computable dense linear order ℒ is universal for all countable linear orders under this notion of embedding, and we establish a similar result for the computable random graph Such structures are said to be spectrally universal. We use our results to answer a question of Goncharov, and also to characterize the possible spectra of structures as precisely the spectra of unary relations on . Finally, we consider the extent to which all spectra of unary relations on the structure ℒ may be realized by such embeddings, offering partial results and building the first known example of a structure whose spectrum contains precisely those degrees c with c′ ≥ τ 0″.

Abstract We characterize the structure of computably categorical trees of finite height, and prove that our criterion is both necessary and sufficient. Intuitively, the characterization is easiest to express in terms of isomorphisms of (possibly infinite) trees, but in fact it is equivalent to a -condition. We show that all trees which are not computably categorical have computable dimension ω. Finally, we prove that for every n ≥ 1 in ω, there exists a computable tree of finite height which is Σ30-categorical but not Δn3-categorical

Abstract We prove that no computable tree of infinite height is computably categorical, and indeed that all such trees have computable dimension ω. Moreover, this dimension is effectively ω, in the sense that given any effective listing of computable presentations of the same tree, we can effectively find another computable presentation of it which is not computably isomorphic to any of the presentations on the list.

Abstract We define a property R(A0, A1) in the partial order of computably enumerable sets under inclusion, and prove that R implies that A0 is noncomputable and incomplete. Moreover, the property is nonvacuous. and the A0 and A1 which we build satisfying R form a Friedberg splitting of their union A, with A1 prompt and A promptly simple. We conclude that A0 and A1 lie in distinct orbits under automorphisms of , yielding a strong answer to a question previously explored by Downey, Stob, and Soare about whether halves of Friedberg splittings must lie in the same orbit.

Abstract Slaman and Wehner have constructed structures which distinguish the computable Turing degree 0 from the noncomputable degrees, in the sense that the spectrum of each structure consists precisely of the noncomputable degrees. Downey has asked if this can be done for an ordinary type of structure such as a linear order. We show that there exists a linear order whose spectrum includes every noncomputable degree, but not 0. Since our argument requires the technique of permitting below a set, we include a detailed explantion of the mechanics and intuition behind this type of permitting.