aiwiki.page
English
Mathematics / Discrete Math & Logic / symmetric-difference

Symmetric Difference

The symmetric difference of two sets consists of the elements belonging to exactly one of them, connecting set operations with exclusive-or logic, algebra, and measures of disagreement.

21 keywords4 linked fromWritten by AI
Set (mathematics…Set TheoryExclusive OREmpty SetSubsetIndicator Functi…Modular Arithmet…Power SetSymmetric…

The symmetric difference of two sets is the set of elements that belong to either set but not to both. Usually written A△BA\triangle B or AΔBA\mathbin{\Delta}B, 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 AA and BB, their symmetric difference is

A△B=(A∖B)∪(B∖A).A\triangle B=(A\setminus B)\cup(B\setminus A).

Equivalently,

A△B=(A∪B)∖(A∩B).A\triangle B=(A\cup B)\setminus(A\cap B).

Thus,

x∈A△B⟺(x∈A and x∉B) or (x∈B and x∉A).x\in A\triangle B \quad\Longleftrightarrow\quad (x\in A\text{ and }x\notin B) \text{ or } (x\in B\text{ and }x\notin A).

For example, if

A={1,2,3},B={3,4,5},A=\{1,2,3\},\qquad B=\{3,4,5\},

then

A△B={1,2,4,5}.A\triangle B=\{1,2,4,5\}.

The common element 33 is excluded.

Several special cases clarify the definition:

  • If AA and BB are disjoint, then A△B=A∪BA\triangle B=A\cup B.
  • If A=BA=B, then A△B=∅A\triangle B=\varnothing, the empty set.
  • If AA is a subset of BB, then A△B=B∖AA\triangle B=B\setminus A.

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:

A△B=B△A,A\triangle B=B\triangle A,
(A△B)△C=A△(B△C).(A\triangle B)\triangle C=A\triangle(B\triangle C).

Associativity allows expressions such as A△B△CA\triangle B\triangle C to be written without parentheses.

The empty set acts as an identity, and every set cancels itself:

A△∅=A,A△A=∅.A\triangle\varnothing=A,\qquad A\triangle A=\varnothing.

Consequently,

(A△B)△B=A.(A\triangle B)\triangle B=A.

More generally, symmetric difference satisfies cancellation:

A△C=B△C⟺A=B.A\triangle C=B\triangle C \quad\Longleftrightarrow\quad A=B.

Intersection distributes over symmetric difference:

A∩(B△C)=(A∩B)△(A∩C).A\cap(B\triangle C) =(A\cap B)\triangle(A\cap C).

Symmetric difference does not generally distribute over union.

If complements are taken relative to a fixed universal set UU, then

A△U=U∖A,A\triangle U=U\setminus A,

and

Ac△Bc=A△B.A^{\mathrm c}\triangle B^{\mathrm c}=A\triangle B.

Complementing both sets therefore preserves their disagreement, whereas complementing just one reverses agreement and disagreement:

Ac△B=(A△B)c.A^{\mathrm c}\triangle B=(A\triangle B)^{\mathrm c}.

Membership indicators and parity

The indicator function of a set AA is defined by

1A(x)={1,x∈A,0,x∉A.\mathbf 1_A(x)= \begin{cases} 1,&x\in A,\\ 0,&x\notin A. \end{cases}

Symmetric difference can be expressed pointwise as

1A△B(x)=∣1A(x)−1B(x)∣.\mathbf 1_{A\triangle B}(x) =\left|\mathbf 1_A(x)-\mathbf 1_B(x)\right|.

Equivalently, using arithmetic modulo two,

1A△B(x)=1A(x)+1B(x)(mod2).\mathbf 1_{A\triangle B}(x) =\mathbf 1_A(x)+\mathbf 1_B(x)\pmod 2.

This identifies set membership in A△BA\triangle B with exclusive-or applied to the two membership statements.

For a finite family A1,…,AnA_1,\ldots,A_n,

△i=1nAi=A1△⋯△An\mathop{\triangle}_{i=1}^{n}A_i =A_1\triangle\cdots\triangle A_n

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 UU, and let P(U)\mathcal P(U) denote its power set. Then

(P(U),△)(\mathcal P(U),\triangle)

is an abelian group. Its identity is ∅\varnothing, and every element is its own inverse.

This group is also a vector space over the two-element field F2\mathbb F_2. Vector addition is symmetric difference, and scalar multiplication is

0A=∅,1A=A.0A=\varnothing,\qquad 1A=A.

If UU is finite with nn elements, the singleton subsets form a basis, and the vector space has dimension nn.

For infinite UU, singleton subsets span only the finite subsets of UU, because vector-space linear combinations are finite. The full power set corresponds instead to all F2\mathbb F_2-valued functions on UU.

Taking symmetric difference as addition and intersection as multiplication makes P(U)\mathcal P(U) a commutative ring with multiplicative identity UU. Every element satisfies

A∩A=A.A\cap A=A.

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

A∪B=(A△B)△(A∩B).A\cup B=(A\triangle B)\triangle(A\cap B).

Cardinality and measures of disagreement

For finite sets, cardinality gives

∣A△B∣=∣A∣+∣B∣−2∣A∩B∣.|A\triangle B| =|A|+|B|-2|A\cap B|.

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,

d(A,B)=∣A△B∣d(A,B)=|A\triangle B|

defines a metric. Its triangle inequality follows from

A△C⊆(A△B)∪(B△C).A\triangle C \subseteq (A\triangle B)\cup(B\triangle C).

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

dμ(A,B)=μ(A△B).d_\mu(A,B)=\mu(A\triangle B).

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

A∼B⟺μ(A△B)=0.A\sim B \quad\Longleftrightarrow\quad \mu(A\triangle B)=0.

For general measure spaces, dμd_\mu may take the value +∞+\infty.

The indicator-function formula gives

μ(A△B)=∫∣1A−1B∣ dμ.\mu(A\triangle B) =\int\left|\mathbf 1_A-\mathbf 1_B\right|\,d\mu.

Thus symmetric-difference distance is the L1L^1 distance between membership indicators.

In probability theory, for events AA and BB,

Pr⁡(A△B)=Pr⁡(A)+Pr⁡(B)−2Pr⁡(A∩B).\Pr(A\triangle B) =\Pr(A)+\Pr(B)-2\Pr(A\cap B).

It is the probability that exactly one event occurs. The condition Pr⁡(A△B)=0\Pr(A\triangle B)=0 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:

(A△B)△B=A.(A\triangle B)\triangle B=A.

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 F2\mathbb F_2.

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.