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

Отношение, обратное к данному. Пусть F - бинар­ное отношение на множестве А. Тогда бинарное отношение на множестве А, состоящее из всех таких пар (а, b), что (b, а) Î Р, называется обратным (или инверсией) для F и обозначается через  .

Таким образом, по определению

.

Например, если Fзадано равенством (*), то

 = {(1,1), (2,2), (6,6), (2,1), (6,1), (6,2)}.

Как уже отмечалось, отношение F является областью истинности предиката ^пх делит у". Легко видеть, что   является областью истинности предиката " х делится на у ".

Заметим, что если бинарное отношение F задано диаграм­мой, то диаграмма обратного к нему отношения полу­чается из данной '''обращением стрелок", т. е. для получения диаграммы отношения   нужно в диаграмме отношения Fкаждую стрелку a ·→· b заменить на стрелку а ·· b.

Для иллюстрации обратимся снова к бинарному отношению F, заданному равенством (*). Его диаграмма построена на рис. 8.

Диаграмма отношения  в этом случае выглядит как на рис. 10.

Очевидно, что любое бинарное отношение Fна множестве имеет обратное   и

.

Композиция. Пусть F и S - бинарные отношения, опре­деленные на множестве А. Тогда их композицией называется бинарное отношение  , состоящее из всех пар (х,у) элементов множества А, для которых во множестве А су­ществует элемент z такой, что (x, z) Î S и (z,у) Î S.

Таким образом, по определению

или

Пример. Пусть А = {а, b,с}, где а, b,с- различные элементы и F = {(а,а),(b,с)}, S = {(а, а), (а, b), (с, а), (с, b)}. Тогда F S = {(а, а), (а, b), (b, а), (b, b)}.

Примечание, Очевидно, что для отношений Fи S, ука­занных в предыдущем примере, равенство F S = S F не верно.

Объединение, пересечение и разность бинарных отношений. Пусть F и S - какие-нибудь бинарные отношения на некотором множестве А. Тогда, по определению, каждое из отношений F и S является подмножеством множества А× А. Отсюда следует, что если применить к F и S одну из опера­ций ("объединение ", "пересечение " либо "разность "), то снова получим подмножество множества А × А, т. е. - бинарное отношение на множестве А.

Это означает, что можно говорить об операциях "объеди­нения", "пересечения" и "разности" над бинарными отноше­ниями на данном множестве А и использовать такие же символы для обозначения результатов этих операций как в теории множеств, т.е. Ç, È и \.

Таким образом, по определению, имеем:

а) - объединение отношений F и S;

b) - пересечение отношений F и S;

c) - разность отношений F и S.

Пример. А, F и S- такие, как и в пункте 2. Тогда ,  и .

Свойства бинарных отношений

Отношение F на множестве А называется рефлексивным, если (x, x) Î F для любого x Î A, т.е. если D Í F либо в другой записи: F - рефлексивно тогда и только тогда, когда .

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

Отношение x > y не рефлексивно, однако отношение х ≥ у будет рефлексивным. Геометрически множество F, изобража­ющее множество точек плоскости, принадлежащих данному отношению, содержит все точки прямой у = х.

Отношение F на множестве А называется симметрич­ным, если из того, что пара (x, у) Î F следует, что (у, x) Î F для любых х, у Î   А:

,

или

.

Заметим, что если А = R, т. е. бинарное отношение задано множестве действительных чисел, то свойство симметричности имеет наглядное геометрическое выражение:

множество пар действительных чисел, принадлежащих симметричному отношению, изображается множеством то­чек, симметричных относительно прямой у = х (рис. 11).

Отношение F называется транзитивным, если из того, что (x, у) Î F и (у, z) Î F следует, что пара (x, z) Î F для любых элементов х, у, z Î А, или

.

Например, отношение "больше" для действительных чисел транзитивно: если х > у и у > z, то и х > z.

Отношение F называется антисимметричным, если из того, что (х,у) Î F и (у, x) Î F следует, что x = у, т.е.

.

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

Предложение. Пусть F - произвольное бинарное отно­шение на некотором множестве А. Тогда:

1) F- рефлексивно Û D Í F, где D - диагональ на множестве А;

2) F- симметрично Û ;

3) F- транзитивно Û ;

4) F- антисимметрично Û .

Докажем, например, утверждение 2).

Пусть F симметрично на множестве А и (х, у) Î .Тогда (у, х) Î F, откуда в силу cсимметричности отношения F следует, что (х,у) Î F, и, значит,  .

Докажем обратное включение.

Пусть (x, y) Î F. Отсюда в силу симметричности от­ношения F следует, что (у, х) Î F, откуда, по определе­нию, (х, у) Î . Следовательно, . Таким образом, .

Этим доказана импликация

F - симметрично Þ  .

Докажем обратную импликацию.

Пусть и (х, у) Î F для некоторой пары (х,у) Î А × А. Тогда в силу равенства получим, что (х, у) Î , откуда, по определению, следует (у, х) Î F. Таким образом,

для любой пары (x, у) Î A× A и, значит, F - симметрично.

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

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

  Легко видеть, что известное отношение ≤ ("меньше либо равно") является отношением частичного порядка на любом множестве чисел.

Другим классическим примером этого типа отношений яв­ляется отношение Í "включения" на множестве Р(А) всех подмножеств произвольного фиксированного множества А.

Бинарное отношение F на множестве А называется отно­шением строгого порядка, если оно антирефлексивно ((а, а) Ï F для любого а Î A), транзитивно и удовлетво­ряет дополнительному условию

.

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

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

Фраза: " - частично упорядоченное множество" означает, что на множестве A задано отношение частичного порядка ≤.

Вместо слов "частично упорядоченное множество" исполь­зуется также сокращенная запись "ч.у. множество".

Пусть - ч.у. множество. Элементы а, b Î А называ­ются сравнимыми, если выполняется хотя бы одно из условий а ≤ b либо b ≤ а.

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

Пусть - ч.у. множество. На множестве А зададим новое бинарное отношение ≥ по правилу:

.

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

Заметим, что если взять порядок, двойственный к ≥, то получим исходный порядок ≤.

 Ч.у. множество  называется двойственным к ч.у. множеству .

 Пусть F - некоторое утверждение о ч.у. множествах, сфор­мулированное в общелогических терминах (и терминах отношения частичного порядка).

Утверждение , полученное из Ф заменой всех вхождений знака ≤. на знак двойственного к нему отношения, называется утверждением, двойственным к Ф.

В теории ч.у. множеств имеет место интересный факт, от­носящийся к теоремам этой теории.

Принцип двойственности. Если некоторое утверждение Ф верно для всех упорядоченных множеств (т.е. является теоремой теории ч.у. множеств), то двойственное к нему утверждение также верно для всех ч.у. множеств.

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

Принцип двойственности позволяет "экономить на доказа­тельствах" (избавляет от проведения лишней работы).

Справедливость его имеет место в силу того, что утверж­дение Ф верно в ч.у. множестве   тогда и только тог­да когда двойственное к нему утверждение имеет место в ч.у. множестве .

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

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

Пусть Ф - утверждение, о котором говорится выше. Его можно представить в виде импликации Р Þ S двух предло­жений (Р - посылка, S - заключение утверждения Ф).

Тогда утверждение будет выглядеть так:

Пусть теперь утверждение Ф верно в любом частично упо­рядоченном множестве.

Пусть - произвольное частично упорядоченное мно­жество. Покажем, что  верно в А. Для этого нужно убе­диться в том, что утверждение  является следствием утверждения   (об элементах множества А). Применим ме­тод вспомогательной гипотезы. Предположим, что  верно в . Тогда  верно в двойственном ч.у. множестве .

Далее, очевидно, что , т.е. Р верно в  . Отсюда, поскольку импликация P Þ S верна в любом ч.у. множестве, то S верно в  , откуда следует, что верно в двойственном ч.у. множестве .

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

 Ниже будут приведены примеры применения принципа двойственности.

 Пусть  - произвольное ч.у. множество.

Элемент а Î А называется минимальным, если из х ≤ а следует x = а для любого х Î А.

Двойственным образом получаем определение максималь­ного элемента:

Элемент а называется максимальным, если из х ≥ а сле­дует х = а для любого х Î А.

Это означает, что при построении предложения , двой­ственного к Ф, необходимо заменить на всех местах слово "ми­нимальный" на "максимальный" и обратно.

Элемент а называется наименьшим, если а ≤ х для всех х Î А.

Двойственное понятие:

Элемент а называется наибольшим, если а ≥ х для всех х Î А.

Примеры:

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

2. Покажем, что если в ч.у. множестве  существует наименьший элемент а, то он единственен. При этом во мно­жестве А никаких других наименьших элементов, отличных от а, не существует.

Действительно, пусть a - наименьший элемент в А.

Предположим, что b также является наименьшим в А. Тогда, с одной стороны, а ≤ b, поскольку а - наименьший в А, а с другой - b ≤ а. Отсюда в силу свойства антисиммет­ричности отношения ≤ следует, что а = b.

Далее, пусть с - произвольный минимальный элемент в А. Тогда а ≤ с, поскольку а - наименьший, откуда в силу опре­деления минимального элемента получим, что а = с.

Отсюда по принципу двойственности справедливо следу­ющее предложение: "Если ч.у. множество   содержит наибольший элемент, то кроме него во множестве А никаких ни наибольших, ни максимальных элементов не существует".

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

§ 10. Отношение эквивалентности

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

Для обозначения эквивалентности используется, как прави­ло, стандартный знак ~. Например, запись x ~ y означает, что х находится в данном отношении ~ с у.

Простейшим примером отношения эквивалентности на множестве X может служить отношение равенства между элементами этого множества.

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

П р и м е р 1. Пусть т Î Z и m > 1. (Z - множество всех целых чисел). Определим бинарное отношение Fна множестве Z как область истинности предиката Р(х, у):

" х - у делится на т".

Это означает, что

xFy Û

либо в краткой записи

xFy Û

  Покажем, что F - эквивалентность на множестве Z.

1. Рефлексивность отношения F.

Поскольку , то для любого числа x Î Z, откуда следует, что

2. Симметричность отношения F.

Пусть xFy для некоторых чисел х, у Î Z. Тогда сущест­вует число k Î Z такое, что x – y = km, откуда y – x =(- k) m, т. е.  и, значит, yFx.

3. Транзитивность отношения F.

Пусть xFy и у Fz для некоторых чисел x, у, z Î Z. Тогда  и , где .

Отсюда получаем

.     1

 

Следовательно, и, значит, xFz.               

П р и м е р 2. Пусть А, В- множества и f: A ® B - отображение. Определим на множестве А бинарное отношение S по правилу

для любых элементов .

Простая проверка показывает, что S - эквивалентность на множестве А.

Это отношение называют ядром отображения f.