Is the derivation of $\vdash (\forall x)(B \implies C) \implies ((\forall x)B \implies (\forall x)C)$ correct

axiomsfirst-order-logicformal-proofshilbert-calculuslogic

I'm reading Introduction to mathematical logic from Mendelson. I'm in chapter 2 "First-order logic and Model theory". Axioms are:

($A1$): $B ⇒ (C ⇒ B)$

($A2$): $(B ⇒ (C ⇒ D)) ⇒ ((B ⇒ C) ⇒ (B ⇒ D))$

($A3$): $(¬C ⇒ ¬B) ⇒ ((¬C ⇒ B) ⇒ C)$

($A4$): $(∀x_i)B(x_i) ⇒ B(t)$ if $B(x_i)$

($A5$): $(∀x_i)(B ⇒ C) ⇒ (B ⇒ (∀x_i)C)$

Rules are :

  1. Modus ponens: $C$ follows from $B$ and $B ⇒ C$. (MP)
  2. Generalization: $(∀x_i)B$ follows from $B$. (Gen)

The exercise 2.27a (from section 2.4) is $⊢ (∀x)(B ⇒ C) ⇒ ((∀x)B ⇒ (∀x)C)$ and I noticed that the derivation that Mendelson gives in the solutions differs from mine (I used Axiom 5 one time and I did not use Gen rule, and Mendelson didnt use Axiom 5 but he used Gen rule), so I wanted to ask:

  1. Is my derivation is correct?
  2. If it is incorrect, what is the error?

My derivation (using deduction theorem) is the following:

  1. $(∀x)(B ⇒ C)$ Hyp
  2. $(∀x)B$ Hyp
  3. $(∀x)(B ⇒ C) ⇒ (B ⇒ (∀x)C)$ Axiom (A5)
  4. $B ⇒ (∀x)C$ MP 1,3
  5. $(∀x)B ⇒ B$ Axiom (A4)
  6. $B$ MP 2,5
  7. $(∀x)C$ MP 4,6
  8. $(∀x)(B ⇒ C), (∀x)B ⊢ (∀x)C$ 1-7
  9. $(∀x)(B ⇒ C) ⊢ (∀x)B ⇒ (∀x)C$ 1-8 corollary 2.6 (Mendelson)
  10. $⊢ (∀x)(B ⇒ C) ⇒ ((∀x)B ⇒ (∀x)C)$ 1-9 corollary 2.6 (Mendelson)

Mendelson`s derivation (using deduction theorem) is the following:

  1. $(∀x)(B ⇒ C)$ Hyp
  2. $(∀x)B$ Hyp
  3. $(∀x)(B ⇒ C) ⇒ (B ⇒ C)$ Axiom (A4)
  4. $B ⇒ C$ 1, 3, MP
  5. $(∀x)B ⇒ B$ Axiom (A4)
  6. $B$ 2, 5, MP
  7. $C$ 4, 6, MP
  8. $(∀x)C$ 7, Gen
  9. $(∀x)(B ⇒ C), (∀x)B ⊢ (∀x)C$ 1–8
  10. $(∀x)(B ⇒ C) ⊢ (∀x)B ⇒ (∀x)C$ 1–9, Corollary 2.6
  11. $⊢ (∀x)(B ⇒ C) ⇒ ((∀x)B ⇒ (∀x)C)$ 1–10, Corollary 2.6

Best Answer

Your attempt of derivation is wrong. Indeed, in axiom $A5$, there is a side condition: the formula $B$ must not contain any free occurrences of the variable $x$ (this side condition should be reported in Mendelson's textbook), while in the formula you want to prove $B$ might contain free occurrences of $x$. Therefore, the third step of your derivation is wrong: you cannot justify the formula $∀x(B \to C) \to (B \to ∀x C)$ as an instance of axiom $A5$, because $x$ might occur free in $B$.

On the contrary, Mendelson's derivation is, of course, perfectly correct. In particular, it does not use any axiom with such restrictions.


By the way, note also that the use of the generalization rule is affected by a side condition: you can derive $\forall x B$ from $B$ provided that the variable $x$ does not occur free in any hypotheses of the derivation. Mendelson's derivation respects this side condition when it uses the generalization rule.

Side conditions are important, because they avoid to derive formulas that should not be provable.