# 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.

-