I've put together a proof on this, (which I would appreciate being verified), but I also want to know what a false counterexample might be for this? I'm new to discrete mathematics, and I'm honestly not entirely sure how to set up a counterexample, so any push in the right direction would be great.

Proposition: For all sets $A, B$ and $C$, $A \cap (B - C) = (A \cap B) - (A \cap C)$

Proof: We must show that $A \cap (B - C) = (A \cap B) - (A \cap C)$. To do so, we must prove that $A \cap (B - C) \subseteq (A \cap B) - (A \cap C)$ and $(A \cap B) - (A \cap C) \subseteq A \cap (B - C)$.

Part 1: Suppose that x is any element in $A \cap (B - C)$. We must prove that $A \cap (B - C) \subseteq (A \cap B) - (A \cap C)$

By the definition of intersection and the definition of set difference, $x \in A$ and $x \in B$ and $x \notin C$.

Since $x \in A$ and $x \in B$, $x \in (A \cap B)$

Since $x \notin C$, then $x \notin (A \cap C)$

Therefore, since $x \in (A \cap B)$ and $x \notin (A \cap C)$, $x \in (A \cap B) - (A \cap C)$

Part 2: Suppose that $x$ is any element in $(A \cap B) - (A \cap C)$. We must prove that $(A \cap B) - (A \cap C) \subseteq A \cap (B - C)$

Since $x \in (A \cap B)$, by the definition of intersection, $x \in A$ and $x \in B$.

Since $x \notin (A \cap C)$, by the definition of set difference, we know that $x \notin C$.

Since $x \in A$ and $x \in B$ and $x \notin C$, then $x \in A \cap (B - C)$.

Conclusion: Therefore, since the propositions of both part 1 and part 2 are true, the overall proposition must be true.

  • 3
    $\begingroup$ What is the definition of "false counterexample"? $\endgroup$
    – GEdgar
    Jan 28, 2016 at 21:56
  • $\begingroup$ Would I assume that A ∩ (B - C) ≠ (A ∩ B) - (A ∩ C), and then use specific sets of A,B, and C, to show that they ARE in fact equal? Thus proving the counterexample false? $\endgroup$
    – 123
    Jan 28, 2016 at 22:10
  • $\begingroup$ I would just draw a three circle Venn diagram and find the region(s) that represent each side of the equation. Your counterexample could then be a set that is just one element that belongs to the proper ones of $A,B,C$ This is given at the end of the question and verified in the answer. $\endgroup$ Oct 28, 2017 at 14:20

1 Answer 1


Here we give a False counter-example

We assume that we always have the following

$$\color{red}{A \cap (B - C) \not= (A \cap B) - (A \cap C)} \tag{F}$$

We aim to construct a counter-example to the statement (F).

To this end, we consider that our universe is $$E =\{\color{red}{1,2,3,4,5,6,7,8,9,10}\color{blue}{,a,b,c,d,e,f,g,h,i,j}\}$$ We consider the sets, $$A =\{\color{red}{1,2,3,4,5}\color{blue}{,a,b,c,d,i,j}\}$$

$$~~~~~~~B =\{\color{red}{1,2,3,4,9,10}\color{blue}{,a,b,c,d,e,f,g}\}$$

$$C =\{\color{red}{4,5,6,7,8}\color{blue}{,d,e,f,g,h,i,j}\}$$ We have \begin{split} A\cap B&=& \{\color{red}{1,2,3,4}\color{blue}{,a,b,c,d}\}\\ A\cap C &=&\{\color{red}{4,5}\color{blue}{,d,i,j}\}\\ C^c=\complement_E^C &=&\{\color{red}{1,2,3,9,10}\color{blue}{,a,b,c}\}\\ B-C =B\cap C^c&= &\{\color{red}{1,2,3,9,10}\color{blue}{,a,b,c}\}\\ (A\cap C )^c=\complement_E^{A\cap C }&=&\{\color{red}{1,2,3,6,7,8,9,10}\color{blue}{,a,b,c,e,f,g,h}\} \end{split}

We then obtain:

\begin{split} A \cap (B - C) &=&\{\color{red}{1,2,3,4,5}\color{blue}{,a,b,c,d,i,j}\}\cap \{\color{red}{1,2,3,9,10}\color{blue}{,a,b,c}\}\\&=&\{\color{red}{1,2,3}\color{blue}{,a,b,c}\}\\ and\\ (A\cap B)- (A\cap C) &=&A\cap B\cap (A\cap C )^c\\&=&\{\color{red}{1,2,3,4}\color{blue}{,a,b,c,d}\}\cap\{\color{red}{1,2,3,6,7,8,9,10}\color{blue}{,a,b,c,e,f,g,h}\}\\&=&\{\color{red}{1,2,3}\color{blue}{,a,b,c}\} \end{split} From this particular example, realize that $$A \cap (B - C)=\{\color{red}{1,2,3}\color{blue}{,a,b,c}\} =(A\cap B)- (A\cap C).$$

Therefore the statement (F) is False.

I would rather propose another prove only by using Morgan's formulas:

First By definition we have, $$A \cap (B - C) = A \cap( B \cap C^c) \tag{I} $$ on the Other hand,

$$ (A \cap B) - (A \cap C) = (A \cap B) \cap (A \cap C)^c \\= (A \cap B) \cap (A^c \cup C^c) \\=(A \cap B\cap C^c) \cup (A \cap B \cap A^c) $$

But $$(A \cap B \cap A^c)= \emptyset$$

Thus, $$ (A \cap B) - (A \cap C) =(A \cap B\cap C^c) \tag{II} $$

(I) and (II) give $$\color{red}{A \cap (B - C) = A \cap( B \cap C^c) = (A \cap B) - (A \cap C)}$$

Now this prove that statement is true for every set A, B and C


You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .