Булеан

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

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

Справедливо наступне твердження: число підмножин кінцевої множини, яка складається з 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|

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

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


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