Isomorphism Types of Rogers Semilattices in the Analytical Hierarchy

Isomorphism Types of Rogers Semilattices in the Analytical Hierarchy Full article

Source

Aspects of Computation and Automata Theory with Applications
Compilation, World Scientific Publishing Co. Pte. Ltd.. 2023. 470 c. ISBN 9789811278624.

Journal

Lecture Notes Series, Institute for Mathematical Sciences
ISSN: 1793-0758

Output data

Year: 2023, Volume: 42, Pages: 97-114 Pages count : 18 DOI: 10.1142/9789811278631_0004

Authors

Bazhenov Nikolay ^1,2 , Ospichev Sergey ^1,3 , Yamaleev M.M. ⁴

Affiliations

1	Department of Mathematics, School of Sciences and Humanities, Nazarbayev University, 53 Qabanbaybatyr Ave., Astana, 010000, Kazakhstan
2	Sobolev Institute of Mathematics, 4 Acad. Koptyug Ave., Novosibirsk, 630090, Russia
3	Novosibirsk State University, 2 Pirogova St., Novosibirsk, 630090, Russia
4	Kazan Federal University, 18 Kremlyovskaya St., Kazan, 420008, Russia

Funding (2)

1	Russian Science Foundation	18-11-00028
2	Russian Foundation for Basic Research	17-01-00247

A numbering of a countable family S is a surjective map from the set of natural numbers ω onto S. A numbering ν is reducible to a numbering µ if there is an effective procedure which given a ν-index of an object from S, computes a µ-index for the same object. The reducibility between numberings gives rise to a class of upper semilattices, which are usually called Rogers semilattices. This chapter studies Rogers semilattices for families S ⊂ P(ω) belonging to various levels of the analytical hierarchy. We prove that for any non-zero natural numbers m ≠ n, any non-trivial Rogers semilattice of a Π1m-computable family cannot be isomorphic to a Rogers semilattice of a Π1n-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.

Bazhenov N. , Ospichev S. , Yamaleev M.M.
Isomorphism Types of Rogers Semilattices in the Analytical Hierarchy
In compilation Aspects of Computation and Automata Theory with Applications. – World Scientific Publishing Co. Pte. Ltd.., 2023. – Т.42. – C.97-114. – ISBN 9789811278624. DOI: 10.1142/9789811278631_0004 Scopus OpenAlex

Published print:	Nov 13, 2023
Published online:	Nov 13, 2023

Scopus:	2-s2.0-85179413785
OpenAlex:	W2996268481

DB	Citing
OpenAlex	2
Scopus	1