| Заглавие | 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 |
| Pagination | 171-206 |
| ISSN | 0205-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 |
| Прикачен файл | Размер |
|---|---|
| 363.1 KB |