Please use this identifier to cite or link to this item:
https://hdl.handle.net/10356/159279
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. https://dx.doi.org/10.1017/jsl.2020.51 | 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. | URI: | https://hdl.handle.net/10356/159279 | ISSN: | 0022-4812 | DOI: | 10.1017/jsl.2020.51 | Schools: | School of Physical and Mathematical Sciences | Rights: | © 2020 The Association for Symbolic Logic. All rights reserved. | Fulltext Permission: | none | Fulltext Availability: | No Fulltext |
Appears in Collections: | SPMS Journal Articles |
SCOPUSTM
Citations
50
4
Updated on Mar 26, 2024
Web of ScienceTM
Citations
50
4
Updated on Oct 26, 2023
Page view(s)
65
Updated on Mar 28, 2024
Google ScholarTM
Check
Altmetric
Items in DR-NTU are protected by copyright, with all rights reserved, unless otherwise indicated.