Tag: Complement

One correct and one incorrect formula for set complements

by RoRi

June 22, 2015

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

Prove relationships between complements, unions and intersections for classes of sets

by RoRi

June 22, 2015

Prove that for a class of sets $\mathcal{F}$ we have,

$B \smallsetminus \bigcup_{A \in \mathcal{F}} A = \bigcap_{A \in \mathcal{F}} (B \smallsetminus A) \qquad \text{and} \qquad B \smallsetminus \bigcap_{A \in \mathcal{F}} A = \bigcup_{A \in \mathcal{F}} (B \smallsetminus A).$

Proof. Let $x$ be an arbitrary element of $B \smallsetminus \bigcup_{A \in \mathcal{F}} A$ . This means that $x \in B$ and $x \notin \bigcup_{A \in \mathcal{F}} A$ , which means that $x$ is not in $A$ for any $A$ in the class $\mathcal{F}$ . Hence, for every $A \in \mathcal{F}$ we have $x \in (B \smallsetminus A)$ (since $x$ is in $B$ no matter what, and $x$ is not in $A$ for any $A$ that we choose, so it must be in $B \smallsetminus A$ ). But, $x \in (B \smallsetminus A)$ for all $A \in \mathcal{F}$ means that $x$ is in the intersection $\bigcap_{A \in \mathcal{F}} (B \smallsetminus A)$ ; and hence, $B \smallsetminus \bigcup_{A \in \mathcal{F}} A \subseteq \bigcap_{A \in \mathcal{F}} (B \smallsetminus A)$ .
For the reverse inclusion, let $x$ be any element in $\bigcap_{A \in \mathcal{F}} (B \smallsetminus A)$ . This means that $x \in (B \smallsetminus A)$ for every $A \in \mathcal{F}$ , i.e., $x \in B$ and $x \notin A$ for every $A \in \mathcal{F}$ . Since $x \notin A$ for every $A$ , we then have $x \notin \bigcup_{A \in \mathcal{F}}$ . Hence, $x \in B \smallsetminus \bigcup_{A \in \mathcal{F}}$ . Therefore, $\bigcap_{A \in \mathcal{F}} (B \smallsetminus A) \subseteq B \smallsetminus \bigcup_{A \in \mathcal{F}} A$ .
Hence, $B \smallsetminus \bigcup_{A \in \mathcal{F}} A = \bigcap_{A \in \mathcal{F}} (B \smallsetminus A)$ . ∎

Proof. Let $x$ be any element of $B \smallsetminus \bigcap_{A \in \mathcal{F}} A$ . This means that $x \in B$ and $x \notin \bigcap_{A \in \mathcal{F}} A$ . Further, $x$ not in the intersection of the sets $A \in \mathcal{F}$ means that there is at least one $A \in \mathcal{F}$ , say $A'$ , such that $x \notin A'$ . Since $x \notin A'$ and $x \in B$ , we know $x \in (B \smallsetminus A')$ . Then we can conclude $x \in \bigcup_{A \in \mathcal{F}} (B \smallsetminus A)$ . Thus, $B \smallsetminus \bigcap_{A \in \mathcal{F}} \subseteq \bigcup_{A \in \mathcal{F}} (B \smallsetminus A)$ .
For the reverse inclusion, we let $x$ be any element in $\bigcup_{A \in \mathcal{F}} (B \smallsetminus A)$ . This means there is at least one $A \in \mathcal{F}$ , say $A'$ , such that $x \in (B \smallsetminus A')$ , which means $x \in B$ and $x \notin A'$ . Since $x \notin A'$ , we know $x \notin \bigcap_{A \in \mathcal{F}} A$ ; therefore, $x \in B \smallsetminus \bigcap_{A \in \mathcal{F}} A$ . Hence, $\bigcup_{A \in \mathcal{F}} (B \smallsetminus A) \subseteq B \smallsetminus \bigcap_{A \in \mathcal{F}} A$ .
Therefore, $B \smallsetminus \bigcap_{A \in \mathcal{F}} A = \bigcup_{A \in \mathcal{F}} (B \smallsetminus A).$ ∎

Prove that the complement of an intersection is the union of the complements

by RoRi

June 22, 2015

Prove that $A \smallsetminus (B \cap C) = (A \smallsetminus B) \cup (A \smallsetminus C)$ .

Proof. First, let $x$ be any element in $A \smallsetminus (B \cap C)$ . By definition of complement, this means that $x \in A$ and $x \notin (B \cap C)$ . Since $x \notin (B \cap C)$ we have either $x \notin B$ or $x \notin C$ which implies, coupled with the fact that $x$ is in $A$ , means $x \in (A \smallsetminus B)$ or $x \in (A \smallsetminus C)$ , respectively. Since $x$ is in at least one of these, $x$ is in the union $(A \smallsetminus B) \cup (A \smallsetminus C)$ . Therefore, $A \smallsetminus (B \cap C) \subseteq (A \smallsetminus B) \cup (A \smallsetminus C)$ .
For the reverse inclusion, let $x$ be an arbitrary element of $(A \smallsetminus B) \cup (A \smallsetminus C)$ . Then, either $x \in (A \smallsetminus B)$ or $x \in (A \smallsetminus C)$ .
If $x \in (A \smallsetminus B)$ , then $x \in A$ and $x \notin B$ ; hence, $x \notin (B \cap C)$ . Therefore, $x$ is in $A \smallsetminus (B \cap C)$ . On the other hand, if $x \in (A \smallsetminus C)$ , then $x \in A$ and $X \notin C$ ; hence, $x \notin (B \cap C)$ . This again implies $x$ is in $A \smallsetminus (B \cap C)$ . Therefore, $(A \smallsetminus B) \cup (A \smallsetminus C) \subseteq A \smallsetminus (B \cap C)$ .
Hence, $A \smallsetminus (B \cap C) = (A \smallsetminus B) \cup (A \smallsetminus C)$ .∎