# zbMATH — the first resource for mathematics

Computability and numberings. (English) Zbl 1157.03022
Cooper, S. Barry (ed.) et al., New computational paradigms. Changing conceptions of what is computable. New York, NY: Springer (ISBN 978-0-387-36033-1/hbk). 19-34 (2008).
Let $$\alpha$$ be a computable ordinal. Denote by $${\mathcal R}^0_\alpha({\mathcal A})$$ the upper semilattice of $$\Sigma^0_\alpha$$-computable numberings of a family of $$\Sigma^0_\alpha$$-sets $$\mathcal A$$. The authors prove that, if $$\alpha$$ and $$\beta$$ are computable ordinals, $$\alpha>0$$, $$\alpha+3\leq\beta$$, $$\mathcal A$$ is a $$\Sigma^0_\alpha$$-computable family and $$\mathcal B$$ is a non-trivial $$\Sigma^0_\beta$$-computable family then the Rogers semilattices $${\mathcal R}^0_\alpha({\mathcal A})$$ and $${\mathcal R}^0_\beta({\mathcal B})$$ are not isomorphic.
For the entire collection see [Zbl 1130.68005].

##### MSC:
 03D45 Theory of numerations, effectively presented structures