A first-order theory of Ulm type

Issue title: Oberwolfach Workshop on Computability Theory 2018

Guest editors: Vasco Brattka, Rod Downey, Julia F. Knight and Steffen Lempp

Article type: Research Article

Authors: Harrison-Trainor, Matthew^{; *}

Affiliations: Department of Pure Mathematics, University of Waterloo, Canada. [email protected]; http://www.math.uwaterloo.ca/~maharris/

Correspondence: [*] Corresponding author. [email protected].

Abstract: The class of Abelian p-groups are an example of some very interesting phenomena in computable structure theory. We will give an elementary first-order theory Tp whose models are each bi-interpretable with the disjoint union of an Abelian p-group and a pure set (and so that every Abelian p-group is bi-interpretable with a model of Tp) using computable infinitary formulas. This answers a question of Knight by giving an example of an elementary first-order theory of “Ulm type”: Any two models, low for ω1CK, and with the same computable infinitary theory, are isomorphic. It also gives a new example of an elementary first-order theory whose isomorphism problem is Σ11-complete but not Borel complete.

Keywords: p-groups, Borel reducibility, computable structure theory

DOI: 10.3233/COM-180099

Journal: Computability, vol. 8, no. 3-4, pp. 347-358, 2019