Abstract In 1998 R. Downey formulated a problem: to describe a property $P$ of classical order types, which guarantees that if $\mathcal{L}$ is a low linear order and $P$ holds for the order type of $\mathcal{L}$ then $\mathcal{L}$ is isomorphic to a computable linear order. We find a new such property $P$. Also, we give an upper bound on a complexity of an isomorphism between computable and low copies and show that this bound is sharp.

Abstract A low linear order with no computable copy constructed by C. Jockusch and R. Soare has Hausdorff rank equal to $2$ . In this regard, the question arises, how simple can be a low linear order with no computable copy from the point of view of the linear order type? The main result of this work is an example of a low strong $\eta $ -representation with no computable copy that is the simplest possible example.

Abstract We characterize the linear order types $\tau $ with the property that given any countable linear order $\mathcal {L}$ , $\tau \cdot \mathcal {L}$ is a computable linear order iff $\mathcal {L}$ is a computable linear order, as exactly the finite nonempty order types.

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.

Journal Article Low linear orderings Get access Andrey N. Frolov Andrey N. Frolov N. G. Chebotarev Research Institute of Mathematics and Mechanics, Kazan Federal University, Kazan, Russia.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 745–754, https://doi.org/10.1093/logcom/exq040 Published: 13 September 2010 Article history Received: 19 October 2009 Published: 13 September 2010

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