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

Теорема 1. Для операций над множествами справедливы следующие свойства:

1. АÈB=ВÈА	1’. АÇB=ВÇА	Коммутативность
2. ( АÈB)ÈС= АÈ(BÈС)	2’. ( АÇB)ÇС= АÇ(BÇС)	Ассоциативность
3. АÈ(BÇС)=(АÈВ)Ç(АÈС)	3’. АÇ(ВÈС)=(АÈВ)Ç(АÈС)	Дистрибутивность
4. АÈ А=А	4’. АÇА=А	Идемпотентность
5.	5’.	Законы де Моргана
6. АÈ (АÇВ)=А	6’. АÇ(АÈВ)=А	Законы поглощения
7. АÈ = U 8. АÈ U= U 9. АÈÆ= А	7’. АÇ =Æ 8’. АÇU=A 9’. АÇÆ=Æ	Законы пустого и универсального множества
10. =А		Закон инволюции
11. А\В=АÇ		Закон исключения разности

Доказательство. Докажем свойство 1.

Левая часть выражения 1 состоит по определению 5 из элементов, принадлежащих либо А, либо В, либо А и В. Правая часть состоит из элементов, принадлежащих либо В, либо А, либо В и А. Очевидно, что левая и правая часть равенства 1 состоит из одних и тех же элементов следовательно по определению 1, .

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

а) и и

б) и и

в) из и следует

Остальные свойства доказываются аналогично.

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

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

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

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

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

Утверждение. Если |M|=n, то |P(M)|=2ⁿ. Другими словами, у конечного множества мощности n существует ровно 2ⁿ попарно различных подмножеств.

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