Computable categoricity and the Ershov hierarchy (Q958489)

A structure is \(F_{\alpha}\)- (accordingly \(G_{\alpha}\)-) categorical, if it has computable presentations and any two computable presentations are isomorphic via a function which belongs (accordingly, its graph belongs) to the \(\alpha\)-th level of the Ershov hierarchy. It is proved that for every ordinal notation \(\alpha\) there is a graph which is \(F_{\alpha}\)-categorical but not \(G_{\alpha}\)-categorical. A graph \(G\) is constructed which is not \(G_{\alpha}\)-categorical for any ordinal notation \(\alpha\). It is also proved that there is a graph which is \(G_2\)-categorical but not \(F_{\alpha}\)-categorical for any notation \(\alpha\). Examples of \(D_3\)-categorical but not \(G_2\)-categorical graphs are given. Considering linear orderings, the authors prove that a linear order \((L,<)\) is \(F_{\alpha}\)-categorical for some \(\alpha\) if and only if it is countable and has only finitely many successive pairs. (By definition, for \(x,y\in L\), \(\langle x,y\rangle\) is a successive pair if \(x<y\) and there are no elements in \(L\) between \(x\) and \(y\).) It follows from this result and some other known facts that every \(F_{\alpha}\)-categorical linear order is also computable-categorical. At last, an example of a linear order which is \(\Delta^0_2\)-categorical but not \(G_{\alpha}\)-categorical for any \(\alpha\), is given.