ON THE NOTION OF JUMP STRUCTURE

ЗаглавиеON THE NOTION OF JUMP STRUCTURE
Вид публикацияJournal Article
Година на публикуване2015
АвториVatev S
СписаниеAnnuaire de l’Université de Sofia “St. Kliment Ohridski”. Faculté de Mathématiques et Informatique
Том102
Pagination171-206
ISSN0205-0808
ключови думиcomputability, definability, structures
Резюме

For a given countable structure $\mathfrak{A}$ and a computable ordinal $\alpha$, we define its  $\alpha$-th jump structure $\mathfrak{A}^{(\alpha)}$. We study how the jump structure relates to the original structure. We consider a relation between structures called conservative extension and show that $\mathfrak{A}^{(\alpha)}$ conservatively extends the structure $\mathfrak{A}$. It follows that the relations definable in $\mathfrak{A}$ by computable infinitary $\sum_{\alpha}$  formulae are exactly the relations definable in $\mathfrak{A}^{(\alpha)}$ by computable infinitary $\sum_{1}$ formulae. Moreover, the Turing degree spectrum of $\mathfrak{A}^{(\alpha)}$ is equal to the  $\alpha$′-th jump Turing degree spectrum of  $\mathfrak{A}$, where  $\alpha′ = \alpha + 1,\text{ if } \alpha < \omega\text{, and }\alpha′ = \alpha$, otherwise.

2000 MSC

03D45, 03D30

Прикачен файлРазмер
PDF icon 102-171-206.pdf363.1 KB