Студопедия.Орг Главная | Случайная страница | Контакты | Мы поможем в написании вашей работы!  
 

Нахождение числа всех подмножеств данного множества



Если задано некоторое множество А, то можно рассматривать новое множество М (А) – множество всех его подмножеств.

Пример 1. Сколько подмножеств имеет множество А = {é}?

По свойствам отношения включения, имеем Æ А и А .

Таким образом, одноэлементное множество А = {é} имеет 2 подмножества.

Пример 2. Сколько всего подмножеств имеет двухэлементное множество А = , в}?

По свойствам отношения включения, имеем Æ А и А .

Одноэлементные подмножества: {а}, {в}.

Таким образом, двухэлементное множество А = , в} всего имеет 4 подмножества.

Пример 3. Сколько всего подмножеств имеет трехэлементное множество А = {, ○, ◊}?

По свойствам отношения включения, имеем Æ А и А .

Одноэлементные подмножества: {}, {○}, {◊}.

Двухэлементные подмножества: {, ○}, {, ◊}, {○, ◊}.

Таким образом, трехэлементное множество А = {, ○, ◊} всего имеет 8 подмножеств.

Пример 4. Сколько всего подмножеств имеет четырехэлементное множество А = , в, с, d}?

По свойствам отношения включения, имеем Æ А и А .

Одноэлементные подмножества: {а}, {в}, {с}, {d}. Двухэлементные подмножества: {а, в}, {а, с}, {a, d}, {в, с}, {в, d}, {с, d}. Трехэлементные подмножества: {а, в, с}, {a, в, d}, {а, с, d}, {в, с, d}.

Таким образом, четырехэлементное множество всего имеет 16 подмножеств.

Нетрудно заметить, что с увеличением количества элементов множества А, число всех его подмножеств значительно увеличивается. Возникает вопрос: сколько подмножеств имеет множество из n – элементов?

Ответ на поставленный вопрос дает следующее утверждение.

Теорема 5. Конечное множество, содержащее n элементов, имеет 2 п подмножеств, то есть если Ап = {а1, а2,..., aп }, то п(М(Ап))=2п.

 Доказательствопроведем, используя метод математической индукции.

1) Путь п = 1, то есть А1 = { а1}. Значит, М(А1)= {Æ, { а1}}.

В этом случае п(М(А1)) = 21 = 2 что и доказывает справедливость теоремы при п = 1.

2) Пусть п = к, то есть Aк = { а1, а2,..., aк }.

Предположим, что п(М(Aк)) = 2 , то есть множество Aк имеет 2 подмножеств.

3) Докажем, что тогда множество Aк+ 1, имеет 2 подмножеств. В самом деле, если к элементам множества Aк, содержащего к элементов, добавить еще один элемент aк+1, то к имеющимся 2 подмножествам добавятся еще 2 новых подмножества, и, следовательно, множество Aк+ 1, содержащее к + 1 элементов, будет иметь 2 + 2 = 2× 2 = 2 подмножеств.

Таким образом, п(М(Aк+ 1 )) = 2 .

На основании метода математической индукции можно сделать вывод, что Теорема. 5 справедлива для любого натурального числа п. Теорема доказана.





Дата публикования: 2015-01-23; Прочитано: 1599 | Нарушение авторского права страницы | Мы поможем в написании вашей работы!



studopedia.org - Студопедия.Орг - 2014-2024 год. Студопедия не является автором материалов, которые размещены. Но предоставляет возможность бесплатного использования (0.007 с)...