§ 2. Декартово произведение двух или нескольких множеств. Понятие отношения. Бинарные отношения

Декартово произведение множеств A и B обозначается :

Элементы этого множества называются упорядоченной парой.

Декартово произведение множеств обозначается :

Если , то множество называется n-й декартовой степенью множества A и обозначается .

Пусть даны два множества A и B.

Определение: Бинарным (или двуместным) отношением называется множество упорядоченных пар, т.е. любое подмножество декартова произведения .

Если пара , то иногда записывают так: (элемент находится в отношении с элементом )

Если A=B, то говорят, что есть отношение, заданное на множестве A.

Определение: Областью определения бинарного отношения называется множество :

Определение: Областью значений бинарного отношения называется множество :

Определение: Обратным отношением (инверсией) бинарного отношения называется отношение :

Определение: Тождественным отношением на множестве A называется отношение :

Определение: Произведением (композицией) бинарных отношений и называется отношение, которое обозначается: , и определяется следующим образом:

Упражнения

2.1. Найти декартово произведение множеств А×В, В×А и изобразить его на координатной плоскости:

а) А=-5, 6, 1 В=1, 3, 7

б) А=0; 1 В=0; 1

в) А=0; ) В=2; 3

г) А=-1; 2 В=(-2; 4

д) А=N В=-2; 5

е) А=R В=Z

2.2. Найти геометрическую интерпретацию множества АВ, где

а) А – множество точек отрезка -1;3, В – множество точек окружности с центром в точке (1, 1) радиусом 1;

б) А – множество точек отрезка 0;2, В – множество точек квадрата с вершинами (0, 0), (0, 1), (1, 0), (1,1).

2.3. Даны множества А=1, 2, 3, 4, 5, 6, 8 и В=3, 4, 6. Задать бинарное отношение между А и В перечислением пар и с помощью графа:

а) ₁=(а, b) | аА, bВ и а делится на b;

б) ₂=(а, b) | аB bA число (а-b) – четное.

Найти композиции бинарных отношений ₁ и ₂.

2.4. Найти область определения и область значений бинарного отношения . Найти инверсию бинарного отношения , композиции ◦, ◦^-1, ^-1◦, ^-1◦^-1, если:

а) =(3, 7), (7, 3), (5, 3), (1, 5);

б) =(1, 1), (1, 2), (1, 3), (2, 3), (2, 4), (3, 5), (2, 1), (3, 6);

в) =(x, y) | x, yR и x+y0;

г) =(x, y) | x, yN, x, y – нечетные;

д) =(х, у) | х, уR и у2х-1;

е) =(х, у) | х, уR и у=х²;

ж) =(х, у) | х, уR и у²+(х-1)²<5

2.5. Записать бинарные отношения, которым соответствуют данные геометрические интерпретации. Найти D_, R_.

а) б)

у

у

2

у=х

х

0

-2

2

х

0

y

y=x²

у

y=׀x׀+1

в)

г)

х

0

x

0

у

д)

у

1

е)

1

х

0

1

-1

х

0

2

-2

-1

-1

§ 3. Специальные бинарные отношения. Отношения эквивалентности

Определение: Бинарное отношение , заданное на множестве A, называется рефлексивным, если .

Определение: Бинарное отношение , заданное на множестве A, называется антирефлексивным, если .

Определение: Бинарное отношение , заданное на множестве A, называется симметричным, если выполняется условие:

: если , то .

Определение: Бинарное отношение , заданное на множестве A, называется антисимметричным, если выполняется условие:

: если и , то .

Определение: Бинарное отношение , заданное на множестве A, называется транзитивным, если выполняется условие:

: если и , то .

Определение: Бинарное отношение , заданное на множестве A, называется антитранзитивным, если выполняется условие:

: если и , то .

Определение: Отношение , заданное на множестве A, называется отношением эквивалентности на множестве A, если рефлексивно, симметрично и транзитивно на данном множестве A.

Определение: Классом эквивалентности, порожденным элементом , называется подмножество множества A, которое обозначается :

.

Определение: Разбиением множества A называется совокупность попарно непересекающихся подмножеств множества A таких, что каждый элемент множества A принадлежит одному и только одному из этих подмножеств, и объединение всех этих подмножеств есть множество A.

Теорема: Всякое разбиение множества A определяет на множестве А отношение эквивалентности . Всякое отношение эквивалентности, заданное на множестве А, определяет разбиение множества А на классы эквивалентности относительно этого отношения.

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

.