Булеан

Матеріал з Вікіпедії — вільної енциклопедії.
Перейти до: навігація, пошук
Елементи булеану множини {x,y,z}, які зображені у порядку включення елементів

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

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

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

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

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

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

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

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

Властивості[ред.ред. код]

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

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

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

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

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

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

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

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

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

Алгоритми[ред.ред. код]

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

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

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

Зв'язок з біномом Ньютона[ред.ред. код]

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

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

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

Підмножини обмеженої потужності[ред.ред. код]

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

Потужність кінцевого булеана[ред.ред. код]

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

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

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

та .

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

.

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

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


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