Язык математики

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

∈, ⊂, ∪, ∩, разность и дополнение — язык, на котором записано всё остальное

Шаг 2 из 117 · ~25 мин

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

Программисту проще всего думать о множестве как о set из стандартной библиотеки. Аналогия хорошая и почти нигде не подводит.

Принадлежность и включение

Два разных отношения, которые постоянно путают.

Принадлежность x∈Ax \in A — «объект xx является элементом AA». Слева стоит элемент, справа множество.

Включение A⊆BA \subseteq B — «каждый элемент AA является элементом BB». Слева и справа стоят множества.

Разница видна на примере. Пусть A={1,2}A = \{1, 2\}. Тогда:

  • 1∈A1 \in A — верно, 11 лежит в AA
  • {1}⊆A\{1\} \subseteq A — верно, множество из одной единицы вкладывается в AA
  • {1}∈A\{1\} \in A — ложно: элементы AA — это числа, а не множества

В коде это разница между x in s и s1.issubset(s2).

Обозначение ⊂\subset у разных авторов означает то ⊆\subseteq (включение, возможно совпадающее), то строгое включение ⊊\subsetneq. Если различие важно, хорошие авторы пишут ⊆\subseteq и ⊊\subsetneq явно. Если видите голое ⊂\subset — почти всегда имеется в виду ⊆\subseteq.

Способы задать множество

Перечислением: {2,3,5,7}\{2, 3, 5, 7\}.

Через условие — это называется аксиома выделения, а выглядит как list comprehension:

{x∈N:x простое и x<10}\{x \in \N : x \text{ простое и } x < 10\}

Двоеточие (или вертикальная черта ∣\mid) читается «такое, что». Слева — откуда берём кандидатов, справа — какому условию они должны удовлетворять. Один в один [x for x in naturals if is_prime(x) and x < 10].

Пустое множество обозначается ∅\emptyset или {}\{\}. Оно единственно и является подмножеством любого множества — включая само себя.

Операции

AB

A ∪ B — объединение: всё, что лежит хотя бы в одном из множеств.

Здесь это: {1, 2, 3, 4, 5, 6, 8}

Все операции над множествами — это ровно те же операции, что над булевыми условиями:

МножестваУсловие на xxЛогика
A∪BA \cup Bx∈Ax \in A или x∈Bx \in Bor
A∩BA \cap Bx∈Ax \in A и x∈Bx \in Band
A∖BA \setminus Bx∈Ax \in A и x∉Bx \notin Band not
Aˉ\bar{A}x∉Ax \notin Anot

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

A∪B‾=Aˉ∩Bˉ,A∩B‾=Aˉ∪Bˉ\overline{A \cup B} = \bar{A} \cap \bar{B}, \qquad \overline{A \cap B} = \bar{A} \cup \bar{B}

Про дополнение

Запись Aˉ\bar{A} (или AcA^c) имеет смысл только когда задан универсум UU — множество, внутри которого мы работаем. Дополнение — это U∖AU \setminus A. Без явного или подразумеваемого UU запись бессмысленна: «всё, что не в AA» — это не множество, а источник парадоксов.

В вероятности универсум — это пространство элементарных исходов Ω\Omega, и Aˉ\bar{A} означает «событие AA не произошло». В блоке 3 это пригодится сразу.

Мощность

∣A∣|A| — число элементов. Для конечных множеств это len(s). Для бесконечных всё интереснее, и к этому мы вернёмся в уроке про счётность.

Полезное тождество, которое стоит запомнить, — формула включения-исключения для двух множеств:

∣A∪B∣=∣A∣+∣B∣−∣A∩B∣|A \cup B| = |A| + |B| - |A \cap B|

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

Чего здесь намеренно нет

Аксиоматики ZFC, парадокса Рассела, ординалов и кардинальной арифметики. Для чтения статей по ML нужен словарь, а не теория множеств как дисциплина.

Источники

Проверки

0 из 2
  1. Принадлежность против включения

    Пусть A={1,  2,  {3}}A = \{1,\; 2,\; \{3\}\}. Отметьте все верные утверждения.

  2. Операции над множествами

    Реализуйте функцию set_ops(a, b), которая принимает два списка чисел и возвращает список из четырёх отсортированных списков:

    1. A∪BA \cup B
    2. A∩BA \cap B
    3. A∖BA \setminus B
    4. A△BA \triangle B (симметрическая разность)

    Входные списки могут содержать дубликаты — множество их не различает.

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

    функция set_ops

    Загрузка редактора…

    Ctrl/⌘ + Enter