In mathematics, the symmetric difference of two sets, also known as the disjunctive union, is the set of elements which are in either of the sets, but not in their intersection. For example, the symmetric difference of the sets and is .
The same fact can be stated as the indicator function (denoted here by ) of the symmetric difference, being the XOR (or addition mod 2) of the indicator functions of its two arguments: or using the Iverson bracket notation .
The symmetric difference can also be expressed as the union of the two sets, minus their intersection:
In particular, ; the equality in this non-strict inclusion occurs if and only if and are disjoint sets. Furthermore, denoting and , then and are always disjoint, so and partition. Consequently, assuming intersection and symmetric difference as primitive operations, the union of two sets can be well defined in terms of symmetric difference by the right-hand side of the equality
Thus, the power set of any set X becomes an abelian group under the symmetric difference operation. (More generally, any field of sets forms a group with the symmetric difference as operation.) A group in which every element is its own inverse (or, equivalently, in which every element has order 2) is sometimes called a Boolean group; the symmetric difference provides a prototypical example of such groups. Sometimes the Boolean group is actually defined as the symmetric difference operation on a set. In the case where X has only two elements, the group thus obtained is the Klein four-group.
From the property of the inverses in a Boolean group, it follows that the symmetric difference of two repeated symmetric differences is equivalent to the repeated symmetric difference of the join of the two multisets, where for each double set both can be removed. In particular:
This implies triangle inequality: the symmetric difference of A and C is contained in the union of the symmetric difference of A and B and that of B and C.
This operation has the same properties as the symmetric difference of sets.
n-ary symmetric differenceEdit
The repeated symmetric difference is in a sense equivalent to an operation on a multiset of sets giving the set of elements which are in an odd number of sets.[clarification needed]
As above, the symmetric difference of a collection of sets contains just elements which are in an odd number of the sets in the collection:
Evidently, this is well-defined only when each element of the union is contributed by a finite number of elements of .
Suppose is a multiset and . Then there is a formula for , the number of elements in , given solely in terms of intersections of elements of :
Symmetric difference on measure spacesEdit
As long as there is a notion of "how big" a set is, the symmetric difference between two sets can be considered a measure of how "far apart" they are.
First consider a finite set S and the counting measure on subsets given by their size. Now consider two subsets of S and set their distance apart as the size of their symmetric difference. This distance is in fact a metric, which makes the power set on S a metric space. If S has n elements, then the distance from the empty set to S is n, and this is the maximum distance for any pair of subsets.
Using the ideas of measure theory, the separation of measurable sets can be defined to be the measure of their symmetric difference. If μ is a σ-finitemeasure defined on a σ-algebra Σ, the function
If is a measure space and are measurable sets, then their symmetric difference is also measurable: . One may define an equivalence relation on measurable sets by letting and
be related if . This relation is denoted .
Given , one writes if to each there's some such that . The relation "" is a partial order on the family of subsets of .
We write if and . The relation "" is an equivalence relationship between the subsets of .
The symmetric closure of is the collection of all -measurable sets that are to some . The symmetric closure of contains . If is a sub--algebra of , so is the symmetric closure of .
The Hausdorff distance and the (area of the) symmetric difference are both pseudo-metrics on the set of measurable geometric shapes. However, they behave quite differently. The figure at the right shows two sequences of shapes, "Red" and "Red ∪ Green". When the Hausdorff distance between them becomes smaller, the area of the symmetric difference between them becomes larger, and vice versa. By continuing these sequences in both directions, it is possible to get two sequences such that the Hausdorff distance between them converges to 0 and the symmetric distance between them diverges, or vice versa.