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$ .∎

4 comments

October 26, 2023 at 8:43 am

Broaden says:

Can a) get proved this way?
A\setminus\left(B\cup C\right) =\{x|x\in A,x\notin\left(B\cup C\right)\} =\{x|x\in A,x\notin B,\ x\notin C\}\ =\{x|x\in\left(A\setminus B\right),x\notin C\} =\left(A\setminus B\right)\setminus C

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

- June 12, 2024 at 2:00 pm
  
  Anonymous says:
  
  k
  
- June 12, 2024 at 2:04 pm
  
  Anonymous says:
  
  (A-B)UC is the set of elements that belong to (A-B) or C or both. That is, the
  set of all elements that belong to at least one of the sets (A-B),C. Its not {1,3,4,5}

Stumbling Robot

One correct and one incorrect formula for set complements

Related

4 comments

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