bulgakov

03. Пересечение и операции над несколькими множествами

Что пригодится из прошлого: объединение множеств — определение «хотя бы в одном»; двоичные коды — запись множества нулями и единицами. Если эти главы знакомы, читайте дальше. Если нет — загляните по ссылке, потом возвращайтесь.

1. Объединение нескольких множеств

Объединение содержит элементы, которые есть хотя бы в одном из множеств. Пусть множеств nn, где n≥1n\ge1; пронумеруем их A1,…,AnA_1,\ldots,A_n. Для их объединения используют запись

⋃i=1nAi=A1∪A2∪⋯∪An.\bigcup_{i=1}^{n}A_i=A_1\cup A_2\cup\cdots\cup A_n.

Здесь ii — номер множества: он пробегает значения от 11 до nn. Большой знак ⋃\bigcup объединяет все перечисленные множества. Например, если

A1={1,2},A2={2,3},A3={2,4},A_1=\{1,2\},\qquad A_2=\{2,3\},\qquad A_3=\{2,4\},

то ⋃i=13Ai={1,2,3,4}\bigcup_{i=1}^{3}A_i=\{1,2,3,4\}.

В условии принадлежности «хотя бы одно» записывают знаком ∃\exists («существует»):

x∈⋃i=1nAi  ⟺  ∃i∈{1,…,n}: x∈Ai.x\in\bigcup_{i=1}^{n}A_i \iff \exists i\in\{1,\ldots,n\}:\ x\in A_i.

Условие с ∃\exists говорит: найдётся хотя бы один подходящий номер ii; других подходящих номеров тоже может быть несколько. Например, 33 входит в объединение благодаря A2A_2; ему не нужно находиться во всех трёх множествах. А чтобы не войти в объединение, элемент должен отсутствовать в каждом AiA_i. Число 55 в нашем примере как раз отсутствует во всех трёх.

2. Пересечение множеств

Пересечение A∩BA\cap B состоит из элементов, которые есть и в AA, и в BB:

A∩B={x∣x∈A и x∈B}.A\cap B=\{x\mid x\in A\text{ и }x\in B\}.

Если A={1,2,3,4}A=\{1,2,3,4\} и B={3,4,5}B=\{3,4,5\}, общие элементы — только 33 и 44:

A∩B={3,4},A∪B={1,2,3,4,5}.\boxed{A\cap B=\{3,4\}},\qquad A\cup B=\{1,2,3,4,5\}.

В объединении достаточно «или», а в пересечении необходимо «и».

Карта областей

Та же «карта» из прошлой главы для A={1,2,3,4}A=\{1,2,3,4\}, B={3,4,5}B=\{3,4,5\} и чисел от 11 до 66 показывает разницу между «или» и «и»:

Область Элементы в AA? в BB? A∪BA\cup B A∩BA\cap B
только в AA 1, 2 да нет ✓ —
и в AA, и в BB 3, 4 да да ✓ ✓
только в BB 5 нет да ✓ —
ни в AA, ни в BB 6 нет нет — —

Пересечение — только область «и в AA, и в BB»; объединение — три области. «Или» собирает больше элементов, «и» — меньше.

Свойства пересечения

Для любых множеств A,B,CA,B,C верно:

Свойство Почему
A∩∅=∅A\cap\varnothing=\varnothing С пустым множеством нет общих элементов.
A∩A=AA\cap A=A Каждый элемент AA есть в обоих экземплярах.
A∩B=B∩AA\cap B=B\cap A Общие элементы не зависят от порядка.
(A∩B)∩C=A∩(B∩C)(A\cap B)\cap C=A\cap(B\cap C) С обеих сторон остаются элементы, входящие во все три множества.
A∩B=B  ⟺  B⊆AA\cap B=B\iff B\subseteq A Всё BB сохранится при пересечении ровно тогда, когда оно содержится в AA.

Почему последнее утверждение работает в обе стороны? Если B⊆AB\subseteq A, каждый элемент BB принадлежит обоим множествам, поэтому A∩B=BA\cap B=B. Обратно, если A∩B=BA\cap B=B, любой элемент BB находится в пересечении, а значит, и в AA. Поэтому B⊆AB\subseteq A.

Например, при B={2,3}⊆A={1,2,3}B=\{2,3\}\subseteq A=\{1,2,3\} пересечение оставит BB, а объединение — AA:

A∩B={2,3},A∪B={1,2,3}.A\cap B=\{2,3\},\qquad A\cup B=\{1,2,3\}.

3. Пересечение нескольких множеств

Запись

⋂i=1nAi=A1∩A2∩⋯∩An\bigcap_{i=1}^{n}A_i=A_1\cap A_2\cap\cdots\cap A_n

означает, что элемент должен принадлежать каждому AiA_i:

x∈⋂i=1nAi  ⟺  ∀i∈{1,…,n}: x∈Ai.x\in\bigcap_{i=1}^{n}A_i \iff \forall i\in\{1,\ldots,n\}:\ x\in A_i.

Знак ∀\forall читается «для всех». В примере из начала только 22 есть во всех трёх множествах, поэтому ⋂i=13Ai={2}\bigcap_{i=1}^{3}A_i=\{2\}. Чтобы не попасть в пересечение, достаточно отсутствовать хотя бы в одном множестве: 33 есть в A2A_2, но его нет в A1A_1.

Проверь себя

1. Найдите A∩BA\cap B и A∪BA\cup B, если A={1,2,3,4,5,6}A=\{1,2,3,4,5,6\}, B={4,5,6,7}B=\{4,5,6,7\}.

Решение

Общие элементы: A∩B={4,5,6}A\cap B=\{4,5,6\}. Объединение — все элементы без повторов: A∪B={1,2,3,4,5,6,7}A\cup B=\{1,2,3,4,5,6,7\}.

2. Даны A1={1,2,3,4}A_1=\{1,2,3,4\}, A2={2,3,4,5}A_2=\{2,3,4,5\}, A3={3,4,5,6}A_3=\{3,4,5,6\}. Найдите ⋂i=13Ai\bigcap_{i=1}^{3}A_i и ⋃i=13Ai\bigcup_{i=1}^{3}A_i.

Решение

В пересечение входят элементы, лежащие в каждом из трёх множеств: ⋂i=13Ai={3,4}\bigcap_{i=1}^{3}A_i=\{3,4\}. В объединение — лежащие хотя бы в одном: ⋃i=13Ai={1,2,3,4,5,6}\bigcup_{i=1}^{3}A_i=\{1,2,3,4,5,6\}.

ПрактикаЗагружаем тест…