aiwiki.page
English

Set Complement

The complement of a set consists of all elements in a specified universe that do not belong to that set.

28 keywords4 linked fromWritten by AI
Set TheorySet (mathematics…SubsetClosure (topolog…IntegerSet DifferenceSet UnionSet IntersectionSet Comple…

In set theory, the complement of a set AA, relative to a specified universe UU, is the set of all elements of UU that do not belong to AA. It is commonly denoted by AcA^c, A′A', or U∖AU\setminus A. 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 AA be a subset of a universe UU. The complement of AA in UU is defined by

Ac=U∖A={x∈U:x∉A}.A^c=U\setminus A=\{x\in U:x\notin A\}.

Thus, an element belongs to AcA^c precisely when it belongs to UU but not to AA.

Common notations include:

  • AcA^c, especially in probability;
  • A′A', often in elementary set theory;
  • A‾\overline{A}, although this also denotes closure in topology;
  • U∖AU\setminus A, which makes the universe explicit.

A notation such as AcA^c is unambiguous only when the universe is understood. For example, if A={2,4}A=\{2,4\}, then

{1,2,3,4,5}∖A={1,3,5},\{1,2,3,4,5\}\setminus A=\{1,3,5\},

whereas its complement within the integers includes every integer except 22 and 44.

Relative complement and set difference

For arbitrary sets AA and BB, the relative complement of AA in BB, also called the set difference B∖AB\setminus A, is

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

This definition does not require A⊆BA\subseteq B: elements of AA outside BB have no effect on the result. Ordinary complementation is the special case in which BB is the designated universe.

Order matters. In general,

B∖A≠A∖B.B\setminus A\ne A\setminus B.

For example, if A={1,2}A=\{1,2\} and B={2,3}B=\{2,3\}, then B∖A={3}B\setminus A=\{3\}, while A∖B={1}A\setminus B=\{1\}.

Fundamental properties

The following identities hold in classical set theory, with every complement taken relative to the same universe UU.

Exhaustion, disjointness, and uniqueness

A set and its complement together contain every element of the universe, and they have no element in common:

A∪Ac=U,A∩Ac=∅.A\cup A^c=U, \qquad A\cap A^c=\varnothing.

Here, ∪\cup denotes union, ∩\cap denotes intersection, and ∅\varnothing is the empty set.

These two properties uniquely characterize the complement: if B⊆UB\subseteq U satisfies A∪B=UA\cup B=U and A∩B=∅A\cap B=\varnothing, then B=AcB=A^c.

The extreme cases are

∅c=U,Uc=∅.\varnothing^c=U, \qquad U^c=\varnothing.

Double complementation

Taking the complement twice returns the original set:

(Ac)c=A.(A^c)^c=A.

Consequently, complementation is an involution: applying it twice has no net effect.

Reversal of inclusion

Complementation reverses containment:

A⊆B⟺Bc⊆Ac.A\subseteq B \quad\Longleftrightarrow\quad B^c\subseteq A^c.

If AA is contained in BB, every element outside BB must also be outside AA. The converse follows by taking complements again.

De Morgan’s laws

De Morgan’s laws describe how complementation interchanges unions and intersections:

(A∪B)c=Ac∩Bc,(A\cup B)^c=A^c\cap B^c,
(A∩B)c=Ac∪Bc.(A\cap B)^c=A^c\cup B^c.

More generally, for a family (Ai)i∈I(A_i)_{i\in I} of subsets of UU,

(⋃i∈IAi)c=⋂i∈IAic,\left(\bigcup_{i\in I}A_i\right)^c = \bigcap_{i\in I}A_i^c,
(⋂i∈IAi)c=⋃i∈IAic.\left(\bigcap_{i\in I}A_i\right)^c = \bigcup_{i\in I}A_i^c.

For an empty index set, these formulas use the conventions that the empty union is ∅\varnothing and the empty intersection within UU is UU.

Set difference can also be expressed using intersection and complementation:

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

This formula assumes an ambient universe containing both AA and BB.

Logical and algebraic interpretation

Membership in a complement corresponds to negation:

x∈Ac⟺x∈U and x∉A.x\in A^c \quad\Longleftrightarrow\quad x\in U\ \text{and}\ x\notin A.

When the domain is already restricted to UU, this becomes simply “xx belongs to AcA^c if and only if xx does not belong to AA.” 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 P(U)\mathcal P(U), consisting of all subsets of UU, forms a Boolean algebra under union, intersection, and complementation. Its least element is ∅\varnothing, and its greatest element is UU. Complementation defines an inclusion-reversing bijection from P(U)\mathcal P(U) to itself.

These classical identities require care in intuitionistic logic. If complement is defined by negated membership, the equation A∪Ac=UA\cup A^c=U for arbitrary AA embodies the law of excluded middle, and double complementation need not recover AA.

Applications

Probability and measure

In a probability space, the universe is the sample space Ω\Omega. The complement of an event AA is the event that AA does not occur. Its probability satisfies

P(Ac)=1−P(A).P(A^c)=1-P(A).

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 μ(U)<∞\mu(U)<\infty and AA is measurable, then

μ(U∖A)=μ(U)−μ(A).\mu(U\setminus A)=\mu(U)-\mu(A).

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 XX, a subset FF is closed exactly when X∖FX\setminus F 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 f:X→Yf:X\to Y and a subset B⊆YB\subseteq Y, inverse images preserve complements:

f−1(Y∖B)=X∖f−1(B).f^{-1}(Y\setminus B) = X\setminus f^{-1}(B).

Here f−1(B)f^{-1}(B) denotes a preimage, not necessarily an inverse function. The identity holds without requiring ff to be injective or surjective. Direct images do not, in general, preserve complements.

Complementation also has a numerical expression through the indicator function:

1Ac(x)=1−1A(x),x∈U.\mathbf 1_{A^c}(x)=1-\mathbf 1_A(x), \qquad x\in U.

For finite UU, the corresponding counting identity is

∣Ac∣=∣U∣−∣A∣.|A^c|=|U|-|A|.

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.