View source for Intersection (set theory)

{{Short description|Set of elements common to all of some sets}}
{{Infobox mathematical statement
| name = Intersection
| image = Venn0001.svg
| caption = The intersection of two sets <math>A</math> and <math>B,</math> represented by circles. <math>A \cap B</math> is in red.
| type = [[Set (mathematics)#Basic operations|Set operation]]
| field = [[Set (mathematics)|Set theory]]
| statement = The intersection of <math>A</math> and <math>B</math> is the set <math>A \cap B</math> of elements that lie in both set <math>A</math> and set <math>B</math>.
| symbolic statement = <math>A \cap B = \{ x: x \in A \text{ and } x \in B\}</math>
}}

In [[Set theory|set theory]], the '''intersection''' of two [[Set (mathematics)|sets]] <math>A</math> and <math>B,</math> denoted by <math>A \cap B,</math><ref>{{Cite web|title=Intersection of Sets|url=http://web.mnstate.edu/peil/MDEV102/U1/S3/Intersection4.htm|access-date=2020-09-04|website=web.mnstate.edu|archive-date=2020-08-04|archive-url=https://web.archive.org/web/20200804163657/http://web.mnstate.edu/peil/MDEV102/U1/S3/Intersection4.htm|url-status=dead}}</ref> is the set containing all elements of <math>A</math> that also belong to <math>B</math> or equivalently, all elements of <math>B</math> that also belong to <math>A.</math><ref>{{cite web|url=http://people.richland.edu/james/lecture/m170/ch05-rul.html|title=Stats: Probability Rules|publisher=People.richland.edu|access-date=2012-05-08}}</ref>

== Notation and terminology ==

Intersection is written using the symbol "<math>\cap</math>" between the terms; that is, in [[Infix notation|infix notation]]. For example:
<math display=block>\{1,2,3\}\cap\{2,3,4\}=\{2,3\}</math>
<math display=block>\{1,2,3\}\cap\{4,5,6\}=\varnothing</math>
<math display=block>\Z\cap\N=\N</math>
<math display=block>\{x\in\R:x^2=1\}\cap\N=\{1\}</math>
The intersection of more than two sets (generalized intersection) can be written as:
<math display=block>\bigcap_{i=1}^n A_i</math>
which is similar to capital-sigma notation.

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

==Definition==

[[File:Venn 0000 0001.svg|thumb|Intersection of three sets:<br /><math>~A \cap B \cap C</math>]]
[[File:Venn diagram gr la ru.svg|thumb|Intersections of the unaccented modern Greek, Latin, and Cyrillic scripts, considering only the shapes of the letters and ignoring their pronunciation]]
[[File:PolygonsSetIntersection.svg|thumb|Example of an intersection with sets]]
The intersection of two sets <math>A</math> and <math>B,</math> denoted by <math>A \cap B</math>,<ref name=":1">{{Cite web|title=Set Operations {{!}} Union {{!}} Intersection {{!}} Complement {{!}} Difference {{!}} Mutually Exclusive {{!}} Partitions {{!}} De Morgan's Law {{!}} Distributive Law {{!}} Cartesian Product|url=https://www.probabilitycourse.com/chapter1/1_2_2_set_operations.php|access-date=2020-09-04|website=www.probabilitycourse.com}}</ref> is the set of all objects that are members of both the sets <math>A</math> and <math>B.</math>
In symbols:
<math display=block>A \cap B = \{ x: x \in A \text{ and } x \in B\}.</math>

That is, <math>x</math> is an element of the intersection <math>A \cap B</math> [[If and only if|if and only if]] <math>x</math> is both an element of <math>A</math> and an element of <math>B.</math><ref name=":1" />

For example:
* The intersection of the sets {1, 2, 3} and {2, 3, 4} is {2, 3}.
* The number 9 is {{em|not}} in the intersection of the set of [[Prime number|prime number]]s {2, 3, 5, 7, 11, ...} and the set of odd numbers {1, 3, 5, 7, 9, 11, ...}, because 9 is not prime.

===Intersecting and disjoint sets===

We say that {{em|{{visible anchor|<math>A</math> intersects (meets) <math>B</math>|Intersects|To intersect|Meets|To meet}}}} if there exists some <math>x</math> that is an element of both <math>A</math> and <math>B,</math> in which case we also say that {{em|<math>A</math> intersects (meets) <math>B</math> '''at''' <math>x</math>}}. Equivalently, <math>A</math> intersects <math>B</math> if their intersection <math>A \cap B</math> is an {{em|[[Inhabited set|inhabited set]]}}, meaning that there exists some <math>x</math> such that <math>x \in A \cap B.</math>

We say that {{em|<math>A</math> and <math>B</math> are [[Disjoint sets|disjoint]]}} if <math>A</math> does not intersect <math>B.</math> In plain language, they have no elements in common. <math>A</math> and <math>B</math> are disjoint if their intersection is [[Empty set|empty]], denoted <math>A \cap B = \varnothing.</math>

For example, the sets <math>\{1, 2\}</math> and <math>\{3, 4\}</math> are disjoint, while the set of even numbers intersects the set of [[Multiple (mathematics)|multiples]] of 3 at the multiples of 6.

== Algebraic properties ==

Binary intersection is an associative operation; that is, for any sets <math>A, B,</math> and <math>C,</math> one has

<math display=block>A \cap (B \cap C) = (A \cap B) \cap C.</math>Thus the parentheses may be omitted without ambiguity: either of the above can be written as <math>A \cap B \cap C</math>. Intersection is also [[Commutative property|commutative]]. That is, for any <math>A</math> and <math>B,</math> one has<math display=block>A \cap B = B \cap A.</math>
The intersection of any set with the [[Empty set|empty set]] results in the empty set; that is, that for any set <math>A</math>,
<math display=block>A \cap \varnothing = \varnothing</math>
Also, the intersection operation is [[Idempotence|idempotent]]; that is, any set <math>A</math> satisfies that <math>A \cap A = A</math>. All these properties follow from analogous facts about [[Logical conjunction|logical conjunction]].

Intersection [[Distributive property|distributes]] over [[Union (set theory)|union]] and union distributes over intersection. That is, for any sets <math>A, B,</math> and <math>C,</math> one has
<math display=block>\begin{align}
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{align}</math>
Inside a universe <math>U,</math> one may define the [[Complement (set theory)|complement]] <math>A^c</math> of <math>A</math> to be the set of all elements of <math>U</math> not in <math>A.</math> Furthermore, the intersection of <math>A</math> and <math>B</math> may be written as the complement of the [[Union (set theory)|union]] of their complements, derived easily from [[De Morgan's laws]]:<math display="block">A \cap B = \left(A^{c} \cup B^{c}\right)^c</math>

==Arbitrary intersections==
{{Further information|Iterated binary operation}}

The most general notion is the intersection of an arbitrary {{em|nonempty}} collection of sets.
If <math>M</math> is a [[Empty set|nonempty]] set whose elements are themselves sets, then <math>x</math> is an element of the {{em|intersection}} of <math>M</math> if and only if [[Universal quantification|for every]] element <math>A</math> of <math>M,</math> <math>x</math> is an element of <math>A.</math>
In symbols:
<math display=block>\left( x \in \bigcap_{A \in M} A \right) \Leftrightarrow \left( \forall A \in M, \ x \in A \right).</math>

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

In the case that the [[Index set|index set]] <math>I</math> is the set of [[Natural number|natural number]]s, notation analogous to that of an [[Infinite product|infinite product]] may be seen:
<math display=block>\bigcap_{i=1}^{\infty} A_i.</math>

When formatting is difficult, this can also be written "<math>A_1 \cap A_2 \cap A_3 \cap \cdots</math>".  This last example, an intersection of countably many sets, is actually very common; for an example, see the article on σ-algebras.

==Nullary intersection==
[[File:Variadic logical AND.svg|thumb|[[Logical conjunction|Conjunctions]] of the arguments in parentheses<br /><br />The conjunction of no argument is the tautology (compare: [[Empty product|empty product]]); accordingly the intersection of no set is the universe.]]

In the previous section, we excluded the case where <math>M</math> was the [[Empty set|empty set]] (<math>\varnothing</math>). The reason is as follows: The intersection of the collection <math>M</math> is defined as the set (see [[Set-builder notation|set-builder notation]])
<math display=block>\bigcap_{A \in M} A = \{x : \text{ for all } A \in M, x \in A\}.</math>
If <math>M</math> is empty, there are no sets <math>A</math> in <math>M,</math> so the question becomes "which <math>x</math><nowiki>'</nowiki>s satisfy the stated condition?" The answer seems to be {{em|every possible <math>x</math>}}. When <math>M</math> is empty, the condition given above is an example of a [[Vacuous truth|vacuous truth]]. So the intersection of the empty family should be the [[Universal set|universal set]] (the [[Identity element|identity element]] for the operation of intersection),<ref>{{cite book|last=Megginson|first=Robert E.|title=An introduction to Banach space theory|series=[[Graduate Texts in Mathematics]]|volume=183|publisher=Springer-Verlag|location=New York|year=1998|pages=xx+596|isbn=0-387-98431-3|chapter=Chapter 1}}</ref>
but in standard ([[Zermelo–Fraenkel set theory|ZF]]) set theory, the universal set does not exist.

However, when restricted to the context of subsets of a given fixed set <math>X</math>, the notion of the intersection of an empty collection of subsets of <math>X</math> is well-defined.  In that case, if <math>M</math> is empty, its intersection is <math>\bigcap M=\bigcap\varnothing=\{x\in X: x\in A \text{ for all }A\in\varnothing\}</math>.  Since all <math>x\in X</math> vacuously satisfy the required condition, the intersection of the empty collection of subsets of <math>X</math> is all of <math>X.</math>  In formulas, <math>\bigcap\varnothing=X.</math>  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|type theory]] <math>x</math> is of a prescribed type <math>\tau,</math> so the intersection is understood to be of type <math>\mathrm{set}\ \tau</math> (the type of sets whose elements are in <math>\tau</math>), and we can define <math>\bigcap_{A \in \empty} A</math> to be the universal set of <math>\mathrm{set}\ \tau</math> (the set whose elements are exactly all terms of type <math>\tau</math>).

== See also ==

* {{annotated link|Algebra of sets}}
* {{annotated link|Cardinality}}
* {{annotated link|Complement (set theory)|Complement}}
* {{annotated link|Intersection (Euclidean geometry)}}
* {{annotated link|Intersection graph}}
* {{annotated link|Intersection theory}}
* {{annotated link|List of set identities and relations}}
* {{annotated link|Logical conjunction}}
* {{annotated link|MinHash}}
* {{annotated link|Naive set theory}}
* {{annotated link|Symmetric difference}}
* {{annotated link|Union (set theory)|Union}}

==References==

{{reflist}}

==Further reading==

* {{cite book|last=Devlin|first=K. J.|title=The Joy of Sets: Fundamentals of Contemporary Set Theory|edition=Second|publisher=Springer-Verlag|location=New York, NY|year=1993|isbn=3-540-94094-4}}
* {{cite book|last=Munkres|first=James R.|title=Topology|edition=Second|location=Upper Saddle River|publisher=Prentice Hall|chapter=Set Theory and Logic|year=2000|isbn=0-13-181629-2}}
* {{cite book|title=Discrete Mathematics and Its Applications|first=Kenneth|last=Rosen|location=Boston|publisher=McGraw-Hill|year=2007|edition=Sixth|isbn=978-0-07-322972-0|chapter=Basic Structures: Sets, Functions, Sequences, and Sums}}

==External links==

* {{MathWorld|title=Intersection|id=Intersection}}

{{Mathematical logic}}

[[Category:Basic concepts in set theory]]

{{Sourceattribution|Intersection (set theory)}}