Symmetric difference
In set theory, the symmetric difference of two sets A and B, denoted A \Delta B, is the set consisting of all elements that belong to exactly one of A or B, but not to both; formally, A \Delta B = (A \setminus B) \cup (B \setminus A).[1] This operation can also be expressed as A \Delta B = (A \cup B) \setminus (A \cap B), highlighting its relation to union and intersection by excluding shared elements.[2] The symmetric difference possesses several key algebraic properties that make it a fundamental binary operation on sets. It is commutative, meaning A \Delta B = B \Delta A, and associative, so (A \Delta B) \Delta C = A \Delta (B \Delta C) for any sets A, B, and C.[3] The empty set \emptyset serves as the identity element, since A \Delta \emptyset = A, and each set is its own inverse, as A \Delta A = \emptyset.[4] These properties endow the power set of any universal set X (the collection of all subsets of X) with the structure of an abelian group under symmetric difference, where the operation corresponds to vector addition modulo 2 when viewing subsets as vectors in \{0,1\}^X.[5] Furthermore, symmetric difference interacts meaningfully with other set operations and extends to broader mathematical contexts. When paired with intersection as multiplication, it forms a Boolean ring on the power set, satisfying distributive laws such as A \Delta (B \cap C) = (A \Delta B) \cap (A \Delta C).[6] In measure theory, the symmetric difference defines a metric on the space of measurable sets, d(A, B) = \mu(A \Delta B), where \mu is a measure, quantifying the "distance" between sets by their differing measure.[7] Applications appear in computer science, such as database queries and error-correcting codes, where it models exclusive-or (XOR) operations on bit vectors, and in topology, for studying symmetric difference topologies on families of sets.Definition and Notation
Definition
In set theory, the symmetric difference of two sets A and B is the set consisting of elements that belong to exactly one of A or B, but not to both.[2] This operation captures the elements unique to each set, excluding their shared elements.[3] Formally, the symmetric difference, denoted A \Delta B, is defined as A \Delta B = \{ x \mid (x \in A \land x \notin B) \lor (x \notin A \land x \in B) \}. [2] An equivalent set-theoretic expression is A \Delta B = (A \cup B) \setminus (A \cap B), where \cup denotes union and \cap denotes intersection.[8] For example, if A = \{1, 2, 3\} and B = \{3, 4\}, then A \Delta B = \{1, 2, 4\}.[9] This operation serves as the set analog of the exclusive or (XOR) in Boolean logic.[10]Notation and Equivalent Expressions
The symmetric difference of two sets A and B is commonly denoted by A \Delta B. In logical and computer science contexts, the notation A \oplus B is also standard, reflecting its correspondence to the exclusive-or operation. Less frequently, it is written as \mathrm{Sym}(A, B).[11] Equivalent expressions for the symmetric difference can be formulated using basic set operations. One standard form is the union of the set differences: A \Delta B = (A \setminus B) \cup (B \setminus A) This captures the elements unique to each set. Another equivalent expression employs complements relative to a universal set U: A \Delta B = (A \cap B^c) \cup (B \cap A^c) where ^c denotes the complement. These formulations are interderivable, as A \setminus B = A \cap B^c. The symmetric difference corresponds directly to the exclusive-or (XOR) operation in the two-element Boolean algebra \{0,1\} with addition modulo 2. To derive this equivalence, consider the characteristic functions \chi_A and \chi_B of sets A and B, which map elements of the universe to 1 if in the set and 0 otherwise. The characteristic function of A \Delta B satisfies \chi_{A \Delta B}(x) = \chi_A(x) + \chi_B(x) \pmod{2}, which is precisely the XOR operation: it yields 1 if exactly one of \chi_A(x) or \chi_B(x) is 1, and 0 otherwise.[12] This connection underscores the symmetric difference's role as the addition in the Boolean ring structure on the power set.[12]Properties
Elementary Properties
The symmetric difference operation on sets is commutative: for any sets A and B, A \Delta B = B \Delta A. This holds because an element x belongs to A \Delta B if and only if it is in exactly one of A or B, a condition that remains unchanged when A and B are swapped.[6] The operation is also associative: (A \Delta B) \Delta C = A \Delta (B \Delta C) for any sets A, B, and C. To verify this, consider an arbitrary element x. The element x lies in the left-hand side if it belongs to an odd number of the sets among A, B, and C, as each symmetric difference step toggles membership based on parity (exclusive or). The same parity condition applies to the right-hand side, independent of grouping, ensuring equality.[13] The empty set acts as the neutral (identity) element: A \Delta \emptyset = A for any set A. Elements in A appear in exactly one set (A itself), while elements outside A appear in none, matching A's membership.[6] Relatedly, every set is self-inverse under symmetric difference: A \Delta A = \emptyset, so A serves as its own additive inverse, returning to the identity when "added" to itself.[6] To illustrate associativity, take A = \{1, 2\}, B = \{2, 3\}, and C = \{3, 4\}. Then A \Delta B = \{1, 3\} and (A \Delta B) \Delta C = \{1, 3\} \Delta \{3, 4\} = \{1, 4\}. Similarly, B \Delta C = \{2, 4\} and A \Delta (B \Delta C) = \{1, 2\} \Delta \{2, 4\} = \{1, 4\}, confirming both sides match.[13]Algebraic Structure
The power set \mathcal{P}(U) of a universe U, equipped with the symmetric difference operation \Delta and the empty set \emptyset as the identity element, forms an abelian group (\mathcal{P}(U), \Delta, \emptyset).[5] Closure holds because for any A, B \subseteq U, the symmetric difference A \Delta B = (A \setminus B) \cup (B \setminus A) is a subset of U, hence an element of \mathcal{P}(U).[5] Associativity follows from the set-theoretic identity (A \Delta B) \Delta C = A \Delta (B \Delta C), as established in elementary properties.[14] The empty set serves as the identity since A \Delta \emptyset = A for any A \subseteq U.[5] Each element is its own inverse because A \Delta A = \emptyset.[5] Commutativity of \Delta ensures the group is abelian.[15] Furthermore, \mathcal{P}(U) forms a Boolean ring when equipped with symmetric difference \Delta as addition and intersection \cap as multiplication.[16][17] This structure satisfies the ring axioms, including distributivity: for any A, B, C \subseteq U, A \cap (B \Delta C) = (A \cap B) \Delta (A \cap C).[14] The ring is commutative because both operations are commutative.[17] It has unity U, since A \cap U = A for any A \subseteq U.[16] In this ring, the union operation relates via the formula A \cup B = (A \Delta B) \Delta (A \cap B), or equivalently in ring notation, A + B + AB (where the characteristic 2 implies no coefficient adjustment).[18] This Boolean ring structure on \mathcal{P}(U) is isomorphic to a vector space over the field \mathrm{GF}(2).[19][20] Each subset A \subseteq U corresponds to its characteristic vector in \{0,1\}^U \cong (\mathrm{GF}(2))^U, where the i-th coordinate is 1 if i \in A and 0 otherwise; symmetric difference \Delta corresponds to componentwise addition modulo 2.[19] Scalar multiplication is defined naturally: $0 \cdot A = \emptyset and $1 \cdot A = A.[20] Intersection \cap then acts as componentwise multiplication in this vector space.[18] For a concrete example, consider U = \{1,2\}. The power set \mathcal{P}(U) = \{\emptyset, \{1\}, \{2\}, \{1,2\}\} is isomorphic to (\mathrm{GF}(2))^2, with basis vectors corresponding to \{1\} and \{2\}. Addition via \Delta yields, for instance, \{1\} \Delta \{2\} = \{1,2\} and \{1\} \Delta \{1,2\} = \{2\}, mirroring vector addition in a 2-dimensional space over \mathrm{GF}(2).[21] The ring multiplication table, represented as operations on these basis elements, forms a $2 \times 2 structure over \mathrm{GF}(2), where \{1\} \cap \{2\} = \emptyset (zero vector) and \{1\} \cap \{1\} = \{1\} (idempotence).[17]Generalizations
n-ary Symmetric Difference
The n-ary symmetric difference of a finite collection of sets A_1, A_2, \dots, A_n is defined as the set of all elements that belong to an odd number of the individual sets A_i.[14] This generalizes the binary case by considering the parity of membership across all sets in the collection.[22] The operation is commonly denoted as \Delta_{i=1}^n A_i or by chaining the binary notation as A_1 \Delta A_2 \Delta \dots \Delta A_n.[14] Due to the associativity of the binary symmetric difference, the result is independent of parenthesization and the order of the sets for any n \geq 2.[23] The cardinality of the n-ary symmetric difference admits an explicit formula derived from inclusion-exclusion principles applied to characteristic functions: \left| \bigoplus_{i=1}^n A_i \right| = \sum_{k=1}^n (-1)^{k-1} 2^{k-1} \sum_{1 \leq i_1 < i_2 < \dots < i_k \leq n} \left| A_{i_1} \cap A_{i_2} \cap \dots \cap A_{i_k} \right|. This expands to \sum_i |A_i| - 2 \sum_{i<j} |A_i \cap A_j| + 4 \sum_{i<j<l} |A_i \cap A_j \cap A_l| - \dots + (-1)^{n-1} 2^{n-1} |A_1 \cap \dots \cap A_n|.[24] The derivation proceeds by induction on n, leveraging the fact that the characteristic function of the symmetric difference satisfies \chi_{A \oplus B} = (\chi_A - \chi_B)^2 = \chi_A + \chi_B - 2 \chi_A \chi_B, and extending this recursively while integrating over the universe to obtain the cardinality.[24] For illustration, consider the sets A = \{1\}, B = \{1, 2\}, and C = \{2, 3\}. The element 1 appears in two sets (A and B), 2 in two sets (B and C), and 3 in one set (C); thus, the n-ary symmetric difference is \{3\}. In the case of a countably infinite collection of sets \{A_i\}_{i=1}^\infty, the symmetric difference is similarly defined as the set of elements belonging to an odd number of the A_i, but it is well-defined only if each element in the ambient space belongs to finitely many of the A_i.[22]Symmetric Difference in Measure Spaces
In a measurable space (X, \Sigma, \mu), where \mu is a measure, the symmetric difference of two measurable sets A, B \in \Sigma is defined as A \Delta B = (A \setminus B) \cup (B \setminus A), and its measure is \mu(A \Delta B).[25] This quantity serves as a measure of dissimilarity between sets, particularly in spaces where the measure \mu may be infinite or continuous. The function d_\mu(A, B) = \mu(A \Delta B) induces a pseudometric on the \sigma-algebra \Sigma. It satisfies non-negativity, as \mu(A \Delta B) \geq 0 with equality if and only if \mu(A \Delta B) = 0, meaning A and B differ by a set of measure zero. Symmetry holds because A \Delta B = B \Delta A. The triangle inequality is given by \mu(A \Delta C) \leq \mu(A \Delta B) + \mu(B \Delta C), which follows from the inclusion A \Delta C \subset (A \Delta B) \cup (B \Delta C) and the subadditivity of \mu.[25] This pseudometric identifies sets that are equivalent modulo null sets, where d_\mu(A, B) = 0; quotienting by this equivalence relation yields a genuine metric space on the collection of measurable sets up to null sets.[25] A fundamental inequality relating the measures of the sets to their symmetric difference is |\mu(A) - \mu(B)| \leq \mu(A \Delta B) \leq \mu(A) + \mu(B). The upper bound follows from subadditivity, as A \Delta B \subset A \cup B. For the lower bound, decompose \mu(A) = \mu(A \cap B) + \mu(A \setminus B) and \mu(B) = \mu(A \cap B) + \mu(B \setminus A), yielding |\mu(A) - \mu(B)| = |\mu(A \setminus B) - \mu(B \setminus A)| \leq \mu(A \setminus B) + \mu(B \setminus A) = \mu(A \Delta B).[26] In the context of probability measures, where \mu is a probability measure, \mu(A \Delta B) relates to the total variation distance between the subprobability measures \nu_A = 1_A \cdot \mu and \nu_B = 1_B \cdot \mu. Specifically, the total variation distance is d_{\mathrm{TV}}(\nu_A, \nu_B) = \frac{1}{2} \int_X |1_A - 1_B| \, d\mu = \frac{1}{2} \mu(A \Delta B), so \mu(A \Delta B) = 2 d_{\mathrm{TV}}(\nu_A, \nu_B). This connection highlights the role of symmetric difference in quantifying distributional differences.[27] For example, consider the Lebesgue measure \lambda on [0,1]. Let A = [0, 0.5] and B = [0.4, 0.9]. Then A \setminus B = [0, 0.4) and B \setminus A = (0.5, 0.9], so A \Delta B = [0, 0.4) \cup (0.5, 0.9] with \lambda(A \Delta B) = 0.4 + 0.4 = 0.8.Comparisons and Applications
Comparison with Hausdorff Distance
The Hausdorff distance provides a metric for measuring the "closeness" of two compact subsets A and B in a metric space (X, d), defined as d_H(A, B) = \max\left\{ \sup_{a \in A} \inf_{b \in B} d(a, b),\ \sup_{b \in B} \inf_{a \in A} d(a, b) \right\}. This quantifies the maximum deviation of points in one set from the other, capturing geometric and topological proximity in a pointwise manner.[28] In contrast, the symmetric difference A \Delta B = (A \setminus B) \cup (B \setminus A) serves as a set-theoretic measure of dissimilarity, often quantified by its Lebesgue measure \mu(A \Delta B) in Euclidean spaces, which assesses the total "mismatched" volume without regard to the underlying metric structure.[28] While the Hausdorff distance emphasizes spatial configuration and is sensitive to the positions of individual points or outliers, the symmetric difference focuses on the aggregate content overlap, rendering it more robust to isolated perturbations but blind to overall arrangement.[28] This insensitivity to spatial layout makes \mu(A \Delta B) less suitable for applications requiring geometric fidelity, such as shape matching in computational geometry.[28] The symmetric difference generally overlooks fine structural details, such as small holes or boundary irregularities in higher dimensions.[28]Applications in Logic and Other Fields
In Boolean logic, the symmetric difference operation corresponds directly to the exclusive or (XOR) gate, which outputs true only when the two inputs differ.[29] This equivalence arises because symmetric difference selects elements unique to each set, mirroring XOR's behavior on binary values. The truth table for the two-input XOR, representing symmetric difference of singleton sets, is as follows:| Input A | Input B | A Δ B (XOR) |
|---|---|---|
| 0 | 0 | 0 |
| 0 | 1 | 1 |
| 1 | 0 | 1 |
| 1 | 1 | 0 |