One correct and one incorrect formula for set complements

Given the two formulas:
$\begin{align*} A - (B - C) &= (A - B) \cup C \\ A - (B \cup C) &= (A-B)-C. \end{align*}$

Identify which one is always correct and which one is sometimes wrong, and prove the result.
Give an additional condition for the incorrect formula to be always true.

The formula $A \smallsetminus (B \smallsetminus C) = (A \smallsetminus B) \cup C$ is false in general.

Proof. Let

$A = \{ 1,2 \}, \quad B = \{ 1 \}, \quad C = \{ 1,2,3 \}.$

Then,

$A \smallsetminus (B \smallsetminus C) = \{ 1,2 \}, \quad \text{but} \quad (A \smallsetminus B) \cup C = \{ 1,2,3 \}.$

Thus, the formula does not hold in this counterexample.∎

The formula $A \smallsetminus (B \cup C) = (A \smallsetminus B) \smallsetminus C$ is correct.
Proof. Let $x$ be any element of $A \smallsetminus (B \cup C)$ . This means $x \in A$ and $x \notin (B \cup C)$ , which in turn means $x \notin B$ and $x \notin C$ . Since $x \in A$ and $x \notin B$ we have $x \in (A \smallsetminus B)$ . Then, since $x \notin C$ , we have $x \in (A \smallsetminus B) \smallsetminus C$ . Thus, $A \smallsetminus (B \cup C) \subseteq (A \smallsetminus B) \smallsetminus C$ .
For the reverse inclusion, let $x$ be any element of $(A \smallsetminus B) \smallsetminus C$ . This gives us $x \in (A \smallsetminus B)$ and $x \notin C$ . The first part in turn gives us $x \in A$ and $x \notin B$ . But then we have $x$ in neither $B$ nor $C$ ; hence, $x \notin (B \cup C)$ . Since $x \in A$ , we then have $x \in A \smallsetminus (B \cup C)$ . Therefore, $(A \smallsetminus B) \smallsetminus C \subseteq A \smallsetminus (B \cup C)$ .
Therefore, $A \smallsetminus (B \cup C) = (A \smallsetminus B) \smallsetminus C$ .∎

To make the first formula in part (a) always correct, we add the condition that $C \subseteq A$ . The claim is then:
If $C \subseteq A$ , then $A \smallsetminus (B \smallsetminus C) = (A \smallsetminus B) \cup C$ .
Proof. Let $x$ be any element in $A \smallsetminus (B \smallsetminus C)$ , then $x \in A$ and $x \notin (B \smallsetminus C)$ . But, $x \notin (B \smallsetminus C)$ means that $x \notin B$ or $x \in C$ (since this is the negation of $x \in (B \smallsetminus)$ which means $x \in B$ and $x \notin C$ , so its negation is $x \notin B$ or $x \in C$ ). So, if $x \notin B$ , then $x \in (A \smallsetminus B)$ and hence $x \in (A \smallsetminus B) \cup C$ . On the other hand, if $x \in C$ , then $x \in (A \smallsetminus B) \cup C$ as well. Hence, $A \smallsetminus (B \cup C) \subseteq (A \smallsetminus B) \cup C$ .
For the reverse inclusion, let $x \in (A \smallsetminus B) \cup C$ . Then $x \in (A \smallsetminus B)$ or $x \in C$ . If $x \in (A \smallsetminus B)$ , then $x \in A$ and $x \notin B$ . Since, $x \notin B$ , then we know $x \notin (B \smallsetminus C)$ (since every $x \in (B \smallsetminus C)$ must be in $B$ ). Therefore, $x \in A \smallsetminus (B \smallsetminus C)$ . On the other hand, if $x \in C$ , then since $C \subseteq A$ (by our additional hypothesis) we know $x \in A$ . Further, since $x \in C$ , we know $x \notin (B \smallsetminus C)$ . Therefore, $x \in A \smallsetminus (B \smallsetminus C)$ . So, $(A \smallsetminus B) \cup C \subseteq A \smallsetminus (B \smallsetminus C)$ .
Therefore, indeed, $A \smallsetminus (B \smallsetminus C) = (A \smallsetminus B) \cup C$ .∎

One comment

March 20, 2020 at 9:52 pm

Anonymous says:

for x in A-(B-C), how come is that equivalent to x in (A-B)UC being that the first affirmation says that x is in A necessarily and the second one means that x is either in C or A but not in B?

for example if A={1,2,3,4} B={2,3,4} and C={3,4,5}

A-(B-C) = A-{2} = {1,3,4} (i.e. (A-B)U(A⋂C))

while when you say

(A-B)UC = {1}UC = {1,3,4,5} (but 5 does not belong to A)

which is the whole point of this affirmation being wrong in the first place

Stumbling Robot

One correct and one incorrect formula for set complements

Related

One comment

Point out an error, ask a question, offer an alternative solution (to use Latex type [latexpage] at the top of your comment): Cancel reply