The symmetric difference of two sets is the set of elements that belong to either set but not to both. Usually written or , it captures the difference between their memberships without giving either set priority. It is a basic operation in set theory and corresponds to exclusive-or in logic and addition modulo two in algebra.
Definition and examples
For sets and , their symmetric difference is
Equivalently,
Thus,
For example, if
then
The common element is excluded.
Several special cases clarify the definition:
Unlike ordinary set difference, symmetric difference is unchanged when the two sets are exchanged. Unlike disjoint union, it removes shared elements rather than retaining separately tagged copies of them.
Fundamental identities
Symmetric difference is commutative and associative:
Associativity allows expressions such as to be written without parentheses.
The empty set acts as an identity, and every set cancels itself:
Consequently,
More generally, symmetric difference satisfies cancellation:
Intersection distributes over symmetric difference:
Symmetric difference does not generally distribute over union.
If complements are taken relative to a fixed universal set , then
and
Complementing both sets therefore preserves their disagreement, whereas complementing just one reverses agreement and disagreement:
Membership indicators and parity
The indicator function of a set is defined by
Symmetric difference can be expressed pointwise as
Equivalently, using arithmetic modulo two,
This identifies set membership in with exclusive-or applied to the two membership statements.
For a finite family ,
contains precisely the elements that occur in an odd number of the sets. In particular, the symmetric difference of three sets includes elements belonging to all three, not only those belonging to exactly one.
For an infinite family, the finite parity rule does not automatically define an operation: an element may belong to infinitely many sets, for which ordinary even–odd counting is unavailable. An infinite symmetric difference can be defined by parity when every element belongs to only finitely many members of the family, but unrestricted infinite families require an additional definition or convergence framework.
Algebraic structure
Fix a set , and let denote its power set. Then
is an abelian group. Its identity is , and every element is its own inverse.
This group is also a vector space over the two-element field . Vector addition is symmetric difference, and scalar multiplication is
If is finite with elements, the singleton subsets form a basis, and the vector space has dimension .
For infinite , singleton subsets span only the finite subsets of , because vector-space linear combinations are finite. The full power set corresponds instead to all -valued functions on .
Taking symmetric difference as addition and intersection as multiplication makes a commutative ring with multiplicative identity . Every element satisfies
A ring in which every element is multiplicatively idempotent is called a Boolean ring. This construction connects symmetric difference with Boolean algebra: union can be recovered from symmetric difference and intersection through
Cardinality and measures of disagreement
For finite sets, cardinality gives
The intersection is subtracted twice because its elements were counted once in each set but must not appear in the symmetric difference.
On subsets of a finite universe,
defines a metric. Its triangle inequality follows from
When subsets are encoded as binary membership vectors, this distance counts the coordinates at which the vectors differ, commonly called Hamming distance.
In measure theory, the analogous construction is
On a finite measure space this is a pseudometric: it satisfies symmetry and the triangle inequality, but distinct sets can have distance zero if they differ only on a set of measure zero. Identifying such sets produces a genuine metric. This identification is an equivalence relation defined by
For general measure spaces, may take the value .
The indicator-function formula gives
Thus symmetric-difference distance is the distance between membership indicators.
In probability theory, for events and ,
It is the probability that exactly one event occurs. The condition means their indicators agree almost surely, although the events need not be identical as sets.
Computational and graph-theoretic uses
In software, symmetric difference identifies elements present in one collection but absent from the other. It is used to compare identifier sets, detect membership changes, and toggle selected elements. Applying the same update set twice restores the original set:
Implementation depends on representation. Bit-vector sets use bitwise exclusive-or. Sorted collections can be processed by a merge-style scan. Hash-based sets can be compared by membership tests, with performance depending on the hashing assumptions. These procedures implement ordinary set semantics; duplicate-sensitive collections require a separately specified rule.
In graph theory, subgraphs on a common vertex set can be combined by taking the symmetric difference of their edge sets. Shared edges cancel, and edges present in exactly one subgraph remain. The edge subsets in which every vertex has even degree are closed under this operation and form the graph’s cycle space over .
Although cycles generate this space, the symmetric difference of two individual cycles need not be a single cycle. It may be empty or consist of several cycles, reflecting the algebraic cancellation of their shared edges.