Coincidence Lemma

Last updated Nov 1, 2022

Let $\mathcal{L}$ be a Language and let $\mathcal{M}$ be an $\mathcal{L}$-structure. Then the following are true

1. Suppose $t$ is a an $\mathcal{L}$-Term and $\sigma, \tau : V \to M$ are Assignments agreeing on all Variable Symbols occuring in $t$. Then $t^{\mathcal{M}}[\sigma]= t^\mathcal{M}[\tau]$.
2. Suppose $\phi$ is an $\mathcal{L}$-Formula and and $\sigma, \tau : V \to M$ are Assignments agreeing on all Variable Symbols occuring freely in $\phi$. Then $\mathcal{M} \models_{\sigma} \phi \Leftrightarrow \mathcal{M} \models_{\tau} \phi$.

TODO Easy way is to use Induction on Complexity.. See Marker - An Invitation Mathematical Logic Book

• Term Evaluation