Intersection (set theory)
 The intersection of two sets [math]\displaystyle{ A }[/math] and [math]\displaystyle{ B, }[/math] represented by circles. [math]\displaystyle{ A \cap B }[/math] is in red. | |
| Type | Set operation |
|---|---|
| Field | Set theory |
| Statement | The intersection of [math]\displaystyle{ A }[/math] and [math]\displaystyle{ B }[/math] is the set [math]\displaystyle{ A \cap B }[/math] of elements that lie in both set [math]\displaystyle{ A }[/math] and set [math]\displaystyle{ B }[/math]. |
In set theory, the intersection of two sets [math]\displaystyle{ A }[/math] and [math]\displaystyle{ B, }[/math] denoted by [math]\displaystyle{ A \cap B, }[/math][1] is the set containing all elements of [math]\displaystyle{ A }[/math] that also belong to [math]\displaystyle{ B }[/math] or equivalently, all elements of [math]\displaystyle{ B }[/math] that also belong to [math]\displaystyle{ A. }[/math][2]
Notation and terminology
Intersection is written using the symbol "[math]\displaystyle{ \cap }[/math]" between the terms; that is, in infix notation. For example: [math]\displaystyle{ \{1,2,3\}\cap\{2,3,4\}=\{2,3\} }[/math] [math]\displaystyle{ \{1,2,3\}\cap\{4,5,6\}=\varnothing }[/math] [math]\displaystyle{ \Z\cap\N=\N }[/math] [math]\displaystyle{ \{x\in\R:x^2=1\}\cap\N=\{1\} }[/math] The intersection of more than two sets (generalized intersection) can be written as: [math]\displaystyle{ \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
The intersection of two sets [math]\displaystyle{ A }[/math] and [math]\displaystyle{ B, }[/math] denoted by [math]\displaystyle{ A \cap B }[/math],[3] is the set of all objects that are members of both the sets [math]\displaystyle{ A }[/math] and [math]\displaystyle{ B. }[/math] In symbols: [math]\displaystyle{ A \cap B = \{ x: x \in A \text{ and } x \in B\}. }[/math]
That is, [math]\displaystyle{ x }[/math] is an element of the intersection [math]\displaystyle{ A \cap B }[/math] if and only if [math]\displaystyle{ x }[/math] is both an element of [math]\displaystyle{ A }[/math] and an element of [math]\displaystyle{ B. }[/math][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.
Intersecting and disjoint sets
We say that [math]\displaystyle{ A }[/math] intersects (meets) [math]\displaystyle{ B }[/math] if there exists some [math]\displaystyle{ x }[/math] that is an element of both [math]\displaystyle{ A }[/math] and [math]\displaystyle{ B, }[/math] in which case we also say that [math]\displaystyle{ A }[/math] intersects (meets) [math]\displaystyle{ B }[/math] at [math]\displaystyle{ x }[/math]. Equivalently, [math]\displaystyle{ A }[/math] intersects [math]\displaystyle{ B }[/math] if their intersection [math]\displaystyle{ A \cap B }[/math] is an inhabited set, meaning that there exists some [math]\displaystyle{ x }[/math] such that [math]\displaystyle{ x \in A \cap B. }[/math]
We say that [math]\displaystyle{ A }[/math] and [math]\displaystyle{ B }[/math] are disjoint if [math]\displaystyle{ A }[/math] does not intersect [math]\displaystyle{ B. }[/math] In plain language, they have no elements in common. [math]\displaystyle{ A }[/math] and [math]\displaystyle{ B }[/math] are disjoint if their intersection is empty, denoted [math]\displaystyle{ A \cap B = \varnothing. }[/math]
For example, the sets [math]\displaystyle{ \{1, 2\} }[/math] and [math]\displaystyle{ \{3, 4\} }[/math] are disjoint, while the set of even numbers intersects the set of multiples of 3 at the multiples of 6.
Algebraic properties
Binary intersection is an associative operation; that is, for any sets [math]\displaystyle{ A, B, }[/math] and [math]\displaystyle{ C, }[/math] one has
[math]\displaystyle{ 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]\displaystyle{ A \cap B \cap C }[/math]. Intersection is also commutative. That is, for any [math]\displaystyle{ A }[/math] and [math]\displaystyle{ B, }[/math] one has[math]\displaystyle{ A \cap B = B \cap A. }[/math] The intersection of any set with the empty set results in the empty set; that is, that for any set [math]\displaystyle{ A }[/math], [math]\displaystyle{ A \cap \varnothing = \varnothing }[/math] Also, the intersection operation is idempotent; that is, any set [math]\displaystyle{ A }[/math] satisfies that [math]\displaystyle{ A \cap A = A }[/math]. All these properties follow from analogous facts about logical conjunction.
Intersection distributes over union and union distributes over intersection. That is, for any sets [math]\displaystyle{ A, B, }[/math] and [math]\displaystyle{ C, }[/math] one has [math]\displaystyle{ \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]\displaystyle{ U, }[/math] one may define the complement [math]\displaystyle{ A^c }[/math] of [math]\displaystyle{ A }[/math] to be the set of all elements of [math]\displaystyle{ U }[/math] not in [math]\displaystyle{ A. }[/math] Furthermore, the intersection of [math]\displaystyle{ A }[/math] and [math]\displaystyle{ B }[/math] may be written as the complement of the union of their complements, derived easily from De Morgan's laws:[math]\displaystyle{ A \cap B = \left(A^{c} \cup B^{c}\right)^c }[/math]
Arbitrary intersections
The most general notion is the intersection of an arbitrary nonempty collection of sets. If [math]\displaystyle{ M }[/math] is a nonempty set whose elements are themselves sets, then [math]\displaystyle{ x }[/math] is an element of the intersection of [math]\displaystyle{ M }[/math] if and only if for every element [math]\displaystyle{ A }[/math] of [math]\displaystyle{ M, }[/math] [math]\displaystyle{ x }[/math] is an element of [math]\displaystyle{ A. }[/math] In symbols: [math]\displaystyle{ \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 theorists will sometimes write "[math]\displaystyle{ \bigcap M }[/math]", while others will instead write "[math]\displaystyle{ {\bigcap}_{A \in M} A }[/math]". The latter notation can be generalized to "[math]\displaystyle{ {\bigcap}_{i \in I} A_i }[/math]", which refers to the intersection of the collection [math]\displaystyle{ \left\{ A_i : i \in I \right\}. }[/math] Here [math]\displaystyle{ I }[/math] is a nonempty set, and [math]\displaystyle{ A_i }[/math] is a set for every [math]\displaystyle{ i \in I. }[/math]
In the case that the index set [math]\displaystyle{ I }[/math] is the set of natural numbers, notation analogous to that of an infinite product may be seen: [math]\displaystyle{ \bigcap_{i=1}^{\infty} A_i. }[/math]
When formatting is difficult, this can also be written "[math]\displaystyle{ 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
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 [math]\displaystyle{ M }[/math] was the empty set ([math]\displaystyle{ \varnothing }[/math]). The reason is as follows: The intersection of the collection [math]\displaystyle{ M }[/math] is defined as the set (see set-builder notation) [math]\displaystyle{ \bigcap_{A \in M} A = \{x : \text{ for all } A \in M, x \in A\}. }[/math] If [math]\displaystyle{ M }[/math] is empty, there are no sets [math]\displaystyle{ A }[/math] in [math]\displaystyle{ M, }[/math] so the question becomes "which [math]\displaystyle{ x }[/math]'s satisfy the stated condition?" The answer seems to be every possible [math]\displaystyle{ x }[/math]. When [math]\displaystyle{ M }[/math] 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 [math]\displaystyle{ X }[/math], the notion of the intersection of an empty collection of subsets of [math]\displaystyle{ X }[/math] is well-defined. In that case, if [math]\displaystyle{ M }[/math] is empty, its intersection is [math]\displaystyle{ \bigcap M=\bigcap\varnothing=\{x\in X: x\in A \text{ for all }A\in\varnothing\} }[/math]. Since all [math]\displaystyle{ x\in X }[/math] vacuously satisfy the required condition, the intersection of the empty collection of subsets of [math]\displaystyle{ X }[/math] is all of [math]\displaystyle{ X. }[/math] In formulas, [math]\displaystyle{ \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 [math]\displaystyle{ x }[/math] is of a prescribed type [math]\displaystyle{ \tau, }[/math] so the intersection is understood to be of type [math]\displaystyle{ \mathrm{set}\ \tau }[/math] (the type of sets whose elements are in [math]\displaystyle{ \tau }[/math]), and we can define [math]\displaystyle{ \bigcap_{A \in \empty} A }[/math] to be the universal set of [math]\displaystyle{ \mathrm{set}\ \tau }[/math] (the set whose elements are exactly all terms of type [math]\displaystyle{ \tau }[/math]).
See also
- 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 shapes
- 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
References
- ↑ "Intersection of Sets". http://web.mnstate.edu/peil/MDEV102/U1/S3/Intersection4.htm.
- ↑ "Stats: Probability Rules". People.richland.edu. http://people.richland.edu/james/lecture/m170/ch05-rul.html.
- ↑ 3.0 3.1 "Set Operations | Union | Intersection | Complement | Difference | Mutually Exclusive | Partitions | De Morgan's Law | Distributive Law | Cartesian Product". https://www.probabilitycourse.com/chapter1/1_2_2_set_operations.php.
- ↑ Megginson, Robert E. (1998). "Chapter 1". An introduction to Banach space theory. Graduate Texts in Mathematics. 183. New York: Springer-Verlag. pp. xx+596. ISBN 0-387-98431-3.
Further reading
- 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.
External links
 |  |
