×

Recursive labelling systems and stability of recursive structures in hyperarithmetical degrees. (English) Zbl 0631.03017

A recursive structure \({\mathfrak A}\) is said to be \(\Delta^ 0_{\alpha}\)- stable if, for every recursive structure \({\mathfrak B}\simeq {\mathfrak A}\), every isomorphism from \({\mathfrak B}\) to \({\mathfrak A}\) is \(\Delta^ 0_{\alpha}\) in Kleene’s hyperarithmetical hierarchy. The author introduces the notion of formally \(\Delta^ 0_{\alpha}\) enumeration of \({\mathfrak A}\) and shows that, under certain assumptions of recursiveness in \({\mathfrak A}\), the recursive structure \({\mathfrak A}\) is \(\Delta^ 0_{\alpha}\)-stable iff there exists a formally \(\Delta^ 0_{\alpha}\) enumeration of \({\mathfrak A}\). This extends the results of the author on the stability of recursive structures in arithmetic degrees.
Reviewer: O.V.Belegradek

MSC:

03C57 Computable structure theory, computable model theory
03D45 Theory of numerations, effectively presented structures
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] C. J. Ash, Stability of recursive structures in arithmetical degrees, Ann. Pure Appl. Logic 32 (1986), no. 2, 113 – 135. · Zbl 0631.03016
[2] -, Categoricity of recursive structures in hyperarithmetical degrees (in preparation).
[3] E. Barker, Intrinsically \( \Sigma _\alpha ^0\) relations (preprint). · Zbl 0651.03034
[4] Jon Barwise, Admissible sets and structures, Springer-Verlag, Berlin-New York, 1975. An approach to definability theory; Perspectives in Mathematical Logic. · Zbl 0316.02047
[5] S. S. Gončarov, The number of nonautoequivalent constructivizations, Algebra i Logika 16 (1977), no. 3, 257 – 282, 377 (Russian).
[6] Hartley Rogers Jr., Theory of recursive functions and effective computability, McGraw-Hill Book Co., New York-Toronto, Ont.-London, 1967.
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.