Меню Главная Случайная статья Настройки Множество всех подмножеств Материал из https://ru.wikipedia.org Множество всех подмножеств (показательное множество, булеан множества — по имени Джорджа Буля (1815 - 1864), англ. математика и логика) — множество, состоящее из всех подмножеств данного множества ${\displaystyle A}$ (включая пустое множество и само множество ${\displaystyle A}$); обозначается как ${\displaystyle {\mathcal {P}}(A)}$, или ${\displaystyle {\mathfrak {B}}\left(A\right)}$, или ${\displaystyle 2^{A}}$ (так как оно соответствует множеству отображений из ${\displaystyle A}$ в ${\displaystyle \{0,1\}}$). Если два множества равномощны, то равномощны и соответствующие множества всех подмножеств. Обратное утверждение (то есть инъективность операции ${\displaystyle \kappa \mapsto 2^{\kappa }}$ для кардиналов) является независимым от ZFC. В категории множеств можно снабдить функцию ${\displaystyle {\mathcal {P}}}$ структурой ковариантного или контравариантного функтора следующим образом: ковариантный функтор отображает функцию ${\displaystyle f\colon A\to B}$ в функцию ${\displaystyle {\mathcal {P}}f\colon {\mathcal {P}}A\to {\mathcal {P}}B}$ такую, что она отображает ${\displaystyle X}$ в образ ${\displaystyle X}$ относительно ${\displaystyle f\ }$; контравариантный функтор отображает функцию ${\displaystyle f\colon A\to B}$ в ${\displaystyle {\mathcal {P}}f\colon {\mathcal {P}}B\to {\mathcal {P}}A}$ такую, что она отображает ${\displaystyle X}$ в полный прообраз ${\displaystyle X}$ относительно ${\displaystyle f\ }$. Содержание 1 Мощность конечного множества подмножеств 2 См. также 3 Примечания 4 Литература Мощность конечного множества подмножеств Справедливо следующее утверждение: число подмножеств конечного множества, состоящего из ${\displaystyle n}$ элементов, равно ${\displaystyle 2^{n}}$. Результат доказывается методом математической индукции. База индукции: у пустого множества ${\displaystyle \varnothing }$ (${\displaystyle n=0}$) только одно подмножество — оно само, и ${\displaystyle 2^{0}=1}$. Шаг индукции: пусть утверждение установлено для множеств мощности ${\displaystyle n}$. Рассмотрим произвольное множество ${\displaystyle M}$ с кардинальным числом ${\displaystyle n+1}$. Если зафиксировать некоторый элемент ${\displaystyle a_{0}\in M}$, подмножества множества ${\displaystyle M}$ разделяются на два семейства: ${\displaystyle M_{1}}$, элементы которого содержат ${\displaystyle a_{0}}$, ${\displaystyle M_{2}}$, элементы которого не содержат ${\displaystyle a_{0}}$, то есть являются подмножествами множества ${\displaystyle M\setminus \{a_{0}\}}$. Подмножеств второго типа по предположению индукции ${\displaystyle 2^{n}}$, однако подмножеств первого типа ровно столько же. С одной стороны, из каждого подмножества второго типа можно получить подмножество первого типа добавлением элемента ${\displaystyle a_{0}}$. С другой стороны, из каждого подмножества первого типа можно получить подмножество второго типа удалением элемента ${\displaystyle a_{0}}$. Следовательно, ${\displaystyle 2^{M}=M_{1}\bigcup M_{2}}$ и ${\displaystyle M_{1}\bigcap M_{2}=\varnothing }$. По индукционному предположению ${\displaystyle \left|M_{1}\right|=2^{n}}$ и ${\displaystyle \left|M_{2}\right|=2^{n}}$, то есть: ${\displaystyle \left|2^{M}\right|=\left|M_{1}\right|+\left|M_{2}\right|=2^{n}+2^{n}=2^{n+1}=2^{\left|M\right|}}$. См. также Аксиома множества подмножеств Теорема Кантора Континуум-гипотеза Примечания Литература Брудно А. Л. Теория функций действительного переменного. — М.: Наука, 1971. — 119 с.