Elementary theories and hereditary undecidability for semilattices of numberings

Archive for Mathematical Logic 58 (3-4):485-500 (2019)

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 \, we consider the upper semilattice \ of all \-computable numberings of all \-computable families of subsets of \. 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 \-computable numberings, where \ is a computable successor ordinal. Furthermore, it is shown that for any of the theories T mentioned above, the \-fragment of T is hereditarily undecidable. Similar results are obtained for the structure of all computably enumerable equivalence relations on \, equipped with composition.
Keywords No keywords specified (fix it)
Categories No categories specified
(categorize this paper)
ISBN(s)
DOI 10.1007/s00153-018-0647-y
Options
Edit this record
Mark as duplicate
Export citation
Find it on Scholar
Request removal from index
Revision history

Download options

Our Archive


Upload a copy of this paper     Check publisher's policy     Papers currently archived: 46,425
External links

Setup an account with your affiliations in order to access resources via your University's proxy server
Configure custom proxy (use this if your affiliation does not provide a proxy)
Through your library

References found in this work BETA

Creative Sets.John Myhill - 1955 - Zeitschrift fur mathematische Logik und Grundlagen der Mathematik 1 (2):97-108.
Creative Sets.John Myhill - 1955 - Mathematical Logic Quarterly 1 (2):97-108.

View all 6 references / Add more references

Citations of this work BETA

No citations found.

Add more citations

Similar books and articles

Strong Reducibility of Partial Numberings.Dieter Spreen - 2004 - Archive for Mathematical Logic 44 (2):209-217.
A Note on Partial Numberings.Serikzhan Badaev & Dieter Spreen - 2005 - Mathematical Logic Quarterly 51 (2):129-136.
Effectively Closed Sets and Enumerations.Paul Brodhead & Douglas Cenzer - 2008 - Archive for Mathematical Logic 46 (7-8):565-582.
Difference Sets and Computability Theory.Rod Downey, Zoltán Füredi, Carl G. Jockusch & Lee A. Rubel - 1998 - Annals of Pure and Applied Logic 93 (1-3):63-72.
A Real Number Structure That is Effectively Categorical.Peter Hertling - 1999 - Mathematical Logic Quarterly 45 (2):147-182.
Some Applications of Computable One-One Numberings.Martin Kummer - 1990 - Archive for Mathematical Logic 30 (4):219-230.

Analytics

Added to PP index
2018-09-26

Total views
9 ( #824,283 of 2,286,306 )

Recent downloads (6 months)
2 ( #576,788 of 2,286,306 )

How can I increase my downloads?

Downloads

My notes

Sign in to use this feature