Non-trivial example of Quantifiers

  • Context: Graduate 
  • Thread starter Thread starter Dragonfall
  • Start date Start date
  • Tags Tags
    Example
Click For Summary

Discussion Overview

The discussion centers around the logical relationship between universal and existential quantifiers, specifically examining the statement \forall x P(x) \rightarrow \exists x P(x) and the conditions under which it may fail. Participants explore the implications of this relationship in the context of formal logic.

Discussion Character

  • Debate/contested

Main Points Raised

  • One participant requests a non-trivial example where \forall x P(x) \rightarrow \exists x P(x) fails.
  • Another participant asserts that the statement is true, explaining that if \forall x P(x) holds, then for any arbitrary x_0, P(x_0) must also hold, thus leading to \exists x P(x) being true. They note that the only scenario where this fails is if the universe of discourse is empty, which they consider trivial.
  • A different participant expresses confusion, suggesting that their intuition aligns with the idea that \forall x P(x) \rightarrow \exists x P(x) would be true whenever \exists x is true.
  • Another participant introduces a thought about decision problems, contrasting no-NP languages with NP languages in terms of universal and existential quantifiers.
  • A later reply indicates that the participant has resolved their confusion and no longer seeks clarification.

Areas of Agreement / Disagreement

Participants exhibit disagreement regarding the existence of non-trivial examples where the statement may fail, with some asserting it is universally true while others express confusion about its implications.

Contextual Notes

Some participants reference the universe of discourse and its implications for the truth of the quantifiers, but the discussion does not resolve the nuances of these definitions or their impact on the logical statements.

Dragonfall
Messages
1,023
Reaction score
5
Can I have a non-trivial example of where [itex]\forall x P(x) \rightarrow \exists x P(x)[/itex] fails?
 
Physics news on Phys.org
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.
 
Dragonfall said:
Can I have a non-trivial example of where [itex]\forall x P(x) \rightarrow \exists x P(x)[/itex] fails?

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.
 
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].
 
Wait, I figured it out. Nevermind.
 

Similar threads

Undergrad Subset definition: universal quantifier over which set?
  • · Replies 33 ·
2
Replies
33
Views
5K
Graduate Quantifying nonlinearity from data
  • · Replies 3 ·
Replies
3
Views
2K
Undergrad Formal derivation of statement from Peano Arithmetic system
  • · Replies 10 ·
Replies
10
Views
2K
High School Translating Abraham Lincoln quote into symbolic logic
  • · Replies 8 ·
Replies
8
Views
4K
MHB Predicate logic with multiple quantifiers
  • · Replies 2 ·
Replies
2
Views
2K
MHB How Do We Find the Logical Negation of Statements?
  • · Replies 6 ·
Replies
6
Views
2K
High School Set Theory Question -- Which one is correct?
  • · Replies 4 ·
Replies
4
Views
2K
Undergrad Negating the uniqueness quantifier
  • · Replies 2 ·
Replies
2
Views
7K
Undergrad Question regarding quantifier statement
  • · Replies 10 ·
Replies
10
Views
1K
High School Why "the conditional in which the antecedent is false" is always true?
  • · Replies 14 ·
Replies
14
Views
3K