Булеан

Матеріал з Вікіпедії — вільної енциклопедії.
Перейти до: навігація, пошук
Елементи булеану множини {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|

Див. також[ред.ред. код]

Посилання[ред.ред. код]


Математична логіка Це незавершена стаття з теорії множин.
Ви можете допомогти проекту, виправивши або дописавши її.