Punctual categoricity and universality

• Main Authors: Downey, Rod, Greenberg, Noam, Melnikov, Alexander, Ng, Keng Meng, Turetsky, Daniel
• Other Authors: School of Physical and Mathematical Sciences
• Format: Article
• Language: English
• Published: 2022
• Subjects: Science::Mathematics; Primitive Recursion; Computable Structures
• Online Access: https://hdl.handle.net/10356/159279
• Institution: Nanyang Technological University

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.