Булеан

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


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

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

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

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

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

  1. содержащие a0,
  2. не содержащие a0, то есть являющиеся подмножествами множества M-\left\{a_0\right\}.

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

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

 
Начальная страница  » 
А Б В Г Д Е Ж З И Й К Л М Н О П Р С Т У Ф Х Ц Ч Ш Щ Ы Э Ю Я
A B C D E F G H I J K L M N O P Q R S T U V W X Y Z
0 1 2 3 4 5 6 7 8 9 Home