Premium
A Completeness Theorem for Certain Classes of Recursive Infinitary Formulas
Author(s) -
Ash Christopher J.,
Knight Julia F.
Publication year - 1994
Publication title -
mathematical logic quarterly
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 0.473
H-Index - 28
eISSN - 1521-3870
pISSN - 0942-5616
DOI - 10.1002/malq.19940400204
Subject(s) - mathematics , completeness (order theory) , isomorphism (crystallography) , generalization , mathematics subject classification , discrete mathematics , relation (database) , property (philosophy) , structured program theorem , pure mathematics , combinatorics , mathematical analysis , chemistry , epistemology , database , computer science , crystal structure , crystallography , philosophy
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.