Substitution Theorem on "A Concise Introduction to Mathematical Logic" by W. Rautenberg

Question

I'm trying to understand the Substitution Theorem (Theorem 3.5, page 71) in "A Concise Introduction to Mathematical Logic" by W. Rautenberg. At some point Rautenberg states: "The reader should recall the definition of $(\forall x\alpha)^\sigma$ page 60 and realize that the induction hypothesis refers to an arbitrary global substitution $\tau$". Why $\tau$ is arbitrary? Shouldn't the induction hypothesis be $\mathscr{M}_x^a\vDash\alpha^\sigma$ $\iff(\mathscr{M}^\sigma)_x^a\vDash\alpha$? Thanks for you help.

Answer 1

What we are trying to prove is :

$\mathscr{M} \vDash \varphi^\sigma \ \iff \ \mathscr{M}^\sigma \vDash \varphi$.

Thus, when unpacking $\mathscr{M} \vDash \forall x \alpha^\tau$ to $\mathscr{M}_x^a \vDash \alpha^\tau, \text { for all } a$, we have to "move" $\tau$ from the formula to the model, according to the induction hypotheses :

$(\mathscr{M}_x^a)^{\tau} \vDash \alpha, \text { for all } a$

The hypotheses is : "and $σ$ a global substitution [whatever]" and $\tau$ (as defined in the clause of page 60) is again a global one.

---

The key point is the def of $(\mathscr{M})^{\sigma}$ [top page 71] : $\sigma$ is an operation of symbols of the language.

Thus, applying it to $\mathscr{M} := (\mathscr{A}, w)$ menas to apply it to $w$, because the structure $\mathscr{A}$ is made of "objects" and not of symbols.

Thus, $(\mathscr{M})^{\sigma} := (\mathscr{A}, w^{\sigma})$, where in turn : $x^{w^{\sigma}}= (x^{\sigma})^{\mathscr{M}}$.

---

---

Long comment

It is harder to formalize the result than describe it with words...

Consider a simple example in the language of arithmetic, with $0$ and $1$ as individual constants, and let $(x=0)$ the formula $\varphi$.

Consider the usual structure $\mathbb N$ of natural numbers and let $0^{\mathbb{N}}$ denotes the number $0$ and the same for $1^{\mathbb{N}}$.

Finally, let $w : \text {Var} \to \mathbb N$ a valuation such that : $w(x)=0^{\mathbb{N}}$ and $w(y)=1^{\mathbb{N}}$, and let $\mathscr{M} := (\mathbb{N}, w)$.

We have $\mathscr{M} \vDash (x=0)$.

Consider now the substitution $\sigma$ such that $\sigma(x)=y$.

Clearly : $\text {not-}(\mathscr{M} \vDash (x=0)^{\sigma})$.

Regarding the Substitution theorem, the above example is enough to show the [quite obvious] fact that :

$\text {not-}(\mathscr{M} \vDash \varphi^\sigma \ \iff \ \mathscr{M} \vDash \varphi)$.

The theorem states that,

regarding the relation of satisfaction $\vDash$ between a formula and a model, the syntactical operation of substitution appied to formulas commutes with the same operation applied to valuations.