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

Булеан (англ. power set, нім. potenzmenge) — в теорії множин, це множина всіх підмножин даної множини , позначається або (так як воно відповідає множині відображень з в ).

Якщо дві множини мають однакову потужність, то їх булеани теж мають рівну потужність. Зворотнє твердження (тобто ін'єктивність операції для кардиналів) є незалежним від ZFC.

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

  • коваріативний функтор відображає функцію у функцію таку, що вона відображає у образ відносно ;
  • контраваріативний функтор відображує функцію в таку, що вона відображає у повний прообраз відносно .

Зміст

ПрикладРедагувати

Нехай  . Тоді підмножинами   є:

  •   (або  ) — порожня множина
  •  
  •  
  •  
  •  
  •  
  •  
  •  

Отже, булеаном множини   є множина     ,  ,  ,  ,  ,  ,  ,   .

ВластивостіРедагувати

Якщо  скінченна множина та  , тоді кількість підмножин   дорівнює  . Цей аспект, який є передумовою до позначення  , може бути представлений наступним чином:

Спершу упорядкуємо елементи   будь-яким чином. Ми записуємо кожну підмножину   у вигляді  , де  , може приймати значення 0 або 1. Якщо  , тоді   -ий елемент множини   знаходиться у підмножині; в іншому випадку, цей елемент відсутній. Очевидно, кількість різних підмножин, які можна отримати таким чином, дорівнює  .

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

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

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

Представлення підмножин як функційРедагувати

У теорії множин,   позначає множину усіх функцій із   в  .   — множина усіх відображень із   у  . Визначаючи функцію в   з відповідним прообразом 1, ми бачимо, що відображення між   та   є бієктивним, де кожна функція є характеристичною функцією підмножини  , у якій вона визначена. Таким чином,   та   можна вважати теоретико-множинно ідентичними.

Це поняття може бути застосоване до вищенаведеного прикладу, де  , щоб побачити ізоморфізм з двійковими числами від 0 до  , де   — кількість елементів у множині. У   "1" на позиції, яка відповідає позиції елемента у множині, позначає присутність цього елемента. Такими чином,  .

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

  •  
  •  
  •  
  •  
  •  
  •  
  •  
  •  

АлгоритмиРедагувати

Для скінченної множини   існує рекурсивний алгоритм для знаходження  .

Визначимо операцію  .

  • Якщо  , тоді повернемо  .
  • В іншому випадку:
    • Нехай   — будь-який одиничний елемент з  .
    • Нехай  , де   — відносне доповнення   в  .
    • Повернемо  .

Зв'язок з біномом НьютонаРедагувати

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

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

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

Підмножини обмеженої потужностіРедагувати

Множина підмножин  , потужність яких менше ніж  , позначається   або  . Таким чином, множина непорожніх підмножин   може бути позначена  .

Потужність кінцевого булеанаРедагувати

Справедливо наступне твердження: число підмножин кінцевої множини, яка складається з   елементів, дорівнює  . Результат доводиться методом матиматичної індукції. В базі пустої множини  ( ) тільки одна підмножина — вона сама, і  . На кроці індукції твердження вважається встановленим для множин потужності   та розглядається довільна множина   з кардинальним числом  ; зафіксувавши деякий елемент  , підмножини множини   розділяються на два сімейства:

  1.  , що містить  ,
  2.  , що не містить  , тобто є підмножинами множини  .

Підмножин другого типу по припущенню індукції  , підмножин першого типу рівно стільки ж, так як підмножина такого типу отримується з деякої єдиної підмножини другого типу додаванням елемента   і, отже:

  та  .

За індукціонним припущенням   та  , тобто:

. 

Див. такожРедагувати

ПосиланняРедагувати