Algebraic and elementary properties of Rogers semilattices and Reverse mathematics

Faculty Development Competitive Research Grant Program (General) 2024-2026

The project explores uniform enumeration procedures for elements of a family of sets, facilitated by computable numberings. The complexity between two numberings can be measured by their ability to transform one enumeration procedure into another. The Rogers semilattice of a family characterizes the relative complexity of all its computable numberings. The concept of computable numberings aligns with the idea of computability within the hierarchical class of sets to which the family belongs. Various hierarchies, such as arithmetical, analytical, and Feiner hierarchies, rely on oracle computations for computability, while the Ershov hierarchy utilizes approximations of the limiting classical computations.
The overarching objective is to explore the shared and distinct properties of known computability concepts. The approach involves studying the algebraic and elementary properties of Rogers semilattices in different hierarchies, aiming to identify global invariants that highlight significant distinctions in the algebraic characteristics of the Rogers semilattices belonging to arithmetical, analytical, Ershov's, and Feiner's hierarchies. These invariants encompass cardinality, minimal and maximal elements, elementary theories, and types of isomorphism.
Moreover, the project aims to analyze Rogers semilattices from the perspective of reverse mathematics