Question

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

or a counter example.


(a) A ⊆ ((A∩B)∪C).

(b) (A∪B)∩C = (A∩B)∪C.

(c) (A\B)∩C = (A∩C) \ (B∩C).
​

Answer 1

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

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

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 \\ot \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 \\ot\in B` and
`x \in C`.

`\implies (x \in A\cap C)` and
`x \\ot\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 \\ot\in B \cap C`.

Note that
`x \\ot\in B \cap C` is equivalent to:

• 
  `x \\ot \in B`, OR
• 
  `x \\ot\in C`, OR
• both
  `x \\ot\in B` AND
  `x \\ot \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 \\ot\in B \cap C` is
`x \\ot \in B`.

To reiterate: if
`x \\ot \in C`, then the assumption that
`x \in A \cap C` would not be true any more. Therefore, the only possibility is that
`x \\ot \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)`.