Булеан

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

Булеан (Шаблон:Lang-en, Шаблон:Lang-de) — у теорії множин, це множина всіх підмножин даної множини $A$, позначається $𝒫(A)$ або $2^A$ (оскільки вона відповідає множині відображень з $A$ в $2=\{0,1\}$).

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

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

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

Приклад

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

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

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

Властивості

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

Спершу якось упорядкуємо елементи $S$. Ми записуємо кожну підмножину $S$ у вигляді $\{{\omega }_1,{\omega }_2,...,{\omega }_n\}$, де ${\omega }_i,1\le i\le 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$ та $𝒫(S)$ є бієктивним, де кожна функція є характеристичною функцією підмножини $𝒫(S)$, у якій вона визначена. Таким чином, $2^S$ та $𝒫(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$ існує рекурсивний алгоритм для знаходження $𝒫(S)$.

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

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

• В іншому випадку:
  • Нехай $e$ — будь-який одиничний елемент з $S$.
  • Нехай $T=S\setminus \{e\}$, де $S\setminus \{e\}$ — відносне доповнення $\{e\}$ в $S$.
  • Повернемо $𝒫(S)=𝒫(T)\cup ℱ(e,𝒫(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$, позначають ${𝒫}_k(S)$ або ${𝒫}_{<k}(S)$. Таким чином, множину непорожніх підмножин $S$ можна позначити ${𝒫}_{\ge 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» Шаблон:Webarchive, на сайті MathWorld.
• Булеан Шаблон:Webarchive на сайті PlanetMath.org.
• Булеан Шаблон:Webarchive на сайті nLab.
• Експоненціал Шаблон:Webarchive на сайті nLab.