# Element proof by contradiction

#### kory

##### Junior Member
I'm trying to practice writing proofs and i've been stuck on this one for a while.
For all sets A, B, and C, if $$\displaystyle A \cap B \subseteq C, Then (A - C) \cap B =\varnothing$$

#### Dr.Peterson

##### Elite Member
I'm trying to practice writing proofs and i've been stuck on this one for a while.
For all sets A, B, and C, if $$\displaystyle A \cap B \subseteq C, Then (A - C) \cap B =\varnothing$$
You say you are stuck; where?

Please show us at least how you started, so we don't have to do that part for you; then take it as far as you can so we can see if you are going in a wrong direction, or if what you did can be rescued.

If you couldn't even get started, I'll tell you that I started by just drawing a Venn diagram to see why this is true, before trying to start a proof.

#### pka

##### Elite Member
I'm trying to practice writing proofs and i've been stuck on this one for a while.
For all sets A, B, and C, if $$\displaystyle A \cap B \subseteq C, Then (A - C) \cap B =\varnothing$$
HINT: oppose that $$\exists t\in (A\setminus C)\cap B$$.

#### lex

##### Full Member
Yes, a direct proof is easy, noting that ($$\displaystyle A-C)\subseteq A$$
However, if you want a proof by contradiction as your title implies, then pka's hint is the way to go:
Assume for a contradiction $$\displaystyle \exists \text{ x} \in (A-C) \cap B...$$

#### kory

##### Junior Member
How is this so far:
Suppose not, that is suppose that sets $$\displaystyle A,B, and$$ $$\displaystyle C$$ exist such that $$\displaystyle A \cap B \subseteq C$$ and$$\displaystyle (A-C) \cap B \neq \varnothing$$

Our supposition implies $$\displaystyle \exists x \in (A-C) \cap B$$
By definition of intersection, $$\displaystyle x \in (A-C) \cap B \to x \in(A-C) \land x \in B$$
By definition of difference, $$\displaystyle x \in (A-C) \to x\in A \land x \notin C$$

#### Dr.Peterson

##### Elite Member
How is this so far:
Suppose not, that is suppose that sets $$\displaystyle A,B, and$$ $$\displaystyle C$$ exist such that $$\displaystyle A \cap B \subseteq C$$ and$$\displaystyle (A-C) \cap B \neq \varnothing$$

Our supposition implies $$\displaystyle \exists x \in (A-C) \cap B$$
By definition of intersection, $$\displaystyle x \in (A-C) \cap B \to x \in(A-C) \land x \in B$$
By definition of difference, $$\displaystyle x \in (A-C) \to x\in A \land x \notin C$$
Keep going; you're almost there! Now you have an x that is in A and B, but not in C, ...

#### lex

##### Full Member
Nicely done.
So, the story so far:
$$\displaystyle x\in A \land x \in B \land x \notin C$$
Now use the only other fact given in the question, to get your contradiction.

#### kory

##### Junior Member
We were given $$\displaystyle A \cap B \subseteq C$$
$$\displaystyle A \cap (B \subseteq C) \to x \in A \land x \in B \land x \in C$$
In Summary, $$\displaystyle x \in A \land x\in B \land x \in C \to x \in A \land x\in B \land x \notin C$$
Therefore, $$\displaystyle x \in C \land x \notin C$$ is a contradiction.

correct?

#### Dr.Peterson

##### Elite Member
We were given $$\displaystyle A \cap B \subseteq C$$
$$\displaystyle A \cap (B \subseteq C) \to x \in A \land x \in B \land x \in C$$
In Summary, $$\displaystyle x \in A \land x\in B \land x \in C \to x \in A \land x\in B \land x \notin C$$
Therefore, $$\displaystyle x \in C \land x \notin C$$ is a contradiction.

correct?
That doesn't make any sense to me. The parentheses are meaningless, and a statement about sets can't directly imply anything about a particular element.

What does what you know about your x imply, in light of $$\displaystyle A \cap B \subseteq C$$?

#### lex

##### Full Member
Suppose not, that is suppose that sets A, B and C exist such that $$\displaystyle A \cap B \subseteq C$$ and$$\displaystyle (A-C) \cap B \neq \varnothing$$

Our supposition implies $$\displaystyle \exists x \in (A-C) \cap B$$
By definition of intersection, $$\displaystyle x \in (A-C) \cap B \to x \in(A-C) \land x \in B$$
By definition of difference, $$\displaystyle x \in (A-C) \to x\in A \land x \notin C$$
$$\displaystyle \therefore x\in A \land x \in B \land x \notin C\quad$$(1)

But $$\displaystyle A \cap B \subseteq C$$
and $$\displaystyle A \cap B \subseteq C \to ((x \in A \land x \in B) \to x \in C)$$
$$\displaystyle \therefore x \in C$$
By (1) $$\displaystyle \text{ } x \notin C$$, therefore $$\displaystyle x \in C \land x \notin C$$, which is a contradiction.
Therefore our assumption was incorrect and for all sets A, B, and C, if $$\displaystyle A \cap B \subseteq C \text{ then }(A - C) \cap B =\varnothing$$

Last edited:

#### kory

##### Junior Member
I think I was close. I had:
We were given $$\displaystyle A \cap B \subseteq$$
By definition of intersect, $$\displaystyle x \in A \cap B \to x \in A \land x \in B$$
By definition of specialization, $$\displaystyle x \in A \land x \in B \to x \in C$$
Therefor, $$\displaystyle x \in C \land x \notin C$$ is a contradiction
Therefor $$\displaystyle A \cap B \subseteq C$$ then $$\displaystyle (A-C) \cap B \neq \varnothing$$

#### lex

##### Full Member
You certainly were! - just a few modifications.