Формула включений и исключений множеств

Пусть А – некоторое множество. Будем обозначать через – количество элементов в этом множестве (мощность множества).

Формулой перекрытий или формулой включений и исключений (или формулой перекрытий). Для двух множеств имеет вид:

.

Для трех множеств формула включений и исключений выглядит несколько сложнее:

С помощью этой формулы легко найти и число элементов некоторого множества, объединения множеств, а также эта формула помогает решать некоторые текстовые задачи.

Декартовым (прямым) произведением множеств А и В называется множество всех пар таких, что , . Это множество обозначается . Таким образом, верно равенство .

Если элементы множества А можно представить в виде точек на числовой прямой, то элементы декартового произведения имеют две составляющих и представляются в виде точек на координатной плоскости. Так, например, вся плоскость – это декартовое произведение множества действительных чисел на себя, т.е. плоскость можно задать как декартовое произведение . Поэтому часто плоскость называют декартовой системой координат.

Бинарным отношением R называется любое множество пар. Например, .

Пусть А – конечное множество. Если R – подмножество декартового произведения , т.е. , тогда говорят, что R – это бинарное отношение на множестве А.

Пример 1. Пусть , тогда декартовое произведение равно

.

Бинарным отношением будет любое множество, составленное из каких-либо (может быть и всех) элементов декартового произведения . Например, бинарными отношениями будут или .

По некоторым важным свойствам выделяют специальные группы бинарных отношений.