Математика · объяснение и практика

Почему множество всех подмножеств имеет два в степени n элементов

Почему все подмножества образуют новый набор из двух в степени n элементов, как кодировать выбор битами и что происходит при пустом исходном множестве.

Синяя и оранжевая половины складываются в целый круг.

В теме Множества, отношения и математическая логика · Учебная карта

В маршруте Множества, отношения и мощности · 10 тем

Главная мысль

Для каждого из n различных элементов независимо решают, включать его в подмножество или нет. Получается 2ⁿ подмножеств, включая пустое и полное; их совокупность называется булеаном.

Считать решения о включении

Пусть A={книга, карта, фонарь}. Подмножество описывает, какие предметы взяли, без порядка упаковки. Для книги есть два решения, для карты ещё два, для фонаря ещё два. Каждая тройка решений задаёт ровно один набор. Поэтому получается восемь подмножеств, а не шесть перестановок всех предметов.

Закодируем включение единицей, отсутствие нулём. Тогда 101 означает книгу и фонарь при заранее фиксированном порядке названий. Такой код не добавляет порядок самому подмножеству: порядок нужен только для чтения позиций записи. Если сменить соглашение о позициях, поменяется кодировка, но не количество допустимых наборов.

Пустой вариант тоже один вариант

Все нули соответствуют пустому множеству, все единицы — всему A. Оба входят в множество всех подмножеств, обозначаемое P(A). Для пустого A есть ровно одно подмножество — ∅, поэтому P(∅)={∅}. Здесь размер равен одному и согласуется с 2⁰=1. Отсутствие предметов не означает отсутствие способа выбрать ничего.

Можно сгруппировать подмножества по размеру. Для трёх элементов получаем одно пустое, три одноэлементных, три двухэлементных и одно полное. Сумма 1+3+3+1=8 совпадает с двоичным подсчётом. При запрете пустого варианта вычитают один, а при запрете и пустого, и полного для непустого A вычитают два.

Пример

У набора из пяти разных карточек разрешены любые поднаборы, кроме пустого и полного. Сколько вариантов?

Всего 2⁵=32 подмножества. Пустое и полное различны, поскольку исходный набор непустой. Исключаем два варианта и получаем 30.

Почему важно различать элементы

Формула относится к множеству из различных элементов. Если в записи повторён один и тот же объект, повтор не увеличивает размер множества. Для физически разных одинаково подписанных карточек нужно решить, различаются ли они в задаче. Если различаются, дают им отдельные метки; если учитывают только количество каждого вида, двоичная модель меняется.

Операция P строит новый уровень объектов: его элементами становятся подмножества, а не исходные предметы. Поэтому |P(P(A))|=2^(2ⁿ), а не 4ⁿ в общем случае. Повторный выбор теперь принимает решение о включении каждого прежнего набора. Быстрый рост отражает смену уровня, а не повторение прежнего выбора дважды.

От чтения к действию

А теперь — вы

Множество A содержит два элемента. Сколько элементов у P(P(A))?

Частые вопросы

Сколько собственных подмножеств у непустого конечного A?

Если собственное означает любое подмножество, не равное A, их 2ⁿ−1; пустое остаётся разрешённым.

Почему перестановка предметов не создаёт новое подмножество?

Множество хранит принадлежность, а не порядок перечисления. Один состав, записанный разными способами, остаётся одним подмножеством.

Источники и работа с материалом

Объяснение, примеры и вопросы написаны для erudeet. Факты и определения сверены по источникам ниже; это ссылки для самостоятельной проверки.

Продолжить разбираться