Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

$\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.

share|improve this question
    
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 1

up vote 2 down vote accepted

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.

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.