- Множество подмножеств
-
Пусть A — множество. Множество всех подмножеств множества A называется булеаном A (также степенью множества, показательным множеством или множеством частей) и обозначается или 2A. Ясно, что и .
Справедливо следующее утверждение:
Число подмножеств конечного множества, состоящего из n элементов равно 2n.
Доказательство проведем методом математической индукции.База. Если n = 0, т. е. множество пусто, то у него только одно подмножество — оно само, и интересующее нас число равно 20 = 1.
Индукционный шаг. Пусть утверждение справедливо для некоторого n и пусть M — множество с кардинальным числом n + 1. Зафиксировав некоторый элемент , разделим подмножества множества M на два типа:
- содержащие a0,
- не содержащие a0, то есть являющиеся подмножествами множества .
Подмножеств типа (2) по предположению индукции 2n. Но подмножеств типа (1) ровно столько же, так как подмножество типа (1) получается из некоторого и притом единственного подмножества типа (2) добавлением элемента a0 и, следовательно, из каждого подмножества типа (2) получается этим способом одно и только одно подмножество типа (1).
Поэтому число всех подмножеств множества M равно 2n + 2n = 2n + 1.
См. также
Wikimedia Foundation. 2010.