## 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.

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 language | English |
---|---|

Article number | 1 |

Number of pages | 15 |

Journal | Archive for Mathematical Logic |

DOIs | |

Publication status | Accepted/In press - 2018 |