Strong jump inversion for abstract structures

Alexandra Soskova, Sofia University. Part of the logic seminar series.

We establish a general result with sufficient conditions for a structure A to admit strong jump inversion.  We say that a structure A admits strong jump inversion provided that for every oracle X, if X' computes D(C)' for some C isomorphic to A, then X computes D(B) for some B isomorphic to A.  Jockusch and Soare showed that there are low linear orderings without computable copies, but Downey and Jockusch showed that every Boolean algebra admits strong jump inversion.  More recently, D. Marker and R. Miller have shown that all countable models of DCF_0 (the theory of differentially closed fields of characteristic 0) 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, 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.

This is joint work with W. Calvert, A. Frolov, V. Harizanov, J. Knight, C. McCoy, and S. Vatev.