Results 1 to 8 of 8

Math Help - Analysis question on quantifiers

  1. #1
    Junior Member
    Joined
    Nov 2007
    Posts
    28

    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
    Follow Math Help Forum on Facebook and Google+

  2. #2
    MHF Contributor
    Grandad's Avatar
    Joined
    Dec 2008
    From
    South Coast of England
    Posts
    2,570
    Thanks
    1

    Quantifiers

    Hello Skinner
    Quote Originally Posted by Skinner View Post
     (\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 View Post
     (\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 View Post
     (\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?

    Grandad
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Senior Member
    Joined
    Nov 2008
    From
    Paris
    Posts
    354
    (\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<y\Rightarrow z<x))

    given an x,\ y=\lfloor x\rfloor works, but there is no y in \mathbb{Z} such that for any x, \forall z(z<y\Rightarrow z<x)
    Follow Math Help Forum on Facebook and Google+

  4. #4
    Junior Member
    Joined
    Nov 2007
    Posts
    28
    I was checking this example:


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

    If there exists a fixed y value for every z value, isn't  z<y 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.
    Follow Math Help Forum on Facebook and Google+

  5. #5
    Senior Member
    Joined
    Nov 2008
    From
    Paris
    Posts
    354
    If there exists a fixed y value for every z value, isn't z<y 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<y;\ \text{indeed}\ \forall z\in\{y-a;\ a\in \mathbb{R}^+\},\ z<y.

    Maybe what you've read is \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 \forall z-scope.
    Last edited by clic-clac; January 31st 2009 at 01:55 AM. Reason: cor
    Follow Math Help Forum on Facebook and Google+

  6. #6
    Junior Member
    Joined
    Nov 2007
    Posts
    28
    Quote Originally Posted by clic-clac View Post
    Well, if you fix an integer y, there is a infinite amount of real numbers z such that z<y;\ \text{indeed}\ \forall z\in\{y-a;\ a\in \mathbb{R}^+\},\ z<y.
    Sure, if you put those restrictions on  \forall z . But if  \exists y \forall z \in \mathbb{R}, z<y , 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<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.
    Follow Math Help Forum on Facebook and Google+

  7. #7
    Senior Member
    Joined
    Nov 2008
    From
    Paris
    Posts
    354
    Yeah, " \forall \exists \forall-formulas " begin to be complex! \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 \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<y\Rightarrow z<\pi). 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.
    Follow Math Help Forum on Facebook and Google+

  8. #8
    Junior Member
    Joined
    Nov 2007
    Posts
    28
    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.
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. quantifiers
    Posted in the Discrete Math Forum
    Replies: 4
    Last Post: August 2nd 2011, 02:10 AM
  2. Replies: 1
    Last Post: August 26th 2009, 08:04 AM
  3. Very simple question about quantifiers.
    Posted in the Discrete Math Forum
    Replies: 1
    Last Post: March 4th 2009, 09:19 PM
  4. Analysis question - quantifiers
    Posted in the Calculus Forum
    Replies: 2
    Last Post: January 25th 2009, 08:26 PM
  5. Quantifiers question
    Posted in the Discrete Math Forum
    Replies: 1
    Last Post: January 31st 2008, 10:25 AM

Search Tags


/mathhelpforum @mathhelpforum