Hostname: page-component-7b7567c8c-z4zkx Total loading time: 0 Render date: 2026-11-17T17:45:28.850Z Has data issue: false hasContentIssue false

PUNCTUAL CATEGORICITY AND UNIVERSALITY

Published online by Cambridge University Press:  22 October 2020

ROD DOWNEY
Affiliation:
SCHOOL OF MATHEMATICS AND STATISTICS VICTORIA UNIVERSITY OF WELLINGTON WELLINGTON, PO BOX 600, NEW ZEALAND E-mail: rod.downey@vuw.ac.nz E-mail: greenberg@msor.vuw.ac.nz
NOAM GREENBERG
Affiliation:
SCHOOL OF MATHEMATICS AND STATISTICS VICTORIA UNIVERSITY OF WELLINGTON WELLINGTON, PO BOX 600, NEW ZEALAND E-mail: rod.downey@vuw.ac.nz E-mail: greenberg@msor.vuw.ac.nz
ALEXANDER MELNIKOV
Affiliation:
MASSEY UNIVERSITY AUCKLAND PRIVATE BAG 102904, NORTH SHORE AUCKLAND 0745, NEW ZEALAND E-mail: alexander.g.melnikov@gmail.com
KENG MENG NG
Affiliation:
SCHOOL OF PHYSICAL AND MATHEMATICAL SCIENCES DIVISION OF MATHEMATICAL SCIENCES NANYANG TECHNOLOGICAL UNIVERSITY, SINGAPORE E-mail: selwyn.km.ng@gmail.com
DANIEL TURETSKY
Affiliation:
SCHOOL OF MATHEMATICS AND STATISTICS VICTORIA UNIVERSITY OF WELLINGTON WELLINGTON, PO BOX 600, NEW ZEALAND E-mail: dan.turetsky@vuw.ac.nz
Rights & Permissions [Opens in a new window]

Abstract

Core share and HTML view are not available for this content. However, as you have access to this content, a full PDF is available via the 'Save PDF' action button.

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.

Information

Type
Articles
Copyright
© The Association for Symbolic Logic 2020