×

Computable categoricity and the Ershov hierarchy. (English) Zbl 1165.03012

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.

MSC:

03C57 Computable structure theory, computable model theory
03C35 Categoricity and completeness of theories
03D45 Theory of numerations, effectively presented structures
03D80 Applications of computability and recursion theory
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Ambainis, Andris; Freivalds, Rūsiņš; Smith, Carl H., Inductive inference with procrastination: Back to definitions, Fundamenta Informaticae, 40, 1, 1-16 (1999) · Zbl 0946.68120
[2] Douglas Cenzer, Geoffrey LaForte, Jeffrey Remmel, Equivalence structures and isomorphisms in the difference hierarchy, Manuscript, 2007; Douglas Cenzer, Geoffrey LaForte, Jeffrey Remmel, Equivalence structures and isomorphisms in the difference hierarchy, Manuscript, 2007 · Zbl 1196.03049
[3] Ershov, Yuri L., A certain hierarchy of sets. I, Algebra i Logika, 7, 1, 47-74 (1968) · Zbl 0216.00901
[4] Ershov, Yuri L., A certain hierarchy of sets. II, Algebra i Logika, 7, 4, 15-47 (1968) · Zbl 0216.00902
[5] Ershov, Yuri L., A certain hierarchy of sets. III, Algebra i Logika, 9, 34-51 (1970)
[6] Freivalds, Rūsiņš; Smith, Carl H., On the role of procrastination in machine learning, Information and Computation, 107, 2, 237-271 (1993) · Zbl 0794.68127
[7] Mark Gold, E., Limiting recursion, The Journal of Symbolic Logic, 30, 1, 28-48 (1965) · Zbl 0203.01201
[8] Goncharov, Sergey S.; Dzgoev, Valeriy D., Autostability of models, Algebra i Logika, 19, 1, 45-58 (1980), 132
[9] Goncharov, Sergey S.; Khoussainov, Bakhadyr, Open problems in the theory of constructive algebraic systems, (Computability Theory and its Applications (Boulder, CO, 1999). Computability Theory and its Applications (Boulder, CO, 1999), Contempary Mathematics, vol. 257 (2000), American Mathematical Society: American Mathematical Society Providence, RI), 145-170 · Zbl 0961.03037
[10] Kummer, Martin, A proof of Beigel’s cardinality conjecture, The Journal of Symbolic Logic, 57, 2, 677-681 (1992) · Zbl 0763.03025
[11] McCoy, Charles, \( \Delta_2^0\)-categoricity in Boolean algebras and linear ordering, Annals of Pure and Applied Logic, 119, 85-120 (2003) · Zbl 1016.03036
[12] McLaughlin, Thomas G., Supersimple sets and the problem of extending a retracing function, Pacific Journal of Mathematics, 41, 2, 485-494 (1972) · Zbl 0255.02043
[13] Putnam, Hillary, Trial and error predicates and the solution to a problem of Mostowski, The Journal of Symbolic Logic, 30, 1, 49-57 (1965) · Zbl 0193.30102
[14] Remmel, Jeff, Recursive categorical linear orderings, Proceedings of the American Mathematical Society, 83, 383-391 (1981) · Zbl 0493.03022
[15] Rogers, Hartley, Theory of Recursive Functions and Effective Computability (1967), McGraw-Hill: McGraw-Hill New York · Zbl 0183.01401
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.