Множества, отношения и функции: задачи с пошаговыми решениями

1Множества и операции над ними

Множество — это совокупность различных элементов: A = {1, 2, 3}. Порядок и повторения не имеют значения. |A| — число элементов, а U — универсальное множество, содержащее всё, о чём идёт речь.

• A ∪ B (объединение): элементы, лежащие в A, или в B, или в обоих.
• A ∩ B (пересечение): элементы, лежащие в обоих.
• A − B (разность): элементы A, не лежащие в B.
• A′ (дополнение): элементы U, не лежащие в A.

На диаграмме Венна два круга делят U на четыре области: только A, оба, только B и ни одно. Каждое выражение для множеств является объединением некоторых из этих областей, поэтому его всегда можно подсчитать по областям.

Здесь |A| = 12 + 5 = 17, |A ∩ B| = 5, |A ∪ B| = 12 + 5 + 8 = 25 и |(A ∪ B)′| = 15.

2Подсчёт по формуле включений и исключений

Сумма |A| и |B| считает пересечение дважды, поэтому вычтите его один раз:

Для трёх множеств вычитаются попарные пересечения, но тогда центр оказывается убран трижды, поэтому его прибавляют обратно:

В текстовых задачах обычно надёжнее заполнять диаграмму Венна от центра к краям: сначала элементы, лежащие во всех трёх множествах, затем каждая пара без центра, затем каждое отдельное множество без уже размещённых элементов.

Часто встречаются ещё два подсчёта: у множества из n элементов 2ⁿ подмножеств (его булеан 𝒫(A)), а упорядоченных пар |A × B| = |A|·|B|.

3Разобранный пример

Пройдите каждый шаг. Попробуйте предсказать следующий, прежде чем открыть его.

4Отношения

Отношение R на множестве X — это множество упорядоченных пар (x, y), где x и y лежат в X. На ориентированном графе каждая пара — стрелка, а (x, x) — петля.

• Рефлексивность: (x, x) ∈ R для каждого x: петля при каждой вершине.
• Симметричность: вместе с (x, y) ∈ R всегда есть (y, x) ∈ R.
• Антисимметричность: (x, y) и (y, x) одновременно лежат в R только при x = y.
• Транзитивность: из (x, y) и (y, z) в R следует (x, z) ∈ R.

Отношение, рефлексивное, симметричное и транзитивное, называется отношением эквивалентности. Оно разбивает X на непересекающиеся классы, например на остатки 0, 1 и 2 для «x ≡ y (mod 3)». Класс из s элементов даёт s² упорядоченных пар.

Чтобы опровергнуть свойство, достаточно одного контрпримера; чтобы доказать его, нужно проверить каждую пару.

5Функции

Функция f: A → B ставит каждому элементу A в соответствие ровно один образ в B.

• Инъективная (взаимно однозначная в одну сторону): разные элементы имеют разные образы; ни в один элемент B не приходят две стрелки.
• Сюръективная (на): в каждый элемент B приходит хотя бы одна стрелка.
• Биективная: и то и другое. Только тогда у f есть обратная функция f⁻¹.

Функция на рисунке инъективна, но не сюръективна: в d не приходит ни одной стрелки. Для инъекции нужно |A| ≤ |B|, для сюръекции |A| ≥ |B|.

При |A| = m и |B| = n существует nᵐ функций и n!/(n − m)! инъективных. Композиция (g ∘ f)(x) = g(f(x)) сначала применяет f.

6Типичные ошибки

• Складывать |A| + |B|, не вычитая пересечение.
• Забывать прибавить обратно центр в формуле включений и исключений для трёх множеств.
• Писать mⁿ вместо nᵐ для числа функций из m элементов в n.
• Думать, что отношение не может быть одновременно симметричным и антисимметричным: отношение {(1, 1)} обладает обоими свойствами.
• Применять g ∘ f в неверном порядке: сначала действует f.

7Как выглядят экзаменационные задачи

• Лёгкий: диаграммы Венна и подмножества. Вы подсчитываете выражение для множеств по диаграмме Венна, выбираете область выражения или находите размер булеана, декартова произведения или семейства подмножеств.
• Средний: формула включений и исключений и отношения. Вы решаете задачи на подсчёт для двух и трёх множеств, подсчитываете выражения по суммам областей, определяете, каким свойством обладает отношение, или считаете пары, нужные для замыкания.
• Сложный: функции и подсчёт. Вы классифицируете функцию как инъективную, сюръективную или биективную, считаете функции, инъекции и сюръекции, вычисляете композиции и обратные функции и считаете пары в отношениях эквивалентности.