Intersection (set theory)

In set theory, the intersection of two sets ${\displaystyle A}${\displaystyle A} and ${\displaystyle B,}${\displaystyle B,} denoted by ${\displaystyle A\cap B,}${\displaystyle A\cap B,}^[1] is the set containing all elements of ${\displaystyle A}${\displaystyle A} that also belong to ${\displaystyle B}${\displaystyle B} or equivalently, all elements of ${\displaystyle B}${\displaystyle B} that also belong to ${\displaystyle A.}${\displaystyle A.}^[2]

Intersection is written using the symbol "${\displaystyle \cap }${\displaystyle \cap }" between the terms; that is, in infix notation. For example: $${\displaystyle \{1,2,3\}\cap \{2,3,4\}=\{2,3\}}$${\displaystyle \{1,2,3\}\cap \{2,3,4\}=\{2,3\}} $${\displaystyle \{1,2,3\}\cap \{4,5,6\}=\varnothing }$${\displaystyle \{1,2,3\}\cap \{4,5,6\}=\varnothing } $${\displaystyle \mathbb {Z} \cap \mathbb {N} =\mathbb {N} }$${\displaystyle \mathbb {Z} \cap \mathbb {N} =\mathbb {N} } $${\displaystyle \{x\in \mathbb {R} :x^{2}=1\}\cap \mathbb {N} =\{1\}}$${\displaystyle \{x\in \mathbb {R} :x^{2}=1\}\cap \mathbb {N} =\{1\}} The intersection of more than two sets (generalized intersection) can be written as: $${\displaystyle \bigcap _{i=1}^{n}A_{i}}$${\displaystyle \bigcap _{i=1}^{n}A_{i}} which is similar to capital-sigma notation.

For an explanation of the symbols used in this article, refer to the table of mathematical symbols.

The intersection of two sets ${\displaystyle A}${\displaystyle A} and ${\displaystyle B,}${\displaystyle B,} denoted by ${\displaystyle A\cap B}${\displaystyle A\cap B},^[3] is the set of all objects that are members of both the sets ${\displaystyle A}${\displaystyle A} and ${\displaystyle B.}${\displaystyle B.} In symbols: $${\displaystyle A\cap B=\{x:x\in A{\text{ and }}x\in B\}.}$${\displaystyle A\cap B=\{x:x\in A{\text{ and }}x\in B\}.}

That is, ${\displaystyle x}${\displaystyle x} is an element of the intersection ${\displaystyle A\cap B}${\displaystyle A\cap B} if and only if ${\displaystyle x}${\displaystyle x} is both an element of ${\displaystyle A}${\displaystyle A} and an element of ${\displaystyle B.}${\displaystyle B.}^[3]

For example:

• The intersection of the sets {1, 2, 3} and {2, 3, 4} is {2, 3}.
• The number 9 is not in the intersection of the set of prime numbers {2, 3, 5, 7, 11, ...} and the set of odd numbers {1, 3, 5, 7, 9, 11, ...}, because 9 is not prime.

We say that ${\displaystyle A}${\displaystyle A} intersects (meets) ${\displaystyle B}${\displaystyle B} if there exists some ${\displaystyle x}${\displaystyle x} that is an element of both ${\displaystyle A}${\displaystyle A} and ${\displaystyle B,}${\displaystyle B,} in which case we also say that ${\displaystyle A}${\displaystyle A} intersects (meets) ${\displaystyle B}${\displaystyle B} at ${\displaystyle x}${\displaystyle x}. Equivalently, ${\displaystyle A}${\displaystyle A} intersects ${\displaystyle B}${\displaystyle B} if their intersection ${\displaystyle A\cap B}${\displaystyle A\cap B} is an inhabited set , meaning that there exists some ${\displaystyle x}${\displaystyle x} such that ${\displaystyle x\in A\cap B.}${\displaystyle x\in A\cap B.}

We say that ${\displaystyle A}${\displaystyle A} and ${\displaystyle B}${\displaystyle B} are disjoint if ${\displaystyle A}${\displaystyle A} does not intersect ${\displaystyle B.}${\displaystyle B.} In plain language, they have no elements in common. ${\displaystyle A}${\displaystyle A} and ${\displaystyle B}${\displaystyle B} are disjoint if their intersection is empty, denoted ${\displaystyle A\cap B=\varnothing .}${\displaystyle A\cap B=\varnothing .}

For example, the sets ${\displaystyle \{1,2\}}${\displaystyle \{1,2\}} and ${\displaystyle \{3,4\}}${\displaystyle \{3,4\}} are disjoint, while the set of even numbers intersects the set of multiples of 3 at the multiples of 6.

Binary intersection is an associative operation; that is, for any sets ${\displaystyle A,B,}${\displaystyle A,B,} and ${\displaystyle C,}${\displaystyle C,} one has

$${\displaystyle A\cap (B\cap C)=(A\cap B)\cap C.}$${\displaystyle A\cap (B\cap C)=(A\cap B)\cap C.}Thus the parentheses may be omitted without ambiguity: either of the above can be written as ${\displaystyle A\cap B\cap C}${\displaystyle A\cap B\cap C}. Intersection is also commutative. That is, for any ${\displaystyle A}${\displaystyle A} and ${\displaystyle B,}${\displaystyle B,} one has$${\displaystyle A\cap B=B\cap A.}$${\displaystyle A\cap B=B\cap A.} The intersection of any set with the empty set results in the empty set; that is, that for any set ${\displaystyle A}${\displaystyle A}, $${\displaystyle A\cap \varnothing =\varnothing }$${\displaystyle A\cap \varnothing =\varnothing } Also, the intersection operation is idempotent; that is, any set ${\displaystyle A}${\displaystyle A} satisfies that ${\displaystyle A\cap A=A}${\displaystyle A\cap A=A}. All these properties follow from analogous facts about logical conjunction.

Intersection distributes over union and union distributes over intersection. That is, for any sets ${\displaystyle A,B,}${\displaystyle A,B,} and ${\displaystyle C,}${\displaystyle C,} one has $${\displaystyle {\begin{aligned}A\cap (B\cup C)=(A\cap B)\cup (A\cap C)\\A\cup (B\cap C)=(A\cup B)\cap (A\cup C)\end{aligned}}}$${\displaystyle {\begin{aligned}A\cap (B\cup C)=(A\cap B)\cup (A\cap C)\\A\cup (B\cap C)=(A\cup B)\cap (A\cup C)\end{aligned}}} Inside a universe ${\displaystyle U,}${\displaystyle U,} one may define the complement ${\displaystyle A^{c}}${\displaystyle A^{c}} of ${\displaystyle A}${\displaystyle A} to be the set of all elements of ${\displaystyle U}${\displaystyle U} not in ${\displaystyle A.}${\displaystyle A.} Furthermore, the intersection of ${\displaystyle A}${\displaystyle A} and ${\displaystyle B}${\displaystyle B} may be written as the complement of the union of their complements, derived easily from De Morgan's laws:$${\displaystyle A\cap B=\left(A^{c}\cup B^{c}\right)^{c}}$${\displaystyle A\cap B=\left(A^{c}\cup B^{c}\right)^{c}}

The most general notion is the intersection of an arbitrary nonempty collection of sets. If ${\displaystyle M}${\displaystyle M} is a nonempty set whose elements are themselves sets, then ${\displaystyle x}${\displaystyle x} is an element of the intersection of ${\displaystyle M}${\displaystyle M} if and only if for every element ${\displaystyle A}${\displaystyle A} of ${\displaystyle M,}${\displaystyle M,} ${\displaystyle x}${\displaystyle x} is an element of ${\displaystyle A.}${\displaystyle A.} In symbols: $${\displaystyle \left(x\in \bigcap _{A\in M}A\right)\Leftrightarrow \left(\forall A\in M,\ x\in A\right).}$${\displaystyle \left(x\in \bigcap _{A\in M}A\right)\Leftrightarrow \left(\forall A\in M,\ x\in A\right).}

The notation for this last concept can vary considerably. Set theorists will sometimes write "${\displaystyle \bigcap M}${\displaystyle \bigcap M}", while others will instead write "${\displaystyle {\bigcap }_{A\in M}A}${\displaystyle {\bigcap }_{A\in M}A}". The latter notation can be generalized to "${\displaystyle {\bigcap }_{i\in I}A_{i}}${\displaystyle {\bigcap }_{i\in I}A_{i}}", which refers to the intersection of the collection ${\displaystyle \left\{A_{i}:i\in I\right\}.}${\displaystyle \left\{A_{i}:i\in I\right\}.} Here ${\displaystyle I}${\displaystyle I} is a nonempty set, and ${\displaystyle A_{i}}${\displaystyle A_{i}} is a set for every ${\displaystyle i\in I.}${\displaystyle i\in I.}

In the case that the index set ${\displaystyle I}${\displaystyle I} is the set of natural numbers, notation analogous to that of an infinite product may be seen: $${\displaystyle \bigcap _{i=1}^{\infty }A_{i}.}$${\displaystyle \bigcap _{i=1}^{\infty }A_{i}.}

When formatting is difficult, this can also be written "${\displaystyle A_{1}\cap A_{2}\cap A_{3}\cap \cdots }${\displaystyle A_{1}\cap A_{2}\cap A_{3}\cap \cdots }". This last example, an intersection of countably many sets, is actually very common; for an example, see the article on σ-algebras.

In the previous section, we excluded the case where ${\displaystyle M}${\displaystyle M} was the empty set (${\displaystyle \varnothing }${\displaystyle \varnothing }). The reason is as follows: The intersection of the collection ${\displaystyle M}${\displaystyle M} is defined as the set (see set-builder notation) $${\displaystyle \bigcap _{A\in M}A=\{x:{\text{ for all }}A\in M,x\in A\}.}$${\displaystyle \bigcap _{A\in M}A=\{x:{\text{ for all }}A\in M,x\in A\}.} If ${\displaystyle M}${\displaystyle M} is empty, there are no sets ${\displaystyle A}${\displaystyle A} in ${\displaystyle M,}${\displaystyle M,} so the question becomes "which ${\displaystyle x}${\displaystyle x}'s satisfy the stated condition?" The answer seems to be every possible ${\displaystyle x}${\displaystyle x}. When ${\displaystyle M}${\displaystyle M} is empty, the condition given above is an example of a vacuous truth. So the intersection of the empty family should be the universal set (the identity element for the operation of intersection),^[4] but in standard (ZF) set theory, the universal set does not exist.

However, when restricted to the context of subsets of a given fixed set ${\displaystyle X}${\displaystyle X}, the notion of the intersection of an empty collection of subsets of ${\displaystyle X}${\displaystyle X} is well-defined. In that case, if ${\displaystyle M}${\displaystyle M} is empty, its intersection is ${\displaystyle \bigcap M=\bigcap \varnothing =\{x\in X:x\in A{\text{ for all }}A\in \varnothing \}}${\displaystyle \bigcap M=\bigcap \varnothing =\{x\in X:x\in A{\text{ for all }}A\in \varnothing \}}. Since all ${\displaystyle x\in X}${\displaystyle x\in X} vacuously satisfy the required condition, the intersection of the empty collection of subsets of ${\displaystyle X}${\displaystyle X} is all of ${\displaystyle X.}${\displaystyle X.} In formulas, ${\displaystyle \bigcap \varnothing =X.}${\displaystyle \bigcap \varnothing =X.} This matches the intuition that as collections of subsets become smaller, their respective intersections become larger; in the extreme case, the empty collection has an intersection equal to the whole underlying set.

Also, in type theory ${\displaystyle x}${\displaystyle x} is of a prescribed type ${\displaystyle \tau ,}${\displaystyle \tau ,} so the intersection is understood to be of type ${\displaystyle \mathrm {set} \ \tau }${\displaystyle \mathrm {set} \ \tau } (the type of sets whose elements are in ${\displaystyle \tau }${\displaystyle \tau }), and we can define ${\displaystyle \bigcap _{A\in \emptyset }A}${\displaystyle \bigcap _{A\in \emptyset }A} to be the universal set of ${\displaystyle \mathrm {set} \ \tau }${\displaystyle \mathrm {set} \ \tau } (the set whose elements are exactly all terms of type ${\displaystyle \tau }${\displaystyle \tau }).

• Algebra of sets – Identities and relationships involving sets
• Cardinality – Definition of the number of elements in a set
• Complement – Set of the elements not in a given subset
• Intersection (Euclidean geometry) – Shape formed from points common to other shapesPages displaying short descriptions of redirect targets
• Intersection graph – Graph representing intersections between given sets
• Intersection theory – Branch of algebraic geometry
• List of set identities and relations – Equalities for combinations of sets
• Logical conjunction – Logical connective AND
• MinHash – Data mining technique
• Naive set theory – Informal set theories
• Symmetric difference – Elements in exactly one of two sets
• Union – Set of elements in any of some sets

• Devlin, K. J. (1993). The Joy of Sets: Fundamentals of Contemporary Set Theory (Second ed.). New York, NY: Springer-Verlag. ISBN 3-540-94094-4.
• Munkres, James R. (2000). "Set Theory and Logic". Topology (Second ed.). Upper Saddle River: Prentice Hall. ISBN 0-13-181629-2.
• Rosen, Kenneth (2007). "Basic Structures: Sets, Functions, Sequences, and Sums". Discrete Mathematics and Its Applications (Sixth ed.). Boston: McGraw-Hill. ISBN 978-0-07-322972-0.

• Weisstein, Eric W. "Intersection". MathWorld .

• Basic concepts in set theory
• Operations on sets
• Intersection

• Articles with short description
• Short description is different from Wikidata
• Pages displaying short descriptions of redirect targets via Module:Annotated link
• Commons category link from Wikidata