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).
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: DOI