Isomorphism types of Rogers semilattices in the analytical hierarchy

DOI10.1142/9789811278631_0004arXiv1912.05226MaRDI QIDQ6330898FDOQ6330898

Authors: Nikolay Bazhenov, S. S. Ospichev, M. M. Yamaleev 

Publication date: 11 December 2019

Abstract: A numbering of a countable family $S$ is a surjective map from the set of natural numbers $omega$ onto $S$. A numbering $u$ is reducible to a numbering $mu$ if there is an effective procedure which given a $u$-index of an object from $S$, computes a $mu$-index for the same object. The reducibility between numberings gives rise to a class of upper semilattices, which are usually called Rogers semilattices. The paper studies Rogers semilattices for families $SsubsetP(omega)$ belonging to various levels of the analytical hierarchy. We prove that for any non-zero natural numbers $meqn$, any non-trivial Rogers semilattice of a $P{i}_m^1$-computable family cannot be isomorphic to a Rogers semilattice of a $P{i}_n^1$-computable family. One of the key ingredients of the proof is an application of the result by Downey and Knight on degree spectra of linear orders.

Mathematics Subject Classification ID

Theory of numerations, effectively presented structures (03D45) Hierarchies of computability and definability (03D55)

This page was built for publication: Isomorphism types of Rogers semilattices in the analytical hierarchy

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6330898)