Proving Set Equivalence Using Set Laws [closed]

$\begingroup$

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?

$\endgroup$ 3

2 Answers

$\begingroup$

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

$\endgroup$ 2 $\begingroup$

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.

$\endgroup$ 1