Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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.

share|cite|improve this question
Looks good to me! – Brian M. Scott Apr 3 '13 at 20:27
Alternative, we could use characteristic function: – Cortizol Apr 3 '13 at 20:58
up vote 6 down vote accepted

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)$$

share|cite|improve this answer
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.)

enter image description here

share|cite|improve this answer

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)$.

share|cite|improve this answer

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.

share|cite|improve this answer

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.