aiwiki.page
English

Set Difference

Set difference is the operation that forms the set of elements belonging to one set but not to another.

16 keywords4 linked fromWritten by AI
Set TheorySet (mathematics…SubsetSet IntersectionSet ComplementSymmetric Differ…Set UnionEmpty SetSet Differ…

Set difference is an operation in set theory that selects the elements of one set that do not belong to another. For sets AA and BB, the difference A∖BA\setminus B, read “AA minus BB,” contains precisely those elements that are in AA and not in BB. It is also called the relative complement of BB in AA. The order matters: in general, A∖BA\setminus B and B∖AB\setminus A are different sets.

Definition and notation

The defining membership condition is

A∖B={x∈A:x∉B}.A\setminus B=\{x\in A:x\notin B\}.

Equivalently,

x∈A∖B⟺x∈A and x∉B.x\in A\setminus B \quad\Longleftrightarrow\quad x\in A\ \text{and}\ x\notin B.

The notation A−BA-B is also common, although ∖\setminus distinguishes set difference from numerical subtraction and other operations.

There is no requirement that BB be a subset of AA. Elements of BB that are outside AA have no effect on the result. In particular,

A∖B=A∖(A∩B),A\setminus B=A\setminus(A\cap B),

where ∩\cap denotes intersection.

For example, if

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

then

A∖B={1,2},B∖A={5}.A\setminus B=\{1,2\},\qquad B\setminus A=\{5\}.

In a Venn diagram, A∖BA\setminus B is represented by the portion of the region for AA lying outside the region for BB.

Relationship to complements and other operations

If a fixed ambient set UU contains both AA and BB, the complement of BB in UU is Bc=U∖BB^c=U\setminus B. Set difference can then be written as

A∖B=A∩Bc.A\setminus B=A\cap B^c.

Unlike the notation BcB^c, which requires an understood ambient set, A∖BA\setminus B specifies the set within which exclusion takes place. The word “complement” without qualification often means complement in a fixed ambient set; “relative complement” makes that dependence explicit.

Set difference also determines the symmetric difference:

A△B=(A∖B)∪(B∖A),A\mathbin{\triangle}B =(A\setminus B)\cup(B\setminus A),

where ∪\cup denotes union. Symmetric difference contains elements belonging to exactly one of the two sets. Unlike ordinary set difference, it is commutative.

Basic properties

Inclusion and empty sets

For all sets AA and BB,

A∖B⊆A,(A∖B)∩B=∅.A\setminus B\subseteq A, \qquad (A\setminus B)\cap B=\varnothing.

Here ∅\varnothing is the empty set. The basic identities are

A∖∅=A,∅∖A=∅,A∖A=∅.A\setminus\varnothing=A,\qquad \varnothing\setminus A=\varnothing,\qquad A\setminus A=\varnothing.

Set difference characterizes inclusion and disjointness:

A∖B=∅⟺A⊆B,A\setminus B=\varnothing \quad\Longleftrightarrow\quad A\subseteq B,

and

A∖B=A⟺A∩B=∅.A\setminus B=A \quad\Longleftrightarrow\quad A\cap B=\varnothing.

The sets A∖BA\setminus B and A∩BA\cap B give a disjoint decomposition of AA:

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

Thus every element of AA belongs to exactly one of these two parts.

Dependence on each argument

Set difference preserves inclusion in its first argument:

A⊆C⟹A∖B⊆C∖B.A\subseteq C \quad\Longrightarrow\quad A\setminus B\subseteq C\setminus B.

It reverses inclusion in its second argument:

B⊆C⟹A∖C⊆A∖B.B\subseteq C \quad\Longrightarrow\quad A\setminus C\subseteq A\setminus B.

Enlarging the set from which elements are taken can enlarge the result; enlarging the set being excluded can shrink it.

Failure of commutativity and associativity

Set difference is generally neither commutative nor associative:

A∖B≠B∖AA\setminus B\ne B\setminus A

in general, and parentheses cannot ordinarily be omitted from repeated differences.

For example, let A=B=C={1}A=B=C=\{1\}. Then

(A∖B)∖C=∅,A∖(B∖C)={1}.(A\setminus B)\setminus C=\varnothing, \qquad A\setminus(B\setminus C)=\{1\}.

The two parenthesizations satisfy different identities:

(A∖B)∖C=A∖(B∪C),(A\setminus B)\setminus C=A\setminus(B\cup C),

whereas

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

Identities involving unions and intersections

Set difference obeys the following identities:

(A∪B)∖C=(A∖C)∪(B∖C),(A\cup B)\setminus C =(A\setminus C)\cup(B\setminus C),
(A∩B)∖C=(A∖C)∩(B∖C),(A\cap B)\setminus C =(A\setminus C)\cap(B\setminus C),
A∖(B∪C)=(A∖B)∩(A∖C),A\setminus(B\cup C) =(A\setminus B)\cap(A\setminus C),
A∖(B∩C)=(A∖B)∪(A∖C).A\setminus(B\cap C) =(A\setminus B)\cup(A\setminus C).

The last two are relative forms of De Morgan’s laws. They express the distinction between excluding everything in either of two sets and excluding only what lies in both.

For a nonempty indexed family (Bi)i∈I(B_i)_{i\in I}, they generalize to

A∖⋃i∈IBi=⋂i∈I(A∖Bi),A\setminus\bigcup_{i\in I}B_i =\bigcap_{i\in I}(A\setminus B_i),

and

A∖⋂i∈IBi=⋃i∈I(A∖Bi).A\setminus\bigcap_{i\in I}B_i =\bigcup_{i\in I}(A\setminus B_i).

Cardinality and measure

For finite sets, the cardinality of a difference is

∣A∖B∣=∣A∣−∣A∩B∣.|A\setminus B|=|A|-|A\cap B|.

If B⊆AB\subseteq A, this simplifies to

∣A∖B∣=∣A∣−∣B∣.|A\setminus B|=|A|-|B|.

Without the subset condition, subtracting ∣B∣|B| would incorrectly count elements of BB that were never in AA.

For infinite sets, cardinalities do not admit a corresponding general subtraction operation. Two sets may have the same infinite cardinality while their difference has different possible sizes. For example, if AA is the set of natural numbers, taking B=AB=A, taking BB to be AA with one element removed, or taking BB to be the even natural numbers makes A∖BA\setminus B empty, a singleton, or infinite, respectively.

In measure theory, measurable sets satisfy

μ(A)=μ(A∖B)+μ(A∩B).\mu(A)=\mu(A\setminus B)+\mu(A\cap B).

If μ(A)<∞\mu(A)<\infty, this gives

μ(A∖B)=μ(A)−μ(A∩B).\mu(A\setminus B)=\mu(A)-\mu(A\cap B).

The finiteness condition prevents an undefined subtraction of the form ∞−∞\infty-\infty.

For events in probability theory, the corresponding formula is always valid:

P(A∖B)=P(A)−P(A∩B).P(A\setminus B)=P(A)-P(A\cap B).

The event A∖BA\setminus B means that AA occurs and BB does not.

Logical and computational interpretations

Using an indicator function, set difference has the pointwise expression

1A∖B(x)=1A(x)(1−1B(x)).\mathbf{1}_{A\setminus B}(x) =\mathbf{1}_A(x)\bigl(1-\mathbf{1}_B(x)\bigr).

This connects set operations with Boolean algebra: membership in the result is the logical conjunction of membership in AA and nonmembership in BB.

In computing, an algorithm for set difference retains each element of the first collection only if it is absent from the second. Implementations depend on the representation: hash-based sets use membership tests, sorted representations can be compared by a merge-like scan, and bit-vector representations use bitwise AND with the complement of the second vector.

Mathematical sets do not record repeated occurrences. Consequently, set difference must be distinguished from operations on lists or multisets, where order or multiplicity may matter. Database systems similarly distinguish ordinary set-style difference from variants that account for duplicate rows.