Recursive expansions

Tom 145 / 1994

C. Ash, J. Knight Fundamenta Mathematicae 145 (1994), 153-169 DOI: 10.4064/fm-145-2-153-169


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.


  • C. Ash
  • J. Knight

Przeszukaj wydawnictwa IMPAN

Zbyt krótkie zapytanie. Wpisz co najmniej 4 znaki.

Przepisz kod z obrazka

Odśwież obrazek

Odśwież obrazek