In set theory, the complement of a set , relative to a specified universe , is the set of all elements of that do not belong to . It is commonly denoted by , , or . Complementation expresses “not belonging” within a fixed domain and is a fundamental operation in logic, probability, topology, and the algebra of sets.
Definition and notation
Let be a subset of a universe . The complement of in is defined by
Thus, an element belongs to precisely when it belongs to but not to .
Common notations include:
- , especially in probability;
- , often in elementary set theory;
- , although this also denotes closure in topology;
- , which makes the universe explicit.
A notation such as is unambiguous only when the universe is understood. For example, if , then
whereas its complement within the integers includes every integer except and .
Relative complement and set difference
For arbitrary sets and , the relative complement of in , also called the set difference , is
This definition does not require : elements of outside have no effect on the result. Ordinary complementation is the special case in which is the designated universe.
Order matters. In general,
For example, if and , then , while .
Fundamental properties
The following identities hold in classical set theory, with every complement taken relative to the same universe .
Exhaustion, disjointness, and uniqueness
A set and its complement together contain every element of the universe, and they have no element in common:
Here, denotes union, denotes intersection, and is the empty set.
These two properties uniquely characterize the complement: if satisfies and , then .
The extreme cases are
Double complementation
Taking the complement twice returns the original set:
Consequently, complementation is an involution: applying it twice has no net effect.
Reversal of inclusion
Complementation reverses containment:
If is contained in , every element outside must also be outside . The converse follows by taking complements again.
De Morgan’s laws
De Morgan’s laws describe how complementation interchanges unions and intersections:
More generally, for a family of subsets of ,
For an empty index set, these formulas use the conventions that the empty union is and the empty intersection within is .
Set difference can also be expressed using intersection and complementation:
This formula assumes an ambient universe containing both and .
Logical and algebraic interpretation
Membership in a complement corresponds to negation:
When the domain is already restricted to , this becomes simply “ belongs to if and only if does not belong to .” Union and intersection similarly correspond to logical disjunction and conjunction. The identities of set complementation therefore parallel identities in classical propositional logic.
The power set , consisting of all subsets of , forms a Boolean algebra under union, intersection, and complementation. Its least element is , and its greatest element is . Complementation defines an inclusion-reversing bijection from to itself.
These classical identities require care in intuitionistic logic. If complement is defined by negated membership, the equation for arbitrary embodies the law of excluded middle, and double complementation need not recover .
Applications
Probability and measure
In a probability space, the universe is the sample space . The complement of an event is the event that does not occur. Its probability satisfies
For example, the event “at least one success occurs” is the complement of “no successes occur.” This can make probabilities easier to calculate, although any assumptions about independence must be justified separately.
A sigma-algebra is, by definition, closed under complementation relative to its underlying space. Thus, whenever an event is measurable, its complement is measurable as well.
More generally, in measure theory, if and is measurable, then
If both measures on the right are infinite, this subtraction is not defined; it cannot be used to determine the measure of the complement.
Topology
In a topological space , a subset is closed exactly when is open. Complementation therefore converts statements about open sets into corresponding statements about closed sets.
For instance, arbitrary unions of open sets are open. By De Morgan’s laws, this is equivalent to the statement that arbitrary intersections of closed sets are closed.
The ambient space remains essential. A set may have different complements, and different openness or closedness properties, depending on which space contains it.
Functions and indicators
For a function and a subset , inverse images preserve complements:
Here denotes a preimage, not necessarily an inverse function. The identity holds without requiring to be injective or surjective. Direct images do not, in general, preserve complements.
Complementation also has a numerical expression through the indicator function:
For finite , the corresponding counting identity is
This finite subtraction rule does not extend directly to arbitrary infinite cardinalities.
Scope and distinctions
In Zermelo–Fraenkel set theory, there is no set containing every set. A complement must therefore be taken relative to a specified set, not an unrestricted universal set. An alleged set of all sets would lead to Russell’s paradox.
Set complementation is also distinct from the orthogonal complement of a subspace in an inner-product space. An orthogonal complement consists of vectors perpendicular to every vector in the given subspace; it is not the collection of vectors outside that subspace. In particular, a subspace and its orthogonal complement both contain the zero vector, whereas a set and its set-theoretic complement are disjoint.