A Completeness Theorem for Certain Classes of Recursive Infinitary Formulas

✍ Scribed by Christopher J. Ash; Julia F. Knight

• Publisher: John Wiley and Sons
• Year: 1994
• Tongue: English
• Weight: 494 KB
• Volume: 40
• Category: Article
• ISSN: 0044-3050
• DOI: 10.1002/malq.19940400204

✦ Synopsis

Abstract

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 Γ(Ø)‐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.