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

 

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

Марк Аврелий

Глава 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 = < Ф, М >, Ф Í МхМ называется отношением антисимметричности, если