All Finite S-structures satisfying "characterizing" S-sentence are isomorphic

390 Views Asked by At

Excercise 5.9, p.44 Ebbinghaus et al - Mathematical logic:

This excercise was discussed here: Can a single sentence be used to distinguish between isomorphic classes of finite structures?

Roughly speaking, we can find a sentence phi which incorporates all rules given by structure A (existence and uniqueness of all elements of the underlying domain, by A defined functions, by A defined constants, by A defined relations), so that A and an isomorphic structures B satisfies phi.

It is asserted that the converse is true, either, i.e. the structures satisfying phi are precisely those isomorphic to A. But what if I take A and extend A by another function/constant/relation and thereby obtain a structure B.

The sentence phi is still satisfied by B but A and B are not isomorphic. I guess I am missing/forgetting some detail of a definition or so.

2

There are 2 best solutions below

0
On

When we say a sentence $\phi$ axiomatises a class of structures, we always have a particular signature in mind. It doesn't make sense to ask whether structures with different signatures are isomorphic, e.g., a ring can't be isomorphic to a group, because the ring has operations that the group doesn't have. A sentence like $\forall x \forall y. xy = yx$ does indeed characterize both commutative groups and commutative rings, but we don't use it to compare a group with a ring.

3
On

Your title contains the key point:

All Finite S-structures satisfying “characterizing” S-sentence are isomorphic

(emphasis mine).

The answer to your question

what if I take A and extend A by another function/constant/relation and thereby obtain a structure B

is, such a $B$ is not an $S$-structure, and so the result quoted doesn't apply.


A version of the quoted result which holds for all language would be:

For every finite language $S$ and every finite $S$-structure $A$, there is an $S$-sentence $\varphi$ such that every structure $B$ which satisfies $\varphi$ has $B\upharpoonright S\cong A$ - that is, the reduct of $B$ to the original language $S$ is isomorphic to $A$ (even if $B$ itself isn't, by virtue of being a structure in a too-big language).