In mathematics, the symmetric difference of two sets is the set of elements which are in either of the sets and not in their intersection. The symmetric difference of the sets A and B is commonly denoted by
For example, the symmetric difference of the sets and is . The symmetric difference of the set of all students and the set of all females consists of all non-female students together with all female non-students.
The power set of any set becomes an abelian group under the operation of symmetric difference, with the empty set as the neutral element of the group and every element in this group being its own inverse. The power set of any set becomes a Boolean ring with symmetric difference as the addition of the ring and intersection as the multiplication of the ring.
and it can also be expressed as the union of the two sets, minus their intersection:
or with the XOR operation:
In particular, .
Thus, the repeated symmetric difference is an operation on a multiset of sets giving the set of elements which are in an odd number of sets.
The symmetric difference of two repeated symmetric differences is the repeated symmetric difference of the join of the two multisets, where for each double set both can be removed. In particular:
This implies a sort of 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. (But note that for the diameter of the symmetric difference the triangle inequality does not hold.)
Taken together, we see that the power set of any set X becomes an abelian group if we use the symmetric difference as operation. Because every element in this group is its own inverse, this is in fact a vector space over the field with 2 elements Z2. If X is finite, then the singletons form a basis of this vector space, and its dimension is therefore equal to the number of elements of X. This construction is used in graph theory, to define the cycle space of a graph.
Intersection distributes over symmetric difference:
Further properties of the symmetric difference:
- , where , is 's complement,'s complement, respectively, relative to any (fixed) set that contains both.
- , where is an arbitrary non-empty index set.
- If is any function and are any sets in 's codomain, then .
The symmetric difference can be defined in any Boolean algebra, by writing
This operation has the same properties as the symmetric difference of sets.
n-ary symmetric difference
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 :
where is meant to indicate that is a subset of distinct elements of , of which there are .
Symmetric difference on measure spaces
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. Formally, if μ is a σ-finite measure defined on a σ-algebra Σ, the function
If , we have: . Indeed,
Let be some measure space and let and .
Symmetric difference is measurable: .
We write iff . The relation "" is an equivalence relation on the -measurable sets.
We write iff to each there's some such that . The relation "" is a partial order on the family of subsets of .
We write iff 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 .
Hausdorff distance vs. Symmetric difference
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.
- Halmos, Paul R. (1960). Naive set theory. The University Series in Undergraduate Mathematics. van Nostrand Company. Zbl 0087.04403.
- Symmetric difference at PlanetMath.org.
- Weisstein, Eric W., "Symmetric Difference", MathWorld.
- Symmetric difference of sets. In Encyclopaedia of Mathematics