Recursive labelling systems and stability of recursive structures in hyperarithmetical degrees

Abstract:

We show that, under certain assumptions of recursiveness in $\mathfrak {A}$, the recursive structure $\mathfrak {A}$ is $\Delta _\alpha ^0$-stable for $\alpha < \omega _1^{CK}$ if and only if there is an enumeration of $\mathfrak {A}$ using a $\Sigma _\alpha ^0$ set of recursive ${\Sigma _\alpha }$ infinitary formulae and finitely many parameters from $\mathfrak {A}$. This extends the results of [1]. To do this, we first obtain results concerning $\Delta _\alpha ^0$ paths in recursive labelling systems, also extending results of [1]. We show, more generally, that a path and a labelling can simultaneously be defined, when each node of the path is to be obtained by a $\Delta _\alpha ^0$ function from the previous node and its label.