Nested Quantifiers Doubt: "If $xy$ is equal to $x$ for all $y$, then $x=0$"

131 Views Asked by At

If $P(x,y,z)$ represents $xy=z$. Then represent the following statement using quantifiers,connectives etc. "If $xy$ is equal to $x$ for all $y$, then $x=0$".

The answer given is $\forall x[ \forall y P(x,y,x)\to x=0]$.

Can't we write the same as: $\forall x\forall y[P(x,y,x)\to x=0]$.

Please help me out when can I take the quantified variables outside and when can I not.

2

There are 2 best solutions below

0
On BEST ANSWER

Those two claims aren't equivalent (as Arthur explains). Which just goes to show that you have to be careful moving quantifiers around -- especially when extracting them from the antecedents of conditionals (where there are in effect hidden negation signs waiting to trip you up!).

To simplify the case for the moment, let's note first that $[\forall yRy \to p]$ is NOT equivalent to $\forall y[Ry \to p]$. In fact, assuming the proposition $p$ doesn't contain the variable $y$, we have:

$$[\forall yRy \to p] \Leftrightarrow [\neg\forall yRy \lor p] \Leftrightarrow [\exists y \neg Ry \lor p]\Leftrightarrow \exists y[ \neg Ry \lor p] \Leftrightarrow \exists y[Ry \to p]$$

Here the quantifier move is ok: Can you see why $[\exists yQy \lor p]$ IS equivalent to $\exists y[Qy \lor p]$?

So in fact $\forall x[\forall yP(x,y,x) \to x = 0]$ -- which is indeed the correct answer -- is equivalent, if you want to export the quantifier -- to $\forall x\exists y[P(x,y,x) \to x = 0].$

This sort of thing will be explained in any elementary text book. I see that P-t-r Sm-th's super Introduction to Formal Logic does it in §24.3 on Moving Quantifiers :-).

0
On

No, that is not the same at all.

  • The first expression says is that for any $x$, the statement "For any $y$ we have $xy = x$" implies the statement "$x = 0$".

  • The second expression says that for any $x$ and $y$, the statement "$xy = x$" implies the statement "$x = 0$".

The second expression isn't true, and particulary the case $y = 1$ throws a wrench in the works, since in that case $xy = x$ holds also for values of $x$ which aren't $0$.