- Thread starter kory
- Start date

- Joined
- Nov 12, 2017

- Messages
- 11,540

You say you are stuck; where?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 \)

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.

- Joined
- Jan 29, 2005

- Messages
- 11,039

HINT: oppose that \(\exists t\in (A\setminus C)\cap B\).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 \)

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...\)

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\)

- Joined
- Nov 12, 2017

- Messages
- 11,540

Keep going; you're almost there! Now you have an x that is in A and B, but not in C, ...

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\)

\(\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?

- Joined
- Nov 12, 2017

- Messages
- 11,540

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.

\(\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?

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

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 \)

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:

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 \)