Suppose $M\models D(N)$. Show that $M$ has a substructure which is isomorphic to $N$

Question

Let $N$ be an $L$-structure. The diagram of $N$, denoted $D(N)$, is the set of all quantifier-free $L_N$-sentences which are true in $N$.

1. Suppose $M$ is a model of $D(N)$. Show that $M$ has a substructure which is isomorphic to $N$.

2. Conversely, suppose that $M$ is an $L$-structure such that $N$ is isomorphic to a submodel of $M$. Show that $M$ can be made into an $L_N$-structure which is a model of $D(N)$.

My attempt:

1. Let $\beta: N\to M: n\mapsto c_n^M$ (the interpretation in $M$ of the constant associated to $n$). This is an injective function, because $\neg(c_n = c_{n'})\in D(N)$ for $n\ne n'$. Now, it remains to show that $N':= \beta(N)$ is a substructure of $M$.

Definition substructure: Let $M$ and $N$ be structures for a language $L$. We say that $N$ is a substructure of $M$ if $N$ is a subset of $M$, and the following conditions are satisfied:

• For every constant $c$ of $L$, $c^N=c^M$.
• For every $n$-place function symbol $f$ of $L$, $f^N:N^n\to N$ is the restriction of $f^M$ to $N^n$.
• For every $n$-place relation symbol $R$ of $L$, $R^N=R^M\cap N^n$.

I'm not sure how to proceed from here on.

2. Let $\beta: N\to N' \le M$ be an isomorphism of $L$-structures. To make an $L_N$-structure, we add $\{c_n\mid n\in N\}$ to $L$. The structures $N$ and $N'$ must satisfy the same $L$-sentences.

For the newly added constants, I need to add $c_n^M$ to $M$. Now $c_n^M = c_n^{N'}$ (submodel), and $c_n^{N'} = \beta(c_n^N)$. So, I need to add these elements to $M$. I don't think that extra functions and relations need to be defined on $M$.

Is this it? I'm mostly looking for some help with question 1., which may possibly contain an interesting idea for 2.

Thanks.

Answer 1

A hint for question 1 :

For relations, say, do you see why $N \models R(n_1,...,n_k)$ iff $M \models R(\beta(n_1),...,\beta(n_k))$, if $R$ is a relation symbol, and $n_1,...,n_k$ are elements of $N$ ?

Another hint for question 1 :

Assume we know that $\beta(N)$ is an $L_N$-structure isomorphic to $N$. Now, we may restrict the language, to view it as an $L$-structure. I claim that, if $f$ is a function symbol in $L$, say, of arity $1$, and $n \in N$, then $f^M(\beta(n)) \in \beta(N) $. Can you see why ? (It has to do with $M \models D(N)$)

For relations, what we have to check is that, if $x,y \in \beta(N)$, if $R$ is a relation (I'll let you deal with the arities, it's not hard), then $\beta(N) \models R(x,y)$ iff $M \models R(x,y)$.

Here, we have to recall that the interpretation of $R$ for $\beta(N)$ was defined in a certain way, using the map $\beta$ and the structure already defined on $N$. Then, as before, exploit the hypothesis
"$M \models D(N)$".

For question 2, the idea is similar. You have to exploit the fact that an isomorphism preserves quantifier-free formulas.

Hint : Can you define the $L_N$ structure on $M$ such that it induces an $L_N$ structure on $N'$ (which is currently a sub - $L$-structure of $M$) that would be isomorphic, as an $L_N$-structure, to $N$ ?

In other words, can you enrich the isomorphism of $L$-structures $N \simeq N'$ into an isomorphism of $L_N$-structures, by defining the obvious $L_N$-structure on $N'$ ?