Question

Which of the following statements is true for all sets A,B and C? Give a proof

Answer 1

Answer:

(a) and (b) are not true in general. Refer to the explanations below for counterexamples.

It can be shown that (c) is indeed true.

Step-by-step explanation:

This explanation will use a lot of empty sets $\phi$ just to keep the counterexamples simple.

(a)

Note that $A \cap B$ can well be smaller than $A$. It should be alarming that the question is claiming $A\!$ to be a subset of something that can be smaller than $\! A$. Here's a counterexample that dramatize this observation:

Consider:

• $A = \left\lbrace 1 \right\rbrace$.
• $B = \phi$ (an empty set, same as $\left\lbrace \right\rbrace$.)
• $C = \phi$ (another empty set.)

The intersection of an empty set with another set should still be an empty set:

$A \cap B = \left\lbrace 1\right\rbrace \cap \left\lbrace\right\rbrace = \left\lbrace\right\rbrace$.

The union of two empty sets should also be an empty set:

$((A \cap B) \cup C) = \left\lbrace\right\rbrace \cup \left\lbrace\right\rbrace = \left\lbrace\right\rbrace$.

Apparently, the one-element set $A = \left\lbrace 1 \right\rbrace$ isn't a subset of an empty set. $A \not \subseteq ((A\cap B) \cup C)$. Contradiction.

(b)

Consider the same counterexample

• $A = \left\lbrace 1 \right\rbrace$.
• $B = \phi$ (an empty set, same as $\left\lbrace \right\rbrace$.)
• $C = \left\lbrace 2 \right\rbrace$ (another empty set.)

Left-hand side:

$(A \cup B) \cap C = \left(\left\lbrace 1 \right\rbrace \cup \left\lbrace \right\rbrace\right) \cap \left\lbrace 2 \right\rbrace\right = \left\lbrace 1 \right\rbrace \cap \left\lbrace 2 \right\rbrace = \left\lbrace \right\rbrace$.

Right-hand side:

$(A \cap B) \cup C = \left(\left\lbrace 1 \right\rbrace \cap \left\lbrace \right\rbrace\right) \cup \left\lbrace 2 \right\rbrace\right = \left\lbrace \right\rbrace \cup \left\lbrace 2 \right\rbrace = \left\lbrace 2 \right\rbrace$.

Apparently, the empty set on the left-hand side $\left\lbrace \right\rbrace$ is not the same as the $\left\lbrace 2 \right\rbrace$ on the right-hand side. Contradiction.

(c)

Part one: show that left-hand side is a subset of the right-hand side.

Let $x$ be a member of the set on the left-hand side.

$x \in (A \backslash B) \cap C$.

$\implies x\in A \backslash B$ and $x \in C$ (the right arrow here reads "implies".)

$\implies x \in A$ and $x \not\in B$ and $x \in C$.

$\implies (x \in A\cap C)$ and $x \not\in B \cap C$.

$\implies x \in (A \cap C) \backslash (B \cap C)$.

Note that $x \in (A \backslash B) \cap C$ (set on the left-hand side) implies that $x \in (A \cap C) \backslash (B \cap C)$ (set on the right-hand side.)

Therefore:

$(A \backslash B) \cap C \subseteq (A \cap C) \backslash (B \cap C)$.

Part two: show that the right-hand side is a subset of the left-hand side. This part is slightly more involved than the first part.

Let $x$ be a member of the set on the right-hand side.

$x \in (A \cap C) \backslash (B \cap C)$.

$\implies x \in A \cap C$ and $x \not\in B \cap C$.

Note that $x \not\in B \cap C$ is equivalent to:

• $x \not \in B$, OR
• $x \not\in C$, OR
• both $x \not\in B$ AND $x \not \in C$.

However, $x \in A \cap C$ implies that $x \in A$ AND $x \in C$.

The fact that $x \in C$ means that the only possibility that $x \not\in B \cap C$ is $x \not \in B$.

To reiterate: if $x \not \in C$, then the assumption that $x \in A \cap C$ would not be true any more. Therefore, the only possibility is that $x \not \in B$.

Therefore, $x \in (A \backslash B)\cap C$.

In other words, $x \in (A \cap C) \backslash (B \cap C) \implies x \in (A \backslash B)\cap C$.

$(A \cap C) \backslash (B \cap C) \subseteq (A \backslash B)\cap C$.

Combine these two parts to obtain: $(A \backslash B) \cap C = (A \cap C) \backslash (B \cap C)$.