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

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

Марк Аврелий

Глава 4. Отношения

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

ЦЕЛИ

Освоив эту главу, студенты должны:

· знать способы задания отношений;

· знать основные свойства отношений;

· уметь решать задачи на доказательство тождеств с отношениями;

· знать понятия отношения рефлексивности, симметричности, трназитивности и эквивалентности;

· уметь выполнять разбиение множеств;

· иметь понятие об отношении порядка.

4.1. Основные понятия отношений

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

В отличие от понятия множества, понятие отношения является определенным понятием. Запись j = < Ф, М > - называется отношением, если ФÍМ², т.е. ФÍМ х М, где j — отношение; Ф — график отношения; М — область задания отношения, представляющая из себя неупорядоченное множество. Отношение такого типа называется бинарным. Если ФÍМ^k, то отношение называется k-арным.

Отношение j с областью задания М называется отношением на множестве М.

Пусть имеем элемент графика, представлдяющий собой пару < a, b >ÎФ. Тогда говорят, что если пара < a, b >ÎФ, то существует отношение a j b, в котором элементы a и b находятся в некоторой связи. Другими словами, элемент a находится в отношении j к элементу b. Если a и b - элементы множества М (a, bÎM), то a j b будет являться истинным или ложным высказыванием.

Рассмотрим некоторые примеры отношений.

1) Пусть дана область задания отношения М = { 1, 2, 3, 4 } и график отношения Ф = { < 1, 1 >, < 1, 2 >, < 2, 2 >, < 3, 2 > }. Тогда можно получить М² = М × М = { < 1, 1 >, < 1, 2 >, < 1, 3 >, < 1, 4 >, < 2, 1 >, < 2, 2 >,..., < 4, 4 > }. На рис. 4.1 точками изображено отношение j = < Ф, М >.

Рис. 4.1. Пример задания отношения на множестве М

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

Отношение также может быть задано в виде графа (рис. 4.2).

Рис. 4.2. Пример задания отношения в виде графа

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

Например, запись х j y ® x < y означает, что j есть «отношение меньше» между элементами x и y.

Тогда высказывание «5 j 3» является ложным отношением, а высказывание 3 j 4 является истинным отношением.

Важным в отношениях является понятие диагонали j = <DМ, M> на множестве М. Это такое отношение, когда все точки графика находятся на диагонали. Например, пусть в отношении j = < DМ, М >, М = { 1, 2, 3, 4 } и график отношения DМ = {< 1, 1 >, < 2, 2 >, < 3, 3 >, < 4, 4 >}. На рис. 4.3 показано графическое представление такого отношения.

Рис. 4.3. Пример отношения

4.2. Основные свойства отношений

Отношение j = <Ф, М> называется полным отношением, если Ф = М², т.е. ("x,yÎM)(x j y). Другими словами, для любых элементов x, y, принадлежащих множеству М, истинно высказывание, что элементы x, y находятся в отношении j.

Отношение j = < Ф, М > называется пустым, если график Ф является пустым множеством. То есть j = < Æ, М >. Другими словами, имеется область задания отношения, на котором не задан график отношения.

Отношение j = < Ф, М > называется отношением равенства, если Ф = DМ. В теоретико-множественном плане можно записать, ("x,yÎM)(x j y ® x = y). Например задано j = < Ф, М >, М = { 1, 2, 3 }, Ф = {<1, 1>, <2, 2>, <3, 3>}. Данное отношение является отношением равенства.

Отношение j = < Ф, М > называется отношением неравенства, если Ф = М²\DМ, т.е. ("x,yÎM)(x j y ® x ¹ y). Например задано j = < Ф, М >, М = { 1, 2, 3 }, Ф = {< 1, 2 >, < 2, 3 >, < 3, 1 > }. Данное отношение является отношением неравенства. Отношения «5 > 3» и «3 < 10» также являются примерами отношения неравенства.

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

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

Объединением отношений j₁ и j₂ на множестве М называется отношение j₃:

j₁Èj₂ = j₃, j₁ = < Ф₁, М >, j₂ = < Ф₂, М >.

j₃ = < Ф₁ÈФ₂, М >,

<a, b> Î Ф₁È Ф₂ ® <a, b> Î Ф₁Ú <a, b> Î Ф₂ & a, bÎ M.

Например, пусть имеем два отношения: j₁ = < Ф₁, М >, j₂ = < Ф₂, М >,

М = { 2, 3, 4 }, Ф₁ = { <2, 1>, <2, 2>, <2, 4> },

Ф₂ = { < 2, 1 >, < 2, 3 >, < 4, 4 > }.

Тогда объединение этих отношений j₃ = < Ф₃, М >, Ф₃ = Ф₁È Ф₂ = { <2,1>, <2,2>, <2,4>, <2,3>, <4,4> }.

Отметим, что для операции объединения над отношениями справедлива следующая запись:

x (j₁Èj₂) y ® x j₁ y Ú x j₂ y.

Пересечением отношений j₁ и j₂ на множестве М называется отношение j₃, для которого:

j₁Çj₂ = j₃, j₁ = < Ф₁, М >, j₂ = < Ф₂, М >,

j₃ = < Ф₁ÇФ₂, М >,

<a, b> Î Ф₁Ç Ф₂ ® <a, b> Î Ф₁& <a, b> Î Ф₂ & a, bÎ M.

Например, пусть имеем два отношения: j₁ = < Ф₁, М >, j₂ = < Ф₂, М >, M = {1, 2}, j₁ = <{<1, 1>, <1, 2>}, {1, 2}>, j₂ = < {< 1, 2 >, < 2, 2 >}, { 1, 2 }>,

Тогда пересечение этих отношений j₃ = <Ф₃, М> = <{< 1, 2 >}, {1, 2}>.

Отметим, что для операции пересечения над отношениями справедлива следующая запись:

x (j₁Çj₂) y ® x j₁ y & x j₂ y.

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

Отношение j₃ называется разностью отношений j₁ и j₂, если

j₁ = <Ф₁, М>, j₂ = <Ф₂, М>, j₃ = j₁\j₂ = <Ф₁\Ф₂, М>,

<a, b> Î Ф₁ \ Ф₂ ® <a, b> Î Ф₁ & <a, b> Ï Ф₂ & a, bÎ M.

Например, пусть имеем два отношения: j₁ = <Ф₁, М>, j₂ = <Ф₂, М>, M = {1, 2, 3}, Ф₁ = {<1, 2>, <2, 2>, <3, 3>}, Ф₂ = {<1, 1>, <2, 2>, <3, 3>}. Тогда Ф₃ = Ф₁\Ф₂ = {<1, 2>}. Разность этих отношений j₃ = <Ф₃, М> = < {<1, 2>}, {1, 2, 3}>.

Отметим, что для операции разности над отношениями справедлива следующая запись:

x (j₁\j₂) y ® x j₁ y & x y.

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

Если j = < Ф, М >, то инверсия j^-1 = < Ф^{-1, М >.}

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

х j^-1 у ® у j х.

Например, для отношения j = <Ф, М>, М = {1, 2, 3}, Ф = {<1, 1>, <1, 2>, <1, 3>}, инверсия j^-1 = <Ф^-1, М> и Ф^-1 = {<1, 1>, <2, 1>, <3, 1>}.

Композицией двух отношений является новое отношение, у которого компонируют графики отношений.

j₁ = <Ф₁, M>, j₂ = <Ф₂, M>.

j₁•j₂ = <Ф₁•Ф₂, М>

Например, j₁ = <Ф₁, M>, j₂ = <Ф₂, M>, М = {1, 2, 3}, Ф₁ = {<1, 1>, <1, 2>, <1, 3>, <3, 3> }, Ф₂ = {<1, 1>, <2, 3>, <3, 1>, <3, 2>}. Тогда композиция графиков этих отношений равна Ф₁•Ф₂={<1, 1>,<1, 3>,<1, 2>, <3, 2>, <3, 1>}.

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

Введем операцию, меняющую область задания отношений.

Пусть j = < Ф, М > и $АÍМ, тогда сужением отношения j на множестве А называется новое отношение

j₁ = < ФÇА², А >

Например, j = < Ф, М >, М = { 1, 2, 3 }, Ф = {< 1, 1 >, < 1, 2 >, <1, 3> }, A = {1, 2}. Тогда j₁ = <{< 1, 1 >, < 1, 2 >}, {1, 2}>.

4.4. Основные свойства специальных отношений

Отношение j = < Ф, М > называется отношением рефлексивности, если

("хÎМ)(х j х).

Другими словами, если для любого элемента хÎМ истинно высказывание х j х, то j - отношение рефлексивности. Это отношение является унарной операцией, т.е. операцией над одним элементом. Примерами отношения рефлексивности являются отношение равенства и отношение параллельности (x = x, x || x). Очевидно, что отношение перпендикулярности между прямыми х и у не является отношением рефлексивности. Отношение j рефлексивно тогда и только тогда, когда DМÍФ, т.е. когда все точки диагонали принадлежат графику отношений.

Отношение j = < Ф, М > называется отношением антирефлексивности, если

("хÎМ)Ø(х j х),

т.е. DМÇФ = Æ.

Например, выражения x > x, x ¹ x, x ^ x являются отношениями антирефлексивности.

Отношение j = < Ф, М > называют отношением симметричности, если

("х,уÎМ)(х j у ® у j х).

Отношение симметричности является бинарной операцией. Например, выражения х=у, хïêу являются отношением симметричности.

Для графика отношения симметричности справедливо Ф = Ф^-1. Например, a = b ® b = a, a ïêb ® b ïê a.

Отношение j = < Ф, М >, Ф Í МхМ называется отношением антисимметричности, если

х j у Ù х ¹ у ® Ø(у j х).

Очевидно, что отношение j = < Ф, М > антисимметрично тогда и только тогда, когда

ФÇФ^-1 Í DМ.

Например, высказывания больше, меньше, неравно являются примерами отношений антисимметричности (x > y, x ¹ y).

Отношение j = < Ф, М > называется отношением транзитивности, если

("х,у,zÎM)(х j у & у j z ® x j z).

Например, если х = у & y = z ® x = z, то j - отношение транзитивности. Для отношения параллельности справедливо: x êê y & y êê z ® x êê z, следовательно, оно является отношением транзитивности.

Для отношения транзитивности (иногда говорят транзитивное отношение) справедливо:

Ф • Ф Í Ф.

Примеры:

1. Полное отношение j =<М², М> является транзитивным отношением. Пусть М = <1, 2>, тогда M² = {<1, 2>, <2, 1>, <1, 1>, <2, 2>} и M² • M² = {<1, 1>, <1, 2>, <2, 2>, <2, 1>}, M² • M² Í M².

2. Пустое отношение является носителем всех свойств.

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

Отношение j называется отношением эквивалентности, если оно рефлексивно (DМ Í Ф), симметрично (Ф = Ф^-1) и транзитивно (Ф•Ф = Ф). Иногда имея в виду отношения рефлексивности, симметричности, транзитивности и т.п., говорят, что эти отношения соответственно рефлексивности, симметричности, транзитивности и т.п.

j ~ j ~ — знак эквивалентности.

Отношение равенства является отношением эквивалентности, т.к. оно рефлексивно(a = a), симметрично (a = b ® b = a) и транзитивно (a = b & b = c ® a = c) на множестве M={a,b,c}. Отношение параллельности является отношением эквивалентности, т.к. оно рефлексивно (a ïï a), симметрично (a ïê b ® b ïê a) и транзитивно (a êê b & b êê c ® a êê c) на множестве M={a,b,c}. Отношения больше, меньше, неравно, перпендикулярности и т.п. не являются отношениями эквивалентности, т.к. не обладают в совокупности тремя свойствами рефлексивности, симметричности и транзитивности.

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

4.5. Разбиение множеств

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

Приведем формальное определение разбиения.

Система W множеств называется разбиением одного множества М, если она удовлетворяет четырем условиям:

1) ("X Î W)(X Í M).

2) ("X Î W)(X ¹ Æ).

3) ("X, Y Î W)(X ¹ Y ® X Ç Y = Æ).

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

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

Разбиение системы W множества М называется поэлементным, если каждый блок разбиения является одноэлементным множеством.

Наример, множество М = {1, 2, 3, 4} может быть разбито на четыре одноэлементных подмножества W = {M₁, M₂, M₃, M₄}, M₁ = {1}, M₂ = {2}, M₃ = {3}, M₄ = {4}.

Например,множество A = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10} можно разбить на 4 блока: M = {X1, X2, X3, X4}, где X1 = {1, 3, 5, 7, 9}, X2 = {2}, X3 = {4}, X4 = {6, 8, 10}.

Разбиение системы называется целым, если W = {М}. Для предыдущего примера получим W = {1, 2, 3, 4}.

Поэлементное и целое разбиения называются тривиальными. Остальные разбиения, если они существуют, называются не тривиальными.

Примеры:

1. Пустое множество имеет единственное разбиение, т.е. пустую систему множеств (W = Æ).

2. Одноэлементное множество М = {a} имеет единственное разбиение W = М = {a}, которое одновременно является и целым, и поэлементным.

3. Множество М = { a, b } имеет два разбиения: W₁ = {M₁(a), M₂(b)}, W₂ = {M}.

4. Множество М = {a, b, c} имеет пять разбиений следующего вида: W₁ = {a, b, c}, W₂ = {{a}, {b}, {c}}, W₃ = {{a}, {b,c}}, W₄ = {{b}, {a,c}}, W₅ = {{c}, {a,b}}. Очевидно, что из пяти разбиений два являются тривиальными (W₁, W₂), а три – не тривиальными (W₃ – W₅).

5. Система курсов факультета является разбиением множества студентов, если ни один студент не учится одновременно на двух курсах.

Диаграмма Эйлера-Венна, иллюстрирующая возможное разбиение множества А = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10} на четыре блока, приведена на рис 4.4. Если принять, что можность каждого из подмножеств разбиения пропорциональна величине занимаемого сектора окружности, то тогда можно записать следующее разбиение: X₁ = {1, 2, 3, 4, 5}; X₂ = {6}; X₃ = {7}; X₄ = {8, 9, 10}.

Рис. 4.4 Пример разбиения множества А на четыре блока

Известно, что отношение j на множестве М и разбиение этого множества сопряжены, если высказывание ("х,уÎМ хjу) является истинным, тогда, когда х и у принадлежат одному и тому же разбиению (к одному и тому же блоку разбиения).

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

Теорема Т1. О единственности разбиения, сопряженного с данным отношением.

Если два разбиения множества М сопряжены с одним и тем же отношением на этом же множестве, то они совпадают.

Другими словами, разбиение, сопряженное с данным отношением, единственно.

Теорема Т2. Об отношении, сопряженном с некоторым разбиением.

Если отношение j на множестве М сопряжено с каким-нибудь разбиением этого множества, то j — отношение эквивалентности.

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

Для любого отношения эквивалентности j, на множестве М существует сопряженное с ним разбиение множества М.

Итак, разбиение, сопряженное с данным отношением j существует тогда (Т3) и только тогда (Т2), когда j — отношение эквивалентности, причем в этом случае сопряженное разбиение единственно (Т1).

Теорема Т4. Пусть j — отношение эквивалентности на непустом множестве М, тогда различные классы эквивалентности определяют разбиение множества М.

4.6. Отношение порядка

Отношение порядка связано с отношениями типа £, <, >, ³.

Отношение j называется отношением нестрогого порядка, если оно транзитивно (Ф•Ф = Ф), рефлексивно (DМ Í Ф) и антисимметрично (ФÇФ^-1 Í DМ).

Отношение j называется отношением строгого порядка, если оно транзитивно (Ф•Ф = Ф), и антирефлексивно (DМÇФ = Æ).

Введем понятие отношения связности. Отношение j = <Ф, М> называется связным, если выполняется условие М²\DМ Í ФÈФ^-1.

Отношение j называется отношением совершенно нестрогого порядка, если оно является отношением связности (М²\DМ Í ФÈФ^-1) и является отношением нестрогого порядка.

Отношение j называется отношением совершенно строгого порядка, если оно является отношением связности (М²\DМ Í ФÈФ^-1) и является отношением строгого порядка.

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

Порядок	Транзитивность Ф•ФÍФ	Рефлексивность DМÍФ	Антирефлексивность DМÇФ = Æ	Антисимметричность ФÇФ^-1 ÍDМ	Связность М²\DМÍФÇФ^-1
нестрогий	+	+		+
совершенно нестрогий	+	+		+	+
строгий	+		+
совершенно строгий	+		+		+

Примеры:

1) х j у ® х > у. Данное высказывание говорит о том, что отношение j является отношением совершенно строгого порядка.

2) х j у ® х ³ у. Данное высказывание говорит о том, что отношение j является отношением совершенно нестрогого порядка.

3) "х,у X j Y ® X Í Y. В данном случае имеет отношение нестрогого порядка.

4) "х,у X j Y ® X Ì Y. В данном случае имеет отношение строгого порядка.

5) Отношение равенства на множестве М является нестрогим порядком, причем это самый маленький нестрогий порядок.

6) Отношение строгого порядка можно задать числовой осью х j у. Инверсию строгого порядка можно изобразить перевернутой числовой осью х j^-1 у.

Как видно из приведенных примеров, первое и второе отношения справедливы для высказываний, а третье четвертое – для множеств.

Совершенно нестрогий порядок есть упорядоченная пара < Х, £ >, где отношение £ частично упорядоченное множество Х.

Например, если F есть некоторая система множеств, то < F, £ > есть частично упорядоченное множество. Для любого предложения об упорядоченных множествах можно указать эквивалентное ему предложение об отношениях порядка и обратно.

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

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

1) Никакой элемент не может доминировать самого себя, т.е х >> х — ложно, т.е. имеет место отношение антирефлексивности (DМ Ç Ф = Æ).

2) В каждой паре элементов в точности один элемент доминирует второго, т.е. х >> у и у >> х — взаимоисключается, значит справедливо отношение антисимметричности (ФÇФ^-1ÍDМ).

В отношении доминирования свойство транзитивности не имеет места. Например, если в соревнованиях команда х победила команду у, а команда у победила команду z, то отсюда еще не следует, что команда х обязательно победит команду z. Для кортежей пример отношения доминирования имеет вид: a = <3, 4> >> b = <1,2>, то есть для первых элементов кортежей a и b справедливо: 3 >> 1, а для вторых элементов кортежей a и b справедливо: 4 >> 2.

Существует еще одно отношение порядка, которое называется квазипорядком (от «квази» — почти).

j = <Ф, М> — называется отношение квазипорядка, если оно транзитивно и рефлексивно.

Для отношения квазипорядка справедливо:

Ф•ФÍФ Ù DМÍФ.

Отношение j = <Ф, М> — называется отношением толерантности, если оно рефлексивно (DМ Í Ф) и симметрично (Ф = Ф^-1). Следовательно, для отношения толерантности справедливо:

DМ Í Ф Ù Ф = Ф^-1.

Другими словами для отношения толерантности

(" х ÎМ)(х j х),

(" х, уÎМ)(х j у ® у j х).

Примеры:

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

2) Отношение А j В, где j определяет, что А не старше курсом, чем В, является примером отношения квазипорядка. Так как оно является транзитивным и рефлексивным.

3) Отношение параллельности является отношением толерантности, т.к. оно рефлексивно (a ïï a) и симметрично (a ïê b ® b ïê a) на множестве M = {a, b}.

КОНТРОЛЬНЫЕ ВОПРОСЫ

1. Дайте определение отношения.

2. Как строятся матрица и график отношения j = <Ф, Х>?

3. Перечислите основные операции над отношениями.

4. Что называется инверсией и композицией отношений?

5. Как определить понятие образа и прообраза множества при композиции двух отношений?

6. В каком случае композиция двух отношений j и y будет являться:

а) функциональным отношением;

б) инъективным отношением;

в) биективным отношением?

7. Дайте определение и приведите пример рефлексивного отношения.

8. Дайте определение и приведите пример симметричного отношения.

9. Дайте определение и приведите пример транзитивного отношения.

10. Дайте определение и приведите пример связного отношения.

11. Может ли антисимметричное отношение быть также рефлексивным?

12. Может ли асимметричное отношение быть также рефлексивным?

13. Может ли рефлексивное отношение быть несвязным?

14. Приведите определение и примеры отношения толерантности.

15. Покажите каким образом отношение толерантности связано с отношениями эквивалентности, доминирования и порядка.

ЗАДАНИЯ ДЛЯ САМОСТОЯТЕЛЬНОЙ РАБОТЫ

1. Пусть задано произвольное множество Х = {x, y, z, t}. Задайте произвольное отношение на этом множестве теоретическим, матричным и графическим способом.

2. Пусть заданы произвольные отношения j = <F, X> и y = <P, X>, где X = {x₁, x₂, x₃, x₄, x₅, x₆, x₇}; F = {<x₁, x₂>; <x₁, x₃>; <x₁, x₅>; <x₂, x₃>; <x₂, x₄>; <x₂, x₆>; <x₃, x₂>; <x₃, x₄>; <x₄, x₁>; <x₄, x₄>; <x₅, x₄>; <x₅, x₆>; <x₆, x₁>; <x₆, x₂>;}; P = {<x₁, x₃>; <x₁, x₅>; <x₃, x₆>; <x₃, x₇>; <x₅, x₁>; <x₅, x₆>; <x₆, x₃>; <x₇, x₁>; <x₇, x₇>}.