Unfriendly jump inversions

Abstract

We introduce a new technique in computable structure theory which we call unfriendly jump inversions. In contrast to the standard technique of jump inversions, we obtain the maximal possible difference between the effective and non-effective settings, namely, the $n$th unfriendly jump inversion behaves like an $n$th jump inversion from the non-effective perspective, but like a $2n$th jump inversion from the effective perspective. We give several applications, among them the construction of a structure which has no arithmetic copy but which has a copy computable from every non-arithmetic set. This has been an open question in the study of degree spectra for some time. We also show that for every $n\ge 2$ there is a computable structure with a ${\Pi }_n$ Scott sentence but no computable ${\Sigma }_{2n}$ Scott sentence.

The title in the metadata was changed from "Relative to any non-arithmetic set" to "Unfriendly jump inversions" to reflect the change in title of the pdf