1. 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:

$\displaystyle (\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:

$\displaystyle (\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:

$\displaystyle (\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

2. Quantifiers

Hello Skinner
Originally Posted by Skinner
$\displaystyle (\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.
Originally Posted by Skinner
$\displaystyle (\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.)
Originally Posted by Skinner
$\displaystyle (\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: $\displaystyle \mathbb{Z}^+$. Then

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

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

Does that help?

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

An exemple where the permutation is impossible:

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

given an $\displaystyle x,\ y=\lfloor x\rfloor$ works, but there is no $\displaystyle y$ in $\displaystyle \mathbb{Z}$ such that for any $\displaystyle x,$ $\displaystyle \forall z(z<y\Rightarrow z<x)$

4. I was checking this example:

$\displaystyle \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 $\displaystyle z<y$ false? If so, isn't that implication statement always true?

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

My mathematical knowledge is very limited, but I thought this would have been true.

5. If there exists a fixed y value for every z value, isn't $\displaystyle z<y$ false? If so, isn't that implication statement always true?
Well, if you fix an integer $\displaystyle y$, there is a infinite amount of real numbers $\displaystyle z$ such that $\displaystyle z<y;\ \text{indeed}\ \forall z\in\{y-a;\ a\in \mathbb{R}^+\},\ z<y.$

Maybe what you've read is $\displaystyle \forall x\exists y, y\in \mathbb{Z}\wedge ((\forall z, z<y)\Rightarrow z<x)$ which is always true because of what you said. But in my formula, the whole implication is under the $\displaystyle \forall z$-scope.

6. Originally Posted by clic-clac
Well, if you fix an integer $\displaystyle y$, there is a infinite amount of real numbers $\displaystyle z$ such that $\displaystyle z<y;\ \text{indeed}\ \forall z\in\{y-a;\ a\in \mathbb{R}^+\},\ z<y.$
Sure, if you put those restrictions on $\displaystyle \forall z$. But if $\displaystyle \exists y \forall z \in \mathbb{R}, z<y$, that's false, right?

Regarding your formula, $\displaystyle \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: $\displaystyle \forall x\exists y, y\in \mathbb{Z}\wedge ((\forall z, z<y)\Rightarrow z<x)$ 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.

7. Yeah, " $\displaystyle \forall \exists \forall$-formulas " begin to be complex! $\displaystyle \exists y\forall z,\ z<y$ is false for real numbers, I agree: there is no real number greater than all the others.

Let's see $\displaystyle \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 $\displaystyle \pi$.

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

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

Hope you see better the meaning of the formula.

8. OH! Okay, I see it now!

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