Булеан

Материал из Википедии — свободной энциклопедии

Пусть A — множество. Множество всех подмножеств множества A называется булеаном A (также степенью множества, показательным множеством или множеством частей) и обозначается или 2^A. Ясно, что и .

Справедливо следующее утверждение:

Число подмножеств конечного множества, состоящего из n элементов равно 2n.

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

База. Если n = 0, т. е. множество пусто, то у него только одно подмножество — оно само, и интересующее нас число равно 2⁰ = 1.

Индукционный шаг. Пусть утверждение справедливо для некоторого n и пусть M — множество с кардинальным числом n + 1. Зафиксировав некоторый элемент , разделим подмножества множества M на два типа:

1. содержащие a₀,
2. не содержащие a₀, то есть являющиеся подмножествами множества .

Подмножеств типа (2) по предположению индукции 2ⁿ. Но подмножеств типа (1) ровно столько же, так как подмножество типа (1) получается из некоторого и притом единственного подмножества типа (2) добавлением элемента a₀ и, следовательно, из каждого подмножества типа (2) получается этим способом одно и только одно подмножество типа (1).

Поэтому число всех подмножеств множества M равно 2ⁿ + 2ⁿ = 2^{n + 1}.

[править] См. также

• Аксиома булеана