Symmetric difference is associative

Posted by Nalin Pithwa

We want to show that : $A \triangle (B \triangle C) = (A \triangle B) \triangle C$

Part I: TPT: $LHS \subset RHS$

Proof of Part I: let $x \in LHS$

Then, $x \in A \triangle (B \triangle C)$ . By definition of symmetric difference,

$x \in \{ A - (B \triangle C)\} \bigcup \{(B \triangle C) -A \}$

Hence, $x \in A$ , $x \notin (B \triangle C)$ , OR $x \in B \triangle C$ , $x \in A$

That is, $x \notin A \bigcap (B \triangle C)$ .

Hence, $x \notin A$ , and $x \notin B \triangle C$

Hence, $x \notin A$ and $x \in B \bigcap C$ .

Hence, $x \in (B \bigcap C)-A$ .

Hence, $x \in B$ , $x \in C$ , but $x \notin A$ .

Therefore, $x \in B$ , but $x \notin A \bigcap C$ . —- Call this I.

Consider $y \in (A \triangle B) \triangle C$ .

Therefore, $y \notin (A \triangle B) \bigcap C$ .

Therefore, $y \notin C$ , and $y \notin A \triangle B$

Therefore, $y \notin C$ , and $y \in A \bigcap B$ .

Therefore, $y \in (A \bigcap B)-C$ .

Hence, $y \in A$ , $y \in B$ , but $y \notin C$ .

That is, $y \in B$ , $y \notin A \bigcap C$ . Call this II.

From I and II, $LHS \subset RHS$ .

Part II: TPT: $RHS \subset LHS$ .

Quite simply, reversing the above steps we prove part II.

QED.

Cheers,

Nalin Pithwa

Leave a Reply Cancel reply

Enter your comment here...

Fill in your details below or click an icon to log in:

Email (required) (Address never made public)

Name (required)

Website

You are commenting using your WordPress.com account. ( Log Out / Change )

You are commenting using your Google account. ( Log Out / Change )

You are commenting using your Twitter account. ( Log Out / Change )

You are commenting using your Facebook account. ( Log Out / Change )

Connecting to %s

This site uses Akismet to reduce spam. Learn how your comment data is processed.

%d bloggers like this: