Алгебра множин
Алгебра множин — розділ теорії множин, який визначає закони композиції множин, виходячи з основних властивостей операцій над ними, а також пропонує певну систематичну процедуру для обчислення теоретико-множинних рівнянь та співвідношень.[джерело?]
З точки зору абстрактної алгебри алгебра множин — це кільце 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 ∩CA = Ø
- властивості одиниці
- 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) = CA∩CB
- C(A∩B) = CA∪CB
- CCA = A
- CØ = U
- CU = Ø
ТВЕРДЖЕННЯ 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 = Ø
- BC ⊆ AC
Алгебра доповнень
ред.ТВЕРДЖЕННЯ 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 = AC ∩B
- (B − A)C = A ∪BC
- U − A = AC
- A − U = Ø
Див. також
ред.Література
ред.- Енциклопедія кібернетики, т. 1, с. 70.
- Куратовский К., Мостовский А. Теория множеств = Set Theory (Teoria mnogości). — М. : Мир, 1970. — 416 с.(рос.)