Please use this identifier to cite or link to this item:
Title: Punctual categoricity and universality
Authors: Downey, Rod
Greenberg, Noam
Melnikov, Alexander
Ng, Keng Meng
Turetsky, Daniel
Keywords: Science::Mathematics
Issue Date: 2020
Source: Downey, R., Greenberg, N., Melnikov, A., Ng, K. M. & Turetsky, D. (2020). Punctual categoricity and universality. Journal of Symbolic Logic, 85(4), 1427-1466.
Journal: Journal of Symbolic Logic
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 -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. We also prove that, with a bit of work, the latter result can be pushed beyond, 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.
ISSN: 0022-4812
DOI: 10.1017/jsl.2020.51
Rights: © 2020 The Association for Symbolic Logic. All rights reserved.
Fulltext Permission: none
Fulltext Availability: No Fulltext
Appears in Collections:SPMS Journal Articles

Citations 50

Updated on Nov 26, 2022

Web of ScienceTM
Citations 50

Updated on Nov 27, 2022

Page view(s)

Updated on Dec 1, 2022

Google ScholarTM




Items in DR-NTU are protected by copyright, with all rights reserved, unless otherwise indicated.