Elementary Theories of Rogers Semilattices in the Analytical Hierarchy
Nikolay A. Bazhenov, Manat Mustafa · Lecture notes series, Institute For Mathematical Sciences · 2025
Lecture Notes Series, Institute for Mathematical Sciences, National University of SingaporeHigher Recursion Theory and Set Theory, pp. 1-18 (2025) Free AccessElementary Theories of Rogers Semilattices in the Analytical HierarchyNikolay Bazhenov and Manat MustafaNikolay BazhenovSobolev Institute of Mathematics, 4 Acad. Koptyug Ave., Novosibirsk, 630090, Russia and Manat MustafaDepartment of Mathematics, School of Sciences and Humanities, Nazarbayev University, 53 Qabanbaybatyr Ave., Astana, 010000, Kazakhstanhttps://doi.org/10.1142/9789819806584_0001Cited by:0 (Source: Crossref) PreviousNext AboutFiguresReferencesRelatedDetailsPDF/EPUB ToolsAdd to favoritesDownload CitationsTrack CitationsRecommend to Library ShareShare onFacebookTwitterLinked InRedditEmail Cite Recommend 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 Σ1nΣn1-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 Σ04Σ40 level. We recommendCOMPLETENESS OF ROOT FUNCTIONS AND ELEMENTARY SOLUTIONS OF THE THERMOELASTICITY SYSTEMMathematical Models and Methods in Applied Sciences, 2011The Level Set Method for Etching and DepositionD. Adalsteinsson, Mathematical Models and Methods in Applied Sciences, 2011A HIERARCHY OF APPROXIMATIONS TO THE RADIATIVE HEAT TRANSFER EQUATIONS: MODELLING, ANALYSIS AND SIMULATIONMathematical Models and Methods in Applied Sciences, 2011Bogolubov and Kinetic Theory: The Bogolubov EquationsE. G. D. Cohen, Mathematical Models and Methods in Applied Sciences, 2011ANALYTICAL AND NUMERICAL SOLUTIONS OF THE SHALLOW WATER EQUATIONS FOR 2D ROTATIONAL FLOWSVLADIMIR TESHUKOV, Mathematical Models and Methods in Applied Sciences, 2011The theory and practice of textual criticism - reconstructing the Old Greek of Proverbs 8 Johann Cook, Old Testament Essays, 2004Women, fire and dangerous things in the Hebrew Bible : insights from the cognitive theory of metaphor Z. Kotze, Old Testament Essays, 2004Thinking at the interface : theory and practice in the South African university/community relationship : part 2 C. Soudien, Old Testament EssaysThe Impact of Solidarity Center Branding on Sustainable Development Okaï Ozbal, Business Research Proceedings, 2023Stone circles in the Bloubos landscape, Northern Cape Isabelle Parsons, Southern African Humanities, 2004Powered by Privacy policyGoogle Analytics settings FiguresReferencesRelatedDetails Recommended Recommended Isomorphism Types of Rogers Semilattices in the Analytical HierarchyBy (author): Nikolay Bazhenov, Sergey Ospichev, and Mars YamaleevAspects of Computation and Automata Theory with ApplicationsELEMENTARY PROPERTIES OF ROGERS SEMILATTICES OF ARITHMETICAL NUMBERINGSS. A. BADAEV, S. S. GONCHAROV, and A. SORBIProceedings of the 7th and 8th Asian Logic ConferencesCUPPING COMPUTABLY ENUMERABLE DEGREES IN THE ERSHOV HIERARCHYGuohua WuComputational Prospects of InfinityThe Ershov HierarchyMarat M. ArslanovComputability in ContextTURING DEGREES AND THE ERSHOV HIERARCHYFRANK STEPHAN, YUE YANG, and LIANG YUProceedings of the 10th Asian Logic ConferenceSectionally pseudocomplemented lattices and semilatticesI. Chajda and R. HalašAdvances in AlgebraCOMPUTABLE NUMBERINGS IN THE HIERARCHY OF ERSHOVS. A. BADAEV and Zh. T. TALASBAEVAMathematical Logic in AsiaLATTICES OF QUASI-EQUATIONAL THEORIES AS CONGRUENCE LATTICES OF SEMILATTICES WITH OPERATORS: PART IKIRA ADARICHEVA and J. B. NATIONInternational Journal of Algebra and ComputationVol. 22, No. 07 Higher Recursion Theory and Set TheoryMetrics Downloaded 12 times History PDF download