First Order Logic: Diffrence b/w $\{\forall x P(x) \implies Q(x) \}$ and $\{ (\forall x P(x)) \implies Q(x)) \}$

Question

There is GATE exam question which is confusing (in first look at least to solve): Which of the following first order formula is logically valid? Here $\alpha(x)$ is a first order formula with $x$ as a free variable, and $\beta$ is a first order formula with no free variable.

A) $[\beta\to(\exists x,\alpha(x))]\to[\forall x,\beta\to\alpha(x)]$

B) $[\exists x,\beta\to\alpha(x)]\to[\beta\to(\forall x,\alpha(x))]$

C) $[(\exists x,\alpha(x))\to\beta]\to[\forall x,\alpha(x)\to\beta]$

D) $[(\forall x,\alpha(x))\to\beta]\to[\forall x,\alpha(x)\to\beta]$

So my question / basic doubt is how parenthesis change the meaning in predicate logic and how we can solve such question?

Answer 1

A) is not valid, since if $\beta$ is a tautology, then $\beta\to\gamma\equiv \gamma$ for any formula $\gamma$, and thus this sentence is equivalent to $\exists x(\alpha(x))\to\forall x(\alpha(x))$.

B) is not valid for the same reason as above

C) is valid: suppose that $\exists x(\alpha(x))\to \beta$ is true, then either $\exists x(\alpha(x))$ is false, or $\beta$ is true. If $\beta$ is true, then $\alpha(x)\to\beta$ is also true for all $x$, and thus $\forall x(\alpha(x)\to\beta)$ is true. On the other hand, if $\exists x(\alpha(x))$ is false, then $\alpha(x)$ is false for every $x$, meaning that $\alpha(x)\to\beta$ is true for every $x$, and thus $\forall x(\alpha(x)\to\beta)$ is true.

D) is not valid, since we can take $\beta$ to be a contradiction and assume $\alpha(x)$ is true for at least one $x$ and false for at least one $x$. Then the antecedent $\forall x(\alpha(x))\to\beta$ is true, since $\forall x(\alpha(x))$ is false, but the consequent $\forall x(\alpha(x)\to\beta)$ is false, since there is at least one $x$ such that $\alpha(x)$ is true, and for this $x$ the formula $\alpha(x)\to\beta$ is false, as $\beta$ is a contradiction.

Answer 2

The short answer is that the parenthesis changes the scope of the quantifier variable binding. To give another example, think of the difference between "If, for all $x$ we have that $x$ is fancy, then $0=1$" and "For all $x$, if $x$ is fancy, then $0=1$." Symbolically this would be $(\forall x \mathcal{F}x)\to 0=1$ and $\forall x(\mathcal{F}x \to 0=1)$, respectively. Then using Vsotvep's argument for $D$ you can see that in some cases the second does not necessarily follow from the first.

It is interesting to note though that the converse is true, that is $$(\forall x(P(x)\to p))\to ((\forall xP(x))\to p)$$ is valid. To prove this, assume $(\forall x(P(x)\to p))$ and $\forall xP(x)$. Instantiate both with the same individual, say $a$ to arrive at $P(a)\to p$ and $P(a)$, whereby simple modus ponens yields $p$.