 Proof: We proceed by induction on the complexity of the formula \(\theta\). The theorem clearly holds if \(\theta\) is atomic, since in those cases only the values of the variable-assignments at the variables in \(\theta\) figure in the definition. Assume, then, that the theorem holds for all formulas less complex than \(\theta\). And suppose that \(s_1\) and \(s_2\) agree on the free variables of \(\theta\). Assume, first, that \(\theta\) is a negation, \(\neg \psi\). Then, by the induction hypothesis, \(M,s_1 \vDash \psi\) if and only if \(M,s_2 \vDash \psi\). So, by the clause for negation, \(M,s_1 \vDash \neg \psi\) if and only if \(M,s_2 \vDash \neg \psi\). The cases where the main connective in \(\theta\) is binary are also straightforward. Suppose that \(\theta\) is \(\exists v\psi\), and that \(M,s_1 \vDash \exists v\psi\). Then there is an assignment \(s_1'\) that agrees with \(s_1\) except possibly at \(v\) such that \(M,s_1'\vDash \psi\). Let \(s_2'\) be the assignment that agrees with \(s_2\) on the free variables not in \(\psi\) and agrees with \(s_1'\) on the others. Then, by the induction hypothesis, \(M,s_2'\vDash \psi\). Notice that \(s_2'\) agrees with \(s_2\) on every variable except possibly \(v\). So \(M,s_2 \vDash \exists v\psi\). The converse is the same, and the case where \(\theta\) begins with a universal quantifier is similar.