I am trying to understand what $\forall$ and $\exists$ mean. Please consider the following expression.
$$ \forall x \, \exists y \, \forall z \, \left( z = \frac{x-y}{3} \right) $$
I claim that the above statement is false because when $x = 2$ is selected and $y = 0$ is
selected we have:
$$ \forall z \, \left( z = \frac{2}{3} \right) $$ which is not true for all $z$
Also consider the following expression.
$$ \forall x \, \forall z \, \exists y \, \left( z = \frac{x-y}{3} \right) $$ I claim this is true because
we can always set $y = x – 3z$.
It appears to me that the order of the variables does matter. That is,
$\forall x \, \exists y \, \forall z$ has a different meaning than
$ \forall x \, \forall z \, \exists y \, $. Am I right?
Logic – How Does Order Matter with \forall and \exists in Multiple Variables?
arithmeticlogic
Related Solutions
The two statements are equivalent, the reason why we write it that way it is because it is easier to deal/prove it. It is irrelevant which way it is easier to say it, the important thing is being able to use.
Just consider the statement $\exists x \in \mathbb Z, x^2+(x+1)^2 \mbox{ is even}$. This is not true, now try to show that this is false.
Try to prove separately each of the following two statements:
- $\not\exists x \in \mathbb Z, x^2+(x+1)^2 \mbox{ is even}$
- $\forall x \in \mathbb Z, x^2+(x+1)^2 \mbox{ is odd}$
It is easier to deal with the second one.
Yes.
One way to prove this is by using a proof tree. You start with the negation of the formula in question then apply a series of contradiction hunting rules to show that, no matter what, that negation is false, like so:
This tree was generated here.
Best Answer
One way to think of it is as a game where if you assert a sentence is true, I get to pick all the variables that have $\forall$ in an effort to make the sentence false and you get to choose the $\exists$ variables in an effort to make the sentence true. We pick in the order the quantifiers come. In your example, if the quantifiers are $\forall x \exists y \forall z$, I pick $x$, then you pick $y$ and finally I pick $z$. For your sentence, it is easy to see I can always pick a $z$ that makes it false. If the quantifiers are $\forall x \forall z \exists y$ I have to pick $x$ and $z$ before you pick $y$. You can rearrange the sentence to $y=x-3z$, so you can make it true no matter which $x,z$ I pick. The first version is false, the second is true, so clearly the order of quantifiers matters.