Equivalence of Definitions of Symmetric Difference
Jump to navigation
Jump to search
Theorem
Let $S$ and $T$ be sets.
The following definitions of the concept of symmetric difference $S \symdif T$ between $S$ and $T$ are equivalent:
Definition 1
- $S \symdif T := \paren {S \setminus T} \cup \paren {T \setminus S}$
Definition 2
- $S \symdif T = \paren {S \cup T} \setminus \paren {S \cap T}$
Definition 3
- $S \symdif T = \paren {S \cap \overline T} \cup \paren {\overline S \cap T}$
Definition 4
- $S \symdif T = \paren {S \cup T}\cap \paren {\overline S \cup \overline T}$
Definition 5
- $S \symdif T := \set {x: x \in S \oplus x \in T}$
Proof
$(1)$ iff $(2)$
| \(\ds S \symdif T\) | \(=\) | \(\ds \paren {S \setminus T} \cup \paren {T \setminus S}\) | Definition 1 of Symmetric Difference | |||||||||||
| \(\ds \) | \(=\) | \(\ds \paren {\paren {S \cup T} \setminus T} \cup \paren {\paren {S \cup T} \setminus S}\) | Set Difference with Union is Set Difference | |||||||||||
| \(\ds \) | \(=\) | \(\ds \paren {S \cup T} \setminus \paren {T \cap S}\) | De Morgan's Laws: Difference with Intersection | |||||||||||
| \(\ds \) | \(=\) | \(\ds \paren {S \cup T} \setminus \paren {S \cap T}\) | Intersection is Commutative |
$\Box$
$(1)$ iff $(3)$
| \(\ds S \symdif T\) | \(=\) | \(\ds \paren {S \setminus T} \cup \paren {T \setminus S}\) | Definition 1 of Symmetric Difference | |||||||||||
| \(\ds \) | \(=\) | \(\ds \paren {S \cap \overline T} \cup \paren {\overline S \cap T}\) | Set Difference as Intersection with Complement |
$\Box$
$(2)$ iff $(4)$
| \(\ds S \symdif T\) | \(=\) | \(\ds \paren {S \cup T} \setminus \paren {S \cap T}\) | Definition 2 of Symmetric Difference | |||||||||||
| \(\ds \) | \(=\) | \(\ds \paren {S \cup T} \cap \paren {\overline {S \cap T} }\) | Set Difference as Intersection with Complement | |||||||||||
| \(\ds \) | \(=\) | \(\ds \paren {S \cup T} \cap \paren {\overline S \cup \overline T}\) | De Morgan's Laws: Complement of Intersection |
$\Box$
$(2)$ iff $(5)$
| \(\ds \) | \(\) | \(\ds x \in S \symdif T\) | ||||||||||||
| \(\ds \) | \(\leadstoandfrom\) | \(\ds x \in S \oplus x \in T\) | Definition 5 of Symmetric Difference | |||||||||||
| \(\ds \) | \(\leadstoandfrom\) | \(\ds \paren {x \in S \lor x \in T} \land \neg \paren {x \in S \land x \in T}\) | Definition of Exclusive Or | |||||||||||
| \(\ds \) | \(\leadstoandfrom\) | \(\ds \paren {x \in S \cup T} \land \paren {x \notin S \cap T}\) | Definition of Set Intersection and Definition of Set Union | |||||||||||
| \(\ds \) | \(\leadstoandfrom\) | \(\ds x \in \paren {S \cup T} \setminus \paren {S \cap T}\) | Definition of Set Difference |
The result follows by definition of set equality.
$\Box$
$(3)$ iff $(5)$
| \(\ds \) | \(\) | \(\ds x \in S \symdif T\) | ||||||||||||
| \(\ds \) | \(\leadstoandfrom\) | \(\ds x \in S \oplus x \in T\) | Definition 5 of Symmetric Difference | |||||||||||
| \(\ds \) | \(\leadstoandfrom\) | \(\ds \paren {\neg \paren {x \in S} \land \paren {x \in T} } \lor \paren {\paren {x \in S} \land \neg \paren {x \in T} }\) | Non-Equivalence as Disjunction of Conjunctions | |||||||||||
| \(\ds \) | \(\leadstoandfrom\) | \(\ds \paren {x \in \overline S \land x \in T} \lor \paren {x \in S \land x \in \overline T}\) | Definition of Set Complement | |||||||||||
| \(\ds \) | \(\leadstoandfrom\) | \(\ds \paren {x \in \overline S \cup T} \lor \paren {x \in S \cup \overline T}\) | Definition of Set Intersection | |||||||||||
| \(\ds \) | \(\leadstoandfrom\) | \(\ds x \in \paren {\overline S \cup T} \cup \paren {S \cup \overline T}\) | Definition of Set Union | |||||||||||
| \(\ds \) | \(\leadstoandfrom\) | \(\ds x \in \paren {S \cup \overline T} \cup \paren {\overline S \cup T}\) | Union is Commutative |
The result follows by definition of set equality.
$\blacksquare$