Лекція 1. Алгебра множин #

Огляд #

Теорія множин — це базова мова всієї дискретної математики. Майже кожен об’єкт, який ми вивчатимемо далі в курсі, — відношення, функції, булеві алгебри, графи, ймовірнісні простори — побудований на множинах. Коли ми кажемо «граф — це пара $(V, E)$, де $E$ — множина ребер», «відношення з $A$ у $B$ — це підмножина $A \times B$» або «подія — це підмножина простору наслідків», ми говоримо мовою множин. Навчитися вільно читати й писати цією мовою зараз — означає полегшити собі кожну наступну лекцію.

У цьому розділі ми вводимо первісне поняття множини та відношення належності, перелічуємо способи задання множин (перелік, характеристична властивість, рекурсія), учимося порівнювати множини (підмножина, рівність), вимірювати їх (потужність, множина-ступінь) і, нарешті, будуємо алгебру множин — операції об’єднання, перетину, різниці, доповнення та закони, яким вони підпорядковані. Дорогою ми доводимо структурні факти ($\varnothing \subseteq A$, критерій рівності через подвійне включення, $|\mathcal{P}(A)| = 2^{n}$) строго, а не просто проголошуємо їх, бо велика частина цінності курсу — навчитися доводити твердження про дискретні структури. Операції над множинами, які ми тут будуємо, знадобляться одразу — вже в цьому розділі, коли ми навчимося лічити об’єднання (§1.10), — а відношення, побудовані на множинах упорядкованих пар, чекають уже в Лекції 2.

Про строгість. Кілька результатів нижче оформлені як теореми чи твердження та супроводжуються доведенням, обмеженим позначками Доведення. … $\blacksquare$. Читайте доведення активно: на кожному кроці запитуйте «чому цей крок дозволений?». Прийоми доведення, показані тут (пряме доведення, доведення від супротивного, за випадками, через бієкцію), ви застосовуватимете протягом усього курсу.

1.1 Множини та належність #

Мотивація #

Сукупності — усюди. Студенти, записані на курс; файли в теці; шрифти в поліграфічній системі; кольори у палітрі; рядки таблиці бази даних — кожне з цього є сукупністю об’єктів, яку розглядають як єдине ціле. Математиці потрібне одне чисте, однакове поняття, що вловлює «сукупність як ціле», ігноруючи випадкові деталі — як-от порядок перелічування чи повторення. Це поняття — множина.

Первісні поняття #

Два поняття вважаємо первісними (неозначуваними, зрозумілими інтуїтивно): множина та належність.

Означення (множина). Множина — це невпорядкована сукупність різних об’єктів, розглянута як ціле. Об’єкти називають елементами множини. Множина повністю визначається тим, які об’єкти вона містить, — не порядком і не повтореннями.

Означення (належність). Запис $x \in A$ означає «$x$ є елементом $A$» (читають «$x$ належить $A$»), а $x \notin A$ — «$x$ не є елементом $A$». Для будь-якого об’єкта $x$ і множини $A$ виконано рівно одне з двох: $x \in A$ або $x \notin A$.

Множини зазвичай позначають великими літерами ($A, B, C, \dots$), а їхні елементи — малими, хоча це лише домовленість: елемент множини сам може бути множиною.

Два структурні принципи випливають одразу з «множина визначається своїми елементами»:

• Порядок несуттєвий: $\{1,2,3\} = \{3,1,2\}$.
• Повторення несуттєве: $\{1,2,2,3\} = \{1,2,3\}$.

Приклад 1.1. Нехай $A = \{a, e, i, o, u\}$ — множина голосних латинської абетки. Тоді $e \in A$, але $b \notin A$. Множина $A$ має рівно п’ять елементів, і $\{u, a, o, i, e\}$ позначає ту саму множину.

Приклад 1.2 (множини множин). Елементи самі можуть бути множинами. У $B = \{\, 1,\ \{1\},\ \{1,2\} \,\}$ маємо $1 \in B$ і $\{1\} \in B$, і це три різні елементи, тож $|B| = 3$. Але $2 \notin B$: хоча $2$ з’являється усередині елемента $\{1,2\}$, він не є елементом самого $B$. Належність «не бачить крізь дужки».

Типова помилка (елемент проти множини). Початківці плутають об’єкт $x$ із одноелементною множиною $\{x\}$, а належність $\in$ — із включенням $\subseteq$ (§1.4). Розрізняйте: $x \in A$ пов’язує об’єкт із множиною; $\{x\} \subseteq A$ пов’язує множину з множиною.

1.2 Способи задання множин #

Є три стандартні способи вказати, які елементи містить множина.

Перелік (списком) #

Явно перелічують елементи у фігурних дужках: $A = \{2, 4, 6, 8\}$. За очевидної закономірності дозволено три крапки: $\mathbb{N} = \{1, 2, 3, \dots\}$ або $\{2, 4, 6, \dots, 100\}$. Перелік практичний лише для малих множин.

Характеристична властивість (предикатом) #

Елементи описують властивістю (предикатом) $P(x)$, якій вони мають задовольняти:

$$A = \{\, x \mid P(x) \,\} \qquad (\text{читають «усі } x \text{ такі, що } P(x)\text{»}).$$

Майже завжди вказують область $U$, з якої беруть $x$, щоб означення було безпечним і визначеним:

$$A = \{\, x \in U \mid P(x) \,\}.$$

Приклад 1.3. Перелік $\{2, 4, 6, 8, 10\}$ дорівнює запису через властивість $\{\, x \in \mathbb{N} \mid x \text{ парне і } x \le 10 \,\}$.

Приклад 1.4 (перелік неможливий). $\{\, x \in \mathbb{R} \mid x^2 < 9 \,\}$ — це проміжок $(-3, 3)$; перелічити його елементи неможливо, тож запис через властивість тут необхідний.

Приклад 1.5 (властивість без короткої формули). Множину простих чисел, менших за $20$, найприродніше задати саме характеристичною властивістю:

$$P = \{\, x \in \mathbb{N} \mid x \text{ просте і } x < 20 \,\} = \{2, 3, 5, 7, 11, 13, 17, 19\}.$$

Тут перелік теж можливий, але правило «бути простим» не зводиться до короткої формули на кшталт $2k$ чи $3k$; характеристична властивість описує множину точніше й чесніше, ніж будь-який частковий перелік.

Рекурсивне (індуктивне) задання #

Задають базові елементи й правила, що породжують нові елементи зі старих. Саме так означують нескінченні множини скінченним описом.

Означення (рекурсивне задання). Рекурсивне задання множини $S$ має три частини: база — кілька елементів, оголошених такими, що належать $S$; індуктивне правило — як будувати нові елементи $S$ з уже наявних; замикання — $S$ не містить нічого, крім породженого базою й правилом.

Приклад 1.6 (додатні парні числа). База: $2 \in E$; правило: якщо $n \in E$, то $n+2 \in E$. Повторне застосування дає $2, 4, 6, 8, \dots$, тобто $E = \{\, 2k \mid k \in \mathbb{N} \,\}$.

Приклад 1.7 (степені двійки). База: $1 \in S$; правило: якщо $x \in S$, то $2x \in S$. Породжує $S = \{1, 2, 4, 8, 16, \dots\} = \{\, 2^{k} \mid k \in \mathbb{N}_0 \,\}$.

Приклад 1.8 (рядки над алфавітом). Зафіксуємо скінченний алфавіт $\Sigma$. Множина $\Sigma^{*}$ усіх скінченних рядків: база — порожній рядок $\varepsilon \in \Sigma^{*}$; правило — якщо $w \in \Sigma^{*}$ і $a \in \Sigma$, то $wa \in \Sigma^{*}$. Це основне означення теорії формальних мов, важливе для опрацювання тексту.

1.3 Особливі множини та числові множини #

Дві множини відіграють особливу роль і заслуговують на власні назви.

Означення (порожня множина). Порожня множина, позначена $\varnothing$ (або $\{\,\}$), — єдина множина, що не має жодного елемента. Для кожного об’єкта $x$ маємо $x \notin \varnothing$.

Стережіться такої різниці, на якій спотикаються майже всі:

$$\varnothing \ne \{\varnothing\}.$$

Ліва частина не містить нічого ($|\varnothing| = 0$). Права — одноелементна множина, єдиний елемент якої — порожня множина ($|\{\varnothing\}| = 1$). Порожня коробка й коробка з однією порожньою коробкою всередині — це різні коробки.

Означення (універсальна множина). У кожній конкретній розмові фіксують універсальну множину (універсум), часто $U$, що складається з усіх об’єктів, доречних у цій розмові. Кожну розглядувану множину вважають підмножиною $U$.

Універсум обирають з міркувань зручності: для цілих чисел $U = \mathbb{Z}$; для літер $U$ — абетка; у задачі про гральний кубик $U = \{1,2,3,4,5,6\}$. Універсум стане суттєвим у §1.7, де доповнення $\overline{A}$ означують як $U \setminus A$.

Числові множини #

Певні нескінченні множини чисел трапляються так часто, що мають зарезервовані позначення.

Ці множини вкладені одна в одну:

$$\mathbb{N} \subset \mathbb{Z} \subset \mathbb{Q} \subset \mathbb{R}.$$

Кожне вкладення власне: є цілі, що не натуральні ($-1$), раціональні, що не цілі ($\tfrac12$), дійсні, що не раціональні ($\sqrt2$).

Приклад 1.9 (класифікація). $5 \in \mathbb{N}$ (а отже й у $\mathbb{Z}, \mathbb{Q}, \mathbb{R}$); $-7 \in \mathbb{Z}$, але $-7 \notin \mathbb{N}$; $\tfrac{3}{4} \in \mathbb{Q}$, але $\notin \mathbb{Z}$; $\sqrt{2} \in \mathbb{R}$, але $\notin \mathbb{Q}$.

1.4 Порівняння множин: підмножини та рівність #

Означення підмножини #

Означення (підмножина). $A$ є підмножиною $B$, запис $A \subseteq B$, якщо кожен елемент $A$ є також елементом $B$:

$$A \subseteq B \;\iff\; (\forall x)\,(x \in A \implies x \in B).$$

Якщо додатково $A \ne B$ (тобто в $B$ є елемент, якого немає в $A$), то $A$ — власна підмножина $B$, запис $A \subset B$.

Означення — це універсально квантована імплікація, і ця логічна форма диктує спосіб доведення включень: щоб довести $A \subseteq B$, беруть довільний $x \in A$ і виводять $x \in B$.

Приклад 1.10. Нехай $A = \{1, 2\}$, $B = \{1, 2, 3, 4\}$. Кожен елемент $A$ лежить у $B$, тож $A \subseteq B$; а оскільки $3 \in B$, але $3 \notin A$, включення власне: $A \subset B$. Натомість $\{1, 5\} \not\subseteq B$, бо $5 \notin B$ — достатньо одного «свідка» поза $B$, щоб спростувати включення.

Приклад 1.11 (включення доводять для довільного елемента). Доведемо, що множина кратних чотирьох є підмножиною множини парних цілих. Нехай $A = \{\, x \in \mathbb{Z} \mid x = 4k,\ k \in \mathbb{Z} \,\}$ і $B = \{\, x \in \mathbb{Z} \mid x = 2m,\ m \in \mathbb{Z} \,\}$. Візьмемо довільний $x \in A$; тоді $x = 4k = 2\,(2k)$, тобто $x = 2m$ при $m = 2k \in \mathbb{Z}$, а отже $x \in B$. Оскільки $x$ був довільний, кожен елемент $A$ лежить у $B$, тобто $A \subseteq B$; до того ж включення власне, бо $2 \in B$, але $2 \notin A$. $\blacksquare$

Порожня множина — підмножина будь-якої множини #

Твердження 1.12. Для кожної множини $A$ маємо $\;\varnothing \subseteq A$.

Доведення. Треба показати $(\forall x)\,(x \in \varnothing \implies x \in A)$. Візьмемо довільний $x$. Передумова «$x \in \varnothing$» хибна, бо порожня множина не має елементів. Імплікація з хибною передумовою істинна (правило хибної передумови, або «порожньо-істинне» твердження). Отже, включення справджується для кожного $x$, тобто $\varnothing \subseteq A$. $\blacksquare$

Рефлексивність і транзитивність #

Твердження 1.13 (рефлексивність). Для кожної множини $A$: $\;A \subseteq A$.

Доведення. Для кожного $x$ імплікація $x \in A \implies x \in A$ істинна. $\blacksquare$

Твердження 1.14 (транзитивність). Якщо $A \subseteq B$ і $B \subseteq C$, то $A \subseteq C$.

Доведення. Нехай $x$ — довільний елемент $A$. Оскільки $A \subseteq B$, з $x \in A$ дістаємо $x \in B$. Оскільки $B \subseteq C$, з $x \in B$ дістаємо $x \in C$. Отже, кожен елемент $A$ є елементом $C$. $\blacksquare$

Рівність множин і метод подвійного включення #

Означення / Аксіома (об’ємності). Дві множини рівні, $A = B$, саме тоді, коли вони мають однакові елементи:

$$A = B \;\iff\; (\forall x)\,(x \in A \iff x \in B).$$

Біумовність «$x \in A \iff x \in B$» розпадається на дві імплікації, а це — рівно два включення. Звідси головна робоча теорема розділу.

Теорема 1.15 (рівність через подвійне включення; антисиметричність $\subseteq$). Для всіх множин $A, B$:

$$A = B \;\iff\; \big(A \subseteq B \ \text{і}\ B \subseteq A\big).$$

Доведення. ($\Rightarrow$) Нехай $A = B$. За об’ємністю для кожного $x$ маємо $x \in A \iff x \in B$; зокрема $x \in A \implies x \in B$ (тобто $A \subseteq B$) і навпаки ($B \subseteq A$). ($\Leftarrow$) Нехай $A \subseteq B$ і $B \subseteq A$. Для довільного $x$ об’єднання двох імплікацій дає $x \in A \iff x \in B$; за об’ємністю $A = B$. $\blacksquare$

Шаблон доведення через подвійне включення. Щоб довести $A = B$: (1) припусти $x \in A$ і виведи $x \in B$ (отже $A \subseteq B$); (2) припусти $x \in B$ і виведи $x \in A$ (отже $B \subseteq A$); (3) за Теоремою 1.15 маємо $A = B$. Цей шаблон використовуватиметься в §1.8 для доведення всіх законів алгебри множин.

Приклад 1.16 (перелік проти властивості). Нехай $A = \{\, x \in \mathbb{Z} \mid x^2 = 1 \,\}$ і $B = \{-1, 1\}$. Доведемо $A = B$. ($\subseteq$) Якщо $x \in A$, то $x^2 = 1$, тобто $(x-1)(x+1)=0$, звідки $x = \pm 1$, отже $x \in B$. ($\supseteq$) $1^2 = 1$ і $(-1)^2 = 1$, тож $1, -1 \in A$. За подвійним включенням $A = B$. $\blacksquare$

1.5 Множина-ступінь #

Оскільки підмножини множини $A$ самі є об’єктами, їх можна зібрати в нову множину.

Означення (множина-ступінь). Множина-ступінь множини $A$, позначена $\mathcal{P}(A)$ (також $2^{A}$), — це множина всіх підмножин $A$:

$$\mathcal{P}(A) = \{\, S \mid S \subseteq A \,\}.$$

Її елементи самі є множинами; $\varnothing$ і $A$ завжди належать $\mathcal{P}(A)$.

Приклад 1.17. $\mathcal{P}(\varnothing) = \{\varnothing\}$ — один елемент, не нуль! $\mathcal{P}(\{a\}) = \{\varnothing, \{a\}\}$; $\mathcal{P}(\{a,b\}) = \{\varnothing, \{a\}, \{b\}, \{a,b\}\}$.

Типова помилка ($\mathcal{P}(\varnothing)$ не порожня). Множина-ступінь ніколи не буває порожньою: у кожної множини є принаймні одна підмножина — сама $\varnothing$. Тому $\mathcal{P}(\varnothing) = \{\varnothing\}$ має один елемент, а не жодного; сплутати $\varnothing$ (нуль елементів) із $\{\varnothing\}$ (один елемент) — та сама пастка, про яку йшлося у §1.3.

Приклад 1.18 (зі слайдів). Для $A = \{1, 2, 3, 4\}$ множина-ступінь має $16$ елементів:

$$\mathcal{P}(A) = \big\{\ \varnothing,\ \{1\},\{2\},\{3\},\{4\},\ \{1,2\},\{1,3\},\{1,4\},\{2,3\},\{2,4\},\{3,4\},$$

$$\{1,2,3\},\{1,2,4\},\{1,3,4\},\{2,3,4\},\ \{1,2,3,4\}\ \big\}.$$

За розміром: $1 + 4 + 6 + 4 + 1 = 16$ — біноміальні коефіцієнти $\binom{4}{k}$.

Теорема 1.19. Якщо $A$ скінченна і $|A| = n$, то $|\mathcal{P}(A)| = 2^{n}$.

Доведення (через характеристичні вектори). Занумеруємо елементи $A = \{a_1, \dots, a_n\}$. Кожній підмножині $S \subseteq A$ зіставимо бітовий рядок $(b_1, \dots, b_n)$, де $b_i = 1$, якщо $a_i \in S$, і $b_i = 0$ інакше. Це зіставлення — бієкція між $\mathcal{P}(A)$ і множиною всіх $n$-бітових рядків $\{0,1\}^{n}$: за рядком однозначно відновлюється підмножина, і навпаки. Кожен із $n$ бітів обирається незалежно з $2$ значень, тож рядків рівно $2^{n}$. Отже, $|\mathcal{P}(A)| = 2^{n}$. $\blacksquare$

Ця бієкція не лише лічильний прийом — саме так множини зберігають у комп’ютері: підмножина $n$-елементного універсуму — це одне $n$-бітове слово.

Приклад 1.20 (характеристичні вектори конкретно). Для $A = \{a, b, c\}$ бієкція з доведення Теореми 1.19 зіставляє кожній підмножині її бітовий рядок $(b_a, b_b, b_c)$, де кожен біт показує наявність відповідного елемента:

$$\begin{array}{llll} \varnothing \leftrightarrow 000 & \{a\} \leftrightarrow 100 & \{b\} \leftrightarrow 010 & \{c\} \leftrightarrow 001 \\ \{a,b\} \leftrightarrow 110 & \{a,c\} \leftrightarrow 101 & \{b,c\} \leftrightarrow 011 & \{a,b,c\} \leftrightarrow 111 \end{array}$$

Вісім підмножин — вісім трибітових рядків від $000$ до $111$, тобто рівно $2^{3} = 8$; перелічити всі підмножини — це те саме, що полічити від $0$ до $7$ у двійковій системі.

1.6 Діаграми Венна та круги Ейлера #

Діаграма Венна зображує кожну множину колом усередині прямокутника $U$ так, щоб було показано всі можливі перетини. Для двох множин — чотири області; для трьох — вісім.

Круги Ейлера — та сама ідея, але показують лише ті зв’язки, що справді існують. Наприклад, якщо $A \subseteq B$, коло $A$ малюють усередині кола $B$ без зайвого перетину; якщо множини не перетинаються — кола розводять.

Як заштрихувати вираз (зсередини назовні). Щоб зобразити область, яку задає формула, обчислюють її, як арифметичний вираз, — спершу внутрішню операцію: об’єднання зафарбовує обидві області, перетин лишає лише спільну частину, різниця $X \setminus Y$ лишає частину $X$ поза $Y$, доповнення зафарбовує все поза областю.

Зауваження (читаємо діаграму як обчислення). Щоб заштрихувати, скажімо, $\overline{A} \cap B$, спершу подумки будуємо $\overline{A}$ — усе поза колом $A$, — а тоді лишаємо з нього тільки те, що потрапляє в коло $B$. Дістаємо «серпик» усередині $B$, але поза $A$, тобто рівно $B \setminus A$. Так діаграма унаочнює тотожність $\overline{A} \cap B = B \setminus A$, яку інакше довелося б перевіряти алгебраїчно.

1.7 Операції над множинами #

Нехай $A$ і $B$ — множини всередині універсуму $U$.

Два факти, якими користуються постійно:

• Доповнення відносне. $\overline{A}$ не має сенсу без універсуму; завжди спершу вказуйте $U$.
• Різниця напрямлена. Загалом $A \setminus B \ne B \setminus A$. Множини з $A \cap B = \varnothing$ називають неперетинними (диз’юнктними).

Найкорисніший місток між операціями:

$$A \setminus B = A \cap \overline{B},$$

тобто «усе в $A$, чого немає в $B$» дорівнює «$A$ у перетині з доповненням $B$».

Симетрична різниця #

Часто нас цікавить не «усе, що в $A$ або $B$», а те, чим множини різняться, — елементи, що належать рівно одній із них. Цю ідею вловлює симетрична різниця, унесена останнім рядком таблиці вище.

Означення (симетрична різниця). Симетричною різницею множин $A$ і $B$, позначеною $A \triangle B$, називають множину елементів, що належать рівно одній із них:

$$A \triangle B = (A \setminus B) \cup (B \setminus A).$$

Рівносильно, $A \triangle B = (A \cup B) \setminus (A \cap B)$ — «об’єднання без спільної частини». На діаграмі Венна це два «серпики» обабіч лінзи перетину, а сама лінза $A \cap B$ лишається незафарбованою.

Приклад 1.21 (обчислення симетричної різниці). Нехай $A = \{1, 2, 3\}$, $B = \{3, 4\}$. Тоді $A \setminus B = \{1, 2\}$ і $B \setminus A = \{4\}$, тож

$$A \triangle B = \{1, 2\} \cup \{4\} = \{1, 2, 4\}.$$

Спільний елемент $3$ у результат не потрапляє — саме він «скорочується». Той самий результат дає й друга формула: $(A \cup B) \setminus (A \cap B) = \{1,2,3,4\} \setminus \{3\} = \{1, 2, 4\}$.

Симетрична різниця поводиться як «додавання за модулем $2$» на множинах і має прості, легко перевірювані властивості.

Твердження 1.22 (властивості симетричної різниці). Для будь-яких множин $A, B$:

1. комутативність: $A \triangle B = B \triangle A$;
2. $A \triangle A = \varnothing$;
3. $A \triangle \varnothing = A$.

Доведення. (1) За означенням $A \triangle B = (A \setminus B) \cup (B \setminus A)$; об’єднання комутативне (§1.8), тож це те саме, що $(B \setminus A) \cup (A \setminus B) = B \triangle A$. (2) Оскільки $A \setminus A = \varnothing$, маємо $A \triangle A = \varnothing \cup \varnothing = \varnothing$: із собою множина «не різниться». (3) Тут $A \setminus \varnothing = A$, а $\varnothing \setminus A = \varnothing$, звідки $A \triangle \varnothing = A \cup \varnothing = A$. $\blacksquare$

Зауваження (асоціативність і XOR). Симетрична різниця ще й асоціативна: $(A \triangle B) \triangle C = A \triangle (B \triangle C)$, і елемент належить цьому результату саме тоді, коли лежить у непарній кількості множин $A, B, C$. Разом із рівністю $A \triangle A = \varnothing$ (кожна множина сама собі протилежна) це робить $\triangle$ точним аналогом булевого «виключного або» (XOR, $\oplus$) — зв’язок, до якого ми повернемося в лекціях про булеві функції.

Пріоритет операцій #

Щоб не ставити зайвих дужок, домовляються про пріоритет (від найвищого до найнижчого):

$$\overline{\ \cdot\ } \;\succ\; \cap \;\succ\; \cup,\ \setminus.$$

Спершу виконують доповнення, потім перетин, потім об’єднання/різницю. Наприклад, $\overline{A} \cap B \cup C$ читається як $((\overline{A}) \cap B) \cup C$.

1.8 Закони алгебри множин #

Операції задовольняють алгебраїчні закони. Вони дають змогу спрощувати вирази та доводити тотожності символьними перетвореннями.

Найважливіші — де Моргана (доповнення об’єднання/перетину змінює операцію на протилежну й доповнює частини) та закон різниці $A \setminus B = A \cap \overline{B}$: разом вони роблять більшу частину роботи в доведеннях.

Теорема 1.23 (перший закон де Моргана). $\overline{A \cup B} = \overline{A} \cap \overline{B}$.

Доведення (подвійне включення). ($\subseteq$) Нехай $x \in \overline{A \cup B}$. Тоді $x \in U$ і $x \notin A \cup B$, тобто $x \notin A$ і $x \notin B$. Отже, $x \in \overline{A}$ і $x \in \overline{B}$, звідки $x \in \overline{A} \cap \overline{B}$. ($\supseteq$) Нехай $x \in \overline{A} \cap \overline{B}$. Тоді $x \notin A$ і $x \notin B$, тож $x$ не належить $A \cup B$, тобто $x \in \overline{A \cup B}$. За подвійним включенням множини рівні. $\blacksquare$

Теорема 1.24 (другий закон де Моргана). $\overline{A \cap B} = \overline{A} \cup \overline{B}$.

Доведення (подвійне включення). ($\subseteq$) Нехай $x \in \overline{A \cap B}$. Тоді $x \in U$ і $x \notin A \cap B$, тобто неправда, що водночас $x \in A$ і $x \in B$. Заперечення кон’юнкції — це диз’юнкція заперечень, тож $x \notin A$ або $x \notin B$, тобто $x \in \overline{A}$ або $x \in \overline{B}$; отже, $x \in \overline{A} \cup \overline{B}$. ($\supseteq$) Нехай $x \in \overline{A} \cup \overline{B}$. Тоді $x \notin A$ або $x \notin B$, тож $x$ не може належати водночас і $A$, і $B$, тобто $x \notin A \cap B$, звідки $x \in \overline{A \cap B}$. За подвійним включенням множини рівні. $\blacksquare$

Теорема 1.25 (дистрибутивність $\cap$ відносно $\cup$). $A \cap (B \cup C) = (A \cap B) \cup (A \cap C)$.

Доведення. Для довільного $x$: $x \in A \cap (B \cup C)$ $\iff x \in A$ і ($x \in B$ або $x \in C$) $\iff$ ($x \in A$ і $x \in B$) або ($x \in A$ і $x \in C$) $\iff x \in (A \cap B) \cup (A \cap C)$. Перехід у середині — дистрибутивність «і» відносно «або» в логіці. Оскільки елемент належить лівій частині саме тоді, коли й правій, множини рівні. $\blacksquare$

Твердження 1.26 (закон поглинання). $A \cup (A \cap B) = A$.

Доведення (подвійне включення). ($\supseteq$) Для довільного $x \in A$ одразу маємо $x \in A \cup (A \cap B)$ (лівий доданок об’єднання вже містить $x$), тож $A \subseteq A \cup (A \cap B)$. ($\subseteq$) Нехай $x \in A \cup (A \cap B)$. Тоді $x \in A$ або $x \in A \cap B$. У першому випадку $x \in A$ безпосередньо; у другому з $x \in A \cap B$ поготів $x \in A$. В обох випадках $x \in A$, тож $A \cup (A \cap B) \subseteq A$. Отже, $A \cup (A \cap B) = A$. Двоїстий закон $A \cap (A \cup B) = A$ доводять симетрично. $\blacksquare$

Приклад 1.27 (спрощення виразу). Спростимо $\overline{\overline{A} \cup B} \cup (A \cap B)$:

$$\begin{aligned} \overline{\overline{A} \cup B} \cup (A \cap B) &= (\overline{\overline{A}} \cap \overline{B}) \cup (A \cap B) && \text{(де Морган)} \\ &= (A \cap \overline{B}) \cup (A \cap B) && \text{(інволюція)} \\ &= A \cap (\overline{B} \cup B) && \text{(дистрибутивність)} \\ &= A \cap U = A. && \text{(доповнення, одиниця)} \end{aligned}$$

Приклад 1.28 (розклад за ознакою). Спростимо $(A \cap B) \cup (A \cap \overline{B})$:

$$\begin{aligned} (A \cap B) \cup (A \cap \overline{B}) &= A \cap (B \cup \overline{B}) && \text{(дистрибутивність)} \\ &= A \cap U && \text{(доповнення)} \\ &= A. && \text{(одиниця)} \end{aligned}$$

Це «розклад за $B$»: кожен об’єкт або має ознаку $B$, або ні, тож перетини $A$ з $B$ і з $\overline{B}$ разом відновлюють увесь $A$. Дзеркальний до нього закон $(A \cup B) \cap (A \cup \overline{B}) = A$ доводять так само, помінявши ролями $\cup$ і $\cap$.

1.9 Потужність, рівнопотужність і бієкція #

Означення (потужність). Потужність множини $A$, позначена $|A|$, — це кількість її елементів. Множина скінченна, якщо $|A| = n$ для деякого $n \in \{0,1,2,\dots\}$, і нескінченна інакше.

• $|\varnothing| = 0$; $|\{a,b,c\}| = 3$; $|\{1,1,2\}| = 2$ (повтори не рахують двічі).

Порівняння розмірів через бієкцію #

Дві множини мають «однаковий розмір», коли їхні елементи можна поставити у взаємно однозначну відповідність — по одному, без залишку з обох боків. Саме ця ідея відповідності, а не лічба, узагальнюється на нескінченні множини.

Означення (бієкція, рівнопотужність). Множини $A$ і $B$ рівнопотужні, запис $A \sim B$ (або $|A| = |B|$), якщо існує бієкція $f : A \to B$ — відповідність, за якою кожному $a \in A$ відповідає рівно один $b \in B$ і кожному $b \in B$ відповідає рівно один $a \in A$.

Приклад 1.29. Для $A = \{a, e, i, o, u\}$ і $B = \{1,2,3,4,5\}$ є бієкція $a\mapsto1, e\mapsto2, i\mapsto3, o\mapsto4, u\mapsto5$, тож $A \sim B$ і $|A| = |B| = 5$.

Зауваження (нескінченні множини). Для нескінченних множин бієкція дає несподівані результати: $\mathbb{N} \sim \mathbb{Z}$ (цілих «удвічі більше», але вони рівнопотужні натуральним) і навіть $\mathbb{N} \sim \mathbb{Q}$. Множини, рівнопотужні $\mathbb{N}$, називають зліченними. Натомість $\mathbb{R}$ не рівнопотужна $\mathbb{N}$ — дійсних чисел «більше». Отже, бувають різні «розміри нескінченності». Це поняття тут лише окреслено; детально в подальших курсах.

Приклад 1.30 (зліченність $\mathbb{Z}$: явна бієкція). Хоча $\mathbb{Z}$ «тягнеться» в обидва боки, її елементи можна вишикувати в один нескінченний список, чергуючи знаки:

$$0,\ 1,\ -1,\ 2,\ -2,\ 3,\ -3,\ \dots$$

Формально бієкцію $f\colon \mathbb{N} \to \mathbb{Z}$ (беручи $\mathbb{N} = \{1, 2, 3, \dots\}$) задають правилом

$$f(n) = \begin{cases} \tfrac{n}{2}, & n \text{ парне}, \\ -\tfrac{n-1}{2}, & n \text{ непарне}. \end{cases}$$

Перевіримо перші значення: $f(1) = 0$, $f(2) = 1$, $f(3) = -1$, $f(4) = 2$, $f(5) = -2$, $\dots$ Кожне ціле число з’являється в цьому списку рівно один раз (парні $n$ дають $0$ і додатні значення, непарні — від’ємні), тож $f$ — бієкція і $\mathbb{N} \sim \mathbb{Z}$: цілих «стільки ж», скільки натуральних.

Той самий задум — «вишикувати все в один список» — показує, що й $\mathbb{Q}$ зліченна (усі дроби можна обійти по діагоналях нескінченної таблиці). А от для $\mathbb{R}$ такого списку не існує: знаменитий діагональний аргумент Кантора доводить, що $\mathbb{R}$ незліченна — дійсних чисел строго більше. Ці два факти подаємо оглядово, без повних доведень.

1.10 Принцип включення-виключення #

Скільки елементів у об’єднанні? Якщо множини неперетинні, відповідь очевидна: $|A \cup B| = |A| + |B|$ (правило суми). Але коли множини мають спільні елементи, просте додавання лічить кожен спільний елемент двічі — по разу в $|A|$ і в $|B|$. Принцип включення-виключення систематично виправляє цей подвійний облік.

Дві множини #

Теорема 1.31 (формула включення-виключення для двох множин). Для будь-яких скінченних множин $A$ і $B$:

$$|A \cup B| = |A| + |B| - |A \cap B|.$$

Доведення. Кожен елемент об’єднання $A \cup B$ належить рівно до однієї з трьох неперетинних частин: лише $A$ (тобто $A \setminus B$), лише $B$ (тобто $B \setminus A$) або обох одразу ($A \cap B$). Для неперетинних частин розміри додаються, тож

$$|A \cup B| = |A \setminus B| + |B \setminus A| + |A \cap B|.$$

З іншого боку, кожна з множин розпадається на «свою частину» й «спільну»: $|A| = |A \setminus B| + |A \cap B|$ і $|B| = |B \setminus A| + |A \cap B|$. Додавши ці дві рівності, дістаємо

$$|A| + |B| = |A \setminus B| + |B \setminus A| + 2\,|A \cap B|.$$

Отже, сума $|A| + |B|$ перевищує $|A \cup B|$ рівно на один зайвий екземпляр $|A \cap B|$. Віднявши цей надлишок, дістаємо формулу. $\blacksquare$

Зауваження (чому «включення-виключення»). Спершу ми включаємо всі елементи $A$ і всі елементи $B$ (додаємо $|A| + |B|$), а потім виключаємо надлишок — спільні елементи, кожен з яких потрапив у суму двічі (віднімаємо $|A \cap B|$). Ця гра «додати зайве — відняти зайве» узагальнюється на будь-яку кількість множин зі знаками, що чергуються.

Три множини #

Для трьох множин подвійний облік хитріший: віднявши всі три попарні перетини, ми заразом тричі вилучаємо спільну для всіх частину $A \cap B \cap C$, яку перед тим тричі додали, — тож її треба повернути.

Теорема 1.32 (включення-виключення для трьох множин). Для скінченних $A, B, C$:

$$|A \cup B \cup C| = |A| + |B| + |C| - |A \cap B| - |A \cap C| - |B \cap C| + |A \cap B \cap C|.$$

Доведення (ідея). Застосуємо формулу для двох множин до $A \cup B$ і $C$:

$$|(A \cup B) \cup C| = |A \cup B| + |C| - |(A \cup B) \cap C|.$$

Розкриємо $|A \cup B| = |A| + |B| - |A \cap B|$, а за дистрибутивністю (§1.8) $(A \cup B) \cap C = (A \cap C) \cup (B \cap C)$, тож знову за формулою для двох множин

$$|(A \cap C) \cup (B \cap C)| = |A \cap C| + |B \cap C| - |A \cap B \cap C|$$

(бо $(A \cap C) \cap (B \cap C) = A \cap B \cap C$). Підставивши це все й розкривши дужки, дістаємо потрібну знакозмінну суму. $\blacksquare$

Приклад 1.33 (числа, що діляться на $2$ або на $3$). Скільки цілих від $1$ до $100$ діляться на $2$ або на $3$? Нехай $A$ — кратні $2$, а $B$ — кратні $3$ у межах $\{1, \dots, 100\}$. Тоді

$$|A| = \left\lfloor \tfrac{100}{2} \right\rfloor = 50, \qquad |B| = \left\lfloor \tfrac{100}{3} \right\rfloor = 33,$$

а спільні елементи — це числа, кратні водночас $2$ і $3$, тобто кратні $6$:

$$|A \cap B| = \left\lfloor \tfrac{100}{6} \right\rfloor = 16.$$

За Теоремою 1.31:

$$|A \cup B| = 50 + 33 - 16 = 67.$$

Отже, $67$ чисел діляться на $2$ або на $3$, а решта $100 - 67 = 33$ — на жодне з них. Саме ці підрахунки й зображено на діаграмі вище.

Приклад 1.34 (замовлення у друкарні). Друкарня прийняла $120$ замовлень. Ламінування замовили для $70$ видань, тверду оправу — для $50$, а обидві послуги разом — для $30$. Скільки замовлень мають принаймні одну з цих послуг і скільки — жодної? Нехай $L$ — множина замовлень із ламінуванням, $H$ — із твердою оправою; тоді $|L| = 70$, $|H| = 50$, $|L \cap H| = 30$, і за формулою включення-виключення

$$|L \cup H| = 70 + 50 - 30 = 90.$$

Принаймні одну послугу мають $90$ замовлень; жодної — $120 - 90 = 30$. Якби ми легковажно додали $70 + 50 = 120$, то порахували б $30$ «подвійних» замовлень двічі й дійшли б безглуздого висновку, що послуги охоплюють геть усі $120$ замовлень.

Загальний випадок (оглядово) #

Для $n$ множин формула продовжує той самий візерунок: додають розміри поодиноких множин, віднімають розміри всіх попарних перетинів, додають усі потрійні, віднімають усі четверні — і так далі, чергуючи знак:

$$\Big| \bigcup_{i=1}^{n} A_i \Big| = \sum_i |A_i| - \sum_{i<j} |A_i \cap A_j| + \sum_{i<j<k} |A_i \cap A_j \cap A_k| - \dots + (-1)^{n-1}\,|A_1 \cap \dots \cap A_n|.$$

Знак перед перетином $k$ множин — це $(-1)^{k-1}$: перетини непарного порядку додають, парного — віднімають. Уже доведені випадки $n = 2$ і $n = 3$ — це перші два рядки цього загального закону.

Зауваження (зв’язок з імовірністю). Та сама структура «додати — відняти — додати» керує ймовірністю об’єднання подій: $P(A \cup B) = P(A) + P(B) - P(A \cap B)$. Ми повернемося до цього в лекціях з теорії ймовірностей, де включення-виключення дає змогу лічити ймовірність того, що станеться хоча б одна з кількох подій.

Історична довідка. Формулу для довільної кількості множин — зі знаками, що чергуються перед сумами перетинів дедалі вищого порядку, — систематично дослідив у XIX ст. Джеймс Джозеф Сильвестр; її загальний вигляд пов’язують також з іменами да Сільви та Пуанкаре. У сучасній комбінаториці це один із найуживаніших інструментів підрахунку.

Типова помилка (забути про перетин). Найпоширеніша помилка — написати $|A \cup B| = |A| + |B|$, не віднявши $|A \cap B|$. Це правильно лише для неперетинних множин ($A \cap B = \varnothing$). Завжди запитуйте себе: «чи можуть множини мати спільні елементи?» — і якщо можуть, віднімайте перетин.

1.11 Застосування у видавництві та поліграфії #

Мова множин безпосередньо описує задачі фаху:

• Кольороподіл. Палітру зображення можна подати як множину кольорів; перетин палітр двох зображень — спільні кольори, різниця — ті, що є лише в одному.
• Шрифти й гліфи. Набір гліфів шрифту — множина; чи можна набрати текст даним шрифтом, — це перевірка включення множини символів тексту в множину гліфів.
• Бази даних. Реляційна модель (Лекція 2) будується просто на множинах кортежів; операції об’єднання/перетину/різниці таблиць — це операції над множинами.
• Характеристичний вектор. Бітова маска обраних параметрів (напр., увімкнені шари в макеті) — це підмножина універсуму параметрів; звідси $2^{n}$ можливих конфігурацій $n$ перемикачів (Теорема 1.19).

Підсумок #

• Множина — невпорядкована сукупність різних елементів; визначається лише тим, які елементи містить (об’ємність). Належність — $x \in A$.
• Множину задають переліком, характеристичною властивістю або рекурсивно.
• $\varnothing$ — порожня множина; $U$ — універсум (потрібен для доповнення). Числові множини вкладені: $\mathbb{N} \subset \mathbb{Z} \subset \mathbb{Q} \subset \mathbb{R}$.
• $A \subseteq B$ означає, що кожен елемент $A$ є в $B$; відношення $\subseteq$ рефлексивне, транзитивне й антисиметричне. Рівність доводять подвійним включенням.
• Множина-ступінь $\mathcal{P}(A)$ містить усі підмножини; $|\mathcal{P}(A)| = 2^{|A|}$.
• Операції $\cup, \cap, \setminus, \overline{\ \cdot\ }$ підпорядковані законам алгебри множин (комутативність, асоціативність, дистрибутивність, де Морган, поглинання, …); тотожності доводять подвійним включенням або перетвореннями.
• Симетрична різниця $A \triangle B = (A \setminus B) \cup (B \setminus A)$ збирає елементи, що належать рівно одній множині; вона комутативна, $A \triangle A = \varnothing$, $A \triangle \varnothing = A$.
• Потужність $|A|$; рівність розмірів — через бієкцію (рівнопотужність).
• Принцип включення-виключення лічить об’єднання без подвійного обліку: $|A \cup B| = |A| + |B| - |A \cap B|$, а для трьох множин — зі знаками, що чергуються ($+$ поодинокі, $-$ попарні, $+$ потрійний перетин).

Вправи #

Для розігріву #

1. Чи правильно, що $\{1,2\} = \{2,1,1\}$? Обґрунтуйте через об’ємність.
2. Випишіть $\mathcal{P}(\{a, b\})$ повністю. Скільки елементів має $\mathcal{P}(A)$, якщо $|A| = 5$?
3. Нехай $U = \{1,\dots,9\}$, $A = \{1,2,3,4\}$, $B = \{3,4,5,6\}$. Обчисліть $A \cup B$, $A \cap B$, $A \setminus B$, $B \setminus A$, $\overline{A}$.
4. Для тих самих $U = \{1,\dots,9\}$, $A = \{1,2,3,4\}$, $B = \{3,4,5,6\}$ обчисліть симетричну різницю $A \triangle B$ двома способами — як $(A \setminus B) \cup (B \setminus A)$ і як $(A \cup B) \setminus (A \cap B)$ — та переконайтесь, що результати збігаються.