# zbMATH — the first resource for mathematics

Borel sets, countable models. (English) Zbl 1289.03023
The main theme of this paper is the application of the interpretation method in the construction of a general methodology for the complexity estimation (e.g., Borel, analytic) of certain important sets in countable (and some uncountable) first-order structures. In the first part (the second section of the paper) a specific $$L_{\omega_1}$$-coding of countable first-order structures is applied to provide uniform and novel proofs of some well-known facts such as Kueker’s theorem. The final section is devoted to the sets of all $$(A,\dots)$$-valuations that satisfy a given $$L_{\omega_1,\omega}$$ formula. In the countable case $$A$$ is considered as a discrete topological space, while in the uncountable case $$A$$ is required to be a Polish space and all functions and relations of the model $$(A,\dots)$$ are required to be Borel as well. The authors measure complexity of the sets of valuations (Borel, analytic, projective).
##### MSC:
 03C07 Basic properties of first-order languages and structures 03C15 Model theory of denumerable and separable structures 03C75 Other infinitary logic 03E15 Descriptive set theory
Full Text: