![]() | |
Type | Set operation |
---|---|
Field | Set theory |
Statement | The symmetric difference is the set of elements that are in either set, but not in the intersection. |
Symbolic statement |
In mathematics, the symmetric difference of two sets, also known as the disjunctive union and set sum, 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 symmetric difference of the sets A and B is commonly denoted by (traditionally, ), , or . It can be viewed as a form of addition modulo 2.
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.
The symmetric difference is equivalent to the union of both relative complements, that is: [1]
The symmetric difference can also be expressed using the XOR operation ⊕ on the predicates describing the two sets in set-builder notation:
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
The symmetric difference is commutative and associative:
The empty set is neutral, and every set is its own inverse:
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; [2] [3] 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. [4] In the case where X has only two elements, the group thus obtained is the Klein four-group.
Equivalently, a Boolean group is an elementary abelian 2-group. Consequently, the group induced by the symmetric difference 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.
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: [5] 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.
Intersection distributes over symmetric difference:
and this shows that the power set of X becomes a ring, with symmetric difference as addition and intersection as multiplication. This is the prototypical example of a Boolean ring.
Further properties of the symmetric difference include:
The symmetric difference can be defined in any Boolean algebra, by writing
This operation has the same properties as the symmetric difference of sets.
Repeated symmetric difference is in a sense equivalent to an operation on a multitude of sets (possibly with multiple appearances of the same set) giving the set of elements which are in an odd number of sets.
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 :
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. [6]
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 σ-finite measure defined on a σ-algebra Σ, the function
is a pseudometric on Σ. dμ becomes a metric if Σ is considered modulo the equivalence relation X ~ Y if and only if . It is sometimes called Fréchet-Nikodym metric. The resulting metric space is separable if and only if L2(μ) is separable.
If , we have: . Indeed,
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 .
iff almost everywhere.
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.
In mathematics, the concept of a measure is a generalization and formalization of geometrical measures and other common notions, such as magnitude, mass, and probability of events. These seemingly distinct concepts have many similarities and can often be treated together in a single mathematical context. Measures are foundational in probability theory, integration theory, and can be generalized to assume negative values, as with electrical charge. Far-reaching generalizations of measure are widely used in quantum physics and physics in general.
In mathematical analysis and in probability theory, a σ-algebra on a set X is a nonempty collection Σ of subsets of X closed under complement, countable unions, and countable intersections. The ordered pair is called a measurable space.
In the mathematical field of real analysis, the monotone convergence theorem is any of a number of related theorems proving the convergence of monotonic sequences that are also bounded. Informally, the theorems state that if a sequence is increasing and bounded above by a supremum, then the sequence will converge to the supremum; in the same way, if a sequence is decreasing and is bounded below by an infimum, it will converge to the infimum.
In mathematics, Fatou's lemma establishes an inequality relating the Lebesgue integral of the limit inferior of a sequence of functions to the limit inferior of integrals of these functions. The lemma is named after Pierre Fatou.
In the mathematical field of measure theory, an outer measure or exterior measure is a function defined on all subsets of a given set with values in the extended real numbers satisfying some additional technical conditions. The theory of outer measures was first introduced by Constantin Carathéodory to provide an abstract basis for the theory of measurable sets and countably additive measures. Carathéodory's work on outer measures found many applications in measure-theoretic set theory, and was used in an essential way by Hausdorff to define a dimension-like metric invariant now called Hausdorff dimension. Outer measures are commonly used in the field of geometric measure theory.
In mathematics, an additive set function is a function mapping sets to numbers, with the property that its value on a union of two disjoint sets equals the sum of its values on these sets, namely, If this additivity property holds for any two sets, then it also holds for any finite number of sets, namely, the function value on the union of k disjoint sets equals the sum of its values on the sets. Therefore, an additive set function is also called a finitely additive set function. However, a finitely additive set function might not have the additivity property for a union of an infinite number of sets. A σ-additive set function is a function that has the additivity property even for countably infinite many sets, that is,
In measure theory, an area of mathematics, Egorov's theorem establishes a condition for the uniform convergence of a pointwise convergent sequence of measurable functions. It is also named Severini–Egoroff theorem or Severini–Egorov theorem, after Carlo Severini, an Italian mathematician, and Dmitri Egorov, a Russian physicist and geometer, who published independent proofs respectively in 1910 and 1911.
A Dynkin system, named after Eugene Dynkin, is a collection of subsets of another universal set satisfying a set of axioms weaker than those of 𝜎-algebra. Dynkin systems are sometimes referred to as 𝜆-systems or d-system. These set families have applications in measure theory and probability.
In mathematics, there are two different notions of a ring of sets, both referring to certain families of sets.
In mathematics, the Hahn decomposition theorem, named after the Austrian mathematician Hans Hahn, states that for any measurable space and any signed measure defined on the -algebra , there exist two -measurable sets, and , of such that:
In measure theory, Carathéodory's extension theorem states that any pre-measure defined on a given ring of subsets R of a given set Ω can be extended to a measure on the σ-ring generated by R, and this extension is unique if the pre-measure is σ-finite. Consequently, any pre-measure on a ring containing all intervals of real numbers can be extended to the Borel algebra of the set of real numbers. This is an extremely powerful result of measure theory, and leads, for example, to the Lebesgue measure.
In mathematics, a π-system on a set is a collection of certain subsets of such that
In mathematics, a positive (or signed) measure μ defined on a σ-algebra Σ of subsets of a set X is called a finite measure if μ(X) is a finite real number (rather than ∞). A set A in Σ is of finite measure if μ(A) < ∞. The measure μ is called σ-finite if X is a countable union of measurable sets each with finite measure. A set in a measure space is said to have σ-finite measure if it is a countable union of measurable sets with finite measure. A measure being σ-finite is a weaker condition than being finite, i.e. all finite measures are σ-finite but there are (many) σ-finite measures that are not finite.
In mathematics, the Lévy–Prokhorov metric is a metric on the collection of probability measures on a given metric space. It is named after the French mathematician Paul Lévy and the Soviet mathematician Yuri Vasilyevich Prokhorov; Prokhorov introduced it in 1956 as a generalization of the earlier Lévy metric.
In mathematics, the disintegration theorem is a result in measure theory and probability theory. It rigorously defines the idea of a non-trivial "restriction" of a measure to a measure zero subset of the measure space in question. It is related to the existence of conditional probability measures. In a sense, "disintegration" is the opposite process to the construction of a product measure.
In mathematics, in particular in measure theory, a content is a real-valued function defined on a collection of subsets such that
In mathematics, a filter on a set is a family of subsets such that:
In mathematics, especially measure theory, a set function is a function whose domain is a family of subsets of some given set and that (usually) takes its values in the extended real number line which consists of the real numbers and
In the mathematical field of set theory, an ultrafilter on a set is a maximal filter on the set In other words, it is a collection of subsets of that satisfies the definition of a filter on and that is maximal with respect to inclusion, in the sense that there does not exist a strictly larger collection of subsets of that is also a filter. Equivalently, an ultrafilter on the set can also be characterized as a filter on with the property that for every subset of either or its complement belongs to the ultrafilter.