I am having trouble proving set equivalence for the following question:

$$A \setminus A \cap B=A \cap B'$$

I understand that both sides are equivalent, however I am struggling to use set laws to prove this. I was wondering how set laws can be applied to this question to prove that it is true?


closed as off-topic by Xander Henderson, Henrik, max_zorn, user21820, Lord Shark the Unknown Aug 3 '18 at 8:12

This question appears to be off-topic. The users who voted to close gave this specific reason:

  • "This question is missing context or other details: Please improve the question by providing additional context, which ideally includes your thoughts on the problem and any attempts you have made to solve it. This information helps others identify where you have difficulties and helps them write answers appropriate to your experience level." – Xander Henderson, Henrik, max_zorn, user21820, Lord Shark the Unknown
If this question can be reworded to fit the rules in the help center, please edit the question.

  • $\begingroup$ Please, use MathJax (i.e. LaTeX commands) for mathematical notations. $\endgroup$ – Taroccoesbrocco Aug 3 '18 at 2:15
  • 1
    $\begingroup$ Write the left hand side as $A\cap (A\cap B)'$. $\endgroup$ – John Douma Aug 3 '18 at 2:24
  • 3
    $\begingroup$ Which "Set Laws" are you able to use for this? $\endgroup$ – Graham Kemp Aug 3 '18 at 3:01

\begin{align} &A\setminus (A\cap B) \\ &= A \cap (A\cap B)^c \\ &=A\cap (A^c\cup B^c) \\ &= (A \cap A^c)\cup (A\cap B^c) \\ &= \emptyset\cup (A\cap B^c) \\ &=(A\cap B^c). \end{align}

Let's see how we can justify these guys.

Equality 1: is an application of the defn of "setminus". That is, $X\setminus Y= X \cap Y^c$

Equality 2: Is De Morgan's Law.

Equality 3: This would be justified as "Intersection distributes over unions" that is, $X\cap (Y \cup Z) = (X \cap Y) \cup (X \cap Z)$.

Equality 4: Follows from the definition of a complement. $X^c \cap X=X \cap X^c=\emptyset$

Equality 5: Follows from the definition of the emptyset. $X \cup \emptyset =\emptyset \cup X=X$

  • 1
    $\begingroup$ I've edited your answer to use the align environment, which (I think) makes it a lot easier to read). If you object, please roll back the edit (I thought you might like to know how to use that environment, and comments aren't great for such things). You should also be able to add line-breaks into MathJax equations, eg. $$ foo \\ bar $$ will typeset as $$ foo \\ bar $$ $\endgroup$ – Xander Henderson Aug 3 '18 at 2:29
  • $\begingroup$ Great. Thanks. I will use align in the future. I have noticed that alot of people prefer to have the first line with an equality but I think it reads nicer with the first line as an expression and all the subsequent lines starting with $=blah$. Anyway. I appreciate it. $\endgroup$ – Mason Aug 3 '18 at 2:32

The basics for proving that two sets, $A$ and $B$, are equal is to show that $A \subseteq B$, so that within some universal set, $U$, $\forall x, x \in A \implies x \in B$ , and $B \subseteq A$, so that $\forall x, x \in B \implies x \in A$. If both sets are contained with one another, they must be the same set, in the same way that, for any two real numbers, $x \leq y \wedge x \geq y \implies x = y$.

To prove this, take some arbitrary element in the left-hand side and prove that it is also an element of the right-hand side. Since the element is arbitrary, it also holds for any element of that set. This establishes that the left set is a subset of the right set. Then, establish the same in the opposite direction.

Proposition. $A \setminus (A \cap B) \subseteq A \cap B^c$

Take $x \in A \setminus (A \cap B)$. So, by definition of the set-theoretic difference, $x \in A$ and $x \not \in A \cap B$. Since $x \not \in A \cap B$, $x \not \in A$ or $x \not \in B$. But, $x \in A$, so $x \not \in A$ would establish a contradiction. So, clearly, $x \not \in B$. Then, by the definition of a set complement, $x \in B^c$. So, we've established $x \in A$ and $x \in B^c$. So, by the definition of the intersection of sets, $x \in A \cap B^c$. So, $x \in A \setminus (A \cap B) \implies x \in A \cap B^c$. Therefore, $A \setminus (A \cap B) \subseteq A \cap B^c$.

Let's do the same in the opposite direction. I'd recommend doing this as an exercise before reading the proof below.

Proposition. $A \cap B^c \subseteq A \setminus (A \cap B)$

Let $y \in A \cap B^c$. By the definition of set intersection, $y \in A$ and $y \in B^c$. Since $y \in B^c$, $y \not \in B$. So, clearly, $y \not \in A \cap B$, as this only requires $y \not \in A$ or $y \not \in B$ (DeMorgan's Law, though this is a somewhat transformed version of it). So, we're done: $y \in A$ but $y \not \in A \cap B$, so $y \in A \setminus (A \cap B)$, so $y \in A \cap B^c \implies y \in A \setminus (A \cap B)$, and $A \setminus (A \cap B) \subseteq A \cap B^c$.

So, both sets are subsets of each other, and thus the same set.

  • $\begingroup$ +1. I suppose answering this question well hinges on what the OP means when they use the expression "set laws." $\endgroup$ – Mason Aug 3 '18 at 2:42

Not the answer you're looking for? Browse other questions tagged or ask your own question.