Universal generalization

Generalization with hypotheses

The full generalization rule allows for hypotheses to the left of the turnstile, but with restrictions. Assume ${\displaystyle \mathrm{\Gamma }}$ is a set of formulas, ${\displaystyle \phi }$ a formula, and ${\displaystyle \mathrm{\Gamma }⊢\phi (y)}$ has been derived. The generalization rule states that ${\displaystyle \mathrm{\Gamma }⊢\mathrm{\forall }x\phi (x)}$ can be derived if ${\displaystyle y}$ is not mentioned in ${\displaystyle \mathrm{\Gamma }}$ and ${\displaystyle x}$ does not occur in ${\displaystyle \phi }$.

These restrictions are necessary for soundness. Without the first restriction, one could conclude ${\displaystyle \mathrm{\forall }xP(x)}$ from the hypothesis ${\displaystyle P(y)}$. Without the second restriction, one could make the following deduction:

1. ${\displaystyle \mathrm{\exists }z\mathrm{\exists }w(z\ne w)}$ (Hypothesis)
2. ${\displaystyle \mathrm{\exists }w(y\ne w)}$ (Existential instantiation)
3. ${\displaystyle y\ne x}$ (Existential instantiation)
4. ${\displaystyle \mathrm{\forall }x(x\ne x)}$ (Faulty universal generalization)

This purports to show that ${\displaystyle \mathrm{\exists }z\mathrm{\exists }w(z\ne w)⊢\mathrm{\forall }x(x\ne x),}$ which is an unsound deduction. Note that ${\displaystyle \mathrm{\Gamma }⊢\mathrm{\forall }y\phi (y)}$ is permissible if ${\displaystyle y}$ is not mentioned in ${\displaystyle \mathrm{\Gamma }}$ (the second restriction need not apply, as the semantic structure of ${\displaystyle \phi (y)}$ is not being changed by the substitution of any variables).