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

Пусть 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 является отношением эквивалентности и частичного порядка. Отношение параллельности на множестве прямых является отношением эквивалентности.

Базовые понятия и утверждения

1. Множества и операции над ними. Подмножеством понимают объединение в единое целое определенных вполне различаемых объектов. Объекты при этом называютэлементами образуемого ими множества.

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

Запись означает, чтоявляется элементом множества
; в противном случае пишут
.

Множество называют конечным , если оно содержит конечное число элементов, ибесконечным , если оно содержит бесконечное число элементов. Множество, не содержащее элементов, называютпустым и обозначают символом
.

Число элементов конечного множества
называют егомощностью и обозначают
.

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

Например, запись
означает, что множество
содержит два элемента - числа
и.

Если каждый элемент множества есть элемент множестваB , то говорят, чтоестьподмножество , и пишут:
.

Заметим, что пустое множество
считают подмножеством любого множества.

Если
и
, то говорят, что множестваиравны , и пишут:
.

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

Множество всех подмножеств множества
называют егобулеаном и обозначают
.

Например, если
, то

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

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

2. Множество, состоящее из тех и только тех элементов, которые принадлежат как множеству , так и множеству, называютпересечением A и B и обозначают
, т.е.
.

Если
, то множестваиназываютнепересекающимися .

3. Множество, состоящее из всех элементов множества , не принадлежащих множеству, называютразностью A и B и обозначают
, т.е.
.

4. Обычно в конкретных рассуждениях всякое множество рассматривают как подмножество некоторого достаточно широкого множества, которое называют универсальным . Множество элементов универсального множества, не принадлежащих множеству, называютдополнением и обозначают, т.е.
. Из определения следует, что
.

5. Множество, состоящее из упорядоченных пар
, в которых- элемент множества, а- элемент множества, называютд екартовым произведением множеств A и B и обозначают
, т.е..

Удобным приемом наглядного изображения операций являются диаграммы Эйлера - Венна. На них множества представлены плоскими фигурами (чаще всего кругами). Области, соответствующие множествам, полученным в результате операции, обычно выделяют цветом. На рис. 1.1 приведены диаграммы Эйлера - Венна, иллюстрирующие некоторые из введенных операций.

В качестве примеранайдем объединение, пересечение, разность и декартово произведение множеств
и
.

Поскольку
,
, то
,
,
,.

Пусть задано универсальное множество . Тогда для любых множеств
выполняются следующиесвойства :

коммутативные законы :

1.
; 2.
;

ассоциативные законы :

дистрибутивные законы :

законы идемпотентности :

7.
; 8.
;

законы де Моргана :

9.
; 10.
;

законы нуля :

11.
; 12.
;

законы единицы :

13.
; 14.
;

законы поглощения :

15.
; 16.
;

законы дополнения :

17.
; 18.
;

закон двойного дополнения :

19.
.

О том, как доказываются эти равенства, можно узнать во второй части данного параграфа.

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

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

Пересечением множеств
называют множество, любой элемент которого является элементом каждого из данных множеств. Обозначение:
или .

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

В частном случае одинаковых сомножителей декартово произведение
обозначают
.

Например, если
, то

Приведем без доказательств утверждения о числе элементов конечных множеств .

1. Если между конечными множествами исуществует взаимно-однозначное соответствие, то
.

2. Если

также конечно и

Например,если
, то множество
имеет мощность
.

3. Если
- конечные попарно-непересекающиеся множества, то множество
также конечно и

Это утверждение называют правилом суммы .

4. Если
- конечные множества, то множествотакже конечно и

Последнее равенство называется формулой включений и исключений . В частных случаях двух и трех множеств она принимает вид:

Заметим, что формула включений и исключений действует и в том случае, когда множества
попарно не пересекаются (в этом случае все слагаемые в правой части формулы, содержащие пересечения множеств, обнуляются и формула трансформируется в правило суммы).

Пусть, например,
,
,
, причем
, а
. Тогда
можно найти по правилу суммы:, а для поиска
нужно использовать формулу включений и исключений:.

Пример 1.В группе из 100 туристов 65 человек знают английский язык, 55 человек знают французский и 38 человек знают оба языка. Сколько туристов в группе знает хотя бы один из этих языков?

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

Упражнение 1.1.Из 100 студентов-лингвистов польский язык изучают 42, чешский - 25, венгерский - 36, польский и чешский - 15, польский и венгерский - 14, чешский и венгерский - 12, польский, чешский и венгерский - 5. Сколько студентов не изучают ни одного из перечисленных языков?

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

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

Упражнение 1.2. Найти все разбиения множества
и множества
.

2. Бинарные отношения на множестве. Бинарные отношения -простой и вместе с тем очень важный объект дискретной математики.

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

Для обозначения бинарных отношений, как правило, будем использовать строчные буквы греческого алфавита:
и т.п.

Пусть - некоторое бинарное отношение на множестве
. Если
, то говорят, чтоисвязаны бинарным отношениеми пишут
.

Пример 2. Пусть
. Тогда

и следующие множества могут служить примерами бинарных отношений на множестве
:

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

Определенное на множестве
бинарное отношение:

рефлексивно, если для
выполняется
;

симметрично , если для
из
следует
;

антисимметрично , если для
из
и
следует
;

транзитивно, если для
из
и
следует
.

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

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

Определение. Пусть- отношение эквивалентности на множестве
и- элемент
. Классом эквивалентности элементапо бинарному отношениюназывают множество
.

Например, множества
,
,

по отношению, а
,
,
- классы эквивалентности элементов
по.

Упражнение 1.3.На множестве
определены бинарные отношения
и
. Задать эти бинарные отношения перечислением элементов, указать свойства этих бинарных отношений, определить, являются ли они отношениями эквивалентности (если являются, то найти классы эквивалентности их элементов).

Перечислим свойства классов эквивалентности , присущие любому отношению эквивалентности, определенному на произвольном множестве
.

1. Класс эквивалентности любого элемента множества
- непустое множество.

2. Классы эквивалентности любых двух элементов множества
либо не пересекаются, либо совпадают.

3. Объединение классов эквивалентности всех элементов множества
совпадает с самим множеством
.

Доказательство этих свойств приведено во второй части параграфа.

Из свойств классов эквивалентности следует утверждение: в сякое отношение эквивалентности, заданное на множестве
, порождает разбиение множества
на классы эквивалентности этого отношения.

Для иллюстрации этого утверждения вновь обратимся к бинарным отношениям ииз примера 2.

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

Для классов эквивалентности
,
,
элементов
по отношениюимеем: классы эквивалентности элементов
исовпадают и при этом не имеют общих элементов с классом эквивалентности элемента, объединение всех классов совпадает с множеством
. Следовательно, отношениепорождает разбиение множества
на два подмножества:
,
.

Рассмотрим еще один важный класс бинарных отношений.

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

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

Например, отношениями порядка являются отношенияииз примера 2 (- линейного,- частичного).

Пример 3. Рассмотрим на множестве
бинарное отношение, определяемое условием. Это отношение рефлексивно, антисимметрично и транзитивно, и, значит, является отношением порядка, причем частичного, поскольку элементне связан с элементоми элементне связан с элементом.

Связанные определения

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

Бинарные отношения могут обладать различными свойствами, такими как

Виды отношений

• Рефлексивное транзитивное отношение называется отношением квазипорядка.
• Рефлексивное симметричное транзитивное отношение называется отношением эквивалентности .
• Рефлексивное антисимметричное транзитивное отношение называется отношением (частичного) порядка .
• Антирефлексивное антисимметричное транзитивное отношение называется отношением строгого порядка .
• Полное антисимметричное (для любых x, y выполняется xRy или yRx) транзитивное отношение называется отношением линейного порядка.
• Антирефлексивное асимметричное отношение называется отношением доминирования.

Виды двухместных отношений

• Обратное отношение [уточнить ] (отношение, обратное к R) - это двухместное отношение, состоящее из пар элементов (у, х), полученных перестановкой пар элементов (х, у) данного отношения R. Обозначается: R −1 . Для данного отношения и обратного ему верно равенство: (R −1) −1 = R.
• Взаимо-обратные отношения (взаимообратные отношения) - отношения, являющиеся обратными друг по отношению к другу. Область значений одного из них служит областью определения другого, а область определения первого - областью значений другого.
• Рефлексивное отношение - двухместное отношение R, определённое на некотором множестве и отличаю­щееся тем, что для любого х этого множества элемент х на­ходится в отношении R к самому себе, то есть для любого элемента х этого множества имеет место xRx. Примеры рефлексивных отношений: равенство , одновременность , сходство.
• Антирефлексивное отношение (Иррефлексивное отношение, отметим, что также как антисимметричность не совпадает с несимметричностью иррефлексивность не совпадает с нерефлексивностью.) - двухместное отношение R, определённое на некотором множестве и отличаю­щееся тем, что для любого элемента х этого множества неверно, что оно находится в отношении R к самому себе (неверно, что xRx), то есть возможен случай, что элемент множества не находится в отно­шении R к самому себе. Примеры нерефлексвных отношений: «заботиться о», «развлекать», «нервировать».
• Транзитивное отношение - двухместное отношение R, оп­ределенное на некотором множестве и отличающееся тем, что для любых х, у, z этого множества из xRy и yRz следует xRz (xRy&yRzxRz). Примеры транзитивных отношений: «больше», «меньше», «равно», «подобно», «выше», «севернее».
• Нетранзитивное отношение [уточнить ] - двухместное отношение R, оп­ределенное на некотором множестве и отличающееся тем, что для любых х, у, z этого множества из xRy и yRz не следует xRz ((xRy&yRzxRz)). Пример нетранзитивного отношения: «x отец y»
• Симметричное отношение - двухместное отношение R, определённое на некотором множестве и отличающееся тем, что для любых элементов х и у этого множества из того, что х находится к у в отношении R (xRy), следует, что и у находится в том же отношении к х (уRx). Примером симметричных отношений могут быть равенство (=), отношение эквивалентности , подобия , одновременности, некоторые отношения родства (например, отношение братства).
• Антисимметричное отношение - двухместное отношение R, определённое на некотором множестве и отличающееся тем, что для любых х и у из xRy и xR −1 y следует х = у (то есть R и R −1 выполняются одновременно лишь для равных между собой членов).
• Асимметричное отношение [уточнить ] - двухместное отношение R, определённое на некотором множестве и отличающееся тем, что для любых х и у из xRy следует yRx. Пример: отношение «больше» (>) и «меньше» (<).
• Отношение эквивалентности (отношение тождества [уточнить ] , отношение типа равенства) - двухместное отношение R между предметами х и у в предметной области D, удовлетворяющее следующим аксиомам (условиям): Таким образом, отношение типа равенства является одновременно рефлексивным, симметричным и транзитивным. Примеры: равенство, равномощность двух множеств, обмениваемость товаров на рынке, подобие , одновременность . Пример отношения, которое удовлетворяет аксиоме (3), но не удовлетворяет аксиомам (1) и (2): «больше».
• Отношения порядка - отношения, обладающие только некоторыми из трёх свойств отношения эквивалентности. В частности, отношение рефлексивное и транзитивное, но несимметричное (например, «не больше») образует «нестрогий» порядок. Отношение транзитивное, но нерефлексивное и несимметричное (например, «меньше») - «строгий» порядок.
• Функция - двухместное отношение R , определенное на некотором мно­жестве, отличающееся тем, что каждому значению x отно­шения xRy y . Пример: «y отец x ». Свойство функциональности отно­шения R записывается в виде аксиомы: (xRy и xRz )→(y ≡z ). Поскольку каждому значению x в выражениях xRy и xRz соответствует одно и то же значение, то y и z совпадут, окажутся одними и теми же. Функциональное отношение однозначно, поскольку каждому значению x отношения xRy соответствует лишь одно-единственное значение y , но не наоборот.
• Биекция (одно-однозначное отношение) - двухместное отношение R , определенное на некотором мно­жестве, отличающееся тем, что в нём каждому значению х соответствует единственное значение у , и каждому значению у соответствует единственное значение х . Одно-однозначное отношение является частным случаем однозначного отношения.
• Связанное отношение - это двухместное отношение R , определённое на некотором множестве, отличающееся тем, что для любых двух различных элементов х и у из этого множества, одно из них находится в отношении R к другому (то есть выполнено одно из двух соотношений: xRy или yRx ). Пример: отношение «меньше» (<).

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

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

Часто вместо объединения, пересечения и дополнения отношений говорят об их дизъюнкции, конъюнкции и отрицании.

Например, , , то есть объединение отношения строгого порядка с отношением равенства совпадает с отношением нестрого порядка, а их пересечение пусто.

Кроме перечисленных важное значение имеют ещё операции обращения и умножения отношений, определяемые следующим образом.

Если , то обратным отношением называется отношение , определённое на паре , и состоящее из тех пар , для которых . Например, .

Пусть теперь , . Произведением отношений , называется отношение такое, что

Если , и , то произведение отношений не определено. Если же отношения рассматривать определённые на каком-то множестве , то такой ситуации не возникает.

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

Бинарные отношения и называются перестановочными, если . Несложно заметить, что для любого бинарного отношения , определённого на , , где символом обозначено равенство, определённое на . Однако равенство не всегда справедливо.

Имеют место следующие тождества:

Отметим, что аналоги последних двух тождеств для не имеют места.

Некоторые свойства отношения можно определить, используя операции над отношениями:

См. также

Литература

• А. И. Мальцев. Алгебраические системы. - М .: Наука, 1970.

Wikimedia Foundation . 2010 .

Смотреть что такое "Бинарное отношение" в других словарях:

Бинарное отношение - . Иначе: двуместное или двойственное. «Бинарным отношением на множестве X» называется подмножество упорядоченных пар элементов из X. Примерами Б.о. являются равенство (=), неравенства (< или >), отношение включения A Ì B.… … Экономико-математический словарь

бинарное отношение - Иначе: двуместное или двойственное. «Бинарным отношением на множестве X» называется подмножество упорядоченных пар элементов из X. Примерами Б.о. являются равенство (=), неравенства (), отношение включения A ? B. В широком смысле слова… … Справочник технического переводчика

Двуместный предикат на заданном множестве. Под Б. о. иногда понимают подмножество множества упорядоченных пар (а, 6) элементов заданного множества А. Б. о. частный случай отношения. Пусть. Если, то говорят, что элемент находится в бинарном… … Математическая энциклопедия

В логике то, что в отличие от свойства характеризует не отдельный предмет, а пару, тройку и т.д. предметов. Традиционная логика не рассматривала О.; в современной логике О. пропозициональная функция от двух или большего числа переменных. Бинарным … Философская энциклопедия

отношение - ОТНОШЕНИЕ множество упорядоченных п ок индивидов (где п > 1), т.е. двоек, троек и т.д. Число п называется «местностью», или «арностью», О. и, соответственно, говорят о n местном (п арном) О. Так, например, двуместное О. называют… … Энциклопедия эпистемологии и философии науки

В теории потребления это формальное описание способности потребителя сравнивать (упорядочивать по желательности) разные наборы товаров (потребительские наборы). Чтобы описать отношение предпочтения, не обязательно измерять желательность… … Википедия

У этого термина существуют и другие значения, см. Отношение. Отношение математическая структура, которая формально определяет свойства различных объектов и их взаимосвязи. Отношения обычно классифицируются по количеству связываемых объектов … Википедия

У этого термина существуют и другие значения, см. Отношение. Отношение в логике первого порядка двух и более аргументный предикат (многоместный предикат), двух и более предикатное свойство. Знак отношения: R.[уточнить] В терминах отношений… … Википедия

У этого термина существуют и другие значения, см. Эквивалентность. Отношение эквивалентности () на множестве это бинарное отношение, для которого выполнены следующие условия: Рефлексивность: для любого в, Симметричность: если … Википедия

Эту статью следует викифицировать. Пожалуйста, оформите её согласно правилам оформления статей. Бинарное отношение на мно … Википедия

Систематизация свойств.

Каждое бинарное (двухместное) отношение характеризуется свойствами рефлексивности, симметричности и транзитивности. Полное или частичное отсутствие этих свойств в отношении отражается в их наименовании приставками соответственно "анти " и "не ". Определённым сочетаниям этих базовых свойств даны свои специальные наименования; например, антисимметричное и антирефлексивное отношение называется асимметричным.

Свойство рефлексивности рассматривается для одного элемента множества.

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

Если отношение имеет место не для любой такой пары, то оно называется не рефлексивным . Нерефлексивно отношение любит , определенное на области пар людей, так как не все люди любят себя.

Если отношение не имеет места ни для одной такой пары, то отношение называется анти рефлексивным . Отношение больше, определённое на области пар материальных предметов, антирефлексивно, поскольку ни один предмет не больше самого себя.

Свойство симметричности рассматривается для двух разных элементов множества.

Отношение называется симметричным , когда для любых пар предметов из области его определения верно, что, когда это отношение x и y , то оно имеет место и в паре (y,x) . Отношение ровесник симметрично, так как для любых двух людей верно, что, если первый ровесник второго, то и второй ровесник первого.

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

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

Свойство транзитивности рассматривается для трёх разных элементов множества.

Отношение называется транзитивным , если оно обязательно имеет место для пары  (x,z) при условии его наличия в парах (x,y) и (y,z) . Отношение ровесник транзитивно, так как для любых трёх людей, если один человек ровесник другого, а тот ровесник третьего, первый непременно является ровесником третьего.

Отношение называется не транзитивным , если это верно не для любыхпредметов из области определения отношения. Нетранзитивно отношение любит , потому что неверно, что оно имеет место в паре (x,z) всегда, когда оно наличествует в парах (x,y) и (y,z), т. е. не обязательно, чтобы первый человек любил третьего, когда первый любит второго, а второй любит третьего.

Отношение называется ан титранзитивным , если в области определения отношения не существует таких предметов, для которых это было бы верно. Антитранзитивно отношение отец , потому что не найдется таких трёх пар указанного вида, чтобы это отношение имело место во всех трёх. Никогда не может быть так, что первый человек - отец второго, второй - отец третьего, и при этом первый - отец третьего.

Определения.

• Определение . Отношение ρ называется рефлексивным , если каждый элемент x∈A находится в этом отношении сам с собой: xρx для всех x∈A . На языке кванторов: ∀ x∈A: xρx
• Определение. Отношение ρ называется симметричным , если из того, что xρy следует, что yρx: ∀x,y∈A: xρy⟹ yρx
• Определение. Отношение ρ называется транзитивным , если из того, что xρy и yρz , следует, что xρz : ∀x,y,z∈A: (xρy ∧ yρz) ⟹ xρz
  • не рефлексивным , если: ¬∀ x∈A: xρx
  • не симметричным , если: ¬∀x,y∈A: xρy⟹ yρx
  • не транзитивным , если: ¬∀x,y∈A: (xρy∧ yρz)⟹ xρz
    • анти рефлексивным (иррефлексивным), если: ∀x∈A: ¬(xρx)
    • анти симметричным , если: ∀x,y∈A : (xρy⟹ yρx) ⟹ x=y
    • анти транзитивным , если: ∀x,y,z∈A: (xρy∧ yρz) ⟹ ¬(xρz)
• Определение. Бинарное отношение на некотором множестве называют эквивалентностью (отношением эквивалентности), если оно рефлексивно, симметрично и транзитивно.