Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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.

share|improve this question
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: stanford.edu/~halcrow/Scott's_Isomorphism_Theorem.pdf –  Carl Mummert Jul 31 '11 at 11:33
add comment

1 Answer 1

up vote 5 down vote accepted

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.

share|improve this answer
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.