Hostname: page-component-5cf477f64f-bmd9x Total loading time: 0 Render date: 2025-04-01T22:22:25.606Z Has data issue: false hasContentIssue false

Algorithmic Properties of Rogers Semilattices

Published online by Cambridge University Press:  18 March 2025

Zhansaya Tleuliyeva*
Affiliation:
Nazarbayev University
Rights & Permissions [Opens in a new window]

Abstract

Core share and HTML view are not available for this content. However, as you have access to this content, a full PDF is available via the ‘Save PDF’ action button.

The thesis uses various approaches to explore the algorithmic complexity of families of subsets of natural numbers. One of these approaches involves investigating upper semilattices of computable numberings of a given family and their complexity in different hierarchies. These semilattices, known as Rogers semilattices, can help distinguish different structural properties of families of partial computable functions and computably enumerable sets. As a result, by using Rogers semilattices of computable numberings, we can measure the algorithmic complexity of the corresponding family.

In the first part of thesis, we focus on limitwise monotonic numberings for families of limitwise monotonic sets and define their Rogers semilattices. The chapter investigates global invariants that show differences in the algebraic and elementary properties of the Rogers semilattices of families of sets from arithmetical hierarchy and Rogers semilattices of limitwise monotonic numberings. Such invariants include cardinality, laticeness, and types of isomorphism.

Within the second part of thesis, we explore the different forms of isomorphism exhibited by Rogers semilattices of families of sets in the analytical hierarchy. Additionally, we take into account various set-theoretic assumptions. Our research demonstrates that, when set-theoretic assumption known as Projective Determinacy is assumed, there exist an infinite number of non-isomorphic Rogers semilattices at each $\Sigma _n^1$-level of the analytical hierarchy.

I would also like to acknowledge the Grant of Science Committee of the Ministry of Science and Higher Education of the Republic of Kazakhstan (AP19676989) and the Nazarbayev University Faculty Development Grant (N021220FD3851) for funding this research.

Abstract prepared by Zhansaya Tleuliyeva

[email protected].

URL: http://nur.nu.edu.kz/handle/123456789/7769.

Type
Thesis Abstract
Copyright
© The Author(s), 2025. Published by Cambridge University Press on behalf of The Association for Symbolic Logic

Footnotes

Supervised by Manat Mustafa and Nikolay Bazhenov.