Множество всех подмножеств
Множество всех подмножеств (булеан, показательное множество) — множество, состоящее из всех подмножеств данного множества (включая пустое множество и само множество ); обозначается или (так как оно соответствует множеству отображений из в ).
Если два множества
В категории множеств можно снабдить функцию структурой
- ковариантный функтор отображает функцию в функцию такую, что она отображает в образ относительно ;
- контравариантный функтор отображает функцию в такую, что она отображает в полный прообразотносительно .
Мощность конечного множества подмножеств
Справедливо следующее утверждение: число подмножеств конечного множества, состоящего из элементов, равно . Результат доказывается методом математической индукции. База индукции: у пустого множества () только одно подмножество — оно само, и . Шаг индукции: пусть утверждение установлено для множеств мощности . Рассмотрим произвольное множество с
- , элементы которого содержат ,
- , элементы которого не содержат , то есть являются подмножествами множества .
Подмножеств второго типа по предположению индукции , однако подмножеств первого типа ровно столько же. С одной стороны, из каждого подмножества второго типа можно получить подмножество первого типа добавлением элемента . С другой стороны, из каждого подмножества первого типа можно получить подмножество второго типа удалением элемента . Следовательно,
- и .
По индукционному предположению и , то есть:
- .
См. также
- Аксиома множества подмножеств
- Теорема Кантора
- Континуум-гипотеза
Примечания
Литература
- Брудно А. Л. Теория функций действительного переменного. — М.: Наука, 1971. — 119 с.
Для улучшения этой статьи желательно:
|