Лекция № 3. Отношения и их свойства.

1. Основные понятия и определения.

Определение. Подмножество называется местным ( мерным) отношением на множестве А. Говорят, что элементы находятся в отношении , если .

Одноместное (одномерное) отношение – это просто некоторое подмножество А. Такие отношения называют признаками. Говорят, что обладает признаком , если и . Свойства одноместных отношений – это свойства подмножеств А, поэтому для случая термин “отношения” употребляется редко.

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

Пример 1. Бинарные отношения на множестве .

а) Отношение “ ” выполняется для пар и не выполняется для пары .

б) Отношение “иметь общий делитель, не равный единице” выполняется для пар и не выполняется для пар .

в) Отношение “быть делителем” выполняется для пар и не выполняется для пар .

Пример 2. Бинарные отношения на множестве точек координатной плоскости.

а) Отношение “быть равноудалёнными от начала координат” выполнятся для пар точек и , но не выполнятся для пары точек и .

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

в) Отношение “быть удалёнными на разное расстояние от начала координат” выполняется для всех точек, для которых не выполняется отношение, описанное в пункте “б”.

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

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

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

Пример 3. Для конечного множества матрицы отношений из примера 1 (а – в) приведены в следующих таблицах.

а)

б)

в)

Поскольку отношения на множестве А задаются подмножествами А², для отношений можно определить те же операции, что и для множеств. Например, отношение “ ” является объединением отношений “<” и “=”.

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

Непосредственно из определения следует, что . Например, для отношения “ ” обратным является отношение “ ”.

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

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

Главная диагональ матрицы рефлексивного отношения содержит только единицы.

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

Главная диагональ матрицы рефлексивного отношения содержит только нули.

Например, отношения “ ” и “иметь общий делитель” являются рефлексивными. Отношения “ ” и “иметь сына” являются антирефлексивными. Отношение “быть симметричным относительно оси абсцисс” не является ни рефлексивным, ни антирефлексивным: точка плоскости симметрична сама себе, если лежит на этой оси, и не симметрична себе, если не лежит на ней.

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

Матрица симметричного отношения симметрична относительно главной диагонали: для любых .

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

Отношение “быть симметричным относительно оси абсцисс” является симметричным: если первая точка симметрична второй относительно этой оси, то и вторая точка симметрична первой. Отношение “ ” является антисимметричным. Действительно, если и , это означает, что .

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

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

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

Замечание. В отличие от отношений рефлексивности и симметричности, для отношения транзитивности не формулируется противоположного понятия (антитранзитивности).

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

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

Если отношение транзитивно, то, очевидно, (и наоборот). Например, отношение “быть делителем” транзитивно для любой цепочки элементов и само является транзитивным замыканием этого отношения.

Если отношение не транзитивно, то .

Например, транзитивным замыканием отношения “быть сыном” является отношение “быть прямым потомком”, включающее в себя понятия “быть сыном”, “быть внуком”, “быть правнуком” и так далее.