1. Limited time only! Sign up for a free 30min personal tutor trial with Chegg Tutors
    Dismiss Notice
Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Homework Help: Proof of a simple logic statement

  1. Feb 28, 2009 #1
    1. The problem statement, all variables and given/known data
    [tex]\forall x \in S <-> \exists x \not \in S[/tex]

    3. The attempt at a solution
    The statement is clearly false.
    I will try to show that by the proof of contradiction.

    [tex]P: \forall x \in S[/tex]
    [tex]Q: \exists x \not\in S [/tex]

    The negation of Q is
    [tex]negQ: \forall x \not\in S [/tex]
    and the negation of P is
    [tex]negP: \exists x \in S [/tex].

    negQ means that all x are not in S, while negP means that there is one x in S.
    This is a contradiction.

    Therefore, the original statement must be false.

    Is my proof correct?
    Last edited: Feb 28, 2009
  2. jcsd
  3. Feb 28, 2009 #2


    User Avatar
    Science Advisor
    Homework Helper

    Your statement is a bit odd.
    "For all x in S, is equivalent to there exists an x such that there exists an S"
    What is on the right hand side? What does x exist in and there exist x and S such that what?

    In first-order logic, your statement is not a well-formed formula :tongue:
  4. Feb 28, 2009 #3
    The statement should be "For all x in S, is equivalent to there does not exist an x in S."

    The rest of the proof is also now as I want.
  5. Mar 2, 2009 #4
    I agree with you. The statement is still false.

    Perhaps, the initial statement should be
    [tex] \forall x \in S <=> \neg(\exists x \not \in S) [/tex]

    It means that: all x in S is equivalent with the negation of the statement that
    there exists x not in S.
Share this great discussion with others via Reddit, Google+, Twitter, or Facebook