1.2.4. Свойства операций над множествами

В табл. 1.1. Приведены основные свойства операций над множествами.

Таблица 1.1

Свойства операций над множествами

Название

Свойство операции

Идемпотентность

A ∩ A = A

A A = A

Коммутативность

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 C)

Дистрибутивность

A B ∩C =

A ∩(B C) =

= (A B) ∩(A C)

= A ∩ B A ∩C

Поглощение

(A ∩ B) A = A

( A B) ∩ A = A

Действия с универсу-

A ∩ I = A

A I = I

мом

Действия с пустым

A ∩ =

A = A

множеством

Свойства дополнения

A ∩

A

= I

A =

A

Двойное дополнение

A = A

Законы де Моргана

A B = A ∩ B

A ∩ B = A B

Выражение для разно-

A \ B = A

∩ B

сти

Выражение для сим-

A B = ( A B) \ ( A ∩ B) = A ∩ B A ∩ B

метрической разности

Результаты всех этих операций над подмножествами универсума I дают также подмножества I. По этой причине мы вправе с помощью рассмотренных операций определить алгебры A на I.

Под алгеброй A = <M, S> понимается совокупность множества М с заданными на нем операциями S = {O1, O2, . . . ,On}.

14

Алгебра A =< B(I ); ,∩, > называется алгеброй Кантора, на

ней выполняются законы: идемпотентность, коммутативность, ассоциативность, дистрибутивность, поглощение, действия с универсумом, действия с пустым множеством, свойства дополнения, двойное дополнение, законы де Моргана.

Задача 1.2. С помощью законов алгебры Кантора упростить выражения:

1)A ∩ B A ∩ B ;

2)A ∩ B A ;

3)A ∩ B A .

Решение.

1)A ∩ B A ∩ B = A ∩ (B B) = A ∩ I = A ;

2)A ∩ B A = A B A = I B = I ;

3)A ∩ B A = A ∩ B ∩ A = B ∩ Ø = Ø.

1.2.5. Аксиоматика теории множеств

Современная теория множеств использует систему аксиом (утверждений), принимаемых без доказательства, из которых выводятся все теоремы и утверждения теории множеств.

Система аксиом Цермело–Френкеля (ZF) является стандартной системой аксиом для теории множеств. К этой системе аксиом часто добавляют аксиому выбора, и называют системой Цермело– Френкеля с аксиомой выбора (ZFC).

1.Аксиома объёмности. Два множества A и B равны тогда и только тогда, когда они имеют одни и те же элементы.

2.Аксиома существования пустого множества. Существует множество без единого элемента. Это множество обычно обознача-

ется {} или .

3. Аксиома объединения. Для произвольного множества A и произвольного множества B существует и причем единственное множество С, называемое объединением множества A и B, состоящее из тех и только тех элементов, которые содержатся в множестве А или в множестве B.

15

4. Аксиома основания. Каждое непустое множество S содержит элемент a, такой, что

S ∩ a = .

5.Аксиома множества подмножеств. Для любого множества

A существует множество B, состоящее из тех и только тех элементов, которые являются подмножествами множества A. Множество подмножеств множества A называется булеаном множества A и обозначается P(A).

6.Схема выделения. Любому множеству A и свойству φ отвечает множество B, элементами которого являются те и только те элементы a, которые обладают свойством ψ. Схема выделения содержит счётное количество аксиом, так как каждая формула φ(х) логики первого порядка порождает аксиому.

7.Аксиома подстановки. Для любого множества A и однозначной функции F, определенной на множестве A, существует

множество, которое состоит в точности из элементов F(х) для x A.

8.Аксиома выбора. Для любого семейства попарно непересекающихся непустых множеств существует множество c такое, что, каково бы ни было множество x данного семейства, множество

x∩c состоит из одного элемента.

9.Аксиома бесконечности. Существует хотя бы одно бесконечное множество – множество натуральных чисел N.

Далее введём определение: множество называется индуктивным, если оно:

а) содержит пустое множество;

б) содержит последователь (то есть элемент a {a}) каждого

своего элемента.

Аксиома бесконечности утверждает, что индуктивные множества существуют:

ω( ω∩ x(x ω → x {x}ω) ).

Непротиворечивость приведённой аксиоматики на настоящий момент не установлена.

16