# 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

Staff Emeritus
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.