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

Теорема 1. Для произвольных множеств А, В, С справедливы следующие равенства:

1. АÇB=ВÇА 2. ( АÇB)ÇС= АÇ(BÇС) 3. ( АÇB)ÈС=(АÈС)Ç(ВÈС) 4. АÇ(АÈВ)=А 5. 6. АÇU=A 7. АÇÆ=Æ 8. АÇ А=Æ 9. АÇА=А 10. =А 11. А\В=АÇВ

1'. АÈB=ВÈА 2'. ( АÈB)ÈС= АÈ(BÈС) 3'.(АÈB)ÇС=(АÇС)È (ВÇС) 4'. АÈ (АÇВ)=А 5'. 6'. АÈU= U 7'. АÈÆ= А 8'. АÈ А= U 9'. АÈА=А

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

Доказательство. Свойства 1, 1', 2, 2', 4, 4', 6-8, 6'-8',10 доказываются на основании определения равенства множеств и операций над множествами. Остальные равенства доказываются методом встречных включений.

Докажем, например, свойство 3 методом встречных включений:

( АÇB) ÈС=(АÈС)Ç(ВÈС)

X Y

Докажем, что X = Y.

I. Докажем, что X Í Y. Пусть xÎX => xÎАÇB или xÎC => xÎА и xÎB или xÎC => возможны два случая:

1. xÎА и xÎB;

2. xÎC.

1. Пусть xÎА и xÎB => xÎАÈС и xÎВÈС => xÎ(АÈС)Ç(ВÈС)=Y, т.е. xÎY.

2. Пусть xÎC => xÎАÈС и xÎВÈС => xÎ(АÈС)Ç(ВÈС)=Y, т.е. xÎY.

Из 1-2 => X Í Y.

II. Докажем, что Y ÍX .

Пусть yÎY=>yÎАÈС и yÎBÈC=>(yÎA или yÎC) и (yÎB или yÎC).

Возможны четыре случая:

1. yÎA и yÎB.

2. yÎA и yÎC.

3. yÎC и yÎB.

4. yÎC.

1. Пусть yÎA и yÎB=>yÎАÇB=>yÎ( АÇB)ÈС=X, т.е. yÎX.

2. Пусть yÎA и yÎC=>yÎ( АÇB)ÈС=X, т.е. yÎ X.

3. Пусть yÎC и yÎB => yÎ( АÇB)ÈС=X, т.е. yÎX.

4. Пусть yÎC => yÎX.

Из 1-4 => YÍX.

Из I-II => X = Y. Теорема доказана.

Замечание 1. Операции пересечения и объединения можно сформулировать в общем виде для конечного и бесконечного числа множеств.

Пусть A₁, A₂, …, A_n - множества. Тогда А₁ÇА₂Ç…ÇА_n - множество всех элементов, принадлежащих каждому из множеств А₁, …, A_n ; A₁È…ÈA_n - множество всех элементов, принадлежащих хотя бы одному из множеств А₁, …, A_n .

Пусть iÎI, I - некоторое множество индексов (конечное или бесконечное),

{B_i | iÎI} - совокупность множеств. Тогда дистрибутивные законы и законы де Моргана можно сформулировать в общем виде:

AÇ(ÈB_i)=È(AÇB_i)

iÎI iÎI - обобщенные дистрибутивные законы.

AÈ(Ç B_i)=Ç(AÈ B_i)

iÎI iÎI

Ç B_i=ÈB_i

iÎI iÎI

- обобщенные законы де Моргана.

ÈB_i=Ç B_i

iÎI iÎI

Замечание 2. Множество называется конечным, если оно состоит из конечного числа элементов. В бесконечном случае различают счетные множества (например, ℤ) и множества мощности континуум (например, ℝ ).

Если конечное множество M состоит из n элементов, то пишут |M|=n, т.е. |M| -мощность множества M.

Таким образом, мощность конечного множества – это число элементов данного множества.

Пусть M – множество. Обозначим через P(M) - совокупность всех подмножеств множества M.

Утверждение 1. Если |M|=n, то |P(M)|=2ⁿ.

Например, если А={1,2}, то |A|=2 и |P(A)|=4.

Замечание 3. На множестве P(U) (совокупность всех рассматриваемых множеств) нами определены операции È, Ç,` , \, причем всякое множество можно представить в виде множества, содержащего лишь две операции:

1) Ç и ` или

2) È и `.

Системы операций 1) и 2) называются минимальными системами операций.