Set difference is an operation in set theory that selects the elements of one set that do not belong to another. For sets and , the difference , read “ minus ,” contains precisely those elements that are in and not in . It is also called the relative complement of in . The order matters: in general, and are different sets.
Definition and notation
The defining membership condition is
Equivalently,
The notation is also common, although distinguishes set difference from numerical subtraction and other operations.
There is no requirement that be a subset of . Elements of that are outside have no effect on the result. In particular,
where denotes intersection.
For example, if
then
In a Venn diagram, is represented by the portion of the region for lying outside the region for .
Relationship to complements and other operations
If a fixed ambient set contains both and , the complement of in is . Set difference can then be written as
Unlike the notation , which requires an understood ambient set, 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:
where 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 and ,
Here is the empty set. The basic identities are
Set difference characterizes inclusion and disjointness:
and
The sets and give a disjoint decomposition of :
Thus every element of belongs to exactly one of these two parts.
Dependence on each argument
Set difference preserves inclusion in its first argument:
It reverses inclusion in its second argument:
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:
in general, and parentheses cannot ordinarily be omitted from repeated differences.
For example, let . Then
The two parenthesizations satisfy different identities:
whereas
Identities involving unions and intersections
Set difference obeys the following identities:
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 , they generalize to
and
Cardinality and measure
For finite sets, the cardinality of a difference is
If , this simplifies to
Without the subset condition, subtracting would incorrectly count elements of that were never in .
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 is the set of natural numbers, taking , taking to be with one element removed, or taking to be the even natural numbers makes empty, a singleton, or infinite, respectively.
In measure theory, measurable sets satisfy
If , this gives
The finiteness condition prevents an undefined subtraction of the form .
For events in probability theory, the corresponding formula is always valid:
The event means that occurs and does not.
Logical and computational interpretations
Using an indicator function, set difference has the pointwise expression
This connects set operations with Boolean algebra: membership in the result is the logical conjunction of membership in and nonmembership in .
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.