SAS

Abstract

The degree spectrum of an abstract structure is a measure of its complexity. We consider a relation between abstract structures $\mathfrak{A}$ and $\mathfrak{B}$, possibly with different signatures and $|\mathfrak{A}|\subseteq |\mathfrak{B}|$, called conservative extension. We give a characterization of this relation in terms of definability by computable $\Sigma_n$ formulae on these structures. We show that this relation provides a finer complexity measure than the one given by degree spectra. As an application, we receive that the $n$-th jump of a structure and its Marker's extension are conservative extensions of the original structure. We present a jump inversion theorem for abstract structures. We prove that for every natural numbers $n$ and $k$ and each complex enough structure $\mathfrak{A}$, there is a structure $\mathfrak{B}$, such that the definable by computable $\Sigma^c_n$ formulae sets on $\mathfrak{A}$ are exactly the definable by computable $\Sigma^c_k$ formulae on $\mathfrak{B}$.