Elementary Substructures vs. Structures

Question

Here is the definition according to Wikipedia of what an elementary substructure is:

I am just wondering about the last part, where it says it follows that $N$ is a substructure of $M$. Why? Because elementary embedding preserves the truth of all $\sigma$-formulas?

Answer 1

Note that for Wikipedia's definition to make sense, we must have $N\subseteq M$.

Now for every $n$-ary relation symbol $R$ and all elements $a_1,\dots,a_n\in N$, we have $(a_1,\dots,a_n)\in R^N$ iff $N\models R(a_1,\dots,a_n)$ iff $M\models R(a_1,\dots,a_n)$ iff $(a_1,\dots,a_n)\in R^M$.

And for every $n$-ary function symbol $f$ and all elements $a_1,\dots,a_n\in N$, we have $f^N(a_1,\dots,a_n) = b$ iff $N\models f(a_1,\dots,a_n) = b$ iff $M\models f(a_1,\dots,a_n) = b$ iff $f^M(a_1,\dots,a_n) = b$.

So $N$ is a substructure of $M$.

Note that only used that $N$ and $M$ agree on the truth of atomic formulas with parameters in $N$. In fact, the following are equivalent:

• $N$ is a substructure of $M$.
• $N$ and $M$ agree on the truth of atomic formulas with variables interpreted in $N$.
• $N$ and $M$ agree on the truth of quantifier-free formulas with variables interpreted in $N$.

Then $N$ is an elementary substructure of $M$ iff $N$ and $M$ agree on the truth of all formulas with variables interpreted in $N$.