Abstract: Investigations of elementary theories for Rogers semilattices constitute one of the core directions in the theory of numberings. In recent years, the studies of significative differences in isomorphism types of these semilattices, witnessed by their algebraic and first-order properties, flourished (especially, in the area of numberings belonging to the levels of various recursion-theoretic hierarchies). Nevertheless, there are not many known results on the algorithmic complexity of elementary theories for Rogers semilattices. In this chapter, we investigate initial segments of Rogers semilattices in the analytical hierarchy, and we study decidability for fragments of the corresponding first-order theories. Let n be a non-zero natural number. For an arbitrary non-trivial Rogers semilattice R induced by a Σ 1 n -computable family of sets, we obtain the following results. The ∏4-fragment of the theory Th(R) in the signature of partial orders is hereditarily undecidable. The Σ1-fragment of Th(R) in the signature of upper semilattices is decidable. Similar results hold for families in the arithmetical hierarchy, starting with the Σ 0 4 level.

Cite: Bazhenov N. , Mustafa M.
Elementary Theories of Rogers Semilattices in the Analytical Hierarchy
In compilation Higher Recursion Theory and Set Theory. – World Scientific Publishing Co Pte. Ltd.., 2025. – C.1-18. – ISBN 978-981-98-0658-4. DOI: 10.1142/9789819806584_0001 Scopus OpenAlex

Dates:

Published print:	Mar 10, 2025
Published online:	Mar 10, 2025

Identifiers:

Scopus:	2-s2.0-105005249347
OpenAlex:	W4408136232

Citing: Пока нет цитирований

Altmetrics: