Если для конечного множества А, , то число всех подмножеств А равно
, то есть
.
Доказательство:
Занумеруем элементы А по номерам от 1 до n.
и рассмотрим множество двоичных векторов из нулей единиц длины n. Каждому подмножеству
поставим в соответствие вектор
следующим образом:
Например, ,
,
,
.
Здесь и далее знаком “ ” обозначено “соответствует”.
Например, , то подмножеству
соответствует вектор (1, 1, 1, 1, 0), а
.
Поэтому, подмножеству соответствует вектор из нулей, а самому А - из единиц. Очевидно, что установленное соответствие между множеством всех подмножеств множества А и двоичными векторами длины n является взаимно однозначным, и число подмножеств А равно
.
А так как является прямым произведением n двухэлементных множеств {0,1} (т. е.
), то, в силу следствия из теоремы о мощности прямого произведения множеств, имеем:
так как
, то есть
.
Определение: Множества равномощны, если между их элементами можно установить взаимно однозначное соответствие.
Для конечных множеств это утверждение доказывается. Для бесконечных множеств оно является определением равномощности.
|
|
Определение: Счетные множества это множества равномощные N (т. е. между ними и N можно установить взаимно однозначное соответствие).