Номер 4, страница 420, часть 1 - гдз по алгебре 10 класс учебник Мордкович, Семенов

4. Сформулируйте теорему о числе подмножеств множества из $n$ элементов.

Формулировка теоремы

Конечное множество, состоящее из $n$ элементов, имеет ровно $2^n$ различных подмножеств (включая пустое множество и само исходное множество).

Множество всех подмножеств множества $A$ называется его булеаном (или множеством-степенью) и обозначается $P(A)$ или $2^A$. Таким образом, теорему можно записать в виде формулы: если мощность множества $|A|=n$, то мощность его булеана $|P(A)|=2^n$.

Доказательство

Теорему можно доказать несколькими способами. Приведем два наиболее наглядных.

1. Комбинаторный метод

Пусть дано множество $A = \{a_1, a_2, \dots, a_n\}$. Для построения любого его подмножества $S$ необходимо для каждого элемента из $A$ решить, включать его в $S$ или нет. Для элемента $a_1$ есть два возможных выбора: включить или не включить. Аналогично, для элемента $a_2$ есть два выбора, и так далее для всех $n$ элементов. Поскольку выборы для каждого элемента независимы, по правилу произведения в комбинаторике, общее число всех возможных комбинаций (то есть подмножеств) равно произведению числа выборов для каждого элемента:

$N = \underbrace{2 \times 2 \times \dots \times 2}_{n \text{ раз}} = 2^n$.

Каждому подмножеству можно однозначно сопоставить двоичную последовательность длины $n$, в которой на $i$-й позиции стоит 1, если элемент $a_i$ включен в подмножество, и 0, если не включен. Общее число таких уникальных последовательностей равно $2^n$.

2. Метод с использованием бинома Ньютона

Общее число подмножеств является суммой числа подмножеств всех возможных размеров от 0 (пустое множество) до $n$ (само исходное множество). Число подмножеств размера $k$, которые можно выбрать из множества с $n$ элементами, равно биномиальному коэффициенту $C_n^k = \binom{n}{k}$.

Следовательно, общее число подмножеств равно сумме: $\sum_{k=0}^{n} \binom{n}{k} = \binom{n}{0} + \binom{n}{1} + \binom{n}{2} + \dots + \binom{n}{n}$.

Согласно формуле бинома Ньютона, $(x+y)^n = \sum_{k=0}^{n} \binom{n}{k} x^{n-k} y^k$. Если подставить в эту формулу значения $x=1$ и $y=1$, мы получим:

$(1+1)^n = 2^n = \sum_{k=0}^{n} \binom{n}{k} 1^{n-k} 1^k = \sum_{k=0}^{n} \binom{n}{k}$.

Это равенство показывает, что сумма всех биномиальных коэффициентов для данного $n$, которая и представляет собой общее число подмножеств, равна $2^n$.

Пример

Рассмотрим множество $A = \{1, 2, 3\}$, где $n=3$. Согласно теореме, число подмножеств должно быть $2^3 = 8$.

Перечислим все подмножества, сгруппировав их по размеру:

• Размер 0 (0 элементов): $\emptyset$ (1 подмножество).

• Размер 1 (1 элемент): $\{1\}, \{2\}, \{3\}$ (3 подмножества).

• Размер 2 (2 элемента): $\{1, 2\}, \{1, 3\}, \{2, 3\}$ (3 подмножества).

• Размер 3 (3 элемента): $\{1, 2, 3\}$ (1 подмножество).

Суммарное количество подмножеств: $1 + 3 + 3 + 1 = 8$, что подтверждает вывод теоремы.

Ответ: Конечное множество, состоящее из $n$ элементов, имеет ровно $2^n$ различных подмножеств.