набор мощности из набора это коллекция всех подмножеств А. При работе с конечным устанавливать с N элементы, один вопрос, который мы могли бы задать: «Сколько элементов в наборе сил ?» Мы увидим, что ответ на этот вопрос 2N и математически доказать, почему это так.
Наблюдение за паттерном
Мы будем искать шаблон, наблюдая за количеством элементов в наборе мощности , где имеет N элементы:
- Если = {} (пустой набор), тогда не имеет элементов, но P (A) = {{}}, набор с одним элементом.
- Если = {а}, тогда имеет один элемент и P (A) = {{}, {a}}, множество с двумя элементами.
- Если = {a, b}, тогда имеет два элемента и P (A) = {{}, {a}, {b}, {a, b}}, набор из двух элементов.
Во всех этих ситуациях легко увидеть наборы с небольшим количеством элементов, которые, если есть конечное число N элементы в затем набор мощности п () имеет 2N элементы. Но эта модель продолжается? Просто потому, что образец верен для N = 0, 1 и 2 не обязательно означает, что шаблон верен для более высоких значений N.
Но эта модель продолжается. Чтобы показать, что это действительно так, мы будем использовать доказательство по индукции.
Доказательство по индукции
Доказательство по индукции полезно для доказательства утверждений, касающихся всех натуральных чисел. Мы достигаем этого в два этапа. Для первого шага мы привязываем наше доказательство, показывая истинное утверждение для первого значения N что мы хотим рассмотреть. Второй шаг нашего доказательства - предположить, что утверждение верно для N = Ки показать, что это подразумевает утверждение верно для N = К + 1.
Другое наблюдение
Чтобы помочь в нашем доказательстве, нам понадобится еще одно наблюдение. Из приведенных выше примеров видно, что P ({a}) является подмножеством P ({a, b}). Подмножества {a} образуют ровно половину подмножеств {a, b}. Мы можем получить все подмножества {a, b}, добавив элемент b к каждому из подмножеств {a}. Это добавление множества выполняется с помощью операции множества объединения:
- Пустое множество U {b} = {b}
- {a} U {b} = {a, b}
Это два новых элемента в P ({a, b}), которые не были элементами P ({a}).
Мы видим аналогичное явление для P ({a, b, c}). Мы начнем с четырех наборов P ({a, b}), и к каждому из них добавим элемент c:
- Пустое множество U {c} = {c}
- {a} U {c} = {a, c}
- {b} U {c} = {b, c}
- {a, b} U {c} = {a, b, c}
И в итоге мы получаем восемь элементов в P ({a, b, c}).
Доказательство
Теперь мы готовы доказать утверждение: «Если множество содержит N элементы, то набор мощности P (A) имеет 2N элементы «.
Начнем с того, что отметим, что доказательство по индукции уже закреплено для случаев N = 0, 1, 2 и 3. По индукции мы предполагаем, что утверждение верно для К. Теперь пусть набор содержать N +1 элемент. Мы можем написать = В U {x}, и рассмотрим, как формировать подмножества .
Мы берем все элементы Р (В)и по индуктивной гипотезе, есть 2N из этих. Затем мы добавляем элемент x к каждому из этих подмножеств В, в результате чего еще 2N подмножества В. Это исчерпывает список подмножеств Ви так всего 2N + 2N = 2(2N) = 2N + 1 элементы силового набора .