Strong \(\Delta ^ 0_ 2\) categoricity (Q1078172)

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.