zbMATH — the first resource for mathematics

Strong \(\Delta ^ 0_ 2\) categoricity. (English) Zbl 0596.03043
Algebra Logic 24, 471-476 (1985); and Algebra Logika 24, No. 6, 718-727 (1985).
The notion of strong \(\Delta^ 0_ 2\) stability for recursive structures is first introduced and discussed. A recursive structure \({\mathfrak A}\) is strongly \(\Delta^ 0_ 2\) stable if there is a total \(\Delta^ 0_ 2\) function f on \(A\times {\mathbb{N}}\) such that for every recursive structure \({\mathfrak B}\), every possible isomorphism from \({\mathfrak A}\) to \({\mathfrak B}\) is f(a,n) for some n. This notion lies between that of recursive stability, previously studied by Goncharov and that of \(\Delta^ 0_ 2\)-stability, studied by Ash. The analogous notion of strong \(\Delta^ 0_ 2\)-categoricity is then also defined.
Several useful-looking examples are produced to show that various combinations of properties can occur, while several questions are posed which remain unanswered. The main question asked is whether there is a natural syntactical characterization (under reasonable assumptions) of the strongly \(\Delta^ 0_ 2\)-categorical recursive structures, along the lines of those obtained by the authors respectively for recursive categoricity and \(\Delta^ 0_ 2\)-categoricity.
The corresponding question is also asked for strong \(\Delta^ 0_ 2\)- stability, although the possibility may be thought to be precluded in this case by the result proved here that a 1-recursive structure is strongly \(\Delta^ 0_ 2\)-stable if and only if it is recursively stable. By contrast, an example shows that a 2-recursive structure may be strongly \(\Delta^ 0_ 2\)-categorical but not recursively categorical.
03D45 Theory of numerations, effectively presented structures
03D25 Recursively (computably) enumerable sets and degrees
03C57 Computable structure theory, computable model theory
03D55 Hierarchies of computability and definability
Full Text: DOI EuDML
[1] C. J. Ash, ”Stability of recursive structures in hyperarithmetical degrees,” Preprint, Monash Univ. (1984). · Zbl 0631.03017
[2] C. J. Ash, ”Categoricity in hyperarithmetical degrees,” Preprint, Monash Univ. (1984). · Zbl 0617.03016
[3] S. S. Goncharov, ”On the number of nonautoequivalent constructivizations,” Algebra Logika,16, No. 3, 257–282 (1977). · Zbl 0407.03040
[4] S. S. Goncharov, ”Self-stability and computable families of constructivizations,” Algebra Logika,14, No. 6, 647–680 (1975). · Zbl 0382.03033
[5] S. S. Goncharov, ”Limit equivalent constructivizations,” Tr. Inst. Mat. Sib. Otd. Akad. Nauk SSSR, 2, Nauka, Novosibirsk (1982). · Zbl 0543.03017
[6] S. S. Goncharov, ”The problem of the number of nonautoequivalent constructivizations,” Dokl. Akad. Nauk SSSR,251, No. 2, 271–274 (1980). · Zbl 0476.03045
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. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.