1
$\begingroup$

Let $\mathcal L$ be an infinite signature and $\mathcal A$, $\mathcal B$ two finite $\mathcal L$-structures such that for each first-order $\mathcal L$-sentence $\varphi$, $$\mathcal A\models\varphi\iff\mathcal B\models\varphi.$$

Does it follow that $\mathcal A$ and $\mathcal B$ are isomorphic?

Clearly, for finite signatures $\mathcal L$ the answer would be "yes".

Improve this question
$\endgroup$
0

1 Answer 1

Reset to default
6
$\begingroup$

Yes. If they are not isomorphic, then for each bijection of $A$ with $B$, there is an atomic formula that the bijection does not respect, that is, a reason that it is not an isomorphism. Since there are only finitely many bijections, we therefore reduce to the case of a finite sublanguage, in which the structures are not isomorphic, contrary to your observation that the conclusion is valid in finite signatures.

Improve this answer
$\endgroup$
7
  • $\begingroup$ What do you mean by an "atomic formula"? I guess you do not mean the acceptation which is explained in en.wikipedia.org/wiki/… since the reason why a bijection from A to B fails to be an isomorphism cannot necessarily be expressed by an atomic formula (where "atomic formula" means what is explained in this article). Also, could you please explain why we can reduce to the case of a finite sublanguage if there are only finitely many bijections? $\endgroup$
    – urpzilmöräqÜ
    Commented May 11, 2016 at 14:24
  • 1
    $\begingroup$ @urpzilmöräqÜ As far as I can see, Joel is using the same meaning of "atomic formula" as the wikipedia article that you linked to. Why do you think these formulas don't suffice as reasons for non-isomorphism? In fact, one could limit further to atomic formulas that are of one of the forms $R(x_1,\dots,x_n)$ for some predicate symbol $R$ and $F(x_1,\dots,x_n)=y$ for some function symbol $F$. $\endgroup$
    – Andreas Blass
    Commented May 11, 2016 at 14:28
  • $\begingroup$ @AndreasBlass: I think that there is not necessarily an atomic formula expressing the reason why a bijection from $A$ to $B$ fails to be an isomorphism, because it is possible that there are some $a\in A$ such that there is no constant symbol $c\in\mathcal L$ with $c^{\mathcal A} = a$. $\endgroup$
    – urpzilmöräqÜ
    Commented May 11, 2016 at 14:48
  • 1
    $\begingroup$ @urpzilmöräqÜ You don’t really need to talk about formulas here. If a bijection fails to be an isomorphism, it is because it fails to preserve some relation or function symbols from the signature, by the definition of isomorphism. So, fix one such symbol for each bijection, and voila, you have a finite sublanguage $L'$ such that the reducts of $\mathcal A$ and $\mathcal B$ to $L'$ are still nonisomorphic. $\endgroup$
    – Emil Jeřábek
    Commented May 11, 2016 at 15:05
  • 1
    $\begingroup$ Now I understand :-D Thank you! Prof. Hamkin's answer and the additional explanations of Prof. Blass and Emil Jeřábek were very helpful! $\endgroup$
    – urpzilmöräqÜ
    Commented May 11, 2016 at 15:35

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .