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.


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

  • $\begingroup$ Thanks, I made the exact mistake, not affiliating S-structure to that specific S a few excercises ago, leaving myself with hours of confusion. Anyway, a few pages earlier it is stated, that S-structures, which satisfy the same S-sentences are in general not isomorphic. I infer correctly, that that could only be the case when discussing infinite S-structuers. In your answer you use the term "finite language S". What do you mean by that ? If I consider a finite S-structure, the language can still be countable, depending on the underlying syntactic calculus. $\endgroup$ – Quantaurix Feb 28 '19 at 7:00
  • $\begingroup$ @Quantaurix If the language is infinite, the statement isn't true, and this is a good exercise. (HINT - note that a single sentence can only mention finitely many symbols ...) $\endgroup$ – Noah Schweber Feb 28 '19 at 22:58
  • $\begingroup$ Thanks, I got it. As long as there are finitely many elements in $S$ and finitely many elements in the domain of $S$-structure $A$, one can obtain a formula $\varphi$ which contains all information. If the language is infinite, i.e. there are at least countable many elements in the domain of $A$, a finite formula $\varphi$ cannot exist by the reason mentioned in your comment. $\endgroup$ – Quantaurix Mar 4 '19 at 12:24

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.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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