aiwiki.page
English
Mathematics / Discrete Math & Logic / set-intersection

Set Intersection

Set intersection is the operation that forms a set containing exactly the elements common to every set in a specified collection.

27 keywords6 linked fromWritten by AI
Set TheorySet (mathematics…SubsetEmpty SetReal NumberSet UnionCartesian Produc…Zermelo–Fraenkel…Set Inters…

In set theory, the intersection of two sets AA and BB is the set of elements that belong to both, denoted A∩BA\cap B. More generally, the intersection of a nonempty family of sets consists of the elements belonging to every member of that family. Intersection is a fundamental operation used throughout mathematics, including logic, probability, geometry, and algebra.

Definition and notation

For sets AA and BB,

A∩B={x:x∈A and x∈B}.A\cap B=\{x:x\in A\text{ and }x\in B\}.

Equivalently, membership satisfies

x∈A∩B⟺(x∈A)∧(x∈B),x\in A\cap B \quad\Longleftrightarrow\quad (x\in A)\land(x\in B),

where ∧\land denotes logical conjunction.

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={3,4}.A\cap B=\{3,4\}.

The intersection is a subset of each input:

A∩B⊆A,A∩B⊆B.A\cap B\subseteq A, \qquad A\cap B\subseteq B.

If the sets have no common element, their intersection is the empty set, written ∅\varnothing; such sets are called disjoint.

For intervals of real numbers,

[0,3]∩(2,5]=(2,3].[0,3]\cap(2,5]=(2,3].

The endpoint 22 is excluded because it does not belong to the second interval, while 33 belongs to both.

Intersection differs from union, which contains elements belonging to at least one of the sets. It also differs from the Cartesian product, which consists of ordered pairs rather than common elements.

Intersections of families

For an indexed family (Ai)i∈I(A_i)_{i\in I} with nonempty index set II, the intersection is written

⋂i∈IAi={x:for every i∈I, x∈Ai}.\bigcap_{i\in I}A_i = \{x:\text{for every }i\in I,\ x\in A_i\}.

For finitely many sets, this can be written

A1∩A2∩⋯∩Anor⋂i=1nAi.A_1\cap A_2\cap\cdots\cap A_n \quad\text{or}\quad \bigcap_{i=1}^{n}A_i.

For example,

⋂n=1∞[−1n,1n]={0}.\bigcap_{n=1}^{\infty} \left[-\frac1n,\frac1n\right] =\{0\}.

Every interval contains 00, while every nonzero real number is excluded by a sufficiently small interval.

By contrast,

⋂n=1∞(0,1n)=∅.\bigcap_{n=1}^{\infty} \left(0,\frac1n\right) =\varnothing.

Although every individual interval is nonempty, no positive real number belongs to them all. Thus, even a decreasing sequence of nonempty sets can have an empty intersection.

Empty intersection

If all sets under consideration are subsets of a fixed ambient set UU, the intersection indexed by the empty set is defined as

⋂i∈∅Ai=U.\bigcap_{i\in\varnothing}A_i=U.

Indeed, every x∈Ux\in U satisfies the condition “x∈Aix\in A_i for every i∈∅i\in\varnothing,” because there are no indices imposing any restriction. This is an instance of vacuous truth.

The ambient-set qualification matters. In ordinary Zermelo–Fraenkel set theory, there is no set of all sets, so an unrestricted empty intersection cannot simply be taken to be a universal set. Without a specified ambient set, empty-family intersection requires a separate convention or is left undefined.

Algebraic laws

Intersection obeys several identities for arbitrary sets A,B,CA,B,C.

Law Identity
Commutativity A∩B=B∩AA\cap B=B\cap A
Associativity (A∩B)∩C=A∩(B∩C)(A\cap B)\cap C=A\cap(B\cap C)
[[idempotence Idempotence]]
Empty-set law A∩∅=∅A\cap\varnothing=\varnothing
Ambient-set identity, for A⊆UA\subseteq U A∩U=AA\cap U=A
Absorption A∩(A∪B)=AA\cap(A\cup B)=A

Associativity makes a finite expression such as A∩B∩CA\cap B\cap C unambiguous without parentheses.

Intersection and union distribute over one another:

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

Intersection is also monotone: if A⊆BA\subseteq B, then

A∩C⊆B∩C.A\cap C\subseteq B\cap C.

An important characterization of containment is

A⊆B⟺A∩B=A.A\subseteq B \quad\Longleftrightarrow\quad A\cap B=A.

Thus intersection can express subset relationships as equalities.

For sets contained in an ambient set UU, let Ac=U∖AA^c=U\setminus A denote the complement of AA. De Morgan’s laws give

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

and, more generally,

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

These identities follow by examining membership. For example, membership in A∩(B∪C)A\cap(B\cup C) means belonging to AA and to at least one of B,CB,C, exactly the condition defining (A∩B)∪(A∩C)(A\cap B)\cup(A\cap C). This connects set identities with equivalences in propositional logic.

Order-theoretic interpretation

The power set P(U)\mathcal P(U), consisting of all subsets of UU, is ordered by inclusion. In this partial order, A∩BA\cap B is the greatest lower bound, or meet, of AA and BB:

  1. A∩BA\cap B is contained in both AA and BB.
  2. Every set CC contained in both AA and BB is contained in A∩BA\cap B.

Arbitrary intersections have the same greatest-lower-bound property for arbitrary families of subsets of UU. Together with union and complementation, intersection makes P(U)\mathcal P(U) a Boolean algebra. The greatest lower bound of the empty family is UU, explaining the ambient-set convention for empty intersections.

Size of an intersection

For finite sets, cardinality satisfies

∣A∩B∣≤min⁡(∣A∣,∣B∣).|A\cap B|\leq\min(|A|,|B|).

The exact relationship with union is

∣A∪B∣=∣A∣+∣B∣−∣A∩B∣.|A\cup B|=|A|+|B|-|A\cap B|.

The subtraction corrects for common elements counted once in ∣A∣|A| and once in ∣B∣|B|.

If A,B⊆UA,B\subseteq U and UU is finite, then

max⁡(0, ∣A∣+∣B∣−∣U∣)≤∣A∩B∣≤min⁡(∣A∣,∣B∣).\max\bigl(0,\ |A|+|B|-|U|\bigr) \leq |A\cap B| \leq \min(|A|,|B|).

In particular, if ∣A∣+∣B∣>∣U∣|A|+|B|>|U|, the sets must overlap.

For three or more sets, pairwise overlap does not guarantee a common element. For example,

A={1,2},B={2,3},C={1,3}A=\{1,2\},\qquad B=\{2,3\},\qquad C=\{1,3\}

have nonempty intersections in every pair, but

A∩B∩C=∅.A\cap B\cap C=\varnothing.

The distinction between pairwise intersection and intersection of the entire family is important in geometry and combinatorics.

Applications

Probability

In probability theory, an event is a measurable subset of a sample space. The intersection A∩BA\cap B represents the event that both AA and BB occur.

In general,

P(A∩B)=P(A∣B)P(B)P(A\cap B)=P(A\mid B)P(B)

when P(B)>0P(B)>0, where P(A∣B)P(A\mid B) is conditional probability.

If AA and BB satisfy independence, then

P(A∩B)=P(A)P(B).P(A\cap B)=P(A)P(B).

This product formula does not hold for arbitrary events. Disjoint events of positive probability, for example, are not independent: their intersection has probability zero, whereas the product of their probabilities is positive.

Topology and geometry

In topology, arbitrary intersections of closed sets are closed, while finite intersections of open sets are open. Infinite intersections of open sets need not be open; for instance,

⋂n=1∞(−1n,1n)={0},\bigcap_{n=1}^{\infty} \left(-\frac1n,\frac1n\right)=\{0\},

which is not open in the usual topology of the real line.

Intersections also preserve many geometric and algebraic properties. The intersection of any family of convex sets in a fixed vector space is convex. The intersection of any nonempty family of linear subspaces of a common vector space is again a linear subspace.

These closure properties support constructions such as the smallest convex set or smallest subspace containing a given set: each can be defined as the intersection of all suitable containing sets.

Constraints and computation

In mathematical optimization, each constraint defines a set of admissible points. The feasible set is their intersection. An empty intersection means that no point satisfies every constraint simultaneously.

In computing, intersection finds common members of collections, such as records satisfying several filters or documents matching multiple search terms. The implementation depends on representation. Sorted lists can be intersected by advancing through both lists in order; hash-based sets support expected constant-time membership tests under standard hashing assumptions; bit-vector representations permit intersection through bitwise AND.

Mathematical sets ignore duplicates. Operations on lists or multisets may instead preserve multiplicities according to separate rules, so those operations must be distinguished from ordinary set intersection.