PL EN


Preferencje help
Widoczny [Schowaj] Abstrakt
Liczba wyników
1994 | 145 | 2 | 153-169
Tytuł artykułu

Recursive expansions

Treść / Zawartość
Warianty tytułu
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.
Słowa kluczowe
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
JavaScript jest wyłączony w Twojej przeglądarce internetowej. Włącz go, a następnie odśwież stronę, aby móc w pełni z niej korzystać.