Space of countable models of a theory T as a Polish space

Question

Someone told me recently that the space of countable models of a first order theory $T$ form a Polish space. Can some one describe this construction to me?

Answer 1

I'm not sure that this answers your question, but for a countable language $L$, a common thing to do is to look at the space of all countable labeled $L$-structures as a Polish space. For convenience, relationalize $L$ (replacing each function with its graph and each constant by a unary predicate). Then, looking only at structures with underlying set $\mathbb{N}$, a structure is determined by whether $R(\overline{a})$ holds for each $n$-ary relation $R$ and each $n$-tuple $\overline{a}$ from $\mathbb{N}$.

Thus, we can view a labeled structure as a point of $X_L = \prod_{R\in L}2^{\mathbb{N}^{n_R}}$ ($n_R$ is the arity of $R$). This space is just a Cantor space, homeomorphic to $2^\mathbb{N}$, which is Polish.

Now a first-order (or even $L_{\omega_1,\omega}$) formula (with free variables corresponding to the elements of $\mathbb{N}$) defines a Borel set in this space: the atomic formulas are the basic clopen sets, Boolean connectives are Boolean operations, and existential quantification corresponds to a particular countable union: $$[\exists x \phi(x)] = \cup_{n\in\mathbb{N}} [\phi(n)]$$

In particular, we can enforce that relations coming from functions and constants are interpreted as functions and constants using first-order sentences ($\forall x, y\, (R_c(x) \land R_c(y))\rightarrow x = y$ for each constant $c$, and $\forall z_1,\dots,z_k,x,y, (R_f(z_1,\dots,z_k,x)\land R_f(z_1,\dots,z_k,y))\rightarrow x = y$ for each $k$-ary function $f$), so the structures in the relationalized version of $L$ which come from honest $L$-structures form a closed (if you look at the form of the sentences in question, they are intersections of clopen sets) and hence Polish subspace.

There's also a natural action (the "logic action") of $S_\infty$, the permutation group of $\mathbb{N}$, on the space $X_L$, given by permuting the labels on elements. An isomorphism class of $L$-structures is exactly an orbit under the logic action, so you can view the space of $L$-structures up to isomorphism as a quotient of this space by the action of $S_\infty$.

Interesting fact: The subsets of $X_L$ which are invariant under the action of $S_\infty$ are exactly those definable by $L_{\omega_1,\omega}$-sentences. This generalizes Scott's Isomorphism Theorem, which says that each orbit (each isomorphism class of countable structures) is defined by a sentence of $L_{\omega_1,\omega}$.

For a reference to all of the above, see section II.16.C. of Kechris' Classical Descriptive Set Theory.