Let $M$ and $N$ be $L$-Structures, $h\colon M \cong N$ an isomorphism. Show $h$ is an elementary map.

Question

Let $M$ and $N$ be $L$-Structures, $h\colon M \cong N$ an isomorphism. Show $h$ is an elementary map.

I'm not even sure where to begin at the moment. I was informed of "induction on the complexity" but not entirely sure what that means and how to go about proving it using this method.

Thanks in advance for any help!

Answer 1

Induction on the complexity of a formula means that you check that the statement is true for atomic formulas; then you show that if it holds for $\psi$ and $\varphi$ then it holds for their conjunction, implication, negation, etc.; and you check to see that it holds under adding a quantifier.

Of course, it suffices to check for $\lnot,\land,\exists$ or $\lnot,\lor,\forall$, or some other mix from which we can define the rest of the connectives and quantifiers.

And the actual proof is really just an exercise in verifying the definitions: The atomic case follows from the fact that $h$ is an isomorphism; the rest is an exercise in verifying the definition of truth of a statement in a structure.