Abstract We prove an effective version of the Lopez-Escobar theorem for continuous domains. Let $Mod(\tau )$ be the set of countable structures with universe $\omega $ in vocabulary $\tau $ topologized by the Scott topology. We show that an invariant set $X\subseteq Mod(\tau )$ is $\Pi ^0_\alpha $ in the Borel hierarchy of this topology if and only if it is definable by a $\Pi ^p_\alpha $ -formula, a positive $\Pi ^0_\alpha $ formula in the infinitary logic $L_{\omega _1\omega }$ . As a corollary of this result we obtain a new pullback theorem for positive computable embeddings: Let $\mathcal {K}$ be positively computably embeddable in $\mathcal {K}'$ by $\Phi $ , then for every $\Pi ^p_\alpha $ formula $\xi $ in the vocabulary of $\mathcal {K}'$ there is a $\Pi ^p_\alpha $ formula $\xi ^{*}$ in the vocabulary of $\mathcal {K}$ such that for all $\mathcal {A}\in \mathcal {K}$ , $\mathcal {A}\models \xi ^{*}$ if and only if $\Phi (\mathcal {A})\models \xi $ . We use this to obtain new results on the possibility of positive computable embeddings into the class of linear orderings.

Abstract Cohesive powersof computable structures are effective analogs of ultrapowers, where cohesive sets play the role of ultrafilters. Let $\omega $ , $\zeta $ , and $\eta $ denote the respective order-types of the natural numbers, the integers, and the rationals when thought of as linear orders. We investigate the cohesive powers of computable linear orders, with special emphasis on computable copies of $\omega $ . If $\mathcal {L}$ is a computable copy of $\omega $ that is computably isomorphic to the usual presentation of $\omega $ , then every cohesive power of $\mathcal {L}$ has order-type $\omega + \zeta \eta $ . However, there are computable copies of $\omega $ , necessarily not computably isomorphic to the usual presentation, having cohesive powers not elementarily equivalent to $\omega + \zeta \eta $ . For example, we show that there is a computable copy of $\omega $ with a cohesive power of order-type $\omega + \eta $ . Our most general result is that if $X \subseteq \mathbb {N} \setminus \{0\}$ is a Boolean combination of $\Sigma _2$ sets, thought of as a set of finite order-types, then there is a computable copy of $\omega $ with a cohesive power of order-type $\omega + \boldsymbol {\sigma }(X \cup \{\omega + \zeta \eta + \omega ^*\})$ , where $\boldsymbol {\sigma }(X \cup \{\omega + \zeta \eta + \omega ^*\})$ denotes the shuffle of the order-types inXand the order-type $\omega + \zeta \eta + \omega ^*$ . Furthermore, ifXis finite and non-empty, then there is a computable copy of $\omega $ with a cohesive power of order-type $\omega + \boldsymbol {\sigma }(X)$ .

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 There is a Turing computable embedding $\Phi $ of directed graphs $\mathcal {A}$ in undirected graphs (see [15]). Moreover, there is a fixed tuple of formulas that give a uniform effective interpretation; i.e., for all directed graphs $\mathcal {A}$ , these formulas interpret $\mathcal {A}$ in $\Phi (\mathcal {A})$ . It follows that $\mathcal {A}$ is Medvedev reducible to $\Phi (\mathcal {A})$ uniformly; i.e., $\mathcal {A}\leq _s\Phi (\mathcal {A})$ with a fixed Turing operator that serves for all $\mathcal {A}$ . We observe that there is a graph G that is not Medvedev reducible to any linear ordering. Hence, G is not effectively interpreted in any linear ordering. Similarly, there is a graph that is not interpreted in any linear ordering using computable $\Sigma _2$ formulas. Any graph can be interpreted in a linear ordering using computable $\Sigma _3$ formulas. Friedman and Stanley [4] gave a Turing computable embedding L of directed graphs in linear orderings. We show that there is no fixed tuple of $L_{\omega _1\omega }$ -formulas that, for all G, interpret the input graph G in the output linear ordering $L(G)$ . Harrison-Trainor and Montalbán [7] have also shown this, by a quite different proof.

We say that a structure $\mathcal{A}$ admits \emph{strong jump inversion} provided that for every oracle $X$, if $X'$ computes $D(\mathcal{C})'$ for some $\mathcal{C}\cong\mathcal{A}$, then $X$ computes $D(\mathcal{B})$ for some $\mathcal{B}\cong\mathcal{A}$. Jockusch and Soare \cite{JS} showed that there are low linear orderings without computable copies, but Downey and Jockusch \cite{DJ} showed that every Boolean algebra admits strong jump inversion. More recently, D.\ Marker and R.\ Miller \cite{MM} have shown that all countable models of $DCF_0$ (the theory of differentially closed fields of characteristic $0$) admit strong jump inversion. We establish a general result with sufficient conditions for a structure $\mathcal{A}$ to admit strong jump inversion. Our conditions involve an enumeration of $B_1$-types, where these are made up of formulas that are Boolean combinations of existential formulas. Our general result applies to some familiar kinds of structures, including some classes of linear orderings and trees. We do not get the result of Downey and Jockusch for arbitrary Boolean algebras, but we do get a result for Boolean algebras with no $1$-atom, with some extra information on the complexity of the isomorphism. Our general result gives the result of Marker and Miller. In order to apply our general result, we produce a computable enumeration of the types realized in models of $DCF_0$. This also yields the fact that the saturated model of $DCF_0$ has a decidable copy.

We prove the following properties of quasi-minimal degrees for the degree spectrum of a structure. There are uncountably many quasi-minimal degrees for every degree spectrum. The first jump spectrum of every structure consists exactly of the enumeration jumps of the quasi-minimal degrees for the degree spectrum. Every element of the first jump spectrum could be represented as the join of two quasi-minimal degrees for the degree spectrum.

Alexandra Soskova, S. Barry Cooper, Andrea Sorbi; Computability at Logic Colloquium 2009, Journal of Logic and Computation, Volume 22, Issue 4, 1 August 20

In the present article, we continue the study of the properties of the spectra of structures as sets of degrees initiated in [11]. Here, we consider the relationships between the spectra and the jump spectra. Our first result is that every jump spectrum is also a spectrum. The main result sounds like a Jump inversion theorem. Namely, we show that if a spectrum 𝒜 is contained in the set of the jumps of the degrees in some spectrum ℬ then there exists a spectrum 𝒞 such that 𝒞⊆ℬ and 𝒜 is equal to the set of the jumps of the degrees in 𝒞.

We present a relativized version of the notion of a degree spectrum of a structure with respect to finitely many abstract structures. We study the connection to the notion of joint spectrum. We prove that some properties of the degree spectrum as a minimal pair theorem and the existence of quasi-minimal degrees are true for the relative spectrum.