Math 557 Sep 5

Substitution

Key Concepts

Substitution:
- Basic idea: $\varphi_{\bar{s}/\bar{x}}$ is obtained by replacing all occurrences of the variable $x_i$ by the term $s_i$.
- Uncontrolled substitution may cause issues with quantifiers. If we try to substitute a variable into the range of a quantifier, we rename the quantified variable to an unused variable ($\exists x \dots$ becomes $\exists u \dots$).
Substitution Lemma:
- Substitution behaves “as expected” with respect to evaluation and satisfaction.
- Evaluating a substituted term yields the same value as evaluating the original term under the “substituted” assignment (i.e. the assignment in which we replace the assignment to $x$ by the value of $s$ under $\alpha$).
- A substituted formula holds in $\mathcal{M}$ under assignment $\alpha$ iff the original formula holds in $\mathcal{M}$ under the “substituted” assignment.

Problems

Exercise 1 (Carry-over from Sep 3)
Show that if $x$ is not free in $\varphi$, $\mathcal{M} \models \varphi[\alpha]$ implies $\mathcal{M} \models \forall x \, \varphi [\alpha]$.

Then verify that

\[\forall x ( \varphi \to \psi) \; \to \; (\varphi \to \forall x \psi) \quad (\text{$x$ not free in $\varphi$})\]

is a validity.

Exercise 2

Show that if $t$ is a term, then $t_{\bar{s}/\bar{x}}$ is a term.
Show that if $\varphi$ is a formula, $\varphi_{\bar{s}/\bar{x}}$ is a formula of the same height.

Exercise 3
Use the Substitution Lemma to verify that \[\varphi_{t/x} \: \to \: \exists x \, \varphi\] is a validity.

Exercise 4
Show that if $y$ does not occur in $\psi$,

\[ [\psi_{y/x}]_{x/y} \equiv \psi \]

Find a counterexample that shows this no longer holds if $y$ does occur in $\psi$.