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 ∑   β 0relative 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 Γ(Ø)‐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 ∑   α 0relative to X , (ii) The relation is defined in A by a ∑   α Γformula with parameters. Mathematics Subject Classification: 03D45, 03C57, 03C75.