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 [MATH]A \cap B \subseteq C, Then (A - C) \cap B =\varnothing [/MATH]
 
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 [MATH]A \cap B \subseteq C, Then (A - C) \cap B =\varnothing [/MATH]
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.
 
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 [MATH]A \cap B \subseteq C, Then (A - C) \cap B =\varnothing [/MATH]
HINT: oppose that \(\exists t\in (A\setminus C)\cap B\).
 
Yes, a direct proof is easy, noting that ([MATH]A-C)\subseteq A[/MATH]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 [MATH] \exists \text{ x} \in (A-C) \cap B...[/MATH]
 
How is this so far:
Suppose not, that is suppose that sets [MATH]A,B, and [/MATH] [MATH]C[/MATH] exist such that [MATH] A \cap B \subseteq C [/MATH] and[MATH] (A-C) \cap B \neq \varnothing [/MATH]
Our supposition implies [MATH]\exists x \in (A-C) \cap B[/MATH]By definition of intersection, [MATH]x \in (A-C) \cap B \to x \in(A-C) \land x \in B[/MATH]By definition of difference, [MATH]x \in (A-C) \to x\in A \land x \notin C[/MATH]
 
How is this so far:
Suppose not, that is suppose that sets [MATH]A,B, and [/MATH] [MATH]C[/MATH] exist such that [MATH] A \cap B \subseteq C [/MATH] and[MATH] (A-C) \cap B \neq \varnothing [/MATH]
Our supposition implies [MATH]\exists x \in (A-C) \cap B[/MATH]By definition of intersection, [MATH]x \in (A-C) \cap B \to x \in(A-C) \land x \in B[/MATH]By definition of difference, [MATH]x \in (A-C) \to x\in A \land x \notin C[/MATH]
Keep going; you're almost there! Now you have an x that is in A and B, but not in C, ...
 
Nicely done.
So, the story so far:
[MATH]x\in A \land x \in B \land x \notin C[/MATH]Now use the only other fact given in the question, to get your contradiction.
 
We were given [MATH]A \cap B \subseteq C [/MATH][MATH]A \cap (B \subseteq C) \to x \in A \land x \in B \land x \in C [/MATH]In Summary, [MATH]x \in A \land x\in B \land x \in C \to x \in A \land x\in B \land x \notin C [/MATH]Therefore, [MATH] x \in C \land x \notin C [/MATH] is a contradiction.

correct?
 
We were given [MATH]A \cap B \subseteq C [/MATH][MATH]A \cap (B \subseteq C) \to x \in A \land x \in B \land x \in C [/MATH]In Summary, [MATH]x \in A \land x\in B \land x \in C \to x \in A \land x\in B \land x \notin C [/MATH]Therefore, [MATH] x \in C \land x \notin C [/MATH] 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 [MATH]A \cap B \subseteq C [/MATH]?
 
Suppose not, that is suppose that sets A, B and C exist such that [MATH] A \cap B \subseteq C [/MATH] and[MATH] (A-C) \cap B \neq \varnothing [/MATH]
Our supposition implies [MATH]\exists x \in (A-C) \cap B[/MATH]By definition of intersection, [MATH]x \in (A-C) \cap B \to x \in(A-C) \land x \in B[/MATH]By definition of difference, [MATH]x \in (A-C) \to x\in A \land x \notin C[/MATH][MATH]\therefore x\in A \land x \in B \land x \notin C\quad[/MATH](1)

But [MATH]A \cap B \subseteq C [/MATH]and [MATH]A \cap B \subseteq C \to ((x \in A \land x \in B) \to x \in C) [/MATH][MATH]\therefore x \in C [/MATH]By (1) [MATH]\text{ } x \notin C [/MATH], therefore [MATH] x \in C \land x \notin C [/MATH], which is a contradiction.
Therefore our assumption was incorrect and for all sets A, B, and C, if [MATH]A \cap B \subseteq C \text{ then }(A - C) \cap B =\varnothing [/MATH]
 
Last edited:
I think I was close. I had:
We were given [MATH] A \cap B \subseteq [/MATH]By definition of intersect, [MATH] x \in A \cap B \to x \in A \land x \in B [/MATH]By definition of specialization, [MATH] x \in A \land x \in B \to x \in C [/MATH]Therefor, [MATH] x \in C \land x \notin C [/MATH] is a contradiction
Therefor [MATH] A \cap B \subseteq C [/MATH] then [MATH] (A-C) \cap B \neq \varnothing [/MATH]
 
Top