Results 1 to 6 of 6

Math Help - Order of Quantifiers changes meaning?

  1. #1
    Member
    Joined
    Oct 2010
    Posts
    95

    Question Order of Quantifiers changes meaning?

    I was told that the order of the quantifiers will change the meaning of a statement. But why is it that sometimes these statements seem like the same even after I changed their quantifiers' order? Am I reading the statements correctly?

    For example, this one...
    \forall a \exists f\; Q(a, f)
    For any airlines a, there exists a flight f.
    So, all airlines have this one particular flight f.

    \exists f \forall a \; Q(a, f)
    There is a flight f that exists on all airlines in a.
    So, there is one particular flight that all airlines in a have it.
    In other words, all airlines have this one particular flight f. Which, is the same thing as the previous statement, isn't it?

    Do the 2 statements mean the same thing?
    Follow Math Help Forum on Facebook and Google+

  2. #2
    Newbie
    Joined
    Jan 2011
    Posts
    16
    The order definitely does matter ... however like many things in set theory or logic it depends on the context

    The first main important thing to say is that the order can go EITHER
    way. The order you use depends on what you want to say. Consider these
    two sample statements, which should be considered to be about
    integers:

    (1) \forall m \exists k \mid k>m which in plain English means: For any integer, there
    is another integer greater than it.

    (2) \exists k \forall m \mid k>m which in plain English means: There is some integer
    that is greater than every integer.

    The only difference is the order of the quantifiers, but the meaning
    is MUCH changed.
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Member
    Joined
    Oct 2010
    Posts
    95
    I think sometimes it is easier to understand in the context of integers because I could imagine the numbers being larger or smaller? But if we say that we apply this in other context such as the one above(the flights and airlines) given in my notes, am I still reading the statements correctly?

    Maybe I should have also stated that [LaTeX ERROR: Convert failed] is defined as where "Flight f is in airline a".

    I am thinking if there is a standard way of reading the statements so that I will always get the correct meaning of what the logic intends to tell be it in any type of context(integers, situation, etc). Otherwise, I find myself always generating different kind of meanings for different sentences of different contexts.
    Follow Math Help Forum on Facebook and Google+

  4. #4
    Newbie
    Joined
    Jan 2011
    Posts
    16
    Ah yes ... if that's what you'd like .. the general rule of thumb is left to right following your first post and mine below it ... it'd be read as follows ...

    For all airlines there exists some flight such that flight f is in airline a
    for all m there exists some k such that k is greater than m

    and

    there exists some flight for all airlines such that flight f is in airline a
    there exists some k for all m such that k is greater than m

    it's about how things are restricted and when .. imagine a bottle neck ... the second statement bottlenecks you really fast and opens up ... while the first statement narrows as you progress through. When I first learned quantifiers I learned them in the context of true and false ...


    Definition. Universal quantifier, \forall x \in X) P(x) Let P(x) be a formula in one variable with universe U. Let X \subseteq U. Let Q be the statement
    ( \forall x \in X ) P(x)
    Then Q is true if for every a \in X, P(a) is true. Otherwise Q is false.


    Definition. Existential quantifier, ( \exists x \in X) P(x) Let P(x) be a formula in one variable with universe U. Let X \subseteq U, X \neq \emptyset . Let Q be the statement
    ( \exists x \in X)  P(x)
    Then Q is true if there is some a \in X for which P(a) is true. Otherwise Q is false. [/tex]


    This might help you a bit to see them ... I can add some more stuff if you'd like
    Follow Math Help Forum on Facebook and Google+

  5. #5
    MHF Contributor
    Joined
    Oct 2009
    Posts
    5,506
    Thanks
    765
    For any airlines a, there exists a flight f.
    So, all airlines have this one particular flight f.
    No, the first sentence says that each airline a may have its own flight f; it does not have to be the same for every airline. In contrast, "There is a flight f that exists on every airline a" says that there is a single flight f that works for every airline a.

    The idea is that is choosing a witness for an existential quantifier, one is allowed to take into account all objects introduced by the preceding universal quantifiers. So, in \forall m\,\exists k\,k>m, one can take m into account while choosing k. For instance, one can take k = m + 1. In contrast, in \exists k\,\forall m\,k>m, there has to be a single k that is greater than all possible m, which is impossible.
    Follow Math Help Forum on Facebook and Google+

  6. #6
    Member
    Joined
    Oct 2010
    Posts
    95
    Thanks imind and emakarov. I am starting to see some light now. I think you made a good point that one can take m into account while choosing k. Thanks a lot!!
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Replies: 0
    Last Post: May 8th 2011, 01:54 PM
  2. quantifiers
    Posted in the Discrete Math Forum
    Replies: 1
    Last Post: November 6th 2009, 08:37 PM
  3. Use of Quantifiers
    Posted in the Discrete Math Forum
    Replies: 0
    Last Post: October 12th 2009, 09:10 AM
  4. Quantifiers
    Posted in the Discrete Math Forum
    Replies: 0
    Last Post: October 10th 2009, 08:57 PM
  5. Replies: 1
    Last Post: August 26th 2009, 08:04 AM

Search Tags


/mathhelpforum @mathhelpforum