Let $M$, $N$ be two countable structures in an uncountable language $L$. Suppose that for any countable sub-language $L'$ of $L$, $M$ and $N$ are isomorphic $L'$-structures. Then, can $M$ and $N$ be non-isomorphic $L$-structures?

I found this problem when I thought about Does any uncountable complete theory have exactly two countable models?. Understanding restrictions to countable languages might help to understand uncountable languages.

Any help would be appreciated. Thank you.


If $M$ and $N$ are isomorphic in every countable sublanguage of $L$, then they are isomorphic in $L$.

For each natural number $k$, and for each choice of $\langle a_1,\dots,a_k\rangle\in M^k$ and $\langle b_1,\dots,b_k\rangle\in N^k$, choose a $k$-ary relation symbol $P$ (if any exist) such that $P(a_1,\dots,a_k)$ in $M$ and $P(b_1,\dots,b_k)$ in $N$ have opposite truth values. Let $L'$ be the countable sublanguage consisting of the relation symbols so chosen. If $f:M\to N$ is an $L'$-isomorphism, then it is also an $L$-isomorphism.

  • 3
    $\begingroup$ it could perhaps be of use to say "$k$-ary atomic formula" instead of "relation symbol" : this doesn't change the argument and helps to deal with the case where $L$ has some function symbols (without having to argue that you can change the language to contain no function symbols, which of course is possible) $\endgroup$ – Max Jul 10 at 13:40

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.