Множества: язык, на котором говорит вся математика

Знакомимся с базовым понятием всей дискретной математики — множеством — и сразу проверяем идеи кодом на Python.

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

Зачем программисту множества

Открой любой язык программирования — и ты почти сразу встретишь множества. В Python это тип set, в Java — HashSet, в SQL результат запроса SELECT DISTINCT — это, по сути, множество. Когда ты убираешь дубликаты из списка, проверяешь «есть ли пользователь в группе доступа», находишь общих друзей двух людей в соцсети — ты работаешь с множествами и их операциями.

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

Интуиция: множество — это «мешок без повторов и без порядка»

Представь мешок, в который ты кладёшь предметы. У этого мешка два важных свойства:

• Нет повторов. Элемент либо в множестве есть, либо нет. Сказать «яблоко лежит в мешке дважды» бессмысленно — оно либо есть, либо нет. Поэтому {1, 2, 2, 3} — это то же самое, что {1, 2, 3}.
• Нет порядка. Множество {1, 2, 3} и {3, 1, 2} — одно и то же множество. Порядок появится позже, когда мы будем говорить о кортежах и последовательностях.

Основное отношение, связанное с множеством, — принадлежность. Запись x ∈ A читается «x принадлежит A» (x — элемент A). Запись x ∉ A — «x не принадлежит A». Это главный вопрос, который мы задаём множеству: «а это здесь есть?».

Как задают множества

Есть два основных способа.

1. Перечислением. Просто выписываем все элементы в фигурных скобках: A = {2, 3, 5, 7} — множество однозначных простых чисел. Удобно, когда элементов немного.

2. Описанием свойства (характеристическим предикатом). Записываем условие, которому должны удовлетворять элементы: B = { x | x — чётное число от 1 до 10 }. Читается «множество всех x таких, что x — чётное от 1 до 10». Вертикальная черта | читается как «такой, что». Так задают даже бесконечные множества: { n | n — натуральное }.

Особый житель — пустое множество ∅ (или {}): множество без единого элемента. Оно ровно одно, и оно понадобится постоянно — как ноль в арифметике.

Числовые множества, которые надо знать в лицо

Подмножества: «часть» множества

Множество A называется подмножеством множества B (запись A ⊆ B), если каждый элемент A является также элементом B. Например, {1, 2} ⊆ {1, 2, 3}, а множество чётных чисел — подмножество целых.

Два важных факта, которые поначалу удивляют:

• Пустое множество — подмножество любого множества: ∅ ⊆ A всегда. Почему? Чтобы ∅ ⊆ A было ложным, нужен элемент пустого множества, которого нет в A. Но в пустом множестве вообще нет элементов — значит, нарушить условие нечем, и оно выполняется «по умолчанию» (вакуумно истинно).
• Любое множество — подмножество самого себя: A ⊆ A.

Если A ⊆ B, но A ≠ B (B содержит что-то ещё), говорят, что A — строгое подмножество, и пишут A ⊂ B. А равенство множеств определяют так: A = B тогда и только тогда, когда A ⊆ B и B ⊆ A одновременно. Этот приём «доказать включение в обе стороны» — рабочая лошадка всех доказательств про множества.

Проверяем всё на Python

В Python множество — это set. Дубликаты исчезают сами, порядок не гарантирован, а принадлежность проверяется оператором in. Посмотрим вживую.

A = {2, 3, 5, 7}
print("Множество A:", A)

# Дубликаты исчезают автоматически
B = {1, 2, 2, 3, 3, 3}
print("Множество B:", B)

# Принадлежность
print("5 принадлежит A?", 5 in A)
print("4 принадлежит A?", 4 in A)

# Подмножество
print("{2, 3} подмножество A?", {2, 3}.issubset(A))

# Пустое множество (внимание: {} это словарь, пустое множество — set())
empty = set()
print("Пустое множество:", empty, "| его длина:", len(empty))
print("Пустое — подмножество A?", empty.issubset(A))

Вывод:

Множество A: {2, 3, 5, 7}
Множество B: {1, 2, 3}
5 принадлежит A? True
4 принадлежит A? False
{2, 3} подмножество A? True
Пустое множество: set() | его длина: 0
Пустое — подмножество A? True

Обрати внимание на ловушку из последней строчки кода: в Python {} — это пустой словарь, а пустое множество создаётся только через set(). Это типичная ошибка новичков.

Проверяем определение подмножества перебором

Определение «A ⊆ B, если каждый элемент A лежит в B» — это буквально квантор всеобщности, и его легко превратить в код. Проверка all(x in B for x in A) — дословный перевод определения. Заодно увидим, почему пустое множество — подмножество чего угодно.

def is_subset(A, B):
    # A ⊆ B  <=>  каждый элемент A принадлежит B
    return all(x in B for x in A)

A = {1, 2}
B = {1, 2, 3, 4}
print("A ⊆ B:", is_subset(A, B), "| встроенная проверка:", A.issubset(B))

# Почему пустое множество — подмножество любого:
# проверять нечего, поэтому all(...) по пустому набору даёт True
print("∅ ⊆ B:", is_subset(set(), B))
print("B ⊆ A:", is_subset(B, A), "(в B есть 3, которой нет в A)")

Вывод:

A ⊆ B: True | встроенная проверка: True
∅ ⊆ B: True
B ⊆ A: False (в B есть 3, которой нет в A)

Обрати внимание на строку ∅ ⊆ B: True: функция all по пустому набору возвращает True, потому что «нарушить нечего». Это и есть та самая «вакуумная истинность», из-за которой пустое множество оказывается подмножеством любого. Код наглядно показывает логику, которую на словах принять труднее.

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

• Путать ∈ и ⊆. 2 ∈ {2, 3} — верно (2 это элемент). {2} ⊆ {2, 3} — верно (множество {2} это подмножество). А вот 2 ⊆ {2, 3} — бессмыслица: число не множество.
• Думать, что порядок важен. {1, 2, 3} = {3, 2, 1}. Если порядок нужен — это уже кортеж, а не множество.
• Забывать, что ∅ ⊆ A. Многие на автомате пишут, что у пустого множества «нет подмножеств». На самом деле у него есть ровно одно подмножество — оно само.

Итог

• Множество — совокупность различимых элементов; повторов и порядка нет.
• Главный вопрос к множеству — принадлежность x ∈ A.
• Задают перечислением {...} или описанием свойства { x | условие }.
• A ⊆ B — каждый элемент A лежит в B; ∅ ⊆ A и A ⊆ A всегда.
• Равенство множеств доказывают включением в обе стороны.