What's the difference between ∀x(P(x)) and ∀xP(x)?

Question

Edit: Changed logically equivalent to logically implies! Sorry. Also realized removing the context when trying to understand something is a bad idea.

Just started learning predicate logic.

What I'm trying to prove is that ∀x∃y( P(x)->Q(y) ) is logically Implies to ( ∀xP(x) ) -> ( ∃yQ(y) ).

I know that ∀x∃y( P(x)->Q(y) ) is satisfied whenever P(x) is false or Q(y) is true (based on the truth table for implies).

And ( ∀xP(x) ) -> ( ∃yQ(y) ) is satisfied whenever ( ∀xP(x) ) is false or ( ∃yQ(y) ) is true.

But I need a better understanding of the difference between ∀x(P(x)) and ∀xP(x).

Question 1: What does ∀x(P(x)) mean? What I thought was that it means "for any element x in the domain, P(x) is true". Doesn't this mean ∀x(P(x)) is Always satisfied?

Question 2: What does ∀xP(x) mean? I thought this also means "for any element x in the domain, P(x) is true".

Note: I was given the answer to this proof, and it states that ∀x∃y( P(x)->Q(y) ) is satisfied when "for any element x, P(x) is falsified" and ( ∀xP(x) ) -> ( ∃yQ(y) ) is satisfied when "for Some element x, P(x) is falsified".

But as mentioned, I'm having difficulty understanding what the formulas mean and how they are different.

Answer 1

I'm afraid there's quite a bit of confusion going on here. So let me try to address not only your two actual questions, but also some other issues that I see here.

[1] Generally speaking, parentheses in logical expressions are used in the same way and for the same purpose as in arithmetical expressions: to show order of operations, or so to speak to show which things go together and which don't. So the answer to the question in your title:

What's the difference between $\forall x(P(x))$ and $\forall xP(x)$?

is that there's no difference, as they mean exactly the same thing: for all values of $x$ (in the given domain or universe) $P(x)$ is true. (Note that this also covers both your Questions 1 and 2.) But...

[2] Taking things out of context is extremely dangerous!!! If someone asks you:

What's the difference between $2+3$ and $(2+3)$?

anybody will say that they are the same thing, both equal to $5$... Until it turns out that they were taken from longer expressions $\color{green}{2+3\cdot4}$ and $\color{blue}{(2+3)\cdot4}$, where presence or absence of parentheses makes a whole lot of difference!

[3] And that's why the actual question in the body of your post hardly has anything to do with what you asked in the title. According to your post, you're

trying to prove is that $\forall x\, \exists y\, (P(x)\to Q(y))$ is logically equivalent to $(\forall x\, P(x))\to(\exists y\,Q(y))$.

Note that while $\forall xP(x)$ is the antecedent of the second formula, $\forall x(P(x))$ does not appear anywhere in either of them. So when you used it in the title, where did it come from?

[4] Moreover, these two statements actually are NOT equivalent to each other. Here's a quick counterexample. Let the domain be all integers $\mathbb{Z}$. Let

$$P(x)=[x\text{ is even}] \quad \text{and} \quad Q(y)=[y+1<y].$$

(I'm using brackets as quotation marks.) Then:

• $\forall x\, \exists y\, (P(x)\to Q(y))$ is false. It requires that for any $x$ there exists some $y$ such that $P(x)\to Q(y)$. But if $x=2$, then $P(2)\to Q(y)$ doesn't hold for any $y$, because $P(2)$ is true and $Q(y)$ is false for any $y$.

• But $(\forall x\, P(x))\to(\exists y\,Q(y))$ is true, because the antecedent $\forall x\, P(x)$ is false.

So if you have been given an exercise where two statements are given and your task is to prove that they are logically equivalent, then maybe you made a typo somewhere?

Answer 2

It seems you have the two different cases i) $\forall x, P (x) \rightarrow \exists y: Q (y)$ and ii) $(\forall x, P (x))\rightarrow \exists y:Q (y)$. These are clearly different, as the if parts are different (have different truth value definitions). In general $P (x) $ being true for all x is different than for all x, if $P (x) $ is true, then such and such. The former condition is false when $\exists x:P (x)$ is false. But in this case, there may be other x such that P (x) is true. So in ii), the conditional is true because your if part is false. In i), you still need to check whether when $P (x) $ is true, the conclusion $(\exists y:Q (y))$ is false or not... Correction Yes, I have seen your edit, they are not equivalent. ..in the situation I referred to ii) can be true while i) is false

Answer 3

Maybe some additional parentheses will help. But your comment makes me think one more thing would be helpful : tracking when a variable depends on another. One of your sentences has a dependency and the other doesn't so this is another way to see that there could be some difference between them.

The sentence $$ \forall x \exists y \left( \strut{} P(x) \implies Q(y) \right)$$ could be additionally parenthesized as $$ \forall x \left( \strut{} \exists y \left( \strut{} P(x) \implies Q(y) \right) \right) \text{.}$$ Let us use subscripts to indicate dependence, for instance "$y_x$" means that the choice of $y$ depends on the choice of $x$ (in the sense that a different choice of $x$ could necessitate a different choice of $y$. Notice that "$\exists y (\dots)$" appears inside the universal quantification of $x$. This means that for each choice of $x$ there exists some $y$ (perhaps depending on $x$) such that ... . So we have $$ \forall x (\exists y_x ( P(x) \implies Q(y_x) )) \text{.}$$ In words: for any $x$ at all, there exists a $y$ (perhaps depending on $x$) such that $P(x)$ being true implies $Q(y)$ is also true.

Your other sentence is $$(\forall x P(x)) \implies (\exists y Q(y))$$ which we could additionally parenthesize as $$(\forall x (P(x))) \implies (\exists y (Q(y))) \text{.}$$ But this time, the choice of $y$ is not permitted to depend on $x$ because "$\exists y$" does not appear in the elliptic subexpression of "$\forall x (\dots)$". That is, there is no relationship between the variables $x$ and $y$. In words: if $P(x)$ happens to be true for every possible choice of $x$, then there is at least one choice of $y$ making $Q(y)$ true.