A question about 2.26 in Mendelson's Introduction to Logic

52 Views Asked by At

I am working through Mendelson's Introduction to Mathematical Logic (3rd), and in exercise 2.26 you are asked to "derive the following theorem:" $$ \vdash (\forall x) (\mathscr{A}\Rightarrow \mathscr{B}) \Rightarrow ((\forall x)\mathscr{A} \Rightarrow (\forall x)\mathscr{B}) $$ The idea is that you then apply the axioms and inference rules of the predicate calculus $K$ to obtain $((\forall x)\mathscr{A} \Rightarrow (\forall x)\mathscr{B})$ from the hypothesis. In trying to solve this problem, I thought the hypothesis was just $(\forall x) (\mathscr{A}\Rightarrow \mathscr{B})$, but after being unable to solve it, I see in the solution that Mendelson also claims $(\forall x)\mathscr{A}$ to be a hypothesis.

Can anyone explain why $(\forall x)\mathscr{A}$ can also be considered a hypothesis here? It is unclear to me how you can conclude $(\forall x)\mathscr{A}$ from the premise $(\forall x) (\mathscr{A}\Rightarrow \mathscr{B})$.

1

There are 1 best solutions below

0
On BEST ANSWER

When proving the theorem

$$ \vdash \forall x [Ax \to Bx] \to (\forall x Ax \to \forall x Bx) $$

consider that you must first assume the antecedent of the outermost conditional statement. In other words, you must first assume $\forall x [Ax \to Bx]$. This is your first hypothesis. Then, you must next assume the antecedent of the innermost conditional statement. In other words, you must next assume $\forall x Ax$. This is your second hypothesis. Under these two assumptions, or hypotheses, the goal is to derive $\forall x Bx$ and then discharge the innermost conditional statement $\forall x Ax \to \forall x Bx$. After having discharged this innermost conditional, you can discharge the outermost conditional $\forall x [Ax \to Bx] \to (\forall x Ax \to \forall x Bx)$. See the proof below...

$ \begin{array}{llll} \{1\} & 1. & \forall x [Ax \to Bx] & \text{Assumption for Conditional Proof} \\ \{2\} & 2. & \forall x Ax & \text{Assumption for Conditional Proof} \\ \{1\} & 3. & Aa \to Ba & \text{1 Universal Elimination} \\ \{2\} & 4. & Aa & \text{2 Universal Elimination} \\ \{1,2\} & 5. & Ba & \text{3,4 Modus Ponens} \\ \{1,2\} & 6. & \forall x Bx & \text{5 Universal Introduction} \\ \{1\} & 7. & \forall x Ax \to \forall x Bx & \text{2,6 Conditional Proof} \\ \{\emptyset\} & 8. & \forall x [Ax \to Bx] \to (\forall x Ax \to \forall x Bx) & \text{1,7 Conditional Proof} & \square \\ \end{array} $

We know the formula on line $8$ is a theorem because its set of dependency numbers is the empty set $\emptyset$.