В, (из х £ А следует х £ В), говорят, что А является подмножеством (subset) множества В и пишут А С В. Если при этом А не совпадает с В, то А называется собственным подмножеством

(proper subset) множества В; в этом случае пишут А С В. (Многие авторы используют обозначение А С В для подмножеств, а не для собственных подмножества.) Для любого множества А выполнено соотношение АСА. Множества А и В равны тогда и только тогда, когда А С В н В С А. Для любых трёх множеств А, В и С из А С В и В С С следует А С С. Для любого множества А имеет место соотношение 0 С А.

Иногда множество определяется как часть другого множества: мы можем выделить из множества А все элементы, обладающие некоторым свойством, и образовать из них новое множество В. Например, множество чётных чисел можно определить как {ж : х £ Z и ж/2 - целое число}. Это обычно читают «множество ж из Z, для которых...» Иногда вместо двоеточия используется вертикальная черта.

Для любых множеств А и В можно построить следующие множества, получаемые с помощью теоретико-множественных операций

(set operations):

•Пересечение (intersection) множеств А и В определяется как множество

АГ\В = {х: хеАпхе В}.

•Объединение (union) множеств А и В определяется как множество

AU В = {х : х е А или ж £ В}.

•Разность (difference) множеств А и В определяется как множество

А\В = {х : х е А и х В}.

Теоретико-множественные операции обладают следующими свойствами:

Свойства пустого множества (empty set laws):

АГ)0 = 0, AU0 = А.

Идемпотентность (idempotency laws):

An А = A, АиА = А.

Коммутативность (commutative laws):

А Г) В = В Г) A, AU В = В U А.

??? На картинке следует заменить минус на \

Рис. 5.1 Диаграмма Венна, иллюстрирующая первый из законов де Моргана (5.2). Множества А, В, С изображены кругами на плоскости.

Ассоциативность (associative laws):

А П (В П С) = (А П В) П С, A U (В U С) = (A U В) U С. Дистрибутивность (distributive laws):

А П (В U С) = (А П В) U (А П С),

A U (В П С) = (A U В) П (A U С)

Законы поглощения (absorption laws):

An(iU5) = i, Au(in5)=i

Законы де Моргана (DeMorgans laws):

А \ (В Г) С) = (А \ В) U (А\С), А \ (В U С) = (А \ В) П (А \ С)

(5.1)

(5.2)

Рис. 5.1 иллюстрирует первый из законов де Моргана (5.1); множества А, В и С изображены в виде кругов на плоскости.

Часто все рассматриваемые множества являются подмножества некоторого фиксированного множества, называемого универсумом (universe). Например, если нас интересуют множества, элементами которых являются целые числа, то в качестве универсума можно взять множество Z целых чисел. Если универсум U фиксирован, можно определить дополнение (complement) множества А как А = U \А. Для любого А С U верны такие утверждения:

А = А, АГ)А = 0, All А = U.

Из законов де Моргана (5.2) следует, что для любых множеств А, В С U имеют место равенства

АП В = All В, All В = АП В.

Два множества А и В называются непересекающимися (disjoint), если они не имеют общих элементов, т.е. если АПВ = 0. Говорят, что семейство S = {Si} непустых множеств образует разбиение (partition) множества S, если

•множества Si попарно не пересекаются (are pairwise disjoint), т. е. Si П Sj = 0 при г ф j,

•их объединение есть S, т.е.

S = [J Si

s.es

Другими словами, семейство S образует разбиение множества S, если любой элемент s G S принадлежит ровно одному из множеств Si семейства.

Число элементов в множестве S называется его мощностью (cardinality), или размером (size), и обозначается \S\. Два множества имеют одну и ту же мощность, если между их элементами можно установить взаимно однозначное соответствие. Мощность пустого множества равна нулю: 0 = 0. Мощность конечного (finite) множества - натуральное число; для бесконечных (infinite) множеств понятие мощности требует аккуратного определения. Оно нам не понадобится; упомянем лишь, что множества, элементы которых можно поставить во взаимно однозначное соответствие с натуральными числами, называются счётными (countably infinite); бесконечные множества, не являющиеся счётными, называют несчётными (uncountable). Множество целых чисел Z счётно, в то время как множество вещественных чисел R несчётно.

Для любых двух конечных множеств А и В выполнено равенство

\AUB\ = \А\ + \В\ -\АГ)В\(5.3)

из этого равенства вытекает, что

AU В\ А + \В\

Если множества А и В не пересекаются, то \А П В\ = 0 и это неравенство обращается в равенство: AUfi = А + \В\. Если А С В, то А \В\.

Конечное множество из га элементов называют га-элементным (га-set); одноэлементное множество именуют иногда синглетоном (singleton). В английской литературе употребляется также термин к-subset, означающий /г-элементное подмножество (какого-либо множества).

Для данного множества S можно рассмотреть множество всех его подмножеств, включая пустое множество и само S; его обозначают 2s и называют множеством-степенью (power set). Например, 2{а,Ь} - {0 {а}, {b}, {а,Ь}}. Для конечного S множество 2s содержит 2l5l элементов.

Упорядоченная пара из двух элементов а и Ь обозначается (а, Ъ) и формально может быть определена как (а, Ъ) = {а, {а, &}}, так что (а, Ъ) отличается от (Ь,а). [Это определение упорядоченной пары