4
$\begingroup$

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.

  • 3
    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: http://www.stanford.edu/~halcrow/Scott's_Isomorphism_Theorem.pdf2011-07-31

1 Answers 1

6

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

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.

  • 0
    I don't quite understand what you mean by "counting indiscernible elements", or how exactly I should appeal to compactness, but I suspect it is something similar to what I had in mind previously but could not carry out fully. Given finite elementary equivalent structures $A$ and $B$, I can partition $A$ as the union of $A_1,...,A_n$, then $B$ will also be partitioned into $B_1,...,B_n$, where for each $i$ $A_i$ and $B_i$ have the same cardinality. It is still not clear, however, that mappings those parts to corresponding parts will give me an isomorphism.2016-06-14