ON THE NOTION OF JUMP STRUCTURE

Authors

  • Stefan V. Vatev

Keywords:

computability, definability, structures

Abstract

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.

Downloads

Published

2015-12-12

How to Cite

V. Vatev, S. (2015). ON THE NOTION OF JUMP STRUCTURE. Ann. Sofia Univ. Fac. Math. And Inf., 102, 171–206. Retrieved from https://stipendii.uni-sofia.bg/index.php/fmi/article/view/69