Intuition behind Scott sentences

logicmodel-theory

A countable structure $\mathcal{A}$ for a countable language $\mathcal{L}$ can be described up to isomorphism by a Scott sentence $\varphi$, an infinitary sentence of $\mathcal{L}_{\omega_1\omega}$ (with countable conjunctions, disjunctions and finite number of quantifiers) in the sense that $\mathcal{A}$ is the unique countable model of $\varphi$.

On page 6 of this slide by Julia Knight, it says that to obtain a Scott sentence, Scott first found formulas $\varphi_{\bar{a}}(\bar{x})$ that define the orbits of the tuples $\bar{a}$ in $\mathcal{A}$. He then took the conjunction of the following:

$\rho_{\varnothing}=(\forall x)\bigvee_b \varphi_b(x)\land \bigwedge_b (\exists x)\varphi_b(x)$

$\rho_{\bar{a}}=(\forall \bar{u})[\varphi_{\bar{a}}(\bar{u})\to ((\forall x)\bigvee_b \varphi_{\bar{a},b}(\bar{u},x)\land \bigwedge_b (\exists x)\varphi_{\bar{a},b}(\bar{u},x))]$

I'd like to know more on the intuition behind above formulas, and how $\varphi_{\bar{a}}(\bar{x})$ define the orbits of the tuples $\bar{a}$ in $\mathcal{A}$.

Best Answer

The intuition behind Scott sentences is that they give recipes for back-and-forth arguments. An excellent exposition is given in Marker's book Model Theory: An Introduction, Section 2.4. The section starts with Cantor's back-and-forth proof that any two countable dense linear orders without endpoints are isomorphic, introduces Ehrenfeucht–Fraïssé games, and builds up to Scott's isomorphism theorem.

Your recent questions indicate that you're interested in the concept of $\omega$-homogeneity, which is also closely related to the back-and-forth idea. I think you'll learn a lot more from reading Marker's Section 2.4 thoroughly than anything I could write in this answer. But I'll try to give the basic idea.

In Knight's presentation, we start with "complete" formulas $\varphi_{\overline{a}}(\overline{x})$, which you should think of as completely describing the behavior of the tuple $\overline{a}$. More on how to get these formulas below. But first, let's imagine we have structures $M$ and $N$ which satisfy all the same sentences $\rho_{\overline{a}}$. We want to show $M\cong N$ by a back-and-forth argument.

Ok, we want to build up an isomorphism between the two element-by-element. Pick some $a_1\in M$. $\rho_\varnothing$ gives a list of complete formulas in one variable and says "every element satisfies one of the formulas in this list, and every formula in the list is satisfied by some element". So $a_1$ satisfies some complete formula $\varphi_1(x)$ on the list, and that same complete formula is satisfied by some element $b_1\in N$. We start our isomorphism by mapping $a_1\mapsto b_1$.

Next, we pick an element $b_2\in N$. The sentence $\rho_{b_1}$ gives a list of complete formulas in two variables which extend $\varphi_1(x)$ and says "if $x$ satisfies $\varphi_1(x)$, then every pair $xy$ extending $x$ satisfies one of the formulas in this list, and every formula in the list is sastified by some pair extending $x$." So $b_1,b_2$ satisfies some complete formula $\varphi_2(x,y)$ on the list, and there is some $a_2\in M$ such that $a_1,a_2$ satisfies that same complete formula. We extend our isomorphism by mapping $a_2\mapsto b_2$.

Continuing this way (back and forth) to handle all of the elements in some enumerations of the countable structures $M$ and $N$, we arrive at an isomorphism.

Now the question remains how to come up with the "complete" formulas $\varphi_{\overline{a}}$, for $\overline{a}$ in $M$. As a first approximation, we can take the conjunction of all atomic and negated atomic formulas satisfied by $\overline{a}$. This captures the quantifier-free type of $\overline{a}$. But knowing the quantifier-free type of $\overline{a}$ does not tell us the possible quantifier-free types of extensions $\overline{a}b$ of the tuple. So we consider formulas of the form $$(\forall y\, \bigvee \psi_i(x,y)) \land (\bigwedge \exists y\, \psi_i(x,y))$$ where the $\psi_i$ are complete quantifier-free formulas. Let's call these formulas $1$-extension formulas. Now we can take the conjunction of all $1$-extension formulas satisfied by a tuple. That tells us about all of the complete quantifier-free types of extensions of the tuple, but not yet about all of the complete $1$-extension types of extensions of the tuple!

In other words, $1$-extension formulas let us start with a partial isomorphism between finite tuples and extend by one more element - but no more! That's not enough to build a total isomorphism by back-and-forth.

So this leads us to define $2$-extension formulas, which look just like $1$-extension formulas, but now the $\psi_i$ are conjunctions of $1$-extension formulas. Satisfying the same $2$-extension formulas means that we can extend a back-and-forth argument by two steps, but no more. Continuing, we can define $n$-extension formulas for all finite $n$. Satisfying the same $n$-extension formulas for all finite $n$ ensures we can continue a back-and-forth argument any finite number of steps, but not necessarily countably many steps.

Scott's idea was to iterate this construction through the countable, defining $\alpha$-extension formulas for all countable ordinals $\alpha$. Now if we assume that $M$ is a countable structure, it has only countably many tuples, so it won't take all $\aleph_1$-many countable ordinals to distinguish all the tuples in $M$. In other words, there is some countable ordinal $\alpha$ (the Scott rank of $M$) such that when trying to understand the behavior of tuples from $M$, it suffices to consider all the $\alpha$-extension formulas satisfied by the tuple. The countable conjunction of all of these are the "complete formulas" referred to in the explanation of the Scott sentence above, and they allow back-and-forth arguments to go "all the way up".

Related Question