Prove that if $\alpha$ is a tautology then $subst(\alpha,s)$ is a tautology > Prove that if $\alpha$ is a tautology then $subst(\alpha,s)$ is a tautology for every $s\in WFF^{Var}$ I know how to do this if $\alpha =\neg\beta $ , But not the other cases. Inductive proof comes to mind but i'm not sure what the base would be since an atom can't be a tautology, and i'm not sure what the assumption would be for that matter.

Call $\alpha^s$ the result of $\text {subst}(\alpha,s)$.

_Example_ : if $\alpha := p \lor \lnot p$ and $s(p)=\lnot q$, then $\alpha^s := \lnot q \lor \lnot \lnot q$.

For each _valuation_ $v$ and substitution $s$, define a new valuation $v^s$ in such a way that $v^s(p) = v(s(p))$, for every atom $p$.

We have that:

> $v \vDash \alpha^s$ iff $v^s \vDash \alpha$.

The proof is by induction:

_(i)_ base case: if $\alpha$ is an atom, the property certainly holds.

_(ii)_ induction step: we consider only the connective $\land$.

$v \vDash (α∧β)^s$ iff $v \vDash α^s ∧ β^s$, by property of subst, iff

$v \vDash α^s, β^s$ iff $v^s \vDash α, β$, by induction hypothesis, iff

$v^s \vDash α ∧ β$.

Consider now a tautology $\alpha$; we have that $v \vDash \alpha$, for every valuation $v$.

Thus also $v^s \vDash \alpha$ and so, by the previous result: $v \vDash \alpha^s$.

But this holds for every valuation $v$, and thus $\alpha^s$ is a tautology.