A Completeness Theorem for Certain Classes of Recursive Infinitary Formulas

We consider the following generalization of the notion of a structure recursive relative to a set X. A relational structure A is said to be a Γ(X)-structure if for each relation symbol R, the interpretation of R in A is ∑ relative to X, where β = Γ(R). We show that a certain, fairly obvious, description of classes ∑ of recursive infinitary formulas has the property that if A is a Γ(O)-structure and S is a further relation on A, then the following are equivalent: (i) For every isomorphism F from A to a Γ(X)-structure, F(S) is ∑ relative to X, (ii) The relation is defined in A by a ∑ formula with parameters. Mathematics Subject Classification: 03D45, 03C57, 03C75.