Question: Let $\sigma$ be a vocabulary where there is only one binary relation symbol $R(\cdot, \cdot)$. Let $N=\langle D^N, R^N\rangle, M=\langle D^M, R^M\rangle $ be two structures for $\sigma$. An function $f: D^M \rightarrow D^N$ is called an embedding function if $\forall a,b\in D^M: (a,b)\in R^M \iff (f(a),f(b))\in R^N$. If there exists an embedding function from M to N prove that if an existential statement is satisfiable in M $\iff$ it is satisfiable in $N$:
My proof:
- Denote $\phi= \exists x_1\ldots x_n \psi$
Denote $v'=$ the assignment s.t given an assignment v : $M,v \vDash \phi$ , then v' $\forall 1 \le i \le n : x_i=f(v(x_i))$
I'll prove that $N,v \vDash \phi$ by induction on the structure of the statement $\psi$:
Base case: if $\psi =R(s_1,s_2)$ (for some terms $s_1, s_2$) then $v(R^M (s_1^M, s_2^M))=T \iff v'(R^N ([f(s_1)]^N, [f(s_2)]^N)=T$ (this is true from the definition of an embedding function).
Closure: let $\alpha, \beta$ be statements and $\operatorname{op}=\{\land, \lor, \rightarrow\}$,
if $\psi=\alpha \operatorname{op} \beta$ then $M,v\vDash \alpha \operatorname{op} \beta \iff (M,v \vDash \alpha) \operatorname{op} (M,v \vDash \beta) \iff (N,v' \vDash \alpha) \operatorname{op} (N,v' \vDash \beta)$ (from the induction hypothesis) $\iff N,v' \vDash \alpha \operatorname{op} \beta$
if $\psi=\neg \alpha$ then proof is very similar to previous case.
Let $Q\in\{\forall, \exists\}$. if $\psi= Qx \alpha$ (WLOG x is one variable, it could be many but the proof is similar, just with more replacements) then $Qd \in D^M : M,v[d/x] \vDash \alpha \iff Qd'\in D^N: d'=f(d): N,v'[d'/x]\vDash \alpha$ (from the definition of embedding function) $\iff N,v'\vDash Qx\alpha$
I was wondering if this proof is correct, this is the first time I've been dealing with such proofs in this subject. Thanks a lot.
The statement you are trying to prove is false.
Take $M$ to be the complete graph on 3 vertices, $N$ the complete graph on 4 vertices. Then
$M$ embeds into $N$,
but the formula "there are four distinct elements" is an existential sentence true in $N$ but false in $M$.
From this, do you see where your proof breaks down?