Equivalence of Definitions of Symmetric Difference

From ProofWiki
Jump to navigation Jump to search

Theorem

Let $S$ and $T$ be sets.

The following definitions of the concept of symmetric difference $S * T$ between $S$ and $T$ are equivalent:

Definition 1

$S * T := \paren {S \setminus T} \cup \paren {T \setminus S}$

Definition 2

$S * T = \paren {S \cup T} \setminus \paren {S \cap T}$

Definition 3

$S * T = \left({S \cap \overline T}\right) \cup \left({\overline S \cap T}\right)$

Definition 4

$S * T = \left({S \cup T}\right) \cap \left({\overline S \cup \overline T}\right)$

Definition 5

$S * T := \set {x: x \in S \oplus x \in T}$


Proof

$(1)$ iff $(2)$

\(\displaystyle S * T\) \(=\) \(\displaystyle \paren {S \setminus T} \cup \paren {T \setminus S}\) Definition 1 of Symmetric Difference
\(\displaystyle \) \(=\) \(\displaystyle \paren {\paren {S \cup T} \setminus T} \cup \paren {\paren {S \cup T} \setminus S}\) Set Difference with Union is Set Difference
\(\displaystyle \) \(=\) \(\displaystyle \paren {S \cup T} \setminus \paren {T \cap S}\) De Morgan's Laws: Difference with Intersection
\(\displaystyle \) \(=\) \(\displaystyle \paren {S \cup T} \setminus \paren {S \cap T}\) Intersection is Commutative

$\Box$


$(1)$ iff $(3)$

\(\displaystyle S * T\) \(=\) \(\displaystyle \left({S \setminus T}\right) \cup \left({T \setminus S}\right)\) Symmetric Difference: Definition 1
\(\displaystyle \) \(=\) \(\displaystyle \left({S \cap \overline T}\right) \cup \left({\overline S \cap T}\right)\) Set Difference as Intersection with Complement

$\Box$


$(2)$ iff $(4)$

\(\displaystyle S * T\) \(=\) \(\displaystyle \left({S \cup T}\right) \setminus \left({S \cap T}\right)\) Symmetric Difference: Definition 2
\(\displaystyle \) \(=\) \(\displaystyle \left({S \cup T}\right) \cap \left({\overline {S \cap T} }\right)\) Set Difference as Intersection with Complement
\(\displaystyle \) \(=\) \(\displaystyle \left({S \cup T}\right) \cap \left({\overline S \cup \overline T}\right)\) De Morgan's Laws: Complement of Intersection

$\Box$


$(2)$ iff $(5)$

\(\displaystyle x \in S * T\) \(\iff\) \(\displaystyle x \in S \oplus x \in T\) Symmetric Difference: Definition 5
\(\displaystyle \) \(\iff\) \(\displaystyle \left({x \in S \lor x \in T} \right) \land \neg \left({x \in S \land x \in T}\right)\) Definition of Exclusive Or
\(\displaystyle \) \(\iff\) \(\displaystyle \left({x \in S \cup T}\right) \land \left({x \notin S \cap T}\right)\) Definition of Set Intersection and Set Union
\(\displaystyle \) \(\iff\) \(\displaystyle x \in \left({S \cup T}\right) \setminus \left({S \cap T}\right)\) Definition of Set Difference

The result follows by definition of set equality.

$\Box$


$(3)$ iff $(5)$

\(\displaystyle x \in S * T\) \(\iff\) \(\displaystyle x \in S \oplus x \in T\) Symmetric Difference: Definition 5
\(\displaystyle \) \(\iff\) \(\displaystyle \left({\neg \left({x \in S}\right) \land \left({x \in T}\right)}\right) \lor \left({\left({x \in S}\right) \land \neg \left({x \in T}\right)}\right)\) Non-Equivalence as Disjunction of Conjunctions
\(\displaystyle \) \(\iff\) \(\displaystyle \left({x \in \overline S \land x \in T}\right) \lor \left({x \in S \land x \in \overline T}\right)\) Definition of Set Complement
\(\displaystyle \) \(\iff\) \(\displaystyle \left({x \in \overline S \cup T}\right) \lor \left({x \in S \cup \overline T}\right)\) Definition of Set Intersection
\(\displaystyle \) \(\iff\) \(\displaystyle x \in \left({\overline S \cup T}\right) \cup \left({S \cup \overline T}\right)\) Definition of Set Union
\(\displaystyle \) \(\iff\) \(\displaystyle x \in \left({S \cup \overline T}\right) \cup \left({\overline S \cup T}\right)\) Union is Commutative

The result follows by definition of set equality.

$\blacksquare$