[proofplan] We prove the stronger assertion that every $\Delta_0$ formula has the same truth value in $M$ and in the ambient universe $V$ under every assignment of its free variables to elements of $M$. The proof is by structural induction on the formation of $\Delta_0$ formulas. Atomic formulas are absolute because equality and membership are the ambient relations restricted to $M$; Boolean connectives preserve absoluteness by the induction hypothesis. The only substantive point is bounded quantification: if the bounding set lies in $M$, then transitivity ensures that all of its elements also lie in $M$, so $M$ and $V$ quantify over the same possible witnesses. [/proofplan] [step:Prove a structural induction invariant for all assignments into $M$] We prove the following statement by induction on the construction of a $\Delta_0$ formula $\psi$. For every finite list of variables $y_1,\dots,y_m$ containing all free variables of $\psi$, and for every assignment $s$ with $s(y_i)\in M$ for each $i\in\{1,\dots,m\}$, \begin{align*} (M,\in)\models \psi[s] \iff V\models \psi[s]. \end{align*} Here $\psi[s]$ denotes satisfaction of $\psi$ under the assignment $s$. This induction invariant implies the theorem by taking $\psi=\varphi$, $y_i=x_i$, and $s(x_i)=a_i$ for each $i\in\{1,\dots,n\}$. [/step] [step:Verify atomic formulas using literal equality and restricted membership] First let $\psi$ be the atomic formula $u=v$, where $u$ and $v$ are variables. Let $s$ be an assignment of the free variables to elements of $M$. Then \begin{align*} (M,\in)\models u=v[s] &\iff s(u)=s(v) \\ &\iff V\models u=v[s], \end{align*} because equality in $(M,\in)$ is ordinary equality. Next let $\psi$ be the atomic formula $u\in v$. Since $s(u),s(v)\in M$, membership in the structure $(M,\in)$ is the ambient membership relation restricted to $M$. Hence \begin{align*} (M,\in)\models u\in v[s] &\iff s(u)\in s(v) \\ &\iff V\models u\in v[s]. \end{align*} Thus the induction invariant holds for all atomic formulas. [/step] [step:Pass absoluteness through Boolean connectives] Assume the induction invariant holds for $\theta$ and $\rho$. For negation, let $\psi$ be $\neg\theta$. For every assignment $s$ into $M$, \begin{align*} (M,\in)\models \neg\theta[s] &\iff \text{not }(M,\in)\models \theta[s] \\ &\iff \text{not }V\models \theta[s] \\ &\iff V\models \neg\theta[s], \end{align*} where the middle equivalence is the induction hypothesis for $\theta$. For conjunction, let $\psi$ be $\theta\wedge\rho$. Then \begin{align*} (M,\in)\models (\theta\wedge\rho)[s] &\iff (M,\in)\models \theta[s]\text{ and }(M,\in)\models \rho[s] \\ &\iff V\models \theta[s]\text{ and }V\models \rho[s] \\ &\iff V\models (\theta\wedge\rho)[s]. \end{align*} The same argument, with the truth table for the connective in question, treats disjunction and implication. Hence the induction invariant is preserved under Boolean connectives. [/step] [step:Handle bounded existential quantifiers by transitivity of $M$] Assume the induction invariant holds for $\theta(x,y,z_1,\dots,z_k)$, and let $\psi(y,z_1,\dots,z_k)$ be the bounded existential formula \begin{align*} \exists x\in y\,\theta(x,y,z_1,\dots,z_k). \end{align*} Let $s$ be an assignment with $s(y)\in M$ and $s(z_i)\in M$ for each $i\in\{1,\dots,k\}$. Define $b:=s(y)$. By transitivity of $M$, every element of $b$ belongs to $M$, since $b\in M$. Therefore \begin{align*} \{c\in M:c\in b\}=\{c:c\in b\}=b. \end{align*} Now compute the satisfaction relation: \begin{align*} (M,\in)\models \exists x\in y\,\theta[s] &\iff \text{there exists }c\in M\text{ such that }c\in b \text{ and }(M,\in)\models \theta[s[x\mapsto c]] \\ &\iff \text{there exists }c\in b \text{ such that }(M,\in)\models \theta[s[x\mapsto c]] \\ &\iff \text{there exists }c\in b \text{ such that }V\models \theta[s[x\mapsto c]] \\ &\iff V\models \exists x\in y\,\theta[s]. \end{align*} The third equivalence uses the induction hypothesis for $\theta$, and it is applicable because $c\in b$ implies $c\in M$ by transitivity, so the extended assignment $s[x\mapsto c]$ still assigns all free variables of $\theta$ to elements of $M$. [/step] [step:Handle bounded universal quantifiers and complete the induction] Assume the induction invariant holds for $\theta(x,y,z_1,\dots,z_k)$, and let $\psi(y,z_1,\dots,z_k)$ be the bounded universal formula \begin{align*} \forall x\in y\,\theta(x,y,z_1,\dots,z_k). \end{align*} Let $s$ be an assignment with $s(y)\in M$ and $s(z_i)\in M$ for each $i\in\{1,\dots,k\}$. Define $b:=s(y)$. As before, transitivity of $M$ gives \begin{align*} \{c\in M:c\in b\}=b. \end{align*} Therefore \begin{align*} (M,\in)\models \forall x\in y\,\theta[s] &\iff \text{for every }c\in M\text{ with }c\in b,\ (M,\in)\models \theta[s[x\mapsto c]] \\ &\iff \text{for every }c\in b,\ (M,\in)\models \theta[s[x\mapsto c]] \\ &\iff \text{for every }c\in b,\ V\models \theta[s[x\mapsto c]] \\ &\iff V\models \forall x\in y\,\theta[s]. \end{align*} Again the induction hypothesis applies because each $c\in b$ lies in $M$. Thus the induction invariant holds for atomic formulas, is preserved by Boolean connectives, and is preserved by bounded existential and bounded universal quantification. Since every $\Delta_0$ formula is built from atomic formulas using only these operations, the invariant holds for every $\Delta_0$ formula. Applying it to $\varphi(x_1,\dots,x_n)$ with $s(x_i)=a_i$ gives \begin{align*} (M,\in)\models\varphi(a_1,\dots,a_n) \iff V\models\varphi(a_1,\dots,a_n), \end{align*} which is the desired absoluteness. [/step]