Element proof by contradiction

kory

Junior Member
Joined
Mar 8, 2021
Messages
66
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
Joined
Nov 12, 2017
Messages
11,540
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
Joined
Jan 29, 2005
Messages
11,039
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
Joined
Mar 3, 2021
Messages
697
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
Joined
Mar 8, 2021
Messages
66
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
Joined
Nov 12, 2017
Messages
11,540
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
Joined
Mar 3, 2021
Messages
697
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
Joined
Mar 8, 2021
Messages
66
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
Joined
Nov 12, 2017
Messages
11,540
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
Joined
Mar 3, 2021
Messages
697
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
Joined
Mar 8, 2021
Messages
66
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
Joined
Mar 3, 2021
Messages
697
You certainly were! - just a few modifications.
 
Top