Czasopismo
Tytuł artykułu
Autorzy
Warianty tytułu
Języki publikacji
Abstrakty
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.
Słowa kluczowe
Kategorie tematyczne
Czasopismo
Rocznik
Tom
Numer
Strony
153-169
Opis fizyczny
Daty
wydano
1994
otrzymano
1993-04-15
Twórcy
autor
- Department of Mathematics, Monash University, Clayton, Victoria 3168, Australia
autor
- 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.
Typ dokumentu
Bibliografia
Identyfikatory
Identyfikator YADDA
bwmeta1.element.bwnjournal-article-fmv145i2p153bwm