Обобщением понятия равенства является отношение эквивалентности.

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

Отношение эквивалентности разбивает множество A на непересекающиеся подмножества, называемые классами эквивалентности. Если в качестве A рассмотреть множество людей, проживающих в домах некоторого города, то отношение проживания в одном доме будет отношением эквивалентности. Более математическим примером является отношение сравнения по модулю n в множестве целых чисел Z : , если делится на n . При этом Z разбивается на классы , характеризуемые остатками от деления на n . Более общим примером является эквивалентность элементов группы G по подгруппе H : если . Классами эквивалентности здесь являются правые смежные классы по подгруппе H .

Рассмотрим отношение «уважать», определенное на множестве всех людей %%M%%. Для полной информации о том, кто кого уважает, составим следующее множество %%R%%. Переберем все пары %%(a, b)%%, где %%a, b%% пробегают множество всех людей. Если %%a%% уважает %%b%%, то пару %%(a,b)%% отнесем к множеству %%R%%, иначе — нет.

Этот список полностью отражает отношение «уважать». Если нужно узнать, уважает ли человек %%a%% человека %%b%%, то просмотрим множество %%R%%. Если пара %%(a, b) \in R%%, то заключаем, что %%a%% уважает %%b%%. В случае %%(a,b) \notin R%% — %%a%% не уважает %%b%%.

Определение

Бинарным отношением , определенным на множестве %%M%%, называется произвольное подмножество %%R%% из декартового произведения %%M^2%%.

Пример

Рассмотрим отношение больше на множестве %%M = \{1, 2\}%%. Тогда

$$ M^2 = \big\{(1, 1), (1,2), (2,1), (2,2)\big\} $$ Из него выбирем все пары %%(a,b)%%, где %%a > b%%. Получим $$ R = \big\{(2,1)\big\} $$

Виды бинарных отношений

Рефлексивное бинарное отношение

рефлексивным , если для любого элемента %%a%% из %%M%%, выполняется условие %%a~R~a%%. $$ \begin{array}{l} \forall a\in M~~a~R~a \text{ или}\\ \forall a\in M~~(a,a) \in R. \end{array} $$

Примеры

1. Рассмотрим отношение больше больше рефлексивным? Если да, то каждое число является больше самого себя, что неверно. Поэтому отношение больше не рефлексивно.
2. Рассмотрим отношение равно на множестве действительных чисел. Оно является рефлексивным , так как каждое действительное число равно самому себе.

Симметричное бинарное отношение

Бинарное отношение %%R%% на множестве %%M%% называется симметричным , если для любых двух элементов %%a, b%% из %%M%%, из условия %%a~R~b%% следует условие %%b~R~a%%.

$$ \begin{array}{l} \forall a,b\in M~~a~R~b \rightarrow b~R~a \text{ или}\\ \forall a,b\in M~~(a,b) \in R \rightarrow (b,a) \in R. \end{array} $$

Примеры

1. Рассмотрим отношение больше на множестве действительных чисел. Является ли отношение больше симметричным? Оно не является симметричным, так как если %%a > b%%, то условие %%b > a%% не выполняется. Поэтому отношение больше не симметрично.
2. Пусть %%R%% — отношение, определенное на множестве %%M = \{a,b,c\}%%. При этом %%R = \big\{ (a,b), (b,c), (a,a), (b,a), (c,b)\big\}%%. Для этого отношения имеем %%\forall x,y \in M ~~ (x,y) \in R \rightarrow (y,x) \in R%%. По определению %%R%% симметрично.

Транзитивное бинарное отношение

Бинарное отношение %%R%% на множестве %%M%% называется транзитивным , если для любых элементов %%a, b, c%% из %%M%%, из условий %%a~R~b%% и %%b~R~c%% следует условие %%a~R~c%%.

$$ \begin{array}{l} \forall a,b,c\in M~~a~R~b \land b~R~c \rightarrow a~R~c \text{ или}\\ \forall a,b,c\in M~~(a,b) \in R \land (b,c) \in R \rightarrow (a,c) \in R. \end{array} $$

Пример

Рассмотрим отношение больше на множестве дейтсвительных чисел. Оно является транзитивным , так как для любых элементов выполняется условние %%\forall a,b,c\in M~~a > b \land b > c \rightarrow a > c%%. Так, например, подставив вместо %%a, b%% и %%c%% числа %%2, 1%% и %%0%% соответственно, получим: если %%2 > 1%% и %%1 > 0%%, то %%2 > 0%% — верное утверждение (вспомните импликацию, из истины следует истина).

Антисимметричное бинарное отношение

Бинарное отношение %%R%% на множестве %%M%% называется антисимметричным , если для любых элементов %%a, b%% из %%M%%, из условий %%a~R~b%% и %%b~R~a%% следует условие %%a = b%%.

$$ \begin{array}{l} \forall a,b,c\in M~~a~R~b \land b~R~a \rightarrow a = b \text{ или}\\ \forall a,b\in M~~(a,b) \in R \land (b,a) \in R \rightarrow a = b. \end{array} $$

Пример

Отношение больше или равно на множестве действительных чисел антисимметрично . Действительно, если %%a \geq b%% и %%b \geq a%%, %%a = b%%.

Эквивалентное бинарное отношение

эквивалентности , если оно рефлексивно , симметрично и транзитивно .

Нетрудно проверить, что отношение параллельности на множестве прямых плоскости является отношением эквивалентности.

Отношение частичного порядка

Бинарное отношение %%R%% на множестве %%M%% называется отношением частичного порядка , если оно рефлексивно , антисимметрично и транзитивно .

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

Построение отрицаний

Пусть %%R%% — бинарное отношение на множестве %%M%%, и %%P%% — одно из следующих условий:

• отношение %%R%% рефлексивно,
• отношение %%R%% симметрично,
• отношение %%R%% транзитивно,
• отношение %%R%% антисимметрично.

Построим для каждого из них отрицание выполнения условия %%P%%.

Отрицание рефлексивности

По определению %%R%% рефлексивно, если каждый элемент множества %%M%% находится в отношении %%R%% к самому себе, то есть %%\forall a \in M~~a~R~a%%. Тогда рассмотрим отрицание рефлексивности как истинное высказывание %%\overline{\forall a \in M~~a~R~a}%%. Используем равносильность %%\overline{\forall x P(x)} \equiv \exists x \overline {P(x)}%%. В нашем случае получаем %%\forall a \in M~~a~R~a \equiv \exists a\in M~~a~\not\text{R }~a%%, что и нужно.

Аналогично получаем и остальные отрицания. В итоге получаем следующие утверждения:

%%R%% не рефлексивно тогда и только тогда, когда

$$ \exists a \in M~~a~\not R~a $$

%%R%% не симметрично тогда и только тогда, когда

$$ \exists a, b \in M~~ a~R~b \land b~\not R~a $$

%%R%% не транзитивно тогда и только тогда, когда

$$ \exists a, b, c \in M a~R~b \land b~R~c \land a~\not R~c $$

%%R%% не антисимметрично тогда и только тогда, когда

$$ \exists a, b \in M~~ a~R~b \land b~R~a \land a \neq b. $$

Определение . Бинарным отношением R называется подмножество пар (a,b)∈R декартова произведения A×B, т. е. R⊆A×B . При этом множество A называют областью определения отношения R, множество B – областью значений.

Обозначение: aRb (т. е. a и b находятся в отношении R). /

Замечание : если A = B , то говорят, что R есть отношение на множестве A .

Способы задания бинарных отношений

1. Списком (перечислением пар), для которых это отношение выполняется.

2. Матрицей. Бинарному отношению R ∈ A × A , где A = (a 1 , a 2 ,..., a n), соответствует квадратная матрица порядка n , в которой элемент c ij , стоящий на пересечении i-й строки и j-го столбца, равен 1, если между a i и a j имеет место отношение R , или 0, если оно отсутствует:

Свойства отношений

Пусть R – отношение на множестве A, R ∈ A×A . Тогда отношение R:

рефлексивно, если Ɐ a ∈ A: a R a (главная диагональ матрицы рефлексивного отношения содержит только единицы);

антирефлексивно, если Ɐ a ∈ A: a R a (главная диагональ матрицы рефле сивного отношения содержит только нули);

симметрично, если Ɐ a , b ∈ A: a R b ⇒ b R a (матрица такого отношения симметрична относительно главной диагонали, т.е. c ij c ji);

антисимметрично, если Ɐ a, b ∈ A: a R b & b R a ⇒ a = b (в матрице такого отношения отсутствуют единицы, симметричные относительно главной диагонали);

транзитивно, если Ɐ a, b, c ∈ A: a R b & b R c ⇒ a R c (в матрице такого отношения должно выполняться условие: если в i-й строке стоит единица, например в j-ой координате (столбце) строки, т. е. c ij = 1 , то всем единицам в j-ой строке (пусть этим единицам соответствуют k е координаты такие, что, c jk = 1) должны соответствовать единицы в i-й строке в тех же k-х координатах, т. е. c ik = 1 (и, может быть, ещё и в других координатах).

Задача 3.1. Определите свойства отношения R – «быть делителем», заданного на множестве натуральных чисел.

Решение.

отношение R = {(a,b):a делитель b}:

рефлексивно, не антирефлексивно, так как любое число делит само себя без остатка: a/a = 1 для всех a∈N ;

не симметрично, антисимметрично, например, 2 делитель 4, но 4 не является делителем 2;

транзитивно,таккакесли b/a ∈ N и c/b ∈ N, то c/a = b/a ⋅ c/b ∈ N, например, если 6/3 = 2∈N и 18/6 = 3∈N, то 18/3 = 18/6⋅6/3 = 6∈N.

Задача 3.2. Определите свойства отношения R – «быть братом», заданного на множестве людей.
Решение.

Отношение R = {(a,b):a - брат b}:

не рефлексивно, антирефлексивно из-за очевидного отсутствия aRa для всех a;

не симметрично, так как в общем случае между братом a и сестрой b имеет место aRb , но не bRa ;

не антисимметрично, так как если a и b –братья, то aRb и bRa, но a≠b;

транзитивно, если называть братьями людей, имеющих общих родителей (отца и мать).

Задача 3.3. Определите свойства отношения R – «быть начальником», заданного на множестве элементов структуры

Решение.

Отношение R = {(a,b) : a - начальник b}:

• не рефлексивно, антирефлексивно, если в конкретной интерпретации не имеет смысла;
• не симметрично, антисимметрично, так как для всех a≠b не выполняется одновременно aRb и bRa;
• транзитивно, так как если a начальник b и b начальник c , то a начальник c .

Определите свойства отношения R i , заданного на множестве M i матрицей, если:

1. R 1 «иметь один и тот же остаток от деления на 5»; M 1 множество натуральных чисел.
2. R 2 «быть равным»; M 2 множество натуральных чисел.
3. R 3 «жить в одном городе»; M 3 множество людей.
4. R 4 «быть знакомым»; M 4 множество людей.
5. R 5 {(a,b):(a-b) - чётное; M 5 множество чисел {1,2,3,4,5,6,7,8,9}.
6. R 6 {(a,b):(a+b) - чётное; M 6 множество чисел {1,2,3,4,5,6,7,8,9}.
7. R 7 {(a,b):(a+1) - делитель (a+b)} ; M 7 - множество {1,2,3,4,5,6,7,8,9}.
8. R 8 {(a,b):a - делитель (a+b),a≠1}; M 8 - множество натуральных чисел.
9. R 9 «быть сестрой»; M 9 - множество людей.
10. R 10 «быть дочерью»; M 10 - множество людей.

Операции над бинарными отношениями

Пусть R 1 , R 1 есть отношения, заданные на множестве A .

объединение R 1 ∪ R 2: R 1 ∪ R 2 = {(a,b) : (a,b) ∈ R 1 или (a,b) ∈ R 2 } ;

пересечение R 1 ∩ R 2: R 1 ∩ R 2 = {(a,b) : (a,b) ∈ R 1 и (a,b) ∈ R 2 } ;

разность R 1 \ R 2: R 1 \ R 2 = {(a,b) : (a,b) ∈ R 1 и (a,b) ∉ R 2 } ;

универсальное отношение U: = {(a;b)/a ∈ A & b ∈ A}. ;

дополнение R 1 U \ R 1 , где U = A × A;

тождественное отношение I: = {(a;a) / a ∈ A};

обратное отношение R -11 : R -11 = {(a,b) : (b,a) ∈ R 1 };

композиция R 1 º R 2: R 1 º R 2: = {(a,b) / a ∈ A&b ∈ B& ∃ c ∈ C: aR 1 c & c R 2 b}, где R 1 ⊂ A × C и R 2 ⊂ C × B;

Определение. Степенью отношения R на множестве A называется его композиция с самим собой.

Обозначение:

Определение . Если R ⊂ A × B , то R º R -1 называется ядром отношения R .

Теорема 3.1. Пусть R ⊂ A × A – отношение, заданное на множестве A .

1. R рефлексивно тогда и только тогда, (далее используется знак ⇔) когда I ⊂ R.
2. R симметрично ⇔ R = R -1 .
3. R транзитивно ⇔ R º R ⊂ R
4. R антисимметрично ⇔ R ⌒ R -1 ⊂ I .
5. R антирефлексивно ⇔ R ⌒ I = ∅ .

Задача 3.4 . Пусть R - отношение между множествами {1,2,3} и {1,2,3,4}, заданное перечислением пар: R = {(1,1), (2,3), (2,4), (3,1), (3,4)}. Кроме того, S - отношение между множествами S = {(1,1), (1,2), (2,1), (3,1), (4,2)}. Вычислите R -1 , S -1 и S º R. Проверьте, что (S º R) -1 = R -1 , S -1 .

Решение.
R -1 = {(1,1), (1,3), (3,2), (4,2), (4,3)};
S -1 = {(1,1), (1,2), (1,3), (2,1), (2,4)};
S º R = {(1,1), (1,2), (2,1), (2,2), (3,1), (3,2)};
(S º R) -1 = {(1,1), (1,2), (1,3), (2,1), (2,2), (2,3)};
R -1 º S -1 = {(1,1), (1,2), (1,3), (2 ,1), (2,2), (2,3)} = (S º R) -1 .

Задача 3.5 . Пусть R отношение «...родитель...», а S отношение «...брат...» на множестве всех людей. Дайте краткое словесное описание отношениям:

R -1 , S -1 , R º S, S -1 º R -1 и R º R.

Решение.

R -1 - отношение«...ребёнок...»;

S -1 - отношение«...брат или сестра...»;

R º S - отношение «...родитель...»;

S -1 º R -1 - отношение «...ребёнок...»

R º R - отношение «...бабушка или дедушка...»

Задачи для самостоятельного решения

1) Пусть R - отношение «...отец...», а S - отношение «...сестра...» на множестве всех людей. Дайте словесное описание отношениям:

R -1 , S -1 , R º S, S -1 º R -1 , R º R.

2) Пусть R - отношение «...брат...», а S - отношение «...мать...» на множестве всех людей. Дайте словесное описание отношениям:

R -1 , S -1 , S º R, R -1 º S -1 , S º S.

3) Пусть R - отношение «...дед...», а S - отношение «...сын...» на множестве всех людей. Дайте словесное описание отношениям:

4) Пусть R - отношение «...дочь...», а S - отношение «...бабушка...» на множе- стве всех людей. Дайте словесное описание отношениям:

5) Пусть R - отношение «...племянница...», а S - отношение «...отец...» на множестве всех людей. Дайте словесное описание отношениям:

R -1 , S -1 , S º R, R -1 º S -1 , R º R.

6) Пусть R - отношение «сестра...», а S - отношение «мать...» на множестве всех людей. Дайте словесное описание отношениям:

R -1 , S -1 , R º S, S -1 º R -1 , S º S.

7) Пусть R - отношение «...мать...», а S - отношение «...сестра...» на множе- стве всех людей. Дайте словесное описание отношениям:

R -1 , S1, R º S, S1 º R1, S º S.

8) Пусть R - отношение «...сын...», а S - отношение «...дед...» на множестве всех людей. Дайте словесное описание отношениям:

R -1 , S -1 , S º R, R -1 º S -1 , R º R.

9) Пусть R - отношение «...сестра...», а S - отношение «...отец...» на множе- стве всех людей. Дайте словесное описание отношениям:

R -1 , S -1 , R º S, S -1 º R -1 , S º S.

10) Пусть R - отношение «...мать...», а S - отношение «...брат...» на множестве всех людей. Дайте словесное описание отношениям:

R -1 , S -1 , S º R, R -1 º S -1 , R º R.

1. Рефлексивность:

2. Слабая рефлексивность:

3. Сильная рефлексивность:

4. Антирефлексивность:

5. Слабая антирефлексивность:

6. Сильная антирефлексивность:

7. Симметричность:

8. Антисимметричность:

9. Асимметричность:

10. Сильная линейность:

11. Слабая линейность:

12. Транзитивность:

Рефлексивность, свойство бинарных (двуместных, двучленных) отношений, выражающее выполнимость их для пар объектов с совпадающими членами (так сказать, между объектом и его "зеркальным отражением"): отношение R называется рефлексивным, если для любого объекта х из области его определения выполняется xRx. Типичные и наиболее важные примеры рефлексивных отношений: отношения типа равенства (тождества, эквивалентности, подобия и т.п.: любой предмет равен самому себе) и отношения нестрогого порядка (любой предмет не меньше и не больше самого себя). Интуитивные представления о "равенстве" (эквивалентности, подобии и т.п.), очевидным образом наделяющие его свойствами симметричности и транзитивности, "вынуждают" и свойство Р., поскольку последнее свойство следует из первых двух. Поэтому многие употребительные в математике отношения, по определению Р. не обладающие, оказывается естественным доопределить таким образом, чтобы они становились рефлексивными, например, считать, что каждая прямая или плоскость параллельна самой себе, и т.п.

Глава 1. Элементы теории множеств

1.1 Множества

Наиболее простая структура данных, используемая в математике, имеет место в случае, когда между отдельными изолированными данными отсутствуют какие-либо взаимосвязи. Совокупность таких данных представляет собой множество . Понятие множества является неопределяемым понятием. Множество не обладает внутренней структурой. Множество можно представить себе как совокупность элементов, обладающих некоторым общим свойством. Для того чтобы некоторую совокупность элементов можно было назвать множеством, необходимо, чтобы выполнялись следующие условия:

Должно существовать правило, позволяющее определить, принадлежит ли указанный элемент данной совокупности.

Должно существовать правило, позволяющее отличать элементы друг от друга. (Это, в частности, означает, что множество не может содержать двух одинаковых элементов).

Множества обычно обозначаются заглавными латинскими буквами. Если элемент

Если каждый элемент множества

Подмножество

Используя понятие множества можно построить более сложные и содержательные объекты.

1.2 Операции над множествами

Основными операциями над множествами являются объединение , пересечение и разность .

Определение 1 . Объединением

Определение 2 . Пересечением двух множеств называется новое множество

Определение 3 . Разностью двух множеств называется новое множество

Если класс объектов, на которых определяются различные множества обозначить

1.3 Декартово произведение множеств

Одним из способов конструирования новых объектов из уже имеющихся множеств является декартово произведение множеств .

Определение 4 . Декартовым (прямым) произведением множеств

Определение 5 . Степенью декартового произведения

Замечание. Если все множества

1.4 Отношение

Определение 6 . Подмножество

Определение 7 . Мощность множества кортежей, входящих в отношение

Замечание. Понятие отношения является очень важным не только с математической точки зрения. Понятие отношения фактически лежит в основе всей реляционной теории баз данных. Как будет показано ниже, отношения являются математическим аналогом таблиц . Сам термин "реляционное представление данных", впервые введенный Коддом , происходит от термина relation , понимаемом именно в смысле этого определения.

Т. к. любое множество можно рассматривать как декартовое произведение степени 1, то любое подмножество, как и любое множество, можно считать отношением степени 1. Это не очень интересный пример, свидетельствующий лишь о том, что термины "отношение степени 1" и "подмножество" являются синонимами. Нетривиальность понятия отношения проявляется, когда степень отношения больше 1. Ключевыми здесь являются два момента:

Во-первых , все элементы отношения есть однотипные кортежи. Однотипность кортежей позволяет считать их аналогами строк в простой таблице, т.е. в такой таблице, в которой все строки состоят из одинакового числа ячеек и в соответствующих ячейках содержатся одинаковые типы данных. Например, отношение, состоящее из трех следующих кортежей { (1, "Иванов", 1000), (2, "Петров", 2000), (3, "Сидоров", 3000) } можно считать таблицей, содержащей данные о сотрудниках и их зарплатах. Такая таблица будет иметь три строки и три колонки, причем в каждой колонке содержатся данные одного типа.

В противоположность этому рассмотрим множество { (1), (1,2), (1, 2,3) }, состоящее из разнотипных числовых кортежей. Это множество не является отношением ни в

Бинарные отношения.

Пусть A и B – произвольные множества. Возьмем по одному элементу из каждого множества, a из A, b из B и запишем их так: (сначала элемент первого множества, затем элемент второго множества – т.е. нам важен порядок, в котором берутся элементы). Такой объект будем называть упорядоченной парой . Равными будем считать только те пары, у которых элементы с одинаковыми номерами равны. = , если a = c и b = d. Очевидно, что если a ≠ b, то ≠ .

Декартовым произведением произвольных множеств A и B (обозначается: AB) называется множество, состоящее из всех возможных упорядоченных пар, первый элемент которых принадлежит A, а второй принадлежит B. По определению: AB = { | aA и bB}. Очевидно, что если A≠B, то AB ≠ BA. Декартово произведение множества A само на себя n раз называется декартовой степенью A (обозначается: A n).

Пример 5. Пусть A = {x, y} и B = {1, 2, 3}.

AB = {, , , , , }.

BA = {<1, x>, <2, x>, <3, x>, <1, y>, <2, y>, <3, y>}.

AA = A 2 = {, , , }.

BB = B 2 = {<1, 1>, <1, 2>, <1, 3>, <2, 1>, <2, 2>, <2, 3>, <3, 1>, <3, 2>, <3, 3>}.

Бинарным отношением на множестве M называется множество некоторых упорядоченных пар элементов множества M. Если r – бинарное отношение и пара принадлежит этому отношению, то пишут: r или x r y. Очевидно, r Í M 2 .

Пример 6. Множество {<1, 2>, <2, 2>, <3, 4>, <5, 2>, <2, 4>} является бинарным отношением на множестве {1, 2, 3, 4, 5}.

Пример 7. Отношение ³ на множестве целых чисел является бинарным отношением. Это бесконечное множество упорядоченных пар вида , где x ³ y, x и y – целые числа. Этому отношению принадлежат, например, пары <5, 3>, <2, 2>, <324, -23> и не принадлежат пары <5, 7>, <-3, 2>.

Пример 8. Отношение равенства на множестве A является бинарным отношением: I A = { | x Î A}. I A называется диагональю множества A.

Поскольку бинарные отношения являются множествами, то к ним применимы операции объединения, пересечения, дополнения и разности.

Областью определения бинарного отношения r называется множество D(r) = { x | существует такое y, что xry }. Областью значений бинарного отношения r называется множество R(r) = { y | существует такое x, что xry }.

Отношением, обратным к бинарному отношению r Í M 2 , называется бинарное отношение r -1 = { | Î r}. Очевидно, что D(r ‑1) = R(r), R(r ‑1) = D(r), r ‑ 1 Í M 2 .

Композицией бинарных отношений r 1 и r 2 , заданных на множестве M, называется бинарное отношение r 2 o r 1 = { | существует y такое, что Î r 1 и Í r 2 }. Очевидно, что r 2 o r 1 Í M 2 .

Пример 9. Пусть бинарное отношение r задано на множестве M = {a, b, c, d}, r = {, , , }. Тогда D(r) = {a, c}, R(r) = {b, c, d}, r ‑1 = {, , , }, r o r = {, , , }, r ‑1 o r = {, , , }, r o r ‑1 = {, , , , , , }.

Пусть r – бинарное отношение на множестве M. Отношение r называется рефлексивным , если x r x для любого x Î M. Отношение r называется симметричным , если вместе с каждой парой оно содержит и пару . Отношение r называется транзитивным , если из того, что x r y и y r z следует, что x r z. Отношение r называется антисимметричным , если оно не содержит одновременно пары и различных элементов x ¹ y множества M.

Укажем критерии выполнения этих свойств.

Бинарное отношение r на множестве M рефлексивно тогда и только тогда, когда I M Í r.

Бинарное отношение r симметрично тогда и только тогда, когда r = r ‑1 .

Бинарное отношение r на множестве M антисимметрично тогда и только тогда, когда r Ç r ‑1 = I M .

Бинарное отношение r транзитивно тогда и только тогда, когда r o r Í r.

Пример 10. Отношение из примера 6 является антисимметричным, но не является симметричным, рефлексивным и транзитивным. Отношение из примера 7 является рефлексивным, антисимметричным и транзитивным, но не является симметричным. Отношение I A обладает всеми четырьмя рассматриваемыми свойствами. Отношения r ‑1 o r и r o r ‑1 являются симметричными, транзитивными, но не являются антисимметричными и рефлексивными.

Отношением эквивалентности на множестве M называется транзитивное, симметричное и рефлексивное на М бинарное отношение.

Отношением частичного порядка на множестве М называется транзитивное, антисимметричное и рефлексивное на М бинарное отношение r.

Пример 11. Отношение из примера 7 является отношением частичного порядка. Отношение I A является отношением эквивалентности и частичного порядка. Отношение параллельности на множестве прямых является отношением эквивалентности.