# Лекція 1. Алгебра множин ## Огляд Теорія множин — це базова мова всієї дискретної математики. Майже кожен об'єкт, який ми вивчатимемо далі в курсі, — відношення, функції, булеві алгебри, графи, ймовірнісні простори — побудований на множинах. Коли ми кажемо «граф — це пара $(V, E)$, де $E$ — множина ребер», «відношення з $A$ у $B$ — це підмножина $A \times B$» або «подія — це підмножина простору наслідків», ми говоримо мовою множин. Навчитися вільно читати й писати цією мовою зараз — означає полегшити собі кожну наступну лекцію. У цьому розділі ми вводимо первісне поняття **множини** та відношення **належності**, перелічуємо способи *задання* множин (перелік, характеристична властивість, рекурсія), учимося *порівнювати* множини (підмножина, рівність), *вимірювати* їх (потужність, множина-ступінь) і, нарешті, будуємо **алгебру множин** — операції об'єднання, перетину, різниці, доповнення та закони, яким вони підпорядковані. Дорогою ми **доводимо** структурні факти ($\varnothing \subseteq A$, критерій рівності через подвійне включення, $|\mathcal{P}(A)| = 2^{n}$) строго, а не просто проголошуємо їх, бо велика частина цінності курсу — навчитися *доводити* твердження про дискретні структури. Операції над множинами, які ми тут будуємо, знадобляться одразу — вже в цьому розділі, коли ми навчимося *лічити* об'єднання (§1.10), — а **відношення**, побудовані на множинах упорядкованих пар, чекають уже в [Лекції 2](ODM-L02.md). > **Про строгість.** Кілька результатів нижче оформлені як **теореми** чи > **твердження** та супроводжуються доведенням, обмеженим позначками *Доведення.* … > $\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}$ | натуральні числа | $\{1, 2, 3, \dots\}$ — лічильні числа | | $\mathbb{Z}$ | цілі числа | $\{\dots, -2, -1, 0, 1, 2, \dots\}$ | | $\mathbb{Q}$ | раціональні числа | дроби $\tfrac{p}{q}$, $p,q \in \mathbb{Z}$, $q \ne 0$ | | $\mathbb{R}$ | дійсні числа | усі раціональні **та** ірраціональні разом | Ці множини **вкладені** одна в одну: $$ \mathbb{N} \subset \mathbb{Z} \subset \mathbb{Q} \subset \mathbb{R}. $$ Кожне вкладення *власне*: є цілі, що не натуральні ($-1$), раціональні, що не цілі ($\tfrac12$), дійсні, що не раціональні ($\sqrt2$). ![Числові множини, вкладені одна в одну: ℕ ⊂ ℤ ⊂ ℚ ⊂ ℝ](img/l01_hierarchy.png) **Приклад 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$.** ![Діаграма Венна для A ⊆ B: коло A цілком лежить усередині кола B](img/l01_subset.png) **Приклад 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}$. ![Множина-ступінь \mathcal{P}({a,b,c}) як ґратка всіх 2³ = 8 підмножин, упорядкованих включенням](img/l01_powerset.png) > **Теорема 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$ без зайвого перетину; якщо множини не перетинаються — кола розводять. ![Круги Ейлера: перетин, неперетинні множини, підмножина](img/l01_euler.png) **Як заштрихувати вираз (зсередини назовні).** Щоб зобразити область, яку задає формула, обчислюють її, як арифметичний вираз, — спершу внутрішню операцію: об'єднання зафарбовує *обидві* області, перетин лишає лише *спільну* частину, різниця $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$. | Операція | Позначення | Означення | Приклад | |---|:--:|---|---| | **Об'єднання** | $A \cup B$ | $\{\, x : x \in A \text{ або } x \in B \,\}$ | $\{1,2,3\}\cup\{3,4\}=\{1,2,3,4\}$ | | **Перетин** | $A \cap B$ | $\{\, x : x \in A \text{ і } x \in B \,\}$ | $\{1,2,3\}\cap\{3,4\}=\{3\}$ | | **Різниця** | $A \setminus B$ | $\{\, x : x \in A \text{ і } x \notin B \,\}$ | $\{1,2,3\}\setminus\{3,4\}=\{1,2\}$ | | **Доповнення** | $\overline{A}$ | $U \setminus A = \{\, x \in U : x \notin A \,\}$ | $\overline{\{1,2\}}=\{3,4,5\}$, якщо $U=\{1,\dots,5\}$ | | **Симетрична різниця** | $A \triangle B$ | $\{\, x : x \in A \text{ або } x \in B, \text{ але не обидва} \,\}$ | $\{1,2,3\}\triangle\{3,4\}=\{1,2,4\}$ | ![Чотири операції над множинами на діаграмах Венна: об'єднання, перетин, різниця, доповнення](img/l01_venn_ops.png) Два факти, якими користуються постійно: - **Доповнення відносне.** $\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$ лишається незафарбованою. ![Симетрична різниця A △ B: заштриховано дві частини, що належать рівно одній множині, а спільну лінзу перетину вилучено](img/l01_symdiff.png) **Приклад 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 \cup B = B \cup A,\quad A \cap B = B \cap A$ | | Асоціативність | $(A \cup B) \cup C = A \cup (B \cup C)$, і так само для $\cap$ | | Дистрибутивність | $A \cap (B \cup C) = (A \cap B) \cup (A \cap C)$; двоїсто для $\cup$ | | Ідемпотентність | $A \cup A = A,\quad A \cap A = A$ | | Одиниці/нулі | $A \cup \varnothing = A,\ A \cap U = A,\ A \cup U = U,\ A \cap \varnothing = \varnothing$ | | Доповнення | $A \cup \overline{A} = U,\quad A \cap \overline{A} = \varnothing$ | | Інволюція | $\overline{\overline{A}} = A$ | | Поглинання | $A \cup (A \cap B) = A,\quad A \cap (A \cup B) = A$ | | Закони де Моргана | $\overline{A \cup B} = \overline{A} \cap \overline{B},\quad \overline{A \cap B} = \overline{A} \cup \overline{B}$ | Найважливіші — **де Моргана** (доповнення об'єднання/перетину змінює операцію на протилежну й доповнює частини) та закон **різниці** $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$ ![Закон де Моргана: доповнення A ∪ B збігається з перетином доповнень](img/l01_demorgan.png) > **Теорема 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$. ![Бієкція між A і B: кожному елементу A відповідає рівно один елемент B і навпаки](img/l01_bijection.png) **Приклад 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$ ![Принцип включення-виключення для U = {1,…,100}: |A ∪ B| = |A| + |B| − |A ∩ B|; спільну частину, полічену двічі, віднімають один раз](img/l01_incl_excl.png) > **Зауваження (чому «включення-виключення»).** Спершу ми **включаємо** всі елементи $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 **Зауваження (зв'язок з імовірністю).** Та сама структура «додати — відняти — додати» > керує ймовірністю об'єднання подій: $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)$ — та переконайтесь, що результати збігаються. ### Стандартні 5. Доведіть подвійним включенням, що $A \setminus (A \setminus B) = A \cap B$. 6. Спростіть вираз $\overline{A \cap B} \cap (A \cup B)$, посилаючись на закони. 7. Задайте характеристичною властивістю множину $\{3, 6, 9, 12, 15\}$ і множину всіх парних цілих у проміжку $[-4, 4]$. 8. Доведіть другий закон де Моргана $\overline{A \cap B} = \overline{A} \cup \overline{B}$. 9. У групі з $30$ студентів $18$ відвідують вибірковий курс із типографіки, $15$ — із кольорознавства, а $7$ — обидва курси. Скориставшись Теоремою 1.31, знайдіть, скільки студентів відвідують хоча б один із цих курсів і скільки — жодного. ### Підвищеної складності 10. Доведіть, що $A \subseteq B \iff A \cup B = B \iff A \cap B = A$ (три рівносильні умови). 11. Побудуйте бієкцію між $\mathbb{N}$ і множиною парних натуральних чисел; поясніть, чому це не суперечить тому, що парні числа — власна підмножина $\mathbb{N}$. 12. Скільки різних булевих масок (підмножин) можна задати для макета з $10$ незалежними шарами? Узагальніть на $n$ шарів і зв'яжіть із Теоремою 1.19. 13. Доведіть тотожність $|A \triangle B| = |A| + |B| - 2\,|A \cap B|$ для скінченних множин. *(Підказка: $A \triangle B = (A \cup B) \setminus (A \cap B)$, до того ж $A \cap B \subseteq A \cup B$; застосуйте принцип включення-виключення.)*