Punctual Categoricity and Universality

Journal of Symbolic Logic 85 (4):1427-1466 (2020)
  Copy   BIBTEX

Abstract

We describe punctual categoricity in several natural classes, including binary relational structures and mono-unary functional structures. We prove that every punctually categorical structure in a finite unary language is${\text {PA}}(0')$-categorical, and we show that this upper bound is tight. We also construct an example of a punctually categorical structure whose degree of categoricity is$0''$. We also prove that, with a bit of work, the latter result can be pushed beyond$\Delta ^1_1$, thus showing that punctually categorical structures can possess arbitrarily complex automorphism orbits.As a consequence, it follows that binary relational structures and unary structures are not universal with respect to primitive recursive interpretations; equivalently, in these classes every rich enough interpretation technique must necessarily involve unbounded existential quantification or infinite disjunction. In contrast, it is well-known that both classes are universal for Turing computability.

Links

PhilArchive



    Upload a copy of this work     Papers currently archived: 94,623

External links

Setup an account with your affiliations in order to access resources via your University's proxy server

Through your library

Similar books and articles

Punctual definability on structures.Iskander Kalimullin, Alexander Melnikov & Antonio Montalban - 2021 - Annals of Pure and Applied Logic 172 (8):102987.
On the complexity of categoricity in computable structures.Walker M. White - 2003 - Mathematical Logic Quarterly 49 (6):603.
Degrees That Are Not Degrees of Categoricity.Bernard Anderson & Barbara Csima - 2016 - Notre Dame Journal of Formal Logic 57 (3):389-398.
Categoricity Spectra for Rigid Structures.Ekaterina Fokina, Andrey Frolov & Iskander Kalimullin - 2016 - Notre Dame Journal of Formal Logic 57 (1):45-57.

Analytics

Added to PP
2020-10-22

Downloads
19 (#811,075)

6 months
10 (#397,791)

Historical graph of downloads
How can I increase my downloads?

Author's Profile

Citations of this work

Punctual definability on structures.Iskander Kalimullin, Alexander Melnikov & Antonio Montalban - 2021 - Annals of Pure and Applied Logic 172 (8):102987.

Add more citations

References found in this work

Polynomial-time abelian groups.Douglas Cenzer & Jeffrey Remmel - 1992 - Annals of Pure and Applied Logic 56 (1-3):313-363.
Space complexity of Abelian groups.Douglas Cenzer, Rodney G. Downey, Jeffrey B. Remmel & Zia Uddin - 2009 - Archive for Mathematical Logic 48 (1):115-140.

Add more references