Describing type spaces

Question

I have been getting stuck on this type of question:

"Let $T$ be this and that theory. Give a concrete description of $S_n(T)$ for each $n$."

I don't see how to start with this kind of problem. Especially since in the notes that I'm using, these kind of questions are asked even before introducing isolated types or quantifier elimination.

For example, describing all types of the Random Graph theory $RG$. I now know that $RG$ is complete, $\omega$-categorical, and has infinite models, so all $n$-types are isolated, which means that each $S_n(T)$ is finite, which means that there is a finite set of formulas with $n$ variables that determine the equivalence classes of formulas relative to the theory $RG$. But I still have problems with concretely describing them. And since the question was asked before any of this was explained, I shouldn't need any of this to describe the types.

My question is thus: How do I start with finding concrete examples of type spaces?

Any general advice is welcome, it doesn't have to be about $RG$ specifically.

Answer 1

This is an inherently open-ended question, of course, and what kind of "concrete description" is suitable depends on the particular theory $T$ you're looking at. The main problem with understanding type spaces is that complete types are infinite sets of first-order formulas of arbitrary complexity, which can be difficult to understand. Usually, a "concrete description" of a type $p(x)$ will amount to an "axiomatization", i.e. giving an explicit set of formulas $\Phi = \{\varphi_i(x)\mid i\in I\}$ such that $p(x)$ is the only type containing $\Phi$. Ideally, the set $\Phi$ will also have some intuitive meaning that you can describe in some way other than just listing the formulas.

Here are two general strategies for doing this:

• Prove that $T$ has quantifier elmination. Then every type is determined by the quantifier-free formulas contained in it. This has the added advantage that for any tuple $a$, the quantifier-free type $\text{qftp}(a)$ contains exactly the information about the isomorphism type over $a$ of the substructure generated by $a$, which gives a reasonable concrete description of the type space. More generally, if $T$ doesn't have QE, you can still hope to prove that every formulas is equivalent modulo $T$ to a Boolean combination of formulas of a certain simple form. This kind of argument also gives a nice description of the topology on the type space, since the sets picked out by the generating formulas and their complements will be a sub-basis for the topology.

• If $T$ is totally transcendental ($\omega$-stable), or more generally small (meaning that $S_n(T)$ is countable for all $n$), carry out the Cantor-Bendixson analysis explicitly. That is, find isolating formulas for the isolated types. Then find isolating formulas for the types which are isolated among the non-isolated types. And repeat until you've described all of the types.

Your specific question about the random graph is the best of both worlds: $T$ has QE, $S_n(T)$ is finite, and every type is isolated. Let $p(x_1,\dots,x_n)$ be a type in $S_n(T)$. Then $p$ is isolated by the conjunction of all atomic and negated atomic formulas in $p$. The instances of $=$ and $\neq$ describe a partition of the variables into equivalence classes. The instances of the edge relation and its complement describe a graph on these equivalence classes. So $p(x_1,\dots,x_n)$ is determined by a graph $G$ of size at most $n$, together with a labeling of the vertices of $G$ by the variables $x_1,\dots,x_n$ such that every vertex gets at least one label (but possibly more).

So the space $S_n(T)$ can be described as the set of all such graph/labeling pairs, equipped with the discrete topology.