Using double inclusion to show $(A △ B) ∪ C = (A ∪ C) △ (B \setminus C)$

Question

Could someone please tell me if I have used double inclusion correctly to prove $(A △ B) ∪ C = (A ∪ C) △ (B \setminus C)$?

(NOTE: "$△$" denotes symmetric difference or exclusive or, i.e. $A △ B = (A ∪ B) \setminus (A ∩ B) = (A \setminus B) \cup (B \setminus A)$.)

Showing $L ⊆ R$:

Let $x ∈ (A △ B) ∪ C$.

By the definition of union, this means that either x is in $C$ (case 3) or in $A \setminus B$ (case 1) or in $B \setminus A$ (case 2).

1. If $x ∈ C$, then $x ∈ A ∪ C$, therefore, $x ∈ (A ∪ C) △ (B \setminus C)$.
2. If $x ∈ A \setminus B$, then x ∈ A ∪ C, therefore, $x ∈ (A ∪ C) △ (B \setminus C)$.
3. If $x ∈ B \setminus A$, then x ∈ B, but $x \notin A$, which implies $x \notin A ∪ C$, which implies $x \notin C$, which implies $x ∈ B \setminus C$. Therefore, $x ∈ (A ∪ C) △ (B \setminus C)$

Showing $L ⊇ R$:

Let $x ∈ (A ∪ C) △ (B \setminus C)$.

By the definition of symmetric difference, this means that x is in $(A ∪ C) \setminus (B \setminus C)$ (case 1) or x is in $(B \setminus C) \setminus (A ∪ C)$ (case 2).

1. By De Morgan's law, $x ∈ (A ∪ C) \setminus (B \setminus C) \iff x ∈ (A ∪ C) \land (\lnot(x \in B) \lor x \in C)$. So, if $x ∈ (A ∪ C) \setminus (B \setminus C)$, then either $x ∈ A \setminus B$ (case 1.1) or $x \in C$ (case 1.2).

• 1.1. If $x ∈ A \setminus B$, then $x ∈ (A △ B)$, which implies $x ∈ (A △ B) ∪ C$.
• 1.2. If $x ∈ C$, then $x ∈ (A △ B) ∪ C$.

2. By De Morgan's law, $x ∈ (B \setminus C) \setminus (A ∪ C) \iff x ∈ (B \setminus C) \land \lnot(x \in A ∪ C)$. $x ∈ (B \setminus C)$ implies $x ∈ B$ and $\lnot(x \in A ∪ C)$ implies $x \notin A$. So we have $x \in B$ and $x \notin A$, which implies $x \in (A △ B)$ and therefore, $x \in (A △ B) ∪ C$.

---

I'm especially unsure about step 2 of $L ⊇ R$. Any guidance would be greatly appreciated, as this is my first time using double inclusion.

---

EDIT: Here's my second attempt. I’ve only included the first half for now, since it ended up being way longer and I’m not sure if it’s correct. But I’ve tried to be more systematic this time.

Some questions that came up:

• Is it ok to use logical equivalences to simplify expressions as I have done in cases 1 and 2? None of the examples of double inclusion I've come across use them, so I don't know if it's cheating.
• I’m not sure about cases 1.3, 2.3 and 3.3. They each simplify to either $x ∈ C$ or $x ∉ C$, but since they contain contradictions, shouldn't they evaluate to the empty set? If so, then we still have $x ∈ (A ∪ C) △ (B \setminus C)$ in each of these cases, since the empty set is a subset of every set.

Proof: (first-half only)

We want to show $(A △ B) ∪ C = (A ∪ C) △ (B \setminus C)$

We start by showing $L ⊆ R$.

Let $x ∈ (A △ B) ∪ C$. Then either $x ∈ (A △ B)$ (case 1) or $x ∈ C$ (case 2) or both (case 3).

• Case 1: x ∈ (A △ B) ∧ x ∉ C.

  \begin{align*} x ∈ (A △ B) ∧ x ∉ C & \iff (x ∈ A \setminus B ∧ x ∉ C) \lor (x ∈ B \setminus A ∧ x ∉ C) &&\text{(distributivity)} \\& \iff (x ∈ A ∧ x ∉ B ∧ x ∉ C) \lor (x ∈ B ∧ x ∉ A ∧ x ∉ C) &&\text{(def of $\setminus$)} \end{align*}

  • Case 1.1: $x ∈ A ∧ x ∉ B ∧ x ∉ C$

    Since $x ∈ A$, $x ∈ A ∪ C$.
    Since $x ∉ B$, $x ∉ B \setminus C$.
    So, we have $x ∈ (A ∪ C) △ (B \setminus C)$.

  • Case 1.2: $x ∈ B ∧ x ∉ A ∧ x ∉ C$

    Since $x ∈ B$ and $x ∉ C$, $x ∈ B \setminus C$.
    Since $x ∉ A$ and $x ∉ C$, $x ∉ (A ∪ C)$.
    So, we have $x ∈ (A ∪ C) △ (B \setminus C)$.

  • Case 1.3: $(x ∈ A ∧ x ∉ B ∧ x ∉ C) ∧ (x ∈ B ∧ x ∉ A ∧ x ∉ C)$.

    \begin{align*} (x ∈ A ∧ x ∉ B ∧ x ∉ C) ∧ (x ∈ B ∧ x ∉ A ∧ x ∉ C) \iff x ∉ C &&\text{(from associativity, idempotent and contradiction laws)} \end{align*}

    Not sure about this. I feel like the contradictions in the unsimplified expression mean that we would end up with $x ∈ Ø$, and so again we have $x ∈ (A ∪ C) △ (B \setminus C)$, since $Ø \subseteq (A ∪ C) △ (B \setminus C)$.

• Case 2: $x ∉ (A △ B) ∧ x ∈ C$.

  \begin{align*} x ∉ (A △ B) ∧ x ∈ C & \iff ¬(x ∈ A \setminus B \lor x ∈ B \setminus A) ∧ x ∈ C \\& \iff ¬[(x ∈ A ∧ ¬(x ∈ B)) \lor (x ∈ B ∧ ¬(x ∈ A))] ∧ x ∈ C &&\text{(def of $\setminus$)} \\& \iff ¬(x ∈ A ∧ ¬(x ∈ B)) ∧ ¬(x ∈ B ∧ ¬(x ∈ A)) ∧ x ∈ C &&\text{(De Morgan)} \\& \iff (¬(x ∈ A) \lor x ∈ B) ∧ (¬(x ∈ B) \lor x ∈ A) ∧ x ∈ C &&\text{(De Morgan)} \\& \iff [¬(x ∈ A) ∧ (¬(x ∈ B) \lor x ∈ A)] \lor [x ∈ B ∧ (¬(x ∈ B) \lor x ∈ A)] ∧ x ∈ C &&\text{(distributivity)} \\& \iff [(¬(x ∈ A) ∧ ¬(x ∈ B)) \lor (¬(x ∈ A) ∧ x ∈ A)] \lor [(x ∈ B ∧ ¬(x ∈ B)) \lor (x ∈ B ∧ x ∈ A)] ∧ x ∈ C &&\text{(distributivity)} \\& \iff [(¬(x ∈ A) ∧ ¬(x ∈ B)) \lor (x ∈ B ∧ x ∈ A)] ∧ x ∈ C &&\text{(P ∨ ⊥ ⟺ P)} \\& \iff [(¬(x ∈ A) ∧ ¬(x ∈ B)) ∧ x ∈ C] \lor [(x ∈ B ∧ x ∈ A) ∧ x ∈ C] &&\text{(distributivity)} \\& \iff [¬(x ∈ A) ∧ ¬(x ∈ B) ∧ x ∈ C] \lor [x ∈ B ∧ x ∈ A ∧ x ∈ C] &&\text{(associativity)} \end{align*}

  • Case 2.1: $¬(x ∈ A) ∧ ¬(x ∈ B) ∧ x ∈ C$

    Since $x ∈ C$, $x ∈ A ∪ C$.
    Since $x ∉ B$, $x ∉ B \setminus C$.
    So, we have $x ∈ (A ∪ C) △ (B \setminus C)$.

  • Case 2.2: $x ∈ B ∧ x ∈ A ∧ x ∈ C$

    Since $x ∈ A$ and $x ∈ C$, $x ∈ A ∪ C$.
    Since $x ∈ B$ and $x ∈ C$, $x ∉ B \setminus C$.
    So, we have $x ∈ (A ∪ C) △ (B \setminus C)$.

  • Case 2.3: $[¬(x ∈ A) ∧ ¬(x ∈ B) ∧ x ∈ C] ∧ [x ∈ B ∧ x ∈ A ∧ x ∈ C]$

    Like case 1.3, this simplifies to $x ∈ C$, but shouldn't it be the empty set?

• Case 3: $x ∈ (A △ B) ∧ x ∈ C$.

  \begin{align*} x ∈ (A △ B) ∧ x ∈ C & \iff (x ∈ A \setminus B ∧ x ∈ C) \lor (x ∈ B \setminus A ∧ x ∈ C) &&\text{(distributivity)} \\& \iff (x ∈ A ∧ x ∉ B ∧ x ∈ C) \lor (x ∈ B ∧ x ∉ A ∧ x ∈ C) &&\text{(def of $\setminus$)} \end{align*}

  • Case 3.1: $x ∈ A ∧ x ∉ B ∧ x ∈ C$

    Since $x ∈ A$ and $x ∈ C$, $x ∈ A ∪ C$.
    Since $x ∉ B$, $x ∉ B \setminus C$.
    So, we have $x ∈ (A ∪ C) △ (B \setminus C)$.

  • Case 3.2: $x ∈ B ∧ x ∉ A ∧ x ∈ C$

    Since $x ∈ B$ and $x ∈ C$, $x ∉ B \setminus C$.
    Since $x ∈ C$, $x ∈ A ∪ C$.
    So we have $x ∈ (A ∪ C) △ (B \setminus C)$.

  • Case 3.3: $(x ∈ A ∧ x ∉ B ∧ x ∈ C) ∧ (x ∈ B ∧ x ∉ A ∧ x ∈ C)$

    Same as case 2.3.

Answer 1

There are a number of errors in the first part of your proof, so I'm going to just deal with those in this answer.

1. If $x ∈ C$, then $x ∈ A ∪ C$, therefore, $x ∈ (A ∪ C) △ (B \setminus C)$.

This is sloppy. Symmetric differences remove part of the sets, so $x\in A$ does not imply that $x\in A\Delta B$. $x\in A\cup C$ is OK but you also need to note that $x\not\in B\setminus C$ before you can plonk it into that symmetric difference.

2. If $x ∈ A \setminus B$, then x ∈ A ∪ C, therefore, $x ∈ (A ∪ C) △ (B \setminus C)$.

Similar, you need to note that it's not in $B$, which is obvious, but the symmetric difference does not contain all of $A\cup C$, so you do need to note it.

3. If $x ∈ B \setminus A$, then x ∈ B, but $x \notin A$, which implies $x \notin A ∪ C$, which implies $x \notin C$

No it does not imply $x\notin A\cup C$, you've completely derailed here. It does imply that $x\notin A\cap C$ though.

, which implies $x ∈ B \setminus C$. Therefore, $x ∈ (A ∪ C) △ (B \setminus C)$

Answer 2

[2022-10-10] Some information added with respect to one of OPs comments.

---

Here I'm just referring to OPs second attempt starting with the EDIT: part. We want to show the identity \begin{align*} \color{blue}{\left(A\triangle B\right)\cup C = (A\cup C)\triangle (B\setminus C)}\tag{1} \end{align*} by double inclusion $\subseteq$ and $\supseteq$. When starting with the left-to-right inclusion part $\subseteq$ of (1) we consider \begin{align*} \left(x\in(A\triangle B)\right)\vee \left(x\in C\right)\tag{2} \end{align*}

Some notes:

• In order to break down a union as in expression (2) it is common to consider just the two cases \begin{align*} (x\in (A\triangle B))\vee (x\in C) \end{align*} It is rather cumbersome to represent (2) as disjoint union of three subsets and analyse each of them which is done in cases 1 to 3. \begin{align*} &\left(\left(x\in\left(A\triangle B\right)\right)\wedge \left(x\in C\right)\right)\qquad\qquad\rightarrow\qquad\text{cases 3.1, 3.2}\\ &\quad\vee\left(\left(x\in\left(A\triangle B\right)\right)\wedge\left(x \not \in C\right)\right)\qquad\rightarrow\qquad\text{cases 1.1, 1.2}\\ &\quad\vee\left(\left(x\not \in\left(A\triangle B\right)\right)\wedge \left(x \in C\right)\right)\qquad\rightarrow\qquad\text{cases 2.1, 2.2}\\ \end{align*} This corresponds to a partition of the set in (2) into \begin{align*} &x\in\left(A\triangle B\right)\cup C \quad\Longleftrightarrow\\ &\quad x\in\left(\left(A\triangle B\right)\cap C\right) \cup\left(\left(A\triangle B\right)\cap C^c\right) \cup \left(\left(A\triangle B\right)^c\cap C\right)\tag{3}\\ \end{align*}

• Note the cases 1.3, 2.3 and 3.3 are not relevant. For instance 1.3 considers \begin{align*} &(x \in A \wedge x \not\in B \wedge x \not\in C) \wedge (x \in B \wedge x \not\in A \wedge x \not\in C)\\ &\qquad\Longrightarrow\qquad x\in A\cap A^c=\emptyset \end{align*} which means this case considers the empty set only and so it can be removed. The same holds for the cases 2.3 and 3.3.

• In order to reduce the complex looking expressions when using the logical operators $\wedge$ and $\vee$, it might be more convenient to stick with the set notation at least for some parts of the derivation. For instance we can write Case 2 following your steps but with somewhat less cumbersome notation as \begin{align*} \color{blue}{\left(A\triangle B\right)^c\cap C} &=\left(\left(A\setminus B\right)\cup\left(B\setminus A\right)\right)^c\cap C\\ &=\left(A\cap B^c\right)^c\cap\left(B\cap A^c\right)^c\cap C\\ &=\left(A^c\cup B\right)\cap\left(B^c\cup A\right)\cap C\\ &=\left(\left(A^c\cap\left(B^c\cup A\right)\right)\cup\left(B\cap\left(B^c\cup A\right)\right)\right)\cap C\\ &=\left(\left(A^c\cap B^c\right)\cup\left(A^c\cap A\right)\right) \cup\left(\left(B\cap B^c\right)\cup\left(B\cap A\right)\right)\cap C\\ &=\left(\left(A^c\cap B^c\right)\cup\left(B\cap A\right)\right)\cap C\\ &\,\,\color{blue}{=\left(A^c\cap B^c\cap C\right)\cup\left(A\cap B\cap C\right)}\tag{4}\\ \end{align*}

  • The subcases 2.1 and 2.2 can now be derived from (4) as in OPs proof. The subcase 2.3 is not relevant and can be skipped.

Alternate approach:

In fact we can show the validity of (1) by sticking on the set notation as in (4). We start with the left-hand side of (1) and obtain \begin{align*} \color{blue}{\left(A\triangle B\right)\cup C} &=\left(\left(A\setminus B\right)\cup\left(B\setminus A\right)\right)\cup C\\ &=\left(\left(A\cap B^c\right)\cup\left(B\cap A^c\right)\right)\cup C\\ &\,\,\color{blue}{=\left(A\cap B^c\right)\cup\left(A^c\cap B\right)\cup C}\tag{5.1}\\ \end{align*} Similarly we transform the right-hand side of (1) and get \begin{align*} &\color{blue}{\left(A\cup C\right)\triangle\left(B\setminus C\right)}\\ &\ \quad=\left(\left(A\cup C\right)\setminus\left(B\setminus C\right)\right) \cup\left(\left(B\setminus C\right)\setminus\left(A\cup C\right)\right)\\ &\ \quad=\left(\left(A\cup C\right)\setminus\left(B\cap C^c\right)\right) \cup\left(\left(B\setminus C\right)\cap\left(A\cup C\right)^c\right)\\ &\ \quad=\left(\left(A\cup C\right)\cap\left(B\cap C^c\right)^c\right) \cup\left(\left(B\cap C^c\right)\cap\left(A^c\cap C^c\right)\right)\\ &\ \quad=\left(\left(A\cup C\right)\cap\left(B^c\cup C\right)\right) \cup\left(A^c\cap B\cap C^c\right)\\ &\ \quad=\left(A\cap\left(B^c\cup C\right)\right)\cup\left(C\cap\left(B^c\cup C\right)\right) \cup\left(A^c\cap B\cap C^c\right)\\ &\ \quad=\left(A\cap B^c\right)\cup\left(A\cap C\right)\cup \left(B^c\cap C\right)\cup C \cup\left(A^c\cap B\cap C^c\right)\\ &\ \quad=\left(A\cap B^c\right)\cup C\cup\left(A^c\cap B\cap C^c\right)\\ &\ \quad=\left(A\cap B^c\right)\cup\left(C\cup\left(A^c\cap B\right)\right)\cup \emptyset\\ &\ \quad\color{blue}{=\left(A\cap B^c\right)\cup C\cup \left(A^c\cap B\right)}\tag{5.2} \end{align*} Since (5.1) and (5.2) are equal disjunctive normal forms the validity of (1) follows.

Another approach:

A common and probably the easiest approach is to use truth tables. We obtain \begin{align*} \begin{array}{ccc|ccccc|ccccccc|c} A&B&C&(A&\triangle&B)&\color{blue}{\cup}&C&(A&\cup&C)&\color{blue}{\triangle}&(B&\setminus&C)&\text{Cases}\\ \hline 1&1&1&1&0&1&\color{blue}{1}&1&1&1&1&\color{blue}{1}&1&0&1&(2.2)\\ 1&1&0&1&0&1&\color{blue}{0}&0&1&1&0&\color{blue}{0}&1&1&0&\\ 1&0&1&1&1&0&\color{blue}{1}&1&1&1&1&\color{blue}{1}&0&0&1&(3.1)\\ 1&0&0&1&1&0&\color{blue}{1}&0&1&1&0&\color{blue}{1}&0&0&0&(1.1)\\ 0&1&1&0&1&1&\color{blue}{1}&1&0&1&1&\color{blue}{1}&1&0&1&(3.2)\\ 0&1&0&0&1&1&\color{blue}{1}&0&0&0&0&\color{blue}{1}&1&1&0&(1.2)\\ 0&0&1&0&0&0&\color{blue}{1}&1&0&1&1&\color{blue}{1}&0&0&1&(2.1)\\ 0&0&0&0&0&0&\color{blue}{0}&0&0&0&0&\color{blue}{0}&0&0&0&\\ \hline &&&1&3&2&\color{blue}{5}&4&6&8&7&\color{blue}{12}&9&11&10\\ \end{array} \end{align*}

• We start with the $2^3=8$ different settings of $A,B$ and $C$ stated in the three left-most columns. The other columns are calculated in increasing order given by the bottom-row. We observe, since the blue marked result columns $5$ and $12$ coincide, validity of (1) is given.

• In the rightmost column we list the cases which were considered by OP. For instance the case 2.2 considers \begin{align*} x \in A \wedge x \in B \wedge x \in C \end{align*} which means $A=B=C=1$ in the truth table.

• Two rows have no reference to a case. They correspond to \begin{align*} \left(x\not\in\left(A\triangle B\right)\right)\wedge \left(x\not\in C\right) \end{align*} which was not to consider.