Перегляд вихідного коду сторінки Булеан

{{unibox}}[[Файл:Hasse diagram of powerset of 3.svg|thumb|Елементи булеана множини {x,y,z}, зображені в порядку включення елементів]]
'''Булеан''' ({{lang-en|power set}}, {{lang-de|potenzmenge}})&nbsp;— у [[теорія множин|теорії множин]], це [[множина]] всіх [[підмножина|підмножин]] даної множини <math>A</math>, позначається <math>\mathcal{P}(A)</math> або <math>2^A</math> (оскільки вона відповідає множині відображень з <math>A</math> в <math>2 = \{ 0,1\}</math>).

Якщо дві множини мають однакову [[Потужність множини|потужність]], то їх булеани теж мають рівну потужність. Обернене твердження (тобто [[Ін'єкція (математика)|ін'єктивність]] операції <math>\kappa \mapsto 2^\kappa</math> для [[Потужність множини|кардиналів]]) є незалежним від [[Аксіоматика теорії множин|ZFC]].

У [[Категорія множин|категорії множин]] можна спорядити функцію <math>\mathcal{P}</math> структурою коваріантного або контраваріантного [[функтор]]а в такий спосіб:
* коваріативний функтор відображає функцію <math>f\colon A\to B</math> у функцію <math>\mathcal{P}f\colon \mathcal{P}A \to \mathcal{P}B</math> таку, що вона відображає <math>X</math> у [[Функція (математика)|образ]] <math>X</math> відносно <math>f</math>;
* контраваріативний функтор відображує функцію <math>f\colon A\to B</math> в <math>\mathcal{P}f\colon \mathcal{P}B \to \mathcal{P}A</math> таку, що вона відображає <math>X</math> у повний [[Функція (математика)|прообраз]] <math>X</math> відносно <math>f</math>.

== Приклад ==
Нехай <math>S\  \mathcal =\ \{x, y, z\}</math>. Тоді підмножинами <math>S</math> є:
* <math>\varnothing</math> (або <math>\emptyset</math>)&nbsp;— порожня множина
* <math>\{x\}</math>
* <math>\{y\}</math>
* <math>\{z\}</math>
* <math>\{x, y\}</math>
* <math>\{x, z\}</math>
* <math>\{y, z\}</math>
* <math>\{x, y, z\}</math>
Отже, булеаном множини <math>S</math> є множина <math>\mathcal{P}(S) = </math> <math>\{</math><math>\varnothing</math>, <math>\{x\}</math>, <math>\{y\}</math>, <math>\{z\}</math>, <math>\{x, y\}</math>, <math>\{x, z\}</math>, <math>\{y, z\}</math>, <math>\{x, y, z\}</math><math>\}</math>.

== Властивості ==
Якщо <math>S</math>&nbsp;— [[скінченна множина]] та <math>|S| = n</math>, то кількість підмножин <math>S</math> дорівнює <math>|\mathcal{P}(S)| = 2^n</math>. Цей аспект, який є передумовою до позначення <math>2^S</math>, можна подати так:
: Спершу якось упорядкуємо елементи <math>S</math>. Ми записуємо кожну підмножину <math>S</math> у вигляді <math>\{\omega_1, \omega_2, ..., \omega_n\}</math>, де <math>\omega_i, 1 \leq i \leq n</math>, може приймати значень 0 або 1. Якщо <math>\omega_i = 1</math>, тоді &nbsp;<math>i</math>-ий елемент множини <math>S</math> належить підмножині; в іншому випадку, цей елемент відсутній. Очевидно, кількість різних підмножин, які можна отримати в такий спосіб, дорівнює <math>2^n</math>.

Діагональний метод Кантора показує, що булеан множини <math>S</math> (скінченної або нескінченної) завжди має строго більшу [[Потужність множини|потужність]], ніж сама множина <math>S</math>. Зокрема, [[теорема Кантора]] свідчить, що булеан [[Зліченна множина|зліченної множини]] є [[Незліченна множина|незліченним]]. Наприклад, можна утворити [[Бієкція|бієктивне відображення]] між булеаном множини натуральних чисел та множиною дійсних чисел.

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

Булеан множини <math>S</math> формує [[Абелева група|абелеву групу]] за операцією [[Симетрична різниця множин|симетричної різниці]] та [[Комутативність|комутативний]] [[моноїд]] за операцією перетину. Отже, можна показати (доводячи [[дистрибутивність]]), що булеан формує [[булеве кільце]] за цими операціями.

== Подання підмножин як функцій ==
У [[Теорія множин|теорії множин]], <math>X^Y</math> позначає множину всіх [[Функція (математика)|функцій]] із <math>Y</math> в <math>X</math>. <math>2^S</math>&nbsp;— множина всіх відображень із <math>S</math> у <math>2 = \{0, 1\}</math>. Визначаючи функцію в <math>2^S</math> з відповідним прообразом 1, ми бачимо, що відображення між <math>2^S</math> та <math>\mathcal{P}(S)</math> є [[Бієкція|бієктивним]], де кожна функція є [[Характеристична функція|характеристичною функцією]] підмножини <math>\mathcal{P}(S)</math>, у якій вона визначена. Таким чином, <math>2^S</math> та <math>\mathcal{P}(S)</math> можна вважати теоретико-множинно ідентичними.

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

Для всієї множини отримуємо:
* <math>\varnothing = 000_2 = 0_{10}</math>
* <math>\{x\} = 100_2 = 4_{10}</math>
* <math>\{y\} = 010_2 = 2_{10}</math>
* <math>\{z\} = 001_2 = 1_{10}</math>
* <math>\{x, y\} = 110_2 = 6_{10}</math>
* <math>\{x, z\} = 101_2 = 5_{10}</math>
* <math>\{y, z\} = 011_2 = 3_{10}</math>
* <math>\{x, y, z\} = 111_2 = 7_{10}</math>

== Алгоритми ==
Для скінченної множини <math>S</math> існує [[Рекурсія|рекурсивний]] [[алгоритм]] для знаходження <math>\mathcal{P}(S)</math>.

Визначимо операцію <math>\mathcal {F}(e, T) = \{X\cup\{e\} | X\in T\}</math>.
* Якщо <math>S = \varnothing</math>, тоді повернемо <math>\mathcal{P}(S) = \{\varnothing\}</math>.

* В іншому випадку:
** Нехай <math>e</math>&nbsp;— будь-який одиничний елемент з <math>S</math>.
** Нехай <math>T = S \setminus \{e\}</math>, де <math>S \setminus \{e\}</math>&nbsp;— відносне [[Доповнення множин|доповнення]] <math>\{e\}</math> в <math>S</math>.
** Повернемо <math>\mathcal{P}(S) = \mathcal{P}(T)\cup \mathcal{F}(e, \mathcal{P}(T))</math>.

== Зв'язок з біномом Ньютона ==
Булеан тісно пов'язаний з [[Біном Ньютона|біномом Ньютона]]. Кількість підмножин потужності <math>k</math> в булеані множини, потужність якої <math>n</math>, є кількістю комбінацій <math>C_n^k</math>, яку також називають [[Біноміальний коефіцієнт|біноміальним коефіцієнтом]].

Наприклад, множина із трьох елементів містить:
* <math>C_3^0 = 1</math> підмножину з 0 елементами (порожня множина);
* <math>C_3^1 = 3</math> підмножини з 1 елементом (одиничні підмножини);
* <math>C_3^2 = 3</math> підмножини з 2 елементами (усі можливі пари одиничних підмножин);
* <math>C_3^3 = 1</math> підмножину з 3 елементами (уся початкова множина).

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

== Потужність скінченного булеана ==
Справедливе таке твердження: число підмножин скінченної множини, яка складається з <math>n</math> елементів, дорівнює <math>2^n</math>. Результат доводиться методом [[Математична індукція|математичної індукції]]. В разі порожньої множини <math>\varnothing</math>(<math>n=0</math>) тільки одна підмножина&nbsp;— вона сама, і <math>2^0=1</math>. На кроці індукції твердження вважають встановленим для множин потужності <math>n</math> та розглядається довільна множина <math>M</math> з [[Потужність множини|кардинальним числом]] <math>n+1</math>; зафіксувавши деякий [[Множина|елемент]] <math>a_0\in M</math>, підмножини множини <math>M</math> розділяють на два сімейства:
# <math>M_1</math>, що містить <math>a_0</math>,
# <math>M_2</math>, що не містить <math>a_0</math><sub>,</sub> тобто є підмножинами множини <math>M \setminus \{ a_0 \}</math>.
Підмножин другого типу, за припущенням індукції, <math>2^n</math>, підмножин першого типу рівно стільки ж, оскільки підмножина такого типу отримується з деякої єдиної підмножини другого типу доданням елемента <math>a_0</math> і, отже<sub>:</sub>

<math>2^M = M_1 \bigcup M_2</math> та <math>M_1 \bigcap M_2 = \varnothing</math>.

За індукційним припущенням <math>\left| M_1 \right| = 2^n  </math> та <math>\left| M_2 \right| = 2^n </math>, тобто:

<math>\left| 2^M \right| = \left| M_1 \right| + \left| M_2 \right| = 2^n + 2^n = 2^{n+1} = 2^\left| M \right|</math>

== Див. також ==
* [[Аксіома булеана]]
* [[Теорема Кантора]]
* [[Континуум-гіпотеза]]
* [[Теорія множин]]
* [[Алгебра множин]]

== Посилання ==
* [http://mathworld.wolfram.com/PowerSet.html Weisstein, Eric W., «Power Set»] {{Webarchive|url=https://web.archive.org/web/20160429053304/http://mathworld.wolfram.com/PowerSet.html |date=29 квітня 2016 }}, на сайті [[MathWorld]].
* [http://planetmath.org/powerset Булеан] {{Webarchive|url=https://web.archive.org/web/20160413073008/http://planetmath.org/powerset |date=13 квітня 2016 }} на сайті [[PlanetMath|PlanetMath.org]].
* [https://ncatlab.org/nlab/show/power+set Булеан] {{Webarchive|url=https://web.archive.org/web/20160412181616/https://ncatlab.org/nlab/show/power+set |date=12 квітня 2016 }} на сайті nLab.
* [https://ncatlab.org/nlab/show/power+object Експоненціал] {{Webarchive|url=https://web.archive.org/web/20160307005037/https://ncatlab.org/nlab/show/power+object |date=7 березня 2016 }} на сайті nLab.

{{Теорія множин}}
{{Математична логіка}}
{{Set-theory-stub}}
[[Категорія:Теорія множин]]
[[Категорія:Абстрактна алгебра]]
[[Категорія:Алгебра]]
[[Категорія:Операції над множинами]]