Алгебра множин

Матеріал з Вікіпедії — вільної енциклопедії.

Алгебра множин — розділ теорії множин, який визначає закони композиції множин, виходячи з основних властивостей операцій над ними, а також пропонує певну систематичну процедуру для обчислення теоретико-множинних рівнянь та співвідношень.^{[Джерело?]}
З точки зору абстрактної алгебри алгебра множин — це кільце K підмножин множини R, що містить R.

Властивості операцій на множинах

Бінарні операції об'єднання та перетину множин, задовольняють певним фундаментальним алгебраїчним властивостям. Далі вони наводяться без доведення.
ТВЕРДЖЕННЯ 1: Для будь-яких множин A, B, та C, виконуються такі співвідношення:

комутативність:

• A ∪B  =  B ∪A
• A ∩B  =  B ∩A

асоціативність:

• (A ∪B) ∪C  =  A ∪(B ∪C)
• (A ∩B) ∩C  =  A ∩(B ∩C)

дистрибутивність операції перетину відносно об'єднання:

• A ∪(B ∩C)  =  (A ∪B) ∩(A ∪C)
• A ∩(B ∪C)  =  (A ∩B) ∪(A ∩C)

Як можна спостерігати з наведених співвідношень, з точки зору основних властивостей можна провести певну аналогію між операцією об'єднання множин та операцією множення чисел, операцією перетину множин та операцією додавання чисел. Ця аналогія розвивається в наступному твердженні:
ТВЕРДЖЕННЯ 2: Для будь-якої підмножини A універсальної множини U, справедливі наступні співвідношення:

• властивості нуля

• A ∪Ø  =  A
• A ∩C_A  =  Ø

• властивості одиниці

• A ∩U  =  A
• A ∪С_A  =  U

Тут елементи Ø та U є нейтральними елементами відносно операцій ∪ та ∩ відповідно, тобто такими, що не впливають на результат операції, аналогічно тому, як в звичайній алгебрі дійсних чисел такими елементами на операціях множення та складання є 1 та 0 відповідно. Але, на відміну від звичайного множення та складання, в алгебрі операцій перетину та об'єднання множин не існує зворотного елементу.
Наведені закони складають основу алгебри множин. Всі інші співвідношення можуть бути виведені з них безпосередньо.

Принцип дуальності

Наведені вище співвідношення демонструють цікаву закономірність. Якщо в якомусь з законів провести заміни ∪ на ∩, а також Ø на U, то він залишиться справедливим. Це фундаментальна властивість алгебри множин, яка має назву принципа дуальності.......

Додаткові співвідношення алгебри множин

ТВЕРДЖЕННЯ 3: Для будь-яких підмножин A та B універсальної множини U, справедливі наступні твердження:

ідемпотентність:

• A ∪A  =  A
• A ∩A  =  A

домінування:

• A ∪U  =  U
• A ∩Ø  =  Ø

поглинання:

• A ∪(A ∩B)  =  A
• A ∩(A ∪B)  =  A

ТВЕРДЖЕННЯ 4: Нехай A та B — підмножини універсуму U, тоді:

правила де Моргана:

• С_(A∪B)  =  C_A∩C_B
• C_(A∩B)  =  C_A∪C_B
• CC_A  =  A
• C_Ø  =  U
• C_U  =  Ø

ТВЕРДЖЕННЯ 5: Нехай A та B — підмножини універсуму U, тоді:

однозначність доповнення:

• Якщо A ∪B  =  U, та A ∩B  =  Ø тоді B = С_A.

Часткова впорядкованість

На множині X можна ввести відношення порядку ⊆, яке задовольняє наступним властивостям:
ТВЕРДЖЕННЯ 6: Якщо A, B та C — деякі множини, то:

рефлексивність:

• A ⊆ A

антисиметричність:

• A ⊆ B та B ⊆ A тоді й тільки тоді, якщо A = B

транзитивність:

• If A ⊆ B та B ⊆ C тоді A ⊆ C

Це твердження говорить про те, що множина X є алгебраїчною структурою, або решіткою, і якщо вона дистрибутивна (що показано в твердженні 1) та для кожного елементу існує його доповнення, то така структура має назву булевої алгебри (таке визначення булевої алгебри не є математично строгим, докладніше дивись в статті Булева алгебра).
ТВЕРДЖЕННЯ 7: Якщо A, B та C — підмножини S, то виконується наступне:

• Ø ⊆ A ⊆ S
• A ⊆ A ∪B
• Якщо A ⊆ C та B ⊆ C то A ∪B ⊆ C
• A ∩B ⊆ A
• Якщо C ⊆ A та C ⊆ B то C ⊆ A ∩B

ТВЕРДЖЕННЯ 8: Для будь-яких множин A та B, наступні твердження еквівалентні:

• A ⊆ B
• A ∩B  =  A
• A ∪B  =  B
• A − B  =  Ø
• B^C ⊆ A^C

Алгебра доповнень

ТВЕРДЖЕННЯ 9: Для універсальної множини U та підмножин A, B, та C з U, справедливе наступне:

• C − (A ∩B)  =  (C − A) ∪(C − B)
• C − (A ∪B)  =  (C − A) ∩(C − B)
• C − (B − A)  =  (A ∩C) ∪(C − B)
• (B − A) ∩C  =  (B ∩C) − A  =  B ∩(C − A)
• (B − A) ∪C  =  (B ∪C) − (A − C)
• A − A  =  Ø
• Ø − A  =  Ø
• A − Ø  =  A
• B − A  =  A^C ∩B
• (B − A)^C  =  A ∪B^C
• U − A  =  A^C
• A − U  =  Ø