Download PDF - Recursive expansions
ArticleOriginal scientific text
Title
Recursive expansions
Authors 1, 2
Affiliations
- Department of Mathematics, Monash University, Clayton, Victoria 3168, Australia
- Mathematics Department, University of Notre Dame, P.O. Box 398, Notre Dame, Indiana 46556, U.S.A.
Abstract
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.
Bibliography
- [AJK] C. J. Ash, C. G. Jockusch and J. F. Knight, Jumps of orderings, Trans. Amer. Math. Soc. 319 (1990), 573-599.
- [AK] C. J. Ash and J. F. Knight, Relatively recursive expansions, Fund. Math. 140 (1992), 137-155.
- [AKS] C. J. Ash, J. F. Knight and T. Slaman, Relatively recursive expansions II, ibid. 142 (1993), 147-161.
- [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.
- [MN] G. Metakides and A. Nerode, Effective content of field theory, Ann. of Math. Logic 17 (1979), 289-320.
- [V] A. Vlach, Hyperarithmetical relations in expansions of recursive structures, Ph.D. thesis, Univ. of Notre Dame, 1993.
Additional information
http://matwbn.icm.edu.pl/ksiazki/fm/fm145/fm14524.pdf