Алгебра. Ткач Л.И. - 13 стр.

UptoLike

ВУЗ: 

ТГТУ | Тамбов

Составители: 

Рубрика: 

2. КОНЕЧНЫЕ МНОЖЕСТВА
2.1. КОНЕЧНОЕ МНОЖЕСТВО И ЕГО ПОДМНОЖЕСТВА
Рассмотрим более подробно конечные множества. Конечные множества выделяются из всех множеств тем, что их мож-
но задать, предъявив явно их элементы. Таким образом, самая простая характеристика конечного множества – это его эле-
менты и их количество. Следующая характеристика конечного множества, по-видимому, это все его подмножества или все
его подмножества определенного типа. Рассмотрим такой вопрос: сколько всего подмножеств у конечного множества, со-
держащего n элементов? Решим сначала задачу.
Задача. Пусть X – конечное множество, a – элемент множества X. Каких подмножеств множества X больше, содержа-
щих элемент a или не содержащих элемент a?
Решение. Каждый раз, когда мы указываем подмножество A множества X, содержащее элемент a, то мы указываем и
подмножество X \ A множества X, не содержащее элемент a, и наоборот. Если мы указываем подмножество множества X, не
содержащее элемент a, то мы указываем и подмножество множества X, содержащее элемент a. Поэтому подмножеств мно-
жества X, содержащих элемент a столько же, сколько и подмножеств множества X, не содержащих элемент a.
Ответ. Поровну.
Теорема 2.1.1. Число подмножеств конечного множества, состоящего из n элементов, равно
n
2 .
Доказательство. Множество, состоящее из одного элемента a, имеет два (т.е.
1
2 ) подмножества: ∅ и
{
}
a . Множество,
состоящее из двух элементов a и b, имеет четыре (т.е.
2
2 ) подмножества: ∅, {a}, {b}, {b; a}.
Множество, состоящее из трех элементов a, b, c имеет восемь (т.е.
3
2
) подмножеств: ∅, {a}, {b}, {b; a}, {c}, {c; a},{c; b},
{c; b; a}.
Ясно, что добавление нового элемента удваивает число подмножеств.
Завершим доказательство применением метода математической индукции. Сущность этого метода в том, что если ут-
верждение (свойство) справедливо для некоторого начального натурального числа n
0
и если из предположения, что оно
справедливо для произвольного
0
nkn ≥
=
, можно доказать его справедливость для числа k + 1, то это свойство справедливо
для всех натуральных чисел
0
nn ≥ .
1. Для n = 1 (и даже для n = 2, 3) теорема доказана.
2. Допустим, что теорема доказана для n = k, т.е. число подмножеств множества, состоящего из k элементов, равно
k
2 .
Докажем, что число подмножеств множества B, состоящего из n = k + 1 элемента, равно
1
2
+k
.
Выбираем некоторый элемент b множества B. Рассмотрим множество A = B\{b}. Оно содержит k элементов. Все под-
множества множества A – это подмножества множества B, не содержащие элемент b и, по предположению, их
k
2
штук.
Подмножеств множества B, содержащих элемент b, столько же, т.е.
k
2 штук (по предыдущей задаче). Следовательно, всех
подмножеств множества B:
k
2 +
k
2 = 2 ⋅
k
2 =
1
2
+k
штук. Теорема доказана.
На вопрос о том, сколько у конечного множества подмножеств того или иного типа отвечает раздел теории множеств –
комбинаторика.
2.2. КОМБИНАТОРИКА. ОСНОВНЫЕ ПРАВИЛА
Комбинаторика – это область математики, в которой изучаются вопросы о том, сколькими различными подмножества-
ми, подчиненными тем или иным условиям, обладает конечное множество. Причем, природа самих элементов, составляю-
щих конечное множество, как принято в теории множеств, не рассматривается. Комбинаторику можно рассматривать как
часть теории множеств – любую комбинаторную задачу можно выразить, используя понятие конечного множества.
Рассмотрим сначала два основных правила комбинаторики – правило суммы и правило произведения, которые являются
аксиомами комбинаторики.
Правило суммы. Если элемент a можно выбрать m способами, а элемент b – n способами, причем любой выбор эле-
мента a не совпадает с каким-нибудь способом выбора элемента b, то выбор «a или b» можно осуществить m + n способами.
Пример. На полке в книжном шкафу стоят книги, среди которых есть учебники: 5 книг по математике, 4 книги по фи-
зике, 6 книг по химии, остальные книги – детективы. Сколькими способами можно выбрать учебник в книжном шкафу?
Книгу по математике можно выбрать 5 способами, книгу по физике – 4 способами, книгу по химии – 6 способами. Выборы
учебников не влияют друг на друга. Значит, по правилу суммы учебник можно выбрать 5 + 4 + 6 = 15 способами.
Правило произведения. Если элемент a можно выбрать m способами и после каждого из этих выборов элемент b мо-
жет быть выбран n способами, то выбор «a и b» может быть осуществлен m ⋅ n способами.
Пример. Сколько трехзначных чисел можно составить из цифр 2, 4, 5, если цифры в числе не повторяются?
На месте сотен поставим любую из трех цифр (т.е. получаем три способа для выбора первой цифры). После каждого та-
кого выбора на месте десятков можно поставить любую из двух оставшихся цифр (т.е. два способа), так как цифры в числе
не повторяются. Наконец, на месте единиц можно поставить оставшуюся одну цифру (т.е. один способ). Применяя правило
произведения два раза, получим: 3 ⋅ 2 ⋅ 1 = 6 трехзначных числа.
Графической иллюстрацией правила произведения является специальная схема, условно называемая «дерево». Для пре-
дыдущего примера соответствующая схема будет выглядеть так:

Страницы