Universal generalization

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

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

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

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

Prove: ${\displaystyle \forall x\,(P(x)\rightarrow Q(x))\rightarrow (\forall x\,P(x)\rightarrow \forall x\,Q(x))}$  is derivable from ${\displaystyle \forall x\,(P(x)\rightarrow Q(x))}$  and ${\displaystyle \forall x\,P(x)}$ .

Proof:

In this proof, universal generalization was used in step 8. The deduction theorem was applicable in steps 10 and 11 because the formulas being moved have no free variables.

• First-order logic
• Hasty generalization
• Universal instantiation