Home » Blog » One correct and one incorrect formula for set complements

One correct and one incorrect formula for set complements

  1. 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.

  2. Give an additional condition for the incorrect formula to be always true.

  1. The formula A \smallsetminus (B \smallsetminus C) = (A \smallsetminus B) \cup C is false in general.
  2. 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.∎

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

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