ArticleOriginal scientific text

Title

Recursive expansions

Authors 1, 2

Affiliations

  1. Department of Mathematics, Monash University, Clayton, Victoria 3168, Australia
  2. 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 {Π}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.

Bibliography

  1. [AJK] C. J. Ash, C. G. Jockusch and J. F. Knight, Jumps of orderings, Trans. Amer. Math. Soc. 319 (1990), 573-599.
  2. [AK] C. J. Ash and J. F. Knight, Relatively recursive expansions, Fund. Math. 140 (1992), 137-155.
  3. [AKS] C. J. Ash, J. F. Knight and T. Slaman, Relatively recursive expansions II, ibid. 142 (1993), 147-161.
  4. [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.
  5. [MN] G. Metakides and A. Nerode, Effective content of field theory, Ann. of Math. Logic 17 (1979), 289-320.
  6. [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

Pages:
153-169
Main language of publication
English
Received
1993-04-15
Published
1994
Exact and natural sciences