Stability of recursive structures in arithmetical degrees (Q1094410): Difference between revisions

A recursive structure \({\mathfrak A}\) is \(\Delta^ 0_ n\)-stable if every isomorphism of \({\mathfrak A}\) with every other recursive structure is \(\Delta^ 0_ n\) in Kleene's arithmetical hierarchy. The notion of a formally \(\Delta^ 0_ n\)-enumeration of a recursive structure \({\mathfrak A}\) is defined in the paper. It is easy to prove that if a recursive structure \({\mathfrak A}\) has a formally \(\Delta^ 0_ n\)-enumeration, then it is \(\Delta^ 0_ n\)-stable. The converse of this result is proved under the assumption that the existential diagram of \({\mathfrak A}\) and the relations, pointed out in the paper, are recursive. For \(\Delta^ 0_ 1\)-stability the proof uses a finite injury priority argument and it was given by \textit{S. S. Goncharov} [Algebra Logika 14, 647-680 (1975; Zbl 0367.02023)]. For \(\Delta^ 0_ 2\)-stability the proof uses an infinite injury argument and for \(\Delta^ 0_ 3\)-stability a `monstrous' injury argument. The author shows how this process can be continued for all n.