Stability of recursive structures in arithmetical degrees. (English) Zbl 0631.03016

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 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.
Reviewer: A.N.Ryaskin


03C57 Computable structure theory, computable model theory
03D45 Theory of numerations, effectively presented structures


Zbl 0367.02023
Full Text: DOI


[1] Ash, C.J.; Nerode, A., Intrinsically recursive relations, (), 26-41 · Zbl 0467.03041
[2] C.J. Ash, Recursive labelling systems and stability in hyperarithmetical degrees, Trans. A.M.S., to appear. · Zbl 0631.03017
[3] Barker, E., ()
[4] J.N. Crossley, A.B. Manaster and M. Moses, Recursive categoricity and recursive stability, Monash Logic Paper No. 49. · Zbl 0605.03023
[5] Goncharov, S.S., Autostability and computable families of constructivizations, Algebra & logic, 14, 392-409, (1975) · Zbl 0382.03033
[6] Keisler, H.J., Model theory for infinitary logic, (1971), North-Holland Amsterdam · Zbl 0222.02064
[7] Rogers, H., Theory of recursive functions and effective computability, (1967), McGraw-Hill New York · Zbl 0183.01401
[8] Rosenstein, J., Linear orderings, (1982), Academic Press New York · Zbl 0511.03018
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.