Categoricity in hyperarithmetical degrees. (English) Zbl 0617.03016

We obtain, under certain assumptions, necessary and sufficient conditions for a recursive structure to be \(\Delta^ 0_{\alpha}\)-categorical. This is done using the author’s \(\alpha\)-systems to construct suitable \(\Delta^ 0_{\alpha +1}\) functions. We show how these results may be applied, for example, to superatomic Boolean algebras.


03C57 Computable structure theory, computable model theory
03C35 Categoricity and completeness of theories
03D30 Other degrees and reducibilities in computability and recursion theory
Full Text: DOI


[1] Ash, C.J., Stability of recursive structures in arithmetical degrees, Ann. pure appl. logic, 32, 113-135, (1986) · Zbl 0631.03016
[2] Ash, C.J., Recursive labelling systems and stability of recursive structures in hyperarithmetical degrees, Trans. amer. math. soc., (1986), to appear · Zbl 0631.03017
[3] E. Barker, Intrinsically Σ0α relations, submitted. · Zbl 0651.03034
[4] Chang, C.C.; Keisler, H.J., Model theory, (1973), North-Holland Amsterdam · Zbl 0276.02032
[5] Goncharov, S.S., Autostability and countable families of constructivizations, Algebra and logic, 14, 392-409, (1975) · Zbl 0382.03033
[6] Gpncharov, S.S., The quantity of nonautoequivalent constructivizations, Algebra and logic, 16, 169-185, (1977) · Zbl 0407.03040
[7] Keisler, H.J., Model theory for infinitary logic, (1971), North-Holland Amsterdam · Zbl 0222.02064
[8] Rogers, H., Theory of recursive functions and effective computability, (1967), McGraw-Hill New York · Zbl 0183.01401
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.