Quantifiers implication question

Question

Let X be the domain of discourse. Suppose $\forall a \in X$ $P(a)$ $\implies Q(a)$ How would I prove that the above implication implies $\forall a\in X$ $Q(a)$?

Answer 1

The negation of your statement is satisfiable $\dots$

The correct version is similar to the rule MP or $\to$ Elim in PL:

$\def\fitch#1#2{\quad\begin{array}{|l}#1\\\hline#2\end{array}}$ $$\fitch{~~1.~P\to Q\\~~2.~P}{~~3.~Q\hspace{10ex}{\to}\textsf{Elim}~1,2}$$

To conlude $Q$ is true also requires that $P$ is true, otherwise it's not sound.

In another word, $(P\to Q)\to Q$ will not hold when $P$ is false and $Q$ is false,

Since this will make $(P\to Q)\equiv\top$ and $Q\equiv\bot$ that $(\top\to\bot)\equiv\bot$ .

Therefore It's not a tautology.

In the case of FOL, Here is a proof of the correct version with natural deduction:

Note that $$\forall x\in X,P(x)$$

$$\text{ iff } \forall x,x\in X\to P(x)$$

We denote $x\in X$ as $X(x)$,

First we need to assume $\forall x(X(x)\to(P(x)\to Q(x)))$ and $\forall x(X(x)\to P(x))$:

$$\fitch{~~1.~\forall x(X(x)\to(P(x)\to Q(x)))\\~~2.~\forall x(X(x)\to P(x))}{\fitch{~~3.~\boxed{a}~X(a)}{~~4.~X(a)\to(P(a)\to Q(a)) \hspace{25ex}{\forall}~\textsf{Elim}~1\\~~5.~X(a)\to P(a)\hspace{35.5ex}{\forall}~\textsf{Elim}~2\\~~6.~P(a)\to Q(a)\hspace{34.5ex}{\to}~\textsf{Elim}~3,4\\~~7.~P(a)\hspace{43.3ex}{\to}~\textsf{Elim}~3,5\\~~8.~Q(a)\hspace{43.3ex}{\to}~\textsf{Elim}~6,7}\\~~9.~\forall x(X(x)\to Q(x))\hspace{34ex}{\forall}~\textsf{Intro}~3-8}$$

Finally, this proves $\forall x\in X,Q(x)$

Answer 2

What you are essentially trying to do is apply a rule of inference that looks like the following:

$p\rightarrow q$

$\therefore q$

However, no such inference rule exists because the above argument form is not valid. The single premise $\forall a \in X$ $P(a)$ $\implies Q(a)$ is not enough to prove $\forall a \in X$ $Q(a)$. You need more premises to work with.