Question: Let T be a theory of statements over a signature $\sigma$ and $\phi$ is a formula over $\sigma$ s.t. $x,y$ are the only free variables. We define a signature $\sigma'$ by adding a new binary function sign $f$ and a new constant sign $c$ to $\sigma$ . Denote $T'=T\cup \lbrace \forall x \forall y (f(x,c)=y \rightarrow \phi)\rbrace$. T' will be called a preserving extension of T if for every formula $\beta: T\vDash \beta \iff T'\vDash \beta$.
Prove or disprove:
if $T \vDash \forall x\exists y \phi (x,y)$ then T' is a preserving extension of T.
My proof
One direction is trivial so I will focus on the more difficult side for my question:
- Assume that $T'\vDash\beta$.
- Let M,v be a structure s.t $M\vDash T $ so $M,v\vDash \forall x \exists y \phi (x,y) \iff \forall a\in D^M \exists b_a\in D^M : M,v[a/x,b_a/y]\vDash \phi(x,y)$
- (We now extend M to M' over \sigma' by defining $f^{M'}(a,c) =b_a$ and defining c as some constant in $D^M$.)
- $\iff \forall a\in D^M : M',v[a/x]\vDash \phi(x,f(x,c)) \iff M'\vDash \forall x \phi(x,f(x,c))$(this is a statement, no assignment needed)
from our definition of $f^{M'}$ the following claim is also true : $M' \vDash \forall x \forall y: (f(x,c)=y)$ (this is a statement, no assignment needed)
Therefore also $M' \vDash \forall x \forall y (f(x,c)=y \rightarrow \phi (x,y)) $ because M' satisfies both suffix and prefix.
Since the original $M$ satisfied $T$, we get that $M' \vDash T' \Rightarrow M'\vDash \beta$
I'm not sure whether the 5th and 6th bullets are correct and are allowed. I want to verify that this is the correct way of doing this proof. Thanks
Your proof is along the right lines, but in the last bullet, what you need to show is that $M \models \beta$, because you are trying to show that any model of $T$ is a model of $\beta$.
What you are calling a "preserving extension" is usually called a "conservative extension". In the definition of a conservative extension as it applies to your example, $\beta$ is a formula that does not contain the symbols $f$ and $c$.
Given a model $M$ of $T$, because $M \models \forall x \exists y\phi(x, y)$, you can expand $M$ to a model of $T' = T\cup \lbrace \forall x \forall y (f(x,c)=y \rightarrow \phi)\rbrace$. ("Expanding" a model means giving interpretations to new symbols using the same carrier set: essentially what you are doing in your third bullet.) Conversely, given a model of $T'$, you can obtain a model of $T$ by forgetting about the interpretations of $f$ and $c$. Hence (using the soundness and completeness of first-order logic), if $\beta$ is a sentence that does not contain the symbols $f$ and $c$, $T \models \beta$ iff $T' \models \beta$.
I hope this gives you enough clues to patch up your argument.