Isomorphism Types of Rogers Semilattices in the Analytical Hierarchy | Sciact - Система учета научной деятельности ИМ СО РАН

Isomorphism Types of Rogers Semilattices in the Analytical Hierarchy Научная публикация

Сборник

Aspects of Computation and Automata Theory with Applications
Сборник, World Scientific Publishing Co. Pte. Ltd.. 2023. 470 c. ISBN 9789811278624.

Журнал

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

Вых. Данные

Год: 2023, Том: 42, Страницы: 97-114 Страниц : 18 DOI: 10.1142/9789811278631_0004

Авторы

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

Организации

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

Информация о финансировании (2)

1	Российский научный фонд	18-11-00028
2	Российский фонд фундаментальных исследований	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
В сборнике 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

Опубликована в печати:	13 нояб. 2023 г.
Опубликована online:	13 нояб. 2023 г.

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

БД	Цитирований
OpenAlex	2
Scopus	1