Let A be a recursive structure, and let ψ be a recursive infinitary sentence involving a new relation symbol. The main result of the paper gives syntactical conditions which are necessary and sufficient for every recursive copy of A to have a recursive expansion to a model of ψ, provided A satisfies certain decidability conditions. The decidability conditions involve a notion of rank. The main result is applied to prove some earlier results of Metakides-Nerode and Goncharov. In these applications, the ranks turn out to be low, but there are examples in which the rank takes arbitrary recursive ordinal values.
@article{bwmeta1.element.bwnjournal-article-fmv145i2p153bwm,
author = {C. Ash and J. Knight},
title = {Recursive expansions},
journal = {Fundamenta Mathematicae},
volume = {144},
year = {1994},
pages = {153-169},
zbl = {0860.03031},
language = {en},
url = {http://dml.mathdoc.fr/item/bwmeta1.element.bwnjournal-article-fmv145i2p153bwm}
}
Ash, C.; Knight, J. Recursive expansions. Fundamenta Mathematicae, Tome 144 (1994) pp. 153-169. http://gdmltest.u-ga.fr/item/bwmeta1.element.bwnjournal-article-fmv145i2p153bwm/
[00000] [AJK] C. J. Ash, C. G. Jockusch and J. F. Knight, Jumps of orderings, Trans. Amer. Math. Soc. 319 (1990), 573-599. | Zbl 0705.03022
[00001] [AK] C. J. Ash and J. F. Knight, Relatively recursive expansions, Fund. Math. 140 (1992), 137-155.
[00002] [AKS] C. J. Ash, J. F. Knight and T. Slaman, Relatively recursive expansions II, ibid. 142 (1993), 147-161. | Zbl 0809.03024
[00003] [G] S. S. Goncharov, Autostability and computable families of constructivizations, Algebra i Logika 14 (1975), 647-680 (in Russian); English transl.: Algebra and Logic 14 (1975), 392-409.
[00004] [MN] G. Metakides and A. Nerode, Effective content of field theory, Ann. of Math. Logic 17 (1979), 289-320. | Zbl 0469.03028
[00005] [V] A. Vlach, Hyperarithmetical relations in expansions of recursive structures, Ph.D. thesis, Univ. of Notre Dame, 1993. | Zbl 0793.03039