Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Non-trivial example of Quantifiers

  1. Aug 2, 2013 #1
    Can I have a non-trivial example of where [itex]\forall x P(x) \rightarrow \exists x P(x)[/itex] fails?
     
  2. jcsd
  3. Aug 2, 2013 #2

    CompuChip

    User Avatar
    Science Advisor
    Homework Helper

    No, because it is a true statement.
    Assume that ##\forall x P(x)##. Let x_0 be arbitrary. Then ##P(x_0)##. ##\exists x P(x)##. QED.

    The only way this can fail is if the universe of discourse is empty, in which case ##\forall x P(x)## is true and ##\exists x P(x)## is false, but I guess this is what you call the trivial case.
     
  4. Aug 2, 2013 #3
    I don't know much formal logic at all, but under any logic that matches my intuition, [itex]\forall x P(x) \rightarrow \exists x P(x)[/itex] would be true whenever [itex]\exists x[/itex] is true.
     
  5. Aug 3, 2013 #4
    Then I'm very confused. I thought no-NP languages are decision problems of the form [itex]\forall x P(x)[/itex] and NP languages are [itex]\exists x P(x)[/itex].
     
  6. Aug 5, 2013 #5
    Wait, I figured it out. Nevermind.
     
Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook




Similar Discussions: Non-trivial example of Quantifiers
  1. Quantifier help? (Replies: 1)

  2. Universal Quantifier (Replies: 4)

Loading...