TY - JOUR

T1 - Elementary theories and hereditary undecidability for semilattices of numberings

AU - Bazhenov, Nikolay

AU - Mustafa, Manat

AU - Yamaleev, Mars

PY - 2019/5/9

Y1 - 2019/5/9

N2 - A major theme in the study of degree structures of all types has been the question of the decidability or undecidability of their first order theories. This is a natural and fundamental question that is an important goal in the analysis of these structures. In this paper, we study decidability for theories of upper semilattices that arise from the theory of numberings. We use the following approach: given a level of complexity, say Σα0, we consider the upper semilattice RΣα0 of all Σα0-computable numberings of all Σα0-computable families of subsets of N. We prove that the theory of the semilattice of all computable numberings is computably isomorphic to first order arithmetic. We show that the theory of the semilattice of all numberings is computably isomorphic to second order arithmetic. We also obtain a lower bound for the 1-degree of the theory of the semilattice of all Σα0-computable numberings, where α≥ 2 is a computable successor ordinal. Furthermore, it is shown that for any of the theories T mentioned above, the Π5-fragment of T is hereditarily undecidable. Similar results are obtained for the structure of all computably enumerable equivalence relations on N, equipped with composition.

AB - A major theme in the study of degree structures of all types has been the question of the decidability or undecidability of their first order theories. This is a natural and fundamental question that is an important goal in the analysis of these structures. In this paper, we study decidability for theories of upper semilattices that arise from the theory of numberings. We use the following approach: given a level of complexity, say Σα0, we consider the upper semilattice RΣα0 of all Σα0-computable numberings of all Σα0-computable families of subsets of N. We prove that the theory of the semilattice of all computable numberings is computably isomorphic to first order arithmetic. We show that the theory of the semilattice of all numberings is computably isomorphic to second order arithmetic. We also obtain a lower bound for the 1-degree of the theory of the semilattice of all Σα0-computable numberings, where α≥ 2 is a computable successor ordinal. Furthermore, it is shown that for any of the theories T mentioned above, the Π5-fragment of T is hereditarily undecidable. Similar results are obtained for the structure of all computably enumerable equivalence relations on N, equipped with composition.

KW - Computability theory

KW - Computably enumerable equivalence relation

KW - Elementary definability

KW - First order arithmetic

KW - Hereditary undecidability

KW - Numbering theory

KW - Rogers semilattice

KW - Second order arithmetic

KW - Upper semilattice

UR - http://www.scopus.com/inward/record.url?scp=85053898304&partnerID=8YFLogxK

U2 - 10.1007/s00153-018-0647-y

DO - 10.1007/s00153-018-0647-y

M3 - Article

AN - SCOPUS:85053898304

VL - 58

SP - 485

EP - 500

JO - Archive for Mathematical Logic

JF - Archive for Mathematical Logic

SN - 0933-5846

IS - 3-4

ER -