Definition of Parity: By induction on degα, we assign to each formula α a parity prα, which is either 0 or 1, as follows:
(1) If α is atomic,then prα = 0.
(2) If α = ¬β, then prα = 1 - prβ.
(3) If α = β→γ, then prα = (1 - prβ)·prγ.
(4) If α = ∀xβ, then prα = prβ.
We say that α is even or odd according as prα is 0 or 1.
Using the above definition, how would we show the following:
Show by induction that for any formula α and any term t we always have pr(α) = pr(α(x/t)).
I'm not sure how to approach this problem, usually we would apply induction on the degree of complexity of the formula, would this still be an appropriate approach? And then check for each of cases (1)-(4) of the definition?
Thank you in advance!
Yes, induction can formalize the (obvious) result.
Base: an atomic formula is still atomic after substitution (no quantifier or connective introduced). Thus parity was $0$ and after substitution will be $0$.
Induction step: consider negation.
If $α=¬β$, then $α(x/t)=¬(β(x/t))$. Thus , $\text{pr}(β)=\text{pr}(β(x/t))$ by induction hypotheses.
So, $\text{pr}(α) = 1 - \text{pr}(β)=1 - \text{pr}(β(x/t))=\text{pr}(¬(β(x/t)))=\text{pr}(α(x/t))$, and again the parity is not affected.
The same for $\to$.
For the quantifier case, the result is immediate by induction hypotheses, if the term $t$ is free for $x$ in $\beta$ (i.e. if the substitution is allowed).