Prove $((\exists x_i)\mathcal{A}\rightarrow\mathcal{B}) \rightarrow(\forall x_i)(\mathcal{A}\rightarrow\mathcal{B})$ (no free $x_i$ occurences in B)?

58 Views Asked by At

Edit: The original "theorem" is a misprint. Thanks to Anne for the help.

I am working through Hamilton's Logic for Mathematicians at the moment and am struggling with the following proof in formal predicate logic:

Prove that $ ((\exists x_i)A\rightarrow B) \rightarrow(\forall x_i)(A\rightarrow B)$ is a theorem of the deductive system for the language $L$, provided that $x_i$ does not occur free in $B$.

The following six axiom schemes are available, where sentence letters represent any well-formed formulae:

  1. $(A\rightarrow(B\rightarrow A))$
  2. $(A\to (B \to C)) \to ((A \to B) \to (A \to C))$
  3. $(\neg A \to \neg B ) \to ( B \to A)$
  4. $((\forall x_i) A \to A )$, if $x_i$ does not occur free in $A$.
  5. $((\forall x_i)A(x_i) \to A(t))$, if $t$ is a term in $L$ which is free for $x_i$ in $A(x_i)$.
  6. $(\forall x_i)(A \to B) \to (A \to (\forall x_i)B)$, if $A$ contains no free occurence of the variable

Modus ponens and generalization (from $A$ deduce $(\forall x_i) A$ for any $A$ and $x_i$) are available as rules of inference. Additionally, there is a deduction metatheorem for L: If $\Gamma \cup \{A\} \vdash B, $ and the deduction contains no application of generalization involving a free variable in A, then $\Gamma \vdash (A \to B), $ where $\Gamma$ is a set of well-formed formulae of $L$ (possibly empty).

I gathered that the first subproof should be $((\exists x_i)A \to B), \neg B \vdash \neg A$ (this is also listed in the back of the book). You would then use the deduction theorem to show that $\neg B \to \neg A$ is a consequence of $((\exists x_i)A \to B)$, deduce $A \to B$ from $\neg B \to \neg A$ and an appropriate version of the third axiom, and finally apply generalization.

The problem is that I am stuck at the first subproof:

  1. $(\exists x_i)A \to B$ Assumption
  2. $\neg B$ Assumption
  3. $((\exists x_i)A \to B) \to ( \neg B \to \neg (\exists x_i)A)$ Third axiom, simplifying for double negation
  4. $\neg B \to \neg (\exists x_i)A$ Modus Ponens on 1 and 3
  5. $\neg (\exists x_i)$ Modus Ponens on 2 and 4
  6. $(\forall x_i)\neg A$ Quantifier Commutation, Double Negation

If I've made a mistake up to this point, please let me know. What I'm most confused about on reflection is that $\neg A$ doesn't seem to be a logical consequence of $\neg B$ and $(\exists x_i)A \to B$. If B is false, then it's the case that for no valuation of $x_i$ in any interpretation is \neg (\exists x_i)A true. But that isn't the same as $A$ being false outright.

1

There are 1 best solutions below

3
On

There is indeed a mistake of parenthesis p. 80 in your book. The correct statement is (6 pages further): $$((\exists x_i)(\mathcal A\to\mathcal B))\to((\forall x_i)\mathcal A\to\mathcal B).$$