XIX Белоусов А.И., Ткачев СБ. Дискретная математика (1081422), страница 10
Текст из файла (страница 10)
Обратно, пусть бинарное отношение р на множестве А таково, что р~ С р, а (х, у) Е р и (у, «) Е р. Тогда в силу определения композиции бинарных отношений на множестве А (х, «) Е рз. Поскольку р~ С р> то (х, «) Е р. Таким образом, из того, что (х, у) Е р и (у, «) Е р, следует, что (х,«) Е р, т.е. бинарное отношение р на множестве А транзитивно. ~ Доказанное свойство целесообразно испольэовать для проверки транзитивности бинарного отношения р на некотором множестве в тех случаях, когда построение квадрата р является более легкой задачей по сравнению с исследованием свойства транзитивности р на основе определения.
Бинарное отношение р на множестве А называется тьаопзным, если для любых х, у Е А, отличных друг от друга и таких, что х р у, найдется «, отличный и от х и от у, такой, что х р « и «ру. Образно говоря, для любой пары элементов, связанных плотным ошношением, всегда найдется третий элемент, который „встраивается между ними" н связан с каждым из них тем же отношением. Так, отношения неравенства (строгого и нестрогого) на множествах рациональных и действительных чисел плотны, но аналогичные отношения на множествах целых и натуравьшах чисел плотными не являются. В самом деле, каковы бы ни были рациональные (или действительные) числа х и у, из того, что х < у, следует, что существует число «, отличное как от х, так и от у, такое, что х < «< у.
Например, 1. МНОЖЕСТВА И ОТНОШЕНИЯ подходит число» = (х+у)/2. Но для целых чисел тп и та+ 1 такого „промежуточного" целого числа нет. Если р — плотное бинарное отношение на множестве А и для некоторых х,у е А имеет место ярд, то найдется» Е А, такой, что хф», уф» и хр», «ру. Отсюда в силу определения композиции отношений следует, что «~Р у. Значит, из (х, р) Е р следует (х, у) Е рз, т.е. р С рз. Итак, если р плотно, то оно содержится в своем квадрате. Напомним, что для транзитивного бинарного отношения рз С р.
Следовательно, если бинарное отношение р одновременно плотно и транзитивно, то р = рз. Среди всех бинарных отношений на произвольном множестве выделяют классы отношений в зависимости от свойств, которыми зти отношения обладают. Бинарное отношение на некотором множестве нжтывают' 1) эквиваленптностпью, если оно рефлексивно, симметрично и транзитивно; 2) тполерантпностпью, если оно рефлексивно и симметрично; 3) порядком (или часптичным порядком), если оно рефлексивно, антисимметрично и транзитивно; 4) предпорядком (или кваэипорядком), если оно рефлексивно и транзитивно; 5) отправим порядком, если оно иррефлексивно, антисимметрично и транзитивно; 6) сптрогим предпорядком, если оно иррефлексивно и транзитивно.
Определенные вьппе бинарные отношения называют отаношениями эквивалентпностпи, тпояерантпностпи, пор*дка (частпичного порядка), предпорядка (квазипор*дка), стпрогого пор*дка, стпрогого предпор*дна. Пример 1.13. а. Бинарное отношение параллельности двух прямых или двух плоскостей в евклидовой геометрии, если 1.б.
Специальные свойства бинлрвых отношений 67 считать каждую прнмую (плоскость) параллельной самой себе, есть отношение эквивалентности. б. Бинарное отношение р на множестве всех непустых подмножеств некоторого множества У, длл которого А р В тогда и только тогда, когда У А О В Ф сВ, является толерантностью. Это А отношение рефлексивно и симметрично, но не транзитивно. Действительно, из того, что А П В ф И и В П С ус И, никак не следует, Рис. 1.9 что А О С ~ сВ (рис. 1.9).
в. Примером отношения порядка нвллетсл есгусесгпвеммый числовой ггорлдом', т.е. отношение неравенства на любом числовом множестве. г. На множестве натуральных чисел М зададим бинарное отношение а~Ь, означающее, что а делит Ь (а является делителем Ь). Это отношение рефлексивно, поскольку любое число ввллетсв делителем самого себя. Покажем антисимметричнсть. Пусть а делит 6 и в то же время Ь делит а. Тогда найдется натуральное число Фм такое, что Ь = аФВ и найдется 8з, такое, что а = Ыз. Отсюда 6 = 6$з$1, что на множестве натурвльных чисел возможно только при 11 = $з = 1. Следовательно, а = 6. Покажем транзитивность.
Если а делит 6, а Ь делит с, то найдутся натуральные числа $м $з, такие, что Ь = а$1 и с = 6|з. Отсюда имеем с = а81$з, т.е. а — делитель с. Таким образом, „отношение делимости" на множестве М является отношением порядка. Если распространить это отношение на множество целых чисел, то оно будет уже только предпорядком, поскольку терлетсл снойство антисимметричности. Например, 2 делится на — 2 и — 2 делится на 2, однако 2 ф.
-2. 'В (1] гто отношение незвано просто есшесшегннмм порядном. Поскольку в дискретной математике нвм пршсодится иметь дело со многвми порядкеми нв нечисювых множествах, мы все время будем говорить „естественный числовой порядок", подчерквввя тем самым, что речь идет об отношенви порядка на множестве действительных чисел (или об его огранвченвв нв мнолсествв рациональных, целых иги нвтурвяьных чисел). 68 1. МНОЖЕСТВА И ОТНОШЕНИЯ д. Рассмотрим множество 2А всех подмножеств множества А. Покажем, что отношение включения С на множестве 2А есть порядок. Это отношение рефлексивно, так как для любого множества Х справедливо включение Х С Х.
Поскольку для любых двух множеств Х и У из Х С У и У С Х следует, что Х = У, рассматриваемое отношение антисимметрично. Из определения включения вытекает, что если Х С У и У С Я, то Х С Е. Следовательно, отношение транзитивно. е. Отношение строгого неравенства на числовом множестве, равно как и отношение строгого включения множеств, есть отношение строгого порядка. ж.
В качестве примера отношения строгого предпорядка можно привести отношение „строгой достижимости" на некотором множестве населенных пунктов: пункт А считаем строго достижимым из отличного от него пункта В, если есть доррга (автомобильная, железная и т.п.) из А в В, причем принимается, что никакой пункт не является строго достижимым из себя самого. ф Трнннитинн симметричность Рис. 1.10 Отношения толерантности, эквивалентности, предпорядка и порядка — важнейшие в современной математике. Связь 1.6. Сиециааьиые свойства Вииариых отиотеиий 69 между этими четырьмя классами бинарных отношений показана на рис.
1.10. Можно сказать, что эквивалентность есть транзитивная толерантность или симметричный предпорядок. Порядок же есть антисимметричный предпорядок. Для любого бинарного отношения р С Аз можно построить отношение р' следующим образом: х р' у тогда и только тогда, когда х = у или существует последовательность хе, хм ..., х„, и > 1, такая, что хо = х, х„ = у и для каждого 1 = О,п-1 выполняется х; рхиь1. В частности, если (х, у) Е р, т.е. х ру, то это означает, что приведенное условие выполняется при п = 1.
Следовательно, (х, у) Е р', т.е. р С р'. Отношение р' называют рефлексивно-перанэипеивным замыканием бинарного отношения р на соответствующем множестве. Можно также обозначить ро=Ыл, р1=р, р"=р р" 1, п>1, и тогда е'=О Отношение р' является рефлексивным, так как Ыл С р'. Докажем его транзитивность. Пусть для каких-то х,у,«выполняется х р" у и у р' «. Докажем, что х р' «. Будем считать, что элементы х, у, «попарно различны (так как при х = у или у = «доказывать нечего).
Тогда существуют последователь- НОСТИ Х ХО~ ХМ ° ° Хо У И У вЂ” УЕ У1 У~а «1 таКИЕ что х; р х+1 для каждого 1 = О, и-1 и уу р уй+1 для каждого Я = О, тт~-1 (п, тп > 1). В итоге получаем последовательность «е, ..., «„, «„+и ..., «о+о,, где «о = х, «„= у, «в+ = «, «; = х; для всякого 1 = 1, н-1, «а+~ =у для всякого у =Т, та-Т, такую, что «; р«;+1 для любого Осси-'т, * р' *. 70 1.
МНОЖЕСТВА И ОТНОШЕНИЯ 1.7, Отношении эквивалентности Пусть А — произвольное множество. Семейство (В;)еег непустых и попарно не пересекающихся мноэсеств называют разбиением множества А, если объединение мноэсеств семейства [В,),ву равно А, т.е. ЦВ; = А. вИ Сами множества В; называют элеменгпами [или членами) разбиения [Вч)вег. Например, множества [О, 1/3), (1/3, 2/3) и [2/3, 1) образуют разбиение отрезка (О, Ц. Тривиальными разбиениями А являются, по определению, разбиение (А), состоящее только из самого А, и разбиение, состоящее из всех одноэлементных подмножеств множества А.
Пусть р — эквивалентность на множестве А и х е А. М~южество всех элементов А, эквивалентных х, т.е. множество 1у: у р х), называют классом эквивалентпносгпи по отношению р и обозначают (х]р. Отметим, что в силу рефлексивности для любого элемента х Е А класс эквивалентности не пуст, так как х Е [х]р. Теорема 1.4.
Для любого отношения эквивалентности на множестве А множество классов эквивалентности образует разбиение множества А. Обратно, любое разбиение множества А задает на нем отношение эквивалентности, для которого классы эквивалентности совпадают с элементами разбиения. ~ Покажем, что отношение эквивалентности р на множестве А определяет некоторое разбиение этого множества. Убедимся вначале, что любые два класса эквивалентности по отношению р либо не пересекаются, либо совпадают. Пусть два класса эквивалентности [х]о и [у]р имеют общий элемент х е (х),> й [у]р. Тогда х р х и э р у.
В силу симметричности отношения р имеем х р х, и тогда х р л и х р у. В силу транэитивности отношения р получим х р у. Пусть и Е (х)р, тогда й р х. Так как х р у, то й р у и, следовательно, Й Е (у)р. 71 1.7. Отношения эквивалентности Обратно, если Ь Е [у]р, то в силу симметричности р получим 5 р у, у р х и в силу транзитивности — Ь р х, т.е. тт Е [х]р. Таким образом [х]и = [у]р Итак, любые два не совпадающих класса эквивалентности не пересекаются. Так как для любого х Е А справедливо х Е [х]р (поскольку х р х), т.е. каждый мемент множества А принадлежит некоторому классу эквивалентности по отношению р, то множество всех классов эквивалентности по отношению р образует разбиение исходного множества А.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
