# Analysis question on quantifiers

• Jan 29th 2009, 08:49 PM
Skinner
Analysis question on quantifiers
Something really important that I have learned is that the order in which one writes the quantifiers is of paramount importance; writing them in the wrong order can affect the truth value.

Now here's my question: Am I looking at quantifiers in a correct way? Let me give an example:

$(\forall x) (\exists y)$

This says that for all possible x values, there exists a y. For every x value, there is at least one y that satisfies whatever..

Then you have:

$(\exists y) (\forall x)$

This says: some y value such that for every possible x... whatever. To me, this makes y appear more "fixed" than in the first statement, since in the first statement, the y is in the context of all x.

Finally, I have encountered statements like:

$(\forall x) (\exists y) (\forall z)$

How must I look at such a statement?

I have posted a lot of questions about this topic, and I feel like I'm beating a dead horse. However, I really want to ensure that I understand this topic well. I've never taken a class like this before, it seems like a whole new way of thinking.

Thanks
• Jan 29th 2009, 10:05 PM
Quantifiers
Hello Skinner
Quote:

Originally Posted by Skinner
$(\forall x) (\exists y)$

This says that for all possible x values, there exists a y. For every x value, there is at least one y that satisfies whatever..

Correct. For example, if x is a real number, then for all x, there exists a y such that y > x. In other words, there is no largest real number.
Quote:

Originally Posted by Skinner
$(\exists y) (\forall x)$

This says: some y value such that for every possible x... whatever. To me, this makes y appear more "fixed" than in the first statement, since in the first statement, the y is in the context of all x.

Again, I think you are interpreting this correctly; the value of y is chosen before the values of x. For example, if x and y are integers, there exists a y such that for all x, xy = x. (The integer is, of course, y = 1.)
Quote:

Originally Posted by Skinner
$(\forall x) (\exists y) (\forall z)$

How must I look at such a statement?

This is rather harder to come up with a simple example. But you just combine the ideas in the first two examples; it means, of course, what it says, reading from left to right: For all values of x, there exists a value of y such that, for all values of z, such-and-such a statement is true. The following example works, but it may seem a little trivial.

Suppose we are considering elements of the set of non-negative integers: $\mathbb{Z}^+$. Then

$(\forall x) (\exists y) (\forall z)\in \mathbb{Z}^+, yz \le x$

Can you see what this value of $y$ is? $y =0 \Rightarrow \forall z, yz = 0 \le x, \forall x\in \mathbb{Z}^+$

Does that help?

• Jan 30th 2009, 11:06 AM
clic-clac
Quote:

$(\forall x) (\exists y) (\forall z)\in \mathbb{Z}^+, yz \le x$

Take care that in this example, when you chose $y=0$, this choice seems independent from the choice of $x$ (and indeed is also a solution for $\exists y\forall x\forall z\in \mathbb{Z}^+, yz\leq x$ )

An exemple where the permutation is impossible:

$\forall x\exists y\forall z\in \mathbb{R},\ ( y\in \mathbb{Z}\wedge (z

given an $x,\ y=\lfloor x\rfloor$ works, but there is no $y$ in $\mathbb{Z}$ such that for any $x,$ $\forall z(z
• Jan 30th 2009, 11:02 PM
Skinner
I was checking this example:

$
\forall x\exists y\forall z\in \mathbb{R},\ ( y\in \mathbb{Z}\wedge (z < y \Rightarrow z < x))
$

If there exists a fixed y value for every z value, isn't $z false? If so, isn't that implication statement always true?

Isn't y also an element of $\mathbb {Z}$ if y is an element of $\mathbb {R}$?

My mathematical knowledge is very limited, but I thought this would have been true.
• Jan 31st 2009, 01:54 AM
clic-clac
Quote:

If there exists a fixed y value for every z value, isn't $z false? If so, isn't that implication statement always true?
Well, if you fix an integer $y$, there is a infinite amount of real numbers $z$ such that $z

Maybe what you've read is $\forall x\exists y, y\in \mathbb{Z}\wedge ((\forall z, z which is always true because of what you said. But in my formula, the whole implication is under the $\forall z$-scope.
• Jan 31st 2009, 09:51 AM
Skinner
Quote:

Originally Posted by clic-clac
Well, if you fix an integer $y$, there is a infinite amount of real numbers $z$ such that $z

Sure, if you put those restrictions on $\forall z$. But if $\exists y \forall z \in \mathbb{R}, z, that's false, right?

Regarding your formula, $\forall x\exists y\forall z\in \mathbb{R},\ ( y\in \mathbb{Z}\wedge (z < y \Rightarrow z < x))$

You said this was different from what I read: $\forall x\exists y, y\in \mathbb{Z}\wedge ((\forall z, z and I understand why you said that. So how must I look at your formula?

This relates to the fact that I'm trying to understand how the order of the the quantifiers changes the formula.
• Jan 31st 2009, 10:24 AM
clic-clac
Yeah, " $\forall \exists \forall$-formulas " begin to be complex! $\exists y\forall z,\ z is false for real numbers, I agree: there is no real number greater than all the others.

Let's see $\forall x\exists y\forall z\in \mathbb{R},\ ( y\in \mathbb{Z}\wedge (z < y \Rightarrow z < x))$ :

Take a real number, for example $\pi$.

The formula says that there exists a real number $y$ which is an integer and such that: $\forall z\in \mathbb{R}(z So is there such a $y$? What about $\lfloor\pi\rfloor =3$?

Let $z$ be a real number. If $z<3,$ then $z<\pi$. The formula works for $\pi$. But if you take any other real number for $x$, I guess you see that you can find an integer such that what we want. In fact, any integer lower than $x$ is a solution; but of course, it will depend on $x$ ( $3$ is a solution for $\pi$ but not for $\sqrt{2}$).

Hope you see better the meaning of the formula.
• Jan 31st 2009, 12:26 PM
Skinner
OH! Okay, I see it now!

This really helps me to understand what the problem itself is asking me. Okay, for any $x \in \mathbb {R}$, we can pick out an integer $y$. There is always an integer $y$ for every $x$. If $z$ is less than that integer $y$, $z$ is not necessarily less than $x$, making the implication $z>y \Rightarrow z>x$ false.