Computable categoricity versus relative computable categoricity. (English) Zbl 1320.03070

Downey, Rodney G.; Kach, Asher M.; Lempp, Steffen; Turetsky, Daniel D.

Fundam. Math. 221, No. 2, 129-159 (2013).

The main result of this paper is that a computable structure which is 1-decidable and computably categorical is relatively \(\Delta^0_2\) categorical. A structure is identified with its atomic diagram for the purpose of measuring its complexity. A computable structure \(\mathcal A\) is computably categorical if it is computably isomorphic to all of its computable copies; and relatively computably categorical if for any copy \(\mathcal B\) of \(\mathcal A\) there is a \(\mathcal B\)-computable isomorphism between \(\mathcal A\) and \(\mathcal B\). By a classical result of S. S. Goncharov’s [Algebra Logika 14, 647–680 (1975; Zbl 0367.02023)], relative computable categoricity has a simple syntactic characterisation: the orbits are definable by a c.e. collection of existential formulas (after adding finitely many parameters). This shows that relative computable categoricity can only result from the application of Cantor’s back and forth method. Goncharov showed that not every computably categorical structure is relatively computably categorical. That is, there are some exotic structures which happen to be computably categorical, but not for a good reason such as the success of the back and forth method. Thus computable categoricity is not a well-behaved notion. Goncharov [loc. cit.] showed though that if the 2-quantifier diagram of the structure is computable, then relative computable categoricity and computable categoricity coincide.
The main result of the paper extends Goncharov’s result by showing that if the decidability requirement is relaxed by only looking that the 1-quantifier diagram, then Goncharov’s result can be obtained if one allows queries to the relative halting problem: for every copy \(\mathcal B\) of \(\mathcal A\) there is an isomorphism between them which is computable from the Turing jump of \(\mathcal B\).
This result is related to the complexity of index-sets. Because of its simple syntactic characterisation, the index-set of the relatively computably categorical structures is \(\Sigma^0_3\). The main result of the paper implies that the index-set of 1-decidable computably categorical structures is also simple.
A natural question to ask is whether the extra step can be taken to weaken the assumption to 0-decidability; that is, whether every computably categorical structure is relatively \(\Delta^0_3\)-categorical. The surprising answer is no, as is showed in the follow-up paper [R. G. Downey et al., Adv. Math. 268, 423–466 (2015; Zbl 1345.03063)], where it is shown that no level of the hyperarithmetic hierarchy is sufficient, and indeed that the index-set of the computably categorical structures is as complicated as possible (\(\Pi^1_1\)). The current paper develops the technique of “pushing on isomorphisms” which is used in the follow-up paper. Here, the technique is used to show, for example, that there is a 1-decidable, computably categorical structure \(\mathcal A\) and a \(\Delta^0_2\) copy \(\mathcal B\) of \(\mathcal A\) which is not \(\Delta^0_2\)-isomorphic to \(\mathcal A\).

Reviewer: Noam Greenberg (Wellington)

MSC:

03C57	Computable structure theory, computable model theory
03C35	Categoricity and completeness of theories
03D45	Theory of numerations, effectively presented structures

Keywords:

computable categoricity; relative computable categoricity