# Proofs involving Negations and Conditionals

Tags:
1. Feb 11, 2016

### YamiBustamante

Suppose that A\B is disjoint from C and x∈ A . Prove that if x ∈ C then x ∈ B .

So I know that A\B∩C = ∅ which means A\B and C don't share any elements.
But I don't necessarily understand how to prove this. I heard I could use a contrapositive to solve it, but how do I set it up. Which is P and which is Q (for P implies Q, or as the contrapositive: not Q implies not P)?

2. Feb 11, 2016

### RUber

You are looking to prove:
$(x \in C) \implies (x \in B)$
The contrapositive is:
$( x \notin B) \implies (x \notin C)$
Your given (supposed) information will not change.

3. Feb 11, 2016

### YamiBustamante

So here is what I have:
If x∉B then x∉C
So, we can assume x∈A\B and since A\B and C are disjoined, then x∈A\B∩C which is true since x∉C. Would this be correct or is there any error in my logic?

4. Feb 11, 2016

### RUber

I don't think you can say x∈A\B∩C, since you said above that that was the empty set. And, you should not use "since x∉C", because you are trying to prove this for the contrapositive.

x is in A. This was given.
If x is not in B, then, it is in A\B.
C is disjoint from A\B. This was given.
x in A\B should tell you what you need to know about C.

5. Feb 12, 2016

### HallsofIvy

No, that is NOT "what you have", it is you are trying to prove.

Simply that you have assumed what you want to prove!

6. Feb 13, 2016

### Kilo Vectors

I am interested too. I understand that A intersection C would be X. or written as:

A intersection C = ( X IS AN ELEMENT OF A) AND (X IS AN ELEMENT OF C)

[ A and NOT B] Intersection C = NULL = [[(X IS AN ELEMENT OF A) AND (X IS NOT AN ELEMENT OF B)]] AND (X IS AN ELEMENT OF C)

A/B intersection C ^^

this logical statement, i believe can be expanded below through commutative property to become:

[[(X IS AN ELEMENT OF A) AND (X IS AN ELEMENT OF C)]] AND [[(X IS NOT AN ELEMENT OF B) AND (X IS AN ELEMENT OF C)]]

^^ A intersection C intersection C/B = null set.
we already know that a intersection C is x..that intersection C AND NOT B is null means that C and NOT B contains x..therefore B contains X?
http://i.imgur.com/BkaBtjf.png

http://i.imgur.com/EKkKdFu.png

sorry I really try to improve my maths

Last edited: Feb 13, 2016
7. Feb 13, 2016

### Kilo Vectors

is the above post of mine on the right track? ^^

8. Feb 13, 2016

### Staff: Mentor

You are basically right but a little too expressive if you avoid the language of symbols.
First you have to be precise in the wording. NULL is a computer term reserved for, e.g. empty datasets. In mathematics a null set is something different. E.g. a single point as 1 on the line of reals is a null set. So tiny compared to the reals that it cannot be measured. In set theory we say empty set to ∅.

The proposed way of proving the statement was by contradiction.
It means that one cannot derive a false statement from a true statement.
From a false statement you can derive everything. E.g. if $1 = 0$ then for any number $x$ is $x = x \cdot 1 = x \cdot 0 = 0$ which means $0$ is the only number at all, which is false.
Or you can derive a true statement. E.g. if $1=0$ then $1=1-0=0-0=0=1$, which is true.

However from a true statement you can only derive other true statements.

In the above statement it is given that $A$\$B ∩ C = ∅$ and $x∈A$ and $x∈C$ which is the same as $x∈A∩C$.
We need to show that $x∈B$.
So if we assume we have an element ($∃$ meaning there is) $x_0∉B$ and end up with a false statement, then this assumption could not have been true.
The essential part is this: $x_0∈A$ (given) and $x_0∉B$ (assumed), i.e. $x_0∈A$\$B$. But $x_0∈C$ (given) which means $x_0∈A$\$B∩C.$ But this intersection is empty so $x_0$ cannot exist. A contradiction, a false statement.
Therefore our assumption $x_0∉B$ must have been a false statement, too. This means the opposite of it is true. And the opposite statement is any ($∀$ meaning for all) $x∈B$ what we wanted to show.

The negation of there is (∃) is for all (∀) and vice versa.