In set theory, the intersection of two sets and is the set of elements that belong to both, denoted . 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 and ,
Equivalently, membership satisfies
where denotes logical conjunction.
For example, if
then
The intersection is a subset of each input:
If the sets have no common element, their intersection is the empty set, written ; such sets are called disjoint.
For intervals of real numbers,
The endpoint is excluded because it does not belong to the second interval, while 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 with nonempty index set , the intersection is written
For finitely many sets, this can be written
For example,
Every interval contains , while every nonzero real number is excluded by a sufficiently small interval.
By contrast,
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 , the intersection indexed by the empty set is defined as
Indeed, every satisfies the condition “ for every ,” 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 .
| Law | Identity |
|---|---|
| Commutativity | |
| Associativity | |
| [[idempotence | Idempotence]] |
| Empty-set law | |
| Ambient-set identity, for | |
| Absorption |
Associativity makes a finite expression such as unambiguous without parentheses.
Intersection and union distribute over one another:
Intersection is also monotone: if , then
An important characterization of containment is
Thus intersection can express subset relationships as equalities.
For sets contained in an ambient set , let denote the complement of . De Morgan’s laws give
and, more generally,
These identities follow by examining membership. For example, membership in means belonging to and to at least one of , exactly the condition defining . This connects set identities with equivalences in propositional logic.
Order-theoretic interpretation
The power set , consisting of all subsets of , is ordered by inclusion. In this partial order, is the greatest lower bound, or meet, of and :
- is contained in both and .
- Every set contained in both and is contained in .
Arbitrary intersections have the same greatest-lower-bound property for arbitrary families of subsets of . Together with union and complementation, intersection makes a Boolean algebra. The greatest lower bound of the empty family is , explaining the ambient-set convention for empty intersections.
Size of an intersection
For finite sets, cardinality satisfies
The exact relationship with union is
The subtraction corrects for common elements counted once in and once in .
If and is finite, then
In particular, if , the sets must overlap.
For three or more sets, pairwise overlap does not guarantee a common element. For example,
have nonempty intersections in every pair, but
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 represents the event that both and occur.
In general,
when , where is conditional probability.
If and satisfy independence, then
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,
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.