Recursive expansions

• Autorzy: C. J. Ash , J. F. Knight
• Języki publikacji: EN

Abstrakty

EN

Let A be a recursive structure, and let ψ be a recursive infinitary ${Π}_2$ 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.

Kategorie tematyczne

• 03D60: Computability and recursion theory on ordinals, admissible sets, etc.
• 03C57: Effective and recursion-theoretic model theory

• Wydawca: Institute of Mathematics Polish Academy of Sciences
• Czasopismo: Fundamenta Mathematicae
• Rocznik: 1994
• Tom: 145
• Numer: 2
• Strony: 153-169

Daty

wydano

1994

otrzymano

1993-04-15

Twórcy

autor

C. J. Ash

• Department of Mathematics, Monash University, Clayton, Victoria 3168, Australia

autor

J. F. Knight

• Mathematics Department, University of Notre Dame, P.O. Box 398, Notre Dame, Indiana 46556, U.S.A.

Bibliografia

• [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.