# Homework Help: Proof of a simple logic statement

1. Feb 28, 2009

### soopo

1. The problem statement, all variables and given/known data
$$\forall x \in S <-> \exists x \not \in S$$

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

Let
$$P: \forall x \in S$$
and
$$Q: \exists x \not\in S$$

The negation of Q is
$$negQ: \forall x \not\in S$$
and the negation of P is
$$negP: \exists x \in S$$.

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. Feb 28, 2009

### CompuChip

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:

3. Feb 28, 2009

### soopo

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.

4. Mar 2, 2009

### soopo

I agree with you. The statement is still false.

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

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