ELEMENTARY THEORIES AND HEREDITARY UNDECIDABILITY FOR SEMILATTICES OF NUMBERINGS

Manat Mustafa, Nikolay Bazhenov, Yamaleev Mars

Research output: Contribution to journalArticle

Abstract

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 $\Sigma^0_{\alpha}$,
we consider the upper semilattice $R_{\Sigma^0_{\alpha}}$ of all $\Sigma^0_{\alpha}$-computable
numberings of all $\Sigma^0_{\alpha}$-computable families of subsets of $\mathbb{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 $\Sigma^0_{\alpha}$-computable numberings, where $\alpha \geq 2$ is a computable successor ordinal.
Furthermore, it is shown that for any of the theories $T$ mentioned above, the $\Pi_5$-fragment of $T$ is hereditarily undecidable. Similar results are obtained for the structure of all computably enumerable equivalence relations on $\mathbb{N}$, equipped with composition.
Original languageEnglish
Article number1
Number of pages15
JournalArchive for Mathematical Logic
DOIs
Publication statusAccepted/In press - 2018

Fingerprint

Undecidability
Semilattice
Decidability
Isomorphic
Second Order Arithmetic
First-order
Equivalence relation
Pi
Fragment
Lower bound
Subset

Cite this

ELEMENTARY THEORIES AND HEREDITARY UNDECIDABILITY FOR SEMILATTICES OF NUMBERINGS. / Mustafa, Manat; Bazhenov, Nikolay; Mars, Yamaleev.

In: Archive for Mathematical Logic, 2018.

Research output: Contribution to journalArticle

@article{52bace09bb844be28f294eaeafe1cabc,
title = "ELEMENTARY THEORIES AND HEREDITARY UNDECIDABILITY FOR SEMILATTICES OF NUMBERINGS",
abstract = "A major theme in the study of degree structures of all types has been the questionof the decidability or undecidability of their first order theories. This is a natural andfundamental 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 $\Sigma^0_{\alpha}$,we consider the upper semilattice $R_{\Sigma^0_{\alpha}}$ of all $\Sigma^0_{\alpha}$-computablenumberings of all $\Sigma^0_{\alpha}$-computable families of subsets of $\mathbb{N}$. We prove thatthe theory of the semilattice of all computable numberings is computably isomorphic to first order arithmetic. We show thatthe 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 $\Sigma^0_{\alpha}$-computable numberings, where $\alpha \geq 2$ is a computable successor ordinal.Furthermore, it is shown that for any of the theories $T$ mentioned above, the $\Pi_5$-fragment of $T$ is hereditarily undecidable. Similar results are obtained for the structure of all computably enumerable equivalence relations on $\mathbb{N}$, equipped with composition.",
author = "Manat Mustafa and Nikolay Bazhenov and Yamaleev Mars",
year = "2018",
doi = "DOI: 10.1007/s00153-018-0647-y",
language = "English",
journal = "Archive for Mathematical Logic",
issn = "0933-5846",
publisher = "Springer New York",

}

TY - JOUR

T1 - ELEMENTARY THEORIES AND HEREDITARY UNDECIDABILITY FOR SEMILATTICES OF NUMBERINGS

AU - Mustafa, Manat

AU - Bazhenov, Nikolay

AU - Mars, Yamaleev

PY - 2018

Y1 - 2018

N2 - A major theme in the study of degree structures of all types has been the questionof the decidability or undecidability of their first order theories. This is a natural andfundamental 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 $\Sigma^0_{\alpha}$,we consider the upper semilattice $R_{\Sigma^0_{\alpha}}$ of all $\Sigma^0_{\alpha}$-computablenumberings of all $\Sigma^0_{\alpha}$-computable families of subsets of $\mathbb{N}$. We prove thatthe theory of the semilattice of all computable numberings is computably isomorphic to first order arithmetic. We show thatthe 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 $\Sigma^0_{\alpha}$-computable numberings, where $\alpha \geq 2$ is a computable successor ordinal.Furthermore, it is shown that for any of the theories $T$ mentioned above, the $\Pi_5$-fragment of $T$ is hereditarily undecidable. Similar results are obtained for the structure of all computably enumerable equivalence relations on $\mathbb{N}$, equipped with composition.

AB - A major theme in the study of degree structures of all types has been the questionof the decidability or undecidability of their first order theories. This is a natural andfundamental 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 $\Sigma^0_{\alpha}$,we consider the upper semilattice $R_{\Sigma^0_{\alpha}}$ of all $\Sigma^0_{\alpha}$-computablenumberings of all $\Sigma^0_{\alpha}$-computable families of subsets of $\mathbb{N}$. We prove thatthe theory of the semilattice of all computable numberings is computably isomorphic to first order arithmetic. We show thatthe 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 $\Sigma^0_{\alpha}$-computable numberings, where $\alpha \geq 2$ is a computable successor ordinal.Furthermore, it is shown that for any of the theories $T$ mentioned above, the $\Pi_5$-fragment of $T$ is hereditarily undecidable. Similar results are obtained for the structure of all computably enumerable equivalence relations on $\mathbb{N}$, equipped with composition.

UR - https://link.springer.com/article/10.1007/s00153-018-0647-y

U2 - DOI: 10.1007/s00153-018-0647-y

DO - DOI: 10.1007/s00153-018-0647-y

M3 - Article

JO - Archive for Mathematical Logic

JF - Archive for Mathematical Logic

SN - 0933-5846

M1 - 1

ER -