Borel sets, countable models. (English) Zbl 1289.03023

Mijajlović, Žarko; Doder, Dragan; Ilić-Stepić, Angelina

Publ. Inst. Math., Nouv. Sér. 90(104), 1-11 (2011).

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

Reviewer: Aleksandar Perović (Beograd)

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