# Can a single sentence be used to distinguish between isomorphic classes of finite structures?

The answer seems to be yes, judging from the following exercise I found in the book Mathematical Logic by H.D. Ebbinghaus, J. Flum, and W. Thomas:

Let $S$ be a finite symbol set and let $\mathfrak{U}$ be a finite $S$-structure. Show that there is an $S$-sentence $\varphi _{\mathfrak{U}}$ the models of which are precisely the $S$-structures isomorphic to $\mathfrak{U}$.

I think I have an idea of how to solve this exercise, but I seem to be unable to materialize it. Thanks.

-
Note that a very similar thing can be done for countable structures using infinitary logic. The result is called the "Scott sentence". These slides are pretty accessible: stanford.edu/~halcrow/Scott's_Isomorphism_Theorem.pdf – Carl Mummert Jul 31 '11 at 11:33

The point is that you can describe your entire structure within one sentence.

Consider this example: $S=\{<\}$ and $\mathfrak U$ is $\{0,1,2\}$ and $<^\mathfrak U$ is the usual ordering of natural numbers.

We can write: \begin{align}\varphi:= \exists x\exists y\exists z&\Big(x\neq y\land x\neq z\land y\neq z \land\\ &\forall a(a=x\lor a=y\lor a=z)\land\\ & x<y\land x<z\land y<z\land \\&z\nless x\land y\nless x\land z\nless y\land\\&\forall a(a\nless a)\Big)\end{align}

This tells us there are exactly three different elements, and how they are ordered. Every structure in which $\varphi$ is true has three elements and they are ordered as such, we can simply write the isomorphism as $0\mapsto x, 1\mapsto y, 2\mapsto z$.

In the general case, since $S$ has finitely many symbols, and $\mathfrak U$ is finite, we can write an exact description including:

1. "There are $n$ different elements in $U$";
2. "There are no other elements than those $n$;
3. For every function symbol $f$ we can write $f(x)=y$, describing the interpretation of $f$ in $U$;
4. For every relation symbol $R$ we can write exactly which $k$-tuples are in $R$ and which are not.

As in the example, it is very simple to write the isomorphism, and prove it is $S$-isomorphism as wanted.

-
I don't see how it is "very simple" to write an isomorphism. I would really appreciate some more details as I have been struggling with this for several days. – Daniel Jun 13 at 19:29
The reason you don't see this as "very simple" is that you're trying to think in the wrong terms, and I don't know what those terms might be, so I can't quite expand on this. But this is very simple. The key point is that you have finitely many elements, and finitely many symbols, and for each symbol you can write explicitly how it is interpreted. For good measure start by assuming that each element of your structure is an interpretation of a constant symbol; then understand that you can omit this requirement by adding the existential quantifiers as in $\varphi$ in my answer. – Asaf Karagila Jun 13 at 19:37
If every element is an interpretation of a constant symbol, it is indeed trivial, because the interpretation of a constant in one structure has to map to the corresponding interpretation of the same constant in the other, and since the models are elementarily equivalent, every sentence involving those constants must be simultaneously true or false in both models. I still do not see how this generalises, though. – Daniel Jun 13 at 19:47
Given an element of the first structure, how do I know where to map it to? – Daniel Jun 13 at 19:50
You're right. But forget this, for a moment. Take any structure with three elements which are the interpretation of three constant symbols, and say two binary relation symbols, and one unary function symbol. How would you describe the model? You need to first say that every element is one of the constants, and that the constants are different from one another; then you need to describe entirely each relation, what pairs are in and which pairs are out (that's eight statements for each relation), then for the function symbol you need another three statements. Now generalize this idea. – Asaf Karagila Jun 13 at 19:52