Булеан

Булеан
Досліджується в	theory of power setsd і теорія множин
Формула	${\mathcal {P}}(S)=\{T\mid T\subseteq S\}$
Підтримується Вікіпроєктом	Вікіпедія:Проєкт:Математика
Булеан у Вікісховищі

Елементи булеана множини {x,y,z}, зображені в порядку включення елементів

Булеан (англ. power set, нім. potenzmenge) — у теорії множин, це множина всіх підмножин даної множини $A$, позначається ${\mathcal {P}}(A)$ або $2^{A}$ (оскільки вона відповідає множині відображень з $A$ в $2=\{0,1\}$).

Якщо дві множини мають однакову потужність, то їх булеани теж мають рівну потужність. Обернене твердження (тобто ін'єктивність операції $\kappa \mapsto 2^{\kappa }$ для кардиналів) є незалежним від ZFC.

У категорії множин можна спорядити функцію ${\mathcal {P}}$ структурою коваріантного або контраваріантного функтора в такий спосіб:

• коваріативний функтор відображає функцію $f\colon A\to B$ у функцію ${\mathcal {P}}f\colon {\mathcal {P}}A\to {\mathcal {P}}B$ таку, що вона відображає $X$ у образ $X$ відносно $f$;
• контраваріативний функтор відображує функцію $f\colon A\to B$ в ${\mathcal {P}}f\colon {\mathcal {P}}B\to {\mathcal {P}}A$ таку, що вона відображає $X$ у повний прообраз $X$ відносно $f$.

Приклад

Нехай $S\ {\mathcal {=}}\ \{x,y,z\}$. Тоді підмножинами $S$ є:

• $\varnothing$ (або $\emptyset$) — порожня множина
• $\{x\}$
• $\{y\}$
• $\{z\}$
• $\{x,y\}$
• $\{x,z\}$
• $\{y,z\}$
• $\{x,y,z\}$

Отже, булеаном множини $S$ є множина ${\mathcal {P}}(S)=$ $\{$$\varnothing$, $\{x\}$, $\{y\}$, $\{z\}$, $\{x,y\}$, $\{x,z\}$, $\{y,z\}$, $\{x,y,z\}$$\}$.

Властивості

Якщо $S$ — скінченна множина та $|S|=n$, то кількість підмножин $S$ дорівнює $|{\mathcal {P}}(S)|=2^{n}$. Цей аспект, який є передумовою до позначення $2^{S}$, можна подати так:

Спершу якось упорядкуємо елементи $S$. Ми записуємо кожну підмножину $S$ у вигляді $\{\omega _{1},\omega _{2},...,\omega _{n}\}$, де $\omega _{i},1\leq i\leq n$, може приймати значень 0 або 1. Якщо $\omega _{i}=1$, тоді  $i$-ий елемент множини $S$ належить підмножині; в іншому випадку, цей елемент відсутній. Очевидно, кількість різних підмножин, які можна отримати в такий спосіб, дорівнює $2^{n}$.

Діагональний метод Кантора показує, що булеан множини $S$ (скінченної або нескінченної) завжди має строго більшу потужність, ніж сама множина $S$. Зокрема, теорема Кантора свідчить, що булеан зліченної множини є незліченним. Наприклад, можна утворити бієктивне відображення між булеаном множини натуральних чисел та множиною дійсних чисел.

Булеан множини $S$, поряд з операціями об'єднання, перетину та доповнення, можна розглядати як приклад булевої алгебри. Можна показати, що будь-яка скінченна булева алгебра є ізоморфною до булевої алгебри булеана скінченної множини. Для нескінченних булевих алгебр ця умова не виконується, але будь-яку нескінченну булеву алгебру можна подати як підалгебру булеана булевої алгебри (див.: теорема Стоуна про представлення булевих алгебр).

Булеан множини $S$ формує абелеву групу за операцією симетричної різниці та комутативний моноїд за операцією перетину. Отже, можна показати (доводячи дистрибутивність), що булеан формує булеве кільце за цими операціями.

Подання підмножин як функцій

У теорії множин, $X^{Y}$ позначає множину всіх функцій із $Y$ в $X$. $2^{S}$ — множина всіх відображень із $S$ у $2=\{0,1\}$. Визначаючи функцію в $2^{S}$ з відповідним прообразом 1, ми бачимо, що відображення між $2^{S}$ та ${\mathcal {P}}(S)$ є бієктивним, де кожна функція є характеристичною функцією підмножини ${\mathcal {P}}(S)$, у якій вона визначена. Таким чином, $2^{S}$ та ${\mathcal {P}}(S)$ можна вважати теоретико-множинно ідентичними.

Це поняття можна застосувати до наведеного вище прикладу, де $S\ {\mathcal {=}}\ \{x,y,z\}$, щоб побачити ізоморфізм з двійковими числами від 0 до $2^{n}-1$, де $n$ — кількість елементів у множині. У $S$ «1» на позиції, яка відповідає позиції елемента у множині, позначає присутність цього елемента. Такими чином, $\{x,y\}=\{1,1,0\}$.

Для всієї множини отримуємо:

• $\varnothing =000_{2}=0_{10}$
• $\{x\}=100_{2}=4_{10}$
• $\{y\}=010_{2}=2_{10}$
• $\{z\}=001_{2}=1_{10}$
• $\{x,y\}=110_{2}=6_{10}$
• $\{x,z\}=101_{2}=5_{10}$
• $\{y,z\}=011_{2}=3_{10}$
• $\{x,y,z\}=111_{2}=7_{10}$

Алгоритми

Для скінченної множини $S$ існує рекурсивний алгоритм для знаходження ${\mathcal {P}}(S)$.

Визначимо операцію ${\mathcal {F}}(e,T)=\{X\cup \{e\}|X\in T\}$.

• Якщо $S=\varnothing$, тоді повернемо ${\mathcal {P}}(S)=\{\varnothing \}$.

• В іншому випадку:
  • Нехай $e$ — будь-який одиничний елемент з $S$.
  • Нехай $T=S\setminus \{e\}$, де $S\setminus \{e\}$ — відносне доповнення $\{e\}$ в $S$.
  • Повернемо ${\mathcal {P}}(S)={\mathcal {P}}(T)\cup {\mathcal {F}}(e,{\mathcal {P}}(T))$.

Зв'язок з біномом Ньютона

Булеан тісно пов'язаний з біномом Ньютона. Кількість підмножин потужності $k$ в булеані множини, потужність якої $n$, є кількістю комбінацій $C_{n}^{k}$, яку також називають біноміальним коефіцієнтом.

Наприклад, множина із трьох елементів містить:

• $C_{3}^{0}=1$ підмножину з 0 елементами (порожня множина);
• $C_{3}^{1}=3$ підмножини з 1 елементом (одиничні підмножини);
• $C_{3}^{2}=3$ підмножини з 2 елементами (усі можливі пари одиничних підмножин);
• $C_{3}^{3}=1$ підмножину з 3 елементами (уся початкова множина).

Підмножини обмеженої потужності

Множину підмножин $S$, потужність яких менша ніж $k$, позначають ${\mathcal {P}}_{k}(S)$ або ${\mathcal {P}}_{<k}(S)$. Таким чином, множину непорожніх підмножин $S$ можна позначити ${\mathcal {P}}_{\geq 1}(S)$.

Потужність скінченного булеана

Справедливе таке твердження: число підмножин скінченної множини, яка складається з $n$ елементів, дорівнює $2^{n}$. Результат доводиться методом математичної індукції. В разі порожньої множини $\varnothing$($n=0$) тільки одна підмножина — вона сама, і $2^{0}=1$. На кроці індукції твердження вважають встановленим для множин потужності $n$ та розглядається довільна множина $M$ з кардинальним числом $n+1$; зафіксувавши деякий елемент $a_{0}\in M$, підмножини множини $M$ розділяють на два сімейства:

1. $M_{1}$, що містить $a_{0}$,
2. $M_{2}$, що не містить $a_{0}$_, тобто є підмножинами множини $M\setminus \{a_{0}\}$.

Підмножин другого типу, за припущенням індукції, $2^{n}$, підмножин першого типу рівно стільки ж, оскільки підмножина такого типу отримується з деякої єдиної підмножини другого типу доданням елемента $a_{0}$ і, отже_:

$2^{M}=M_{1}\bigcup M_{2}$ та $M_{1}\bigcap M_{2}=\varnothing$.

За індукційним припущенням $\left|M_{1}\right|=2^{n}$ та $\left|M_{2}\right|=2^{n}$, тобто:

$\left|2^{M}\right|=\left|M_{1}\right|+\left|M_{2}\right|=2^{n}+2^{n}=2^{n+1}=2^{\left|M\right|}$

Див. також

• Аксіома булеана
• Теорема Кантора
• Континуум-гіпотеза
• Теорія множин
• Алгебра множин

Посилання

• Weisstein, Eric W., «Power Set» [Архівовано 29 квітня 2016 у Wayback Machine.], на сайті MathWorld.
• Булеан [Архівовано 13 квітня 2016 у Wayback Machine.] на сайті PlanetMath.org.
• Булеан [Архівовано 12 квітня 2016 у Wayback Machine.] на сайті nLab.
• Експоненціал [Архівовано 7 березня 2016 у Wayback Machine.] на сайті nLab.