Symmetric Difference is Associative
From ProofWiki
Contents |
Theorem
Symmetric difference is associative:
- $R * \left({S * T}\right) = \left({R * S}\right) * T$
Proof 1
We can directly expand the expressions for $R * \left({S * T}\right)$ and $\left({R * S}\right) * T$, and see that they come to the same thing.
Expanding the RHS:
| \(\displaystyle \) | \(\displaystyle \) | \(\displaystyle \) | \(\displaystyle \) | \(\) | \(\displaystyle \) | \(\displaystyle \left({R * S}\right) * T\) | \(\displaystyle \) | \(\displaystyle \) | |||
| \(\displaystyle \) | \(\displaystyle \) | \(\displaystyle \) | \(\displaystyle \) | \(=\) | \(\displaystyle \) | \(\displaystyle \left({\left({\left({R \cap \overline S}\right) \cup \left({\overline R \cap S}\right)}\right) \cap \overline T}\right) \cup \left({\overline {R * S} \cap T}\right)\) | \(\displaystyle \) | \(\displaystyle \) | Definition of Symmetric Difference: Definition 3 | ||
| \(\displaystyle \) | \(\displaystyle \) | \(\displaystyle \) | \(\displaystyle \) | \(=\) | \(\displaystyle \) | \(\displaystyle \left({\left({\left({R \cap \overline S}\right) \cup \left({\overline R \cap S}\right)}\right) \cap \overline T}\right) \cup \left({\overline {\left({\left({R \cup S}\right) \cap \left({\overline R \cup \overline S}\right)}\right)} \cap T}\right)\) | \(\displaystyle \) | \(\displaystyle \) | Definition of Symmetric Difference: Definition 4 | ||
| \(\displaystyle \) | \(\displaystyle \) | \(\displaystyle \) | \(\displaystyle \) | \(=\) | \(\displaystyle \) | \(\displaystyle \left({R \cap \overline S \cap \overline T}\right) \cup \left({\overline R \cap S \cap \overline T}\right) \cup \left({\left({\overline {\left({R \cup S}\right)} \cup \overline {\left({\overline R \cup \overline S}\right)} }\right) \cap T}\right)\) | \(\displaystyle \) | \(\displaystyle \) | Intersection Distributes over Union and De Morgan | ||
| \(\displaystyle \) | \(\displaystyle \) | \(\displaystyle \) | \(\displaystyle \) | \(=\) | \(\displaystyle \) | \(\displaystyle \left({R \cap \overline S \cap \overline T}\right) \cup \left({\overline R \cap S \cap \overline T}\right) \cup \left({\left({\left({\overline R \cap \overline S}\right) \cup \left({R \cap S}\right)}\right) \cap T}\right)\) | \(\displaystyle \) | \(\displaystyle \) | De Morgan | ||
| \(\displaystyle \) | \(\displaystyle \) | \(\displaystyle \) | \(\displaystyle \) | \(=\) | \(\displaystyle \) | \(\displaystyle \left({R \cap \overline S \cap \overline T}\right) \cup \left({\overline R \cap S \cap \overline T}\right) \cup \left({\overline R \cap \overline S \cap T}\right) \cup \left({R \cap S \cap T}\right)\) | \(\displaystyle \) | \(\displaystyle \) | Intersection Distributes over Union |
Expanding the LHS:
| \(\displaystyle \) | \(\displaystyle \) | \(\displaystyle \) | \(\displaystyle \) | \(\) | \(\displaystyle \) | \(\displaystyle R * \left({S * T}\right)\) | \(\displaystyle \) | \(\displaystyle \) | |||
| \(\displaystyle \) | \(\displaystyle \) | \(\displaystyle \) | \(\displaystyle \) | \(=\) | \(\displaystyle \) | \(\displaystyle \left({R \cap \overline {S * T} }\right) \cup \left({\overline R \cap \left({\left({S \cap \overline T}\right) \cup \left({\overline S \cap T}\right)}\right)}\right)\) | \(\displaystyle \) | \(\displaystyle \) | Definition of Symmetric Difference: Definition 3 | ||
| \(\displaystyle \) | \(\displaystyle \) | \(\displaystyle \) | \(\displaystyle \) | \(=\) | \(\displaystyle \) | \(\displaystyle \left({R \cap \overline {\left({\left({S \cup T}\right) \cap \left({\overline S \cup \overline T}\right)}\right)} }\right) \cup \left({\overline R \cap \left({\left({S \cap \overline T}\right) \cup \left({\overline S \cap T}\right)}\right)}\right)\) | \(\displaystyle \) | \(\displaystyle \) | Definition of Symmetric Difference: Definition 4 | ||
| \(\displaystyle \) | \(\displaystyle \) | \(\displaystyle \) | \(\displaystyle \) | \(=\) | \(\displaystyle \) | \(\displaystyle \left({R \cap \left({\overline {\left({S \cup T}\right)} \cup \overline {\left({\overline S \cup \overline T}\right)} }\right)}\right) \cup \left({\overline R \cap S \cap \overline T}\right) \cup \left({\overline R \cap \overline S \cap T}\right)\) | \(\displaystyle \) | \(\displaystyle \) | Intersection Distributes over Union and De Morgan | ||
| \(\displaystyle \) | \(\displaystyle \) | \(\displaystyle \) | \(\displaystyle \) | \(=\) | \(\displaystyle \) | \(\displaystyle \left({R \cap \left({\left({\overline S \cap \overline T}\right) \cup \left({S \cap T}\right)}\right)}\right) \cup \left({\overline R \cap S \cap \overline T}\right) \cup \left({\overline R \cap \overline S \cap T}\right)\) | \(\displaystyle \) | \(\displaystyle \) | De Morgan | ||
| \(\displaystyle \) | \(\displaystyle \) | \(\displaystyle \) | \(\displaystyle \) | \(=\) | \(\displaystyle \) | \(\displaystyle \left({R \cap \overline S \cap \overline T}\right) \cup \left({R \cap S \cap T}\right) \cup \left({\overline R \cap S \cap \overline T}\right) \cup \left({\overline R \cap \overline S \cap T}\right)\) | \(\displaystyle \) | \(\displaystyle \) | Intersection Distributes over Union |
From Union is Commutative it is seen that the LHS and RHS are the same, and the result is proved.
$\blacksquare$
Proof 2
There is another way of doing this.
Expanding the RHS:
| \(\displaystyle \) | \(\displaystyle \) | \(\displaystyle \) | \(\displaystyle \) | \(\) | \(\displaystyle \) | \(\displaystyle \left({R * S}\right) * T\) | \(\displaystyle \) | \(\displaystyle \) | |||
| \(\displaystyle \) | \(\displaystyle \) | \(\displaystyle \) | \(\displaystyle \) | \(=\) | \(\displaystyle \) | \(\displaystyle \left({\left({\left({R \cup S}\right) \cap \left({\overline R \cup \overline S}\right)}\right) \cup T}\right) \cap \left({\overline {R * S} \cup \overline T}\right)\) | \(\displaystyle \) | \(\displaystyle \) | Definition of Symmetric Difference: Definition 4 | ||
| \(\displaystyle \) | \(\displaystyle \) | \(\displaystyle \) | \(\displaystyle \) | \(=\) | \(\displaystyle \) | \(\displaystyle \left({\left({\left({R \cup S}\right) \cap \left({\overline R \cup \overline S}\right)}\right) \cup T}\right) \cap \left({\overline {\left({\left({R \cap \overline S}\right) \cup \left({\overline R \cap S}\right)}\right)} \cup \overline T}\right)\) | \(\displaystyle \) | \(\displaystyle \) | Definition of Symmetric Difference: Definition 3 | ||
| \(\displaystyle \) | \(\displaystyle \) | \(\displaystyle \) | \(\displaystyle \) | \(=\) | \(\displaystyle \) | \(\displaystyle \left({R \cup S \cup T}\right) \cap \left({\overline R \cup \overline S \cup T}\right) \cap \left({\left({\overline {\left({R \cap \overline S}\right)} \cap \overline {\left({\overline R \cap S}\right)} }\right) \cup \overline T}\right)\) | \(\displaystyle \) | \(\displaystyle \) | Union Distributes over Intersection and De Morgan | ||
| \(\displaystyle \) | \(\displaystyle \) | \(\displaystyle \) | \(\displaystyle \) | \(=\) | \(\displaystyle \) | \(\displaystyle \left({R \cup S \cup T}\right) \cap \left({\overline R \cup \overline S \cup T}\right) \cap \left({\left({\left({\overline R \cup S}\right) \cap \left({R \cup \overline S}\right)}\right) \cup \overline T}\right)\) | \(\displaystyle \) | \(\displaystyle \) | De Morgan | ||
| \(\displaystyle \) | \(\displaystyle \) | \(\displaystyle \) | \(\displaystyle \) | \(=\) | \(\displaystyle \) | \(\displaystyle \left({R \cup S \cup T}\right) \cap \left({\overline R \cup \overline S \cup T}\right) \cap \left({\overline R \cup S \cup \overline T}\right) \cap \left({R \cup \overline S \cup \overline T}\right)\) | \(\displaystyle \) | \(\displaystyle \) | Union Distributes over Intersection |
Expanding the LHS:
| \(\displaystyle \) | \(\displaystyle \) | \(\displaystyle \) | \(\displaystyle \) | \(\) | \(\displaystyle \) | \(\displaystyle R * \left({S * T}\right)\) | \(\displaystyle \) | \(\displaystyle \) | |||
| \(\displaystyle \) | \(\displaystyle \) | \(\displaystyle \) | \(\displaystyle \) | \(=\) | \(\displaystyle \) | \(\displaystyle \left({R \cup \left({\left({S \cup T}\right) \cap \left({\overline S \cup \overline T}\right)}\right)}\right) \cap \left({\overline R \cup \overline {S * T} }\right)\) | \(\displaystyle \) | \(\displaystyle \) | Definition of Symmetric Difference: Definition 4 | ||
| \(\displaystyle \) | \(\displaystyle \) | \(\displaystyle \) | \(\displaystyle \) | \(=\) | \(\displaystyle \) | \(\displaystyle \left({R \cup \left({\left({S \cup T}\right) \cap \left({\overline S \cup \overline T}\right)}\right)}\right) \cap \left({\overline R \cup \overline {\left({\left({S \cap \overline T}\right) \cup \left({\overline S \cap T}\right)}\right)} }\right)\) | \(\displaystyle \) | \(\displaystyle \) | Definition of Symmetric Difference: Definition 3 | ||
| \(\displaystyle \) | \(\displaystyle \) | \(\displaystyle \) | \(\displaystyle \) | \(=\) | \(\displaystyle \) | \(\displaystyle \left({R \cup S \cup T}\right) \cap \left({R \cup \overline S \cup \overline T}\right) \cap \left({\overline R \cup \left({\overline {\left({S \cap \overline T}\right)} \cap \overline {\left({\overline S \cap T}\right)} }\right)}\right)\) | \(\displaystyle \) | \(\displaystyle \) | Union Distributes over Intersection and De Morgan | ||
| \(\displaystyle \) | \(\displaystyle \) | \(\displaystyle \) | \(\displaystyle \) | \(=\) | \(\displaystyle \) | \(\displaystyle \left({R \cup S \cup T}\right) \cap \left({R \cup \overline S \cup \overline T}\right) \cap \left({\overline R \cup \left({\left({\overline S \cup T}\right) \cap \left({S \cup \overline T}\right)}\right)}\right)\) | \(\displaystyle \) | \(\displaystyle \) | De Morgan | ||
| \(\displaystyle \) | \(\displaystyle \) | \(\displaystyle \) | \(\displaystyle \) | \(=\) | \(\displaystyle \) | \(\displaystyle \left({R \cup S \cup T}\right) \cap \left({R \cup \overline S \cup \overline T}\right) \cap \left({\overline R \cup \overline S \cup T}\right) \cap \left({\overline R \cup S \cup \overline T}\right)\) | \(\displaystyle \) | \(\displaystyle \) | Union Distributes over Intersection |
From Intersection is Commutative, it can be seen that the LHS and RHS are the same, and the result is proved.
$\blacksquare$
Comment
This illustrates that you can express the symmetric difference of three sets as the union of four intersections (which seems more intuitively obvious) as well as the intersection of four unions (which is not quite so obvious).
Also see
Sources
- Paul R. Halmos: Naive Set Theory (1960)... (previous)... (next): $\S 5$: Complements and Powers
- J.A. Green: Sets and Groups (1965)... (previous)... (next): Exercise $1.7 \ \text{(iii)}$
- Allan Clark: Elements of Abstract Algebra (1971)... (previous)... (next): $\S 8 \alpha$
- T.S. Blyth: Set Theory and Abstract Algebra (1975)... (previous)... (next): $\S 1$: Exercise $14$
- Thomas A. Whitelaw: An Introduction to Abstract Algebra (1978)... (previous)... (next): Exercise $1.9 \ \text{(ii)}$
- René L. Schilling: Measures, Integrals and Martingales (2005)... (previous)... (next): $\S 2$: Problem $6 \ \text{(ii)}$
