BOREL SETS AND COUNTABLE MODELS


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




We show that certain families of sets and functions related to a countable structure $\Bbb{A}$ are analytic subsets of a Polish space. Examples include sets of automorphisms, endomorphisms and congruences of $\Bbb{A}$ and sets of the combinatorial nature such as coloring of countable plain graphs and domino tiling of the plane. This implies, without any additional set-theoretical assumptions, i.e., in ZFC alone, that cardinality of every such uncountable set is $2^{\aleph_0}$.