Are these two statements on predicates equivalent?

$\forall x [P(x) \rightarrow Q(x)] \Rightarrow [\forall x P(x) \rightarrow \forall x Q(x)]$

$\forall x [P(x) \rightarrow Q(x)] \Rightarrow [\forall y P(y) \rightarrow \forall z Q(z)]$

How do you prove them if it's the case?

I mean, we don't know the domain of x, y or z.

For instance if the LHS is true for x, but the RHS is false for y and z, then we'd have a contradiction, right?

Do we have to do a proof by case, where if the LHS is false, the RHS is false or true, and if the LHS is true, the RHS must be true?

I don't know how to prove the RHS is true if the LHS is true, because the variables aren't the same.

-
The names of quantified variables are irrelevant. The formula $\forall{x}\phi(x)$ is always equivalent to $\forall{y}\phi(y)$. – mjqxxxx Oct 31 '12 at 18:06

1 Answer

It’s understood that the domains of the quantifiers are all the same.

Let’s take an informal look.

• $\forall x[P(x)\to Q(x)]$ says that if you pick an $x$ from the relevant domain, and it happens to have property $P$, then it will also have property $Q$.

• $\forall xP(x)\to\forall xQ(x)$ says that if every element of the domain has property $P$, then every element of the domain has property $Q$. There’s no real connection between the $x$ in $\forall xP(x)$ and the $x$ in $\forall xQ(x)$: the scope of the first quantifier extends only over $P(x)$.

• $\forall yP(y)\to\forall zQ(z)$ also says that if every element of the domain has property $P$, then every element of the domain has property $Q$. This version just makes explicit, by using different variables, the fact that the scope of the first quantifier extends only over $P(y)$; it doesn’t reach the righthand side of the implication.

Informally, then, we can see that

$$\forall x [P(x) \rightarrow Q(x)] \Rightarrow [\forall x P(x) \rightarrow \forall x Q(x)]\tag{1}$$

and

$$\forall x [P(x) \rightarrow Q(x)] \Rightarrow [\forall y P(y) \rightarrow \forall z Q(z)]\tag{2}$$

say the same thing. The point of the exercise is that if a variable is bound, meaning that it’s governed by (technically, within the scope of) some quantifier, it is not the same as any other bound variable, even if they share the same name. Statement $(1)$ actually contains three different variables that are all called $x$; in statement $(2)$ they are given different names.

By the way, $(1)$ (and therefore $(2)$) is true, though that apparently isn’t part of the exercise.

Added: A similar phenomenon from another part of mathematics may be helpful. Suppose that $f(x)$ and $g(x)$ are continuous, real-valued functions on the interval $[0,1]$, and that $f(x)\le g(x)$ for all $x\in[0,1]$. Consider the following (true) statements:

\begin{align*} &\int_0^1f(x)~dx\le\int_0^1g(x)~dx\tag{3}\\ &\int_0^1f(x)~dx\le\int_0^1g(y)~dy\tag{4} \end{align*}

$(3)$ and $(4)$ are exactly equivalent, even though $(3)$ uses the same variable on both sides of the inequality, and $(4)$ uses different variables. These definite integrals are just numbers, and the value of that number is independent of the name of the variable of integration. The $x$ in the lefthand integral in $(3)$ isn’t actually the same as the $x$ in the righthand integral: each in a sense ‘exists’ only within its own integral. The bound variables in your statements are similarly tied to the scopes of their respective quantifiers and in a sense ‘exist’ only within those scopes.

-