# Prove that $A \mathop \triangle C \subseteq (A \mathop \triangle B)\cup (B \mathop \triangle C)$

Suppose A, B, and C are sets, prove that $A \mathop \triangle C \subseteq (A \mathop \triangle B)\cup (B \mathop \triangle C)$

I'm just wondering if this proof is ok, or if I'm overlooking something, thanks!

Proof. Suppose $x \in A \mathop \triangle C$. If $x \in A \mathop \triangle B$, then clearly $x \in (A \mathop \triangle B) \cup (B \mathop \triangle C)$, so we will consider the case when $x \notin A \mathop \triangle B$. Suppose $x \notin A \mathop \triangle B$. This means that $x \in A \leftrightarrow x \in B$. Since $x \in A \mathop \triangle C$, either $x \in A \mathop \backslash C$ or $x \in C \mathop \backslash A$. We will consider both cases.

Case 1: $x \in A \mathop \backslash C$. So $x \in A$ and $x \notin C$. Since $x \in A$ and $x \in A \leftrightarrow x \in B$, it follows that $x \in B$. Then since $x \notin C$, $x \in B \mathop \backslash C$, so $x \in B \mathop \triangle C$. Hence, $x \in (A \mathop \triangle B)\cup (B \mathop \triangle C)$

Case 2: $x \in C \mathop \backslash A$. So $x \in C$ and $x \notin A$. Then since $x \notin A$ and $x \in A \leftrightarrow x \in B$, it follows that $x \notin B$. Thus, $x \in C \mathop \backslash B$, so $x \in B \mathop \triangle C$, and hence, $x \in (A \mathop \triangle B)\cup (B \mathop \triangle C)$.

Edit: Also, I would be interested to see any alternative methods of proving this.

-
Looks good to me! –  Brian M. Scott Apr 3 '13 at 20:27
Alternative, we could use characteristic function: en.wikipedia.org/wiki/Indicator_function –  Cortizol Apr 3 '13 at 20:58

Here is an alternative:

$$A\triangle C=A\triangle\varnothing\triangle C=A\triangle(B\triangle B)\triangle C=(A\triangle B)\triangle(B\triangle C)\subseteq(A\triangle B)\cup(B\triangle C)$$

-
This is a nice argument, assuming that you know that symmetric difference is associative. –  Sammy Black Apr 3 '13 at 21:16
Of course. ${}{}{}{}$ –  Asaf Karagila Apr 3 '13 at 21:32

How about some Venn diagrams? (Please don't comment on the lack of rigor.)

-

Let $x \in A \mathop \triangle C$.

Case $1$: $x \in A \backslash C$. Then $x \in A$ and $x \notin C$. If $x \in B$ then $x \in B\backslash C$ and if $x\notin B$ then $x \in A\backslash B$. In either case we have $x \in(A \mathop \triangle B)\cup (B \mathop \triangle C)$.

Case $2$: $x\in C\backslash A$. Then $x \in C$ and $x \notin A$. If $x \in B$ then $x \in B \backslash A$ and if $x \notin B$ then $x \in C \backslash B$. In either case we have $x \in (A \mathop \triangle B)\cup (B \mathop \triangle C)$.

-

Here is another alternative proof, in my favorite proof format: the calculational Feijen(-Dijkstra-Scholten-Gries-etc.) format. I will use the following definition of $\Delta$: $$x \in P \Delta Q \equiv x \in P \not\equiv x \in Q$$

Starting with the most complex side, and working on the element level, we try to transform $x \in (A \Delta B) \cup (B \Delta C)$ and work towards $A \Delta C$ using logic: \begin{align} & x \in (A \Delta B) \cup (B \Delta C) \\ \equiv & \;\;\;\;\;\text{"definition of \cup; above definition of \Delta, twice"} \\ & (x \in A \not\equiv x \in B) \lor (x \in B \not\equiv x \in C) \\ \equiv & \;\;\;\;\;\text{"logic: use negation of right side of \lor in left side -- to bring A and C together"} \\ & (x \in A \not\equiv x \in C) \lor (x \in B \not\equiv x \in C) \\ \Leftarrow & \;\;\;\;\;\text{"logic: weakening"} \\ & x \in A \not\equiv x \in C \\ \equiv & \;\;\;\;\;\text{"above definition of \Delta"} \\ & x \in A \Delta C \\ \end{align} By the definition of $\subseteq$ this completes the proof.

-