Intersection (set theory)

Intersection is written using the symbol "$\backslash cap$" between the terms; that is, in infix notation. For example:

$$\backslash \{1,2,3\backslash \}\backslash cap\backslash \{2,3,4\backslash \}=\backslash \{2,3\backslash \}$$

$$\backslash \{1,2,3\backslash \}\backslash cap\backslash \{4,5,6\backslash \}=\backslash varnothing$$

$$\backslash Z\backslash cap\backslash N=\backslash N$$

$$\backslash \{x\backslash in\backslash R:x^2=1\backslash \}\backslash cap\backslash N=\backslash \{1\backslash \}$$

The intersection of more than two sets (generalized intersection) can be written as:

$$\backslash 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.

File:Venn 0000 0001.svg

File:Venn diagram gr la ru.svg, Latin, and Cyrillic scripts, considering only the shapes of the letters and ignoring their pronunciation]]

File:PolygonsSetIntersection.svg

The intersection of two sets $A$ and $B,$ denoted by $A\; \backslash cap\; B$,{{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}} is the set of all objects that are members of both the sets $A$ and $B.$

In symbols:

$$A\; \backslash cap\; B\; =\; \backslash \{\; x:\; x\; \backslash in\; A\; \backslash text\{\; and\; \}\; x\; \backslash in\; B\backslash \}.$$

That is, $x$ is an element of the intersection $A\; \backslash cap\; B$ if and only if $x$ is both an element of $A$ and an element of $B.$

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 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 {{em|{{visible anchor|$A$ intersects (meets) $B$|Intersects|To intersect|Meets|To meet}}}} if there exists some $x$ that is an element of both $A$ and $B,$ in which case we also say that {{em|$A$ intersects (meets) $B$ at $x$}}. Equivalently, $A$ intersects $B$ if their intersection $A\; \backslash cap\; B$ is an {{em|inhabited set}}, meaning that there exists some $x$ such that $x\; \backslash in\; A\; \backslash cap\; B.$

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

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

{{See also|List of set identities and relations|Algebra of sets}}

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

$$A\; \backslash cap\; (B\; \backslash cap\; C)\; =\; (A\; \backslash cap\; B)\; \backslash cap\; C.$$Thus the parentheses may be omitted without ambiguity: either of the above can be written as $A\; \backslash cap\; B\; \backslash cap\; C$. Intersection is also commutative. That is, for any $A$ and $B,$ one has$$A\; \backslash cap\; B\; =\; B\; \backslash cap\; A.$$

The intersection of any set with the empty set results in the empty set; that is, that for any set $A$,

$$A\; \backslash cap\; \backslash varnothing\; =\; \backslash varnothing$$

Also, the intersection operation is idempotent; that is, any set $A$ satisfies that $A\; \backslash 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 $A,\; B,$ and $C,$ one has

$$\backslash 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}

Inside a universe $U,$ one may define the complement $A^c$ of $A$ to be the set of all elements of $U$ not in $A.$ Furthermore, the intersection of $A$ and $B$ may be written as the complement of the union of their complements, derived easily from De Morgan's laws:$$A\; \backslash cap\; B\; =\; \backslash left(A^\{c\}\; \backslash cup\; B^\{c\}\backslash right)^c$$

{{Further information|Iterated binary operation}}

The most general notion is the intersection of an arbitrary {{em|nonempty}} collection of sets.

If $M$ is a nonempty set whose elements are themselves sets, then $x$ is an element of the {{em|intersection}} of $M$ if and only if for every element $A$ of $M,$ $x$ is an element of $A.$

In symbols:

$$\backslash left(\; x\; \backslash in\; \backslash bigcap\_\{A\; \backslash in\; M\}\; A\; \backslash right)\; \backslash Leftrightarrow\; \backslash left(\; \backslash forall\; A\; \backslash in\; M,\; \backslash \; x\; \backslash in\; A\; \backslash right).$$

The notation for this last concept can vary considerably. Set theorists will sometimes write "$\backslash bigcap\; M$", while others will instead write "$\{\backslash bigcap\}\_\{A\; \backslash in\; M\}\; A$".

The latter notation can be generalized to "$\{\backslash bigcap\}\_\{i\; \backslash in\; I\}\; A\_i$", which refers to the intersection of the collection $\backslash left\backslash \{\; A\_i\; :\; i\; \backslash in\; I\; \backslash right\backslash \}.$

Here $I$ is a nonempty set, and $A\_i$ is a set for every $i\; \backslash in\; I.$

In the case that the index set $I$ is the set of natural numbers, notation analogous to that of an infinite product may be seen:

$$\backslash bigcap\_\{i=1\}^\{\backslash infty\}\; A\_i.$$

When formatting is difficult, this can also be written "$A\_1\; \backslash cap\; A\_2\; \backslash cap\; A\_3\; \backslash cap\; \backslash cdots$". This last example, an intersection of countably many sets, is actually very common; for an example, see the article on σ-algebras.

File:Variadic logical AND.svg of the arguments in parentheses

The conjunction of no argument is the tautology (compare: empty product); accordingly the intersection of no set is the universe.]]

In the previous section, we excluded the case where $M$ was the empty set ($\backslash varnothing$). The reason is as follows: The intersection of the collection $M$ is defined as the set (see set-builder notation)

$$\backslash bigcap\_\{A\; \backslash in\; M\}\; A\; =\; \backslash \{x\; :\; \backslash text\{\; for\; all\; \}\; A\; \backslash in\; M,\; x\; \backslash in\; A\backslash \}.$$

If $M$ is empty, there are no sets $A$ in $M,$ so the question becomes "which $x$'s satisfy the stated condition?" The answer seems to be {{em|every possible $x$}}. When $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),{{cite book|last=Megginson|first=Robert E.|author-link=Robert Megginson|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}}

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

• {{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}}

{{reflist}}

• {{cite book|author-link=Keith J. Devlin|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.|author-link=James Munkres|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}}

{{commons category}}

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

{{Set theory}}

{{Mathematical logic}}

{{Authority control}}

Category:Basic concepts in set theory

Category:Operations on sets

Category:Intersection