The INI has a new website!

This is a legacy webpage. Please visit the new site to ensure you are seeing up to date information.

Skip to content



Conservative extensions and the jump of a structure

Soskova, A (Sofia University)
Thursday 07 June 2012, 16:30-17:00

Seminar Room 1, Newton Institute


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}$.


[pdf ]


The video for this talk should appear here if JavaScript is enabled.
If it doesn't, something may have gone wrong with our embedded player.
We'll get it fixed as soon as possible.

Back to top ∧