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

5

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 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.2016-06-13
  • 0
    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.2016-06-13
  • 0
    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.2016-06-13
  • 0
    Given an element of the first structure, how do I know where to map it to?2016-06-13
  • 0
    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.2016-06-13
  • 0
    I think I have it: let the structures be $A = {x_1,...,x_n}$ and $B$. Let $\phi(x_1,...,x_n)$ be a complete formula representing the type of $(x_1,...,x_n)$. Since $A$ and $B$ are elementarily equivalent, there must be an n-tuple $(y_1,...,y_n)$ in B (i.e. some permutation of the elements of B), which satisfies $\phi$, and consequently has the same type as $(x_1,...,x_n)$. Then, clearly $f(x_i) = y_i$ defines an isomorphism between $A$ and $B$.2016-06-13
  • 0
    Note that the types will be isolated even if the language is infinite, so this is no real restriction.2016-06-13
  • 0
    This would have been infinitely easier if you had said that you are familiar with the notion of types.2016-06-13
  • 0
    I am sorry I didn't mention that, I cannot possibly mention all the things I am familiar with in a comment. I now see that it is indeed very simple to construct the isomorphism, as you say, but for some reason I couldn't see that earlier. I kept focusing on 1-types when I really should be looking at n-types.2016-06-13
  • 0
    Yes, I know that you can't. Which is why I am not angry or upset in any way. This might have been the situation if you were asking a separate question, where you have more space to write about your difficulties. I was just saying that if you are familiar with types then this becomes an extremely simple question. Simply write that there are $n$ distinct elements, and then go ahead and describe the type of every one of them, and every tuple of them for whichever tuples it is relevant (the language is finite, so the process is finite).2016-06-13
  • 0
    Hum… Aren't the types of any tuple already included in the type of the tuple formed by all the elements in the structure? Also, I know that this result is also true for infinite languages. Doesn't this same argument carry over to the infinite case as well?2016-06-13
  • 0
    Yes, you're right. As for infinite languages, yes, but then you need to appeal to compactness. Because you can't write a single sentence, and you essentially need to argue that you can fully describe what and how each element is doing in a "more or less unique way" by counting indiscernible elements and positing that there are this and that many of each equivalence class. But this is not a single sentence anymore.2016-06-13
  • 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