Skip to content

SAS

Seminar

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

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

Presentation

[pdf ]

Video

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 ∧