I'm stuck on this model theory problem. It seems like a fundamental result.
Let $L$ and $L'$ be languages with $L' \subseteq L$. Given an $L$-structure $M$, let $M|L'$ be the $L'$-structure obtained from $M$ by forgetting the interpretations of all symbols in $L \setminus L'$.
Suppose that $M$ and $N$ are $L$-structures, and that $M$ is finite. Prove that $M \cong N$ if and only if for every finite $L' \subseteq L$ we have $M|L' \cong N|L'$.
I have figured out the forward direction (assuming that $M \cong N$) but I'm lost going the other way. Any hints would be appreciated.
Also what if M and N are infinite? The result seems false but I can't find a counter example.
Let's prove the contrapositive. Suppose $M\not\cong N$. We want to find a finite $L'\subseteq L$ such that $M|L'\not\cong N|L'$.
If $|M|\neq |N|$, then the empty language works. So assume $|M| = |N| = n$. There are finitely many $(n!)$ bijections $M\to N$. For each bijection $f\colon M\to N$, the fact that $f$ is not an $L$-isomorphism is witnessed by the fact that it fails to respect some symbol in the language. Choose one witnessing symbol for each bijection, and let $L'$ be the resulting sublanguage of $L$.
Here's a counterexample in the infinite case. Let $L = \{c_n\mid n\in \mathbb{N}\}$, where the $c_n$ are all constant symbols. Let $M = \mathbb{N}$, with each constant symbol $c_n$ interpreted as the natural number $n$. Let $N = \mathbb{N}\cup \{\infty\}$, with each constant symbol $c_n$ interpreted as the natural number $n$. Then $M\not\cong N$, since every element of $M$ is named by a constant symbol, but $N$ has an element $\infty$ not named by a constant symbol.
But for any finite sublanguage $L'\subseteq L$, $M'|L'\cong N'|L'$. Indeed, both structures consist of finitely many distinct elements named by the constant symbols in $L'$, together with countably many other unnamed elements.