Английская Википедия:Intersection (set theory)
Шаблон:Short description Шаблон:Broader Шаблон:Infobox mathematical statement
In set theory, the intersection of two sets <math>A</math> and <math>B,</math> denoted by <math>A \cap B,</math>[1] 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>[2]
Notation and terminology
Intersection is written using the symbol "<math>\cap</math>" between the terms; that is, in 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
<math>~A \cap B \cap C</math>
The intersection of two sets <math>A</math> and <math>B,</math> denoted by <math>A \cap B</math>,[3] 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 <math>x</math> is both an element of <math>A</math> and an element of <math>B.</math>[3]
For example:
- The intersection of the sets {1, 2, 3} and {2, 3, 4} is {2, 3}.
- The number 9 is Шаблон:Em 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 Шаблон:Em 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. Equivalently, <math>A</math> intersects <math>B</math> if their intersection <math>A \cap B</math> is an Шаблон:Em, meaning that there exists some <math>x</math> such that <math>x \in A \cap B.</math>
We say that Шаблон:Em 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, 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 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. 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 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 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.
Intersection distributes over 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 <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 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
The most general notion is the intersection of an arbitrary Шаблон:Em collection of sets. If <math>M</math> is a nonempty set whose elements are themselves sets, then <math>x</math> is an element of the Шаблон:Em of <math>M</math> if and only if 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 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 <math>I</math> is the set of natural numbers, notation analogous to that of an 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
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>M</math> was the 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) <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>'s satisfy the stated condition?" The answer seems to be Шаблон:Em. When <math>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>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 <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
- Шаблон:Annotated link
- Шаблон:Annotated link
- Шаблон:Annotated link
- Шаблон:Annotated link
- Шаблон:Annotated link
- Шаблон:Annotated link
- Шаблон:Annotated link
- Шаблон:Annotated link
- Шаблон:Annotated link
- Шаблон:Annotated link
- Шаблон:Annotated link
References
Further reading
External links
Шаблон:Set theory Шаблон:Mathematical logic Шаблон:Authority control
