Conservative extensions and the jump of a structure

Presented by:
A Soskova [Sofia University]
Date:
Thursday 7th June 2012 - 16:30 to 17:00
Venue:
INI Seminar Room 1
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}$.
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.
Presentation Material: