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.

    Let
    [tex]P: \forall x \in S[/tex]
    and
    [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

    CompuChip

    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