In this paper, we consider the following basic question. Let A be an L-structure and let ψ be an infinitary sentence in the language L∪R, where R is a new relation symbol. When is it the case that for every B ≅ A, there is a relation R such that (B,R) ⊨ ψ and ? We succeed in giving necessary and sufficient conditions in the case where ψ is a “recursive” infinitary sentence. (A recursive infinitary formula is an infinitary formula with recursive disjunctions and conjunctions.) We consider also...
Let A be a recursive structure, and let ψ be a recursive infinitary 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,...
In [AK], we asked when a recursive structure A and a sentence φ, with a new relation symbol, have the following property: for each ℬ≅ A there is a relation S such that S is recursive relative to ℬ and ℬ,S)⊨ φ. Here we consider several related properties, in which there is a uniform procedure for determining S from ℬ ≅A, or from ℬ,¯b)≅(A,ā), for some fixed sequence of parameters ā from A; or in which ℬ and S are required to be recursive. We investigate relationships between these properties, showing...
Download Results (CSV)