Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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|improve this question
1  
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
add comment

4 Answers 4

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|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
add comment

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

enter image description here

share|improve this answer
add comment

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|improve this answer
add comment

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|improve this answer
add comment

Your Answer

 
discard

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.