03. Отношения

Подмножество называется П-местным Отношением на множестве М. Говорят, что находятся в отношении R, если Одноместное отношение — это просто подмножество М. Такие отношения называют признаками: А обладает признаком R, если и Свойства одноместных отношений — это свойства подмножеств М, поэтому для случая П = 1 термин «отношение» употребляется редко. Примером трехместного (или, как говорят, тернарного) отношения является Множество троек нападающих в хоккейной команде. Каждый из нападающих находится в этом отношении со всеми теми игроками, с которыми он играет в одной тройке (один нападающий может, вообще говоря, участвовать более чем в одной тройке).

Наиболее часто встречающимися и хорошо изученными являются двухместные, или Бинарные, отношения. Именно о них будет идти речь в дальнейшем (слово «бинарные» будем опускать). Если А, B находятся в отношении R, это часто записывается как АRb.

Пример 11.

1) Отношения на N: а) отношение £ выполняется для пар (7, 9) и (7,7), но не выполняется для пары (9,7); б) отношение «иметь общий делитель, отличный от единицы» выполняется для пар (6, 9), (4, 2), (2, 4), (4, 4), но не выполняется для пар (7, 9) и (9, 7); в) отношение «быть делителем» (т. е. АRb означает «А — делитель B») выполняется для пар (2, 4) и (4, 4), но не выполняется для пар (4, 2) и (7, 9).

2) Отношения на множестве точек действительной плоскости: а) отношение «находиться на одинаковом расстоянии от начала координат» выполняется для пары точек (3, 4) И (-2, ), но не выполняется для пары точек (3, 4) и (1, 6); это отношение совпадает с отношением «находиться на одной и той же окружности с центром в начале координат»; б) отношение «находиться на разном расстоянии от начала координат» выполняется для тех и только тех пар точек, для которых не выполняется предыдущее отношение; в) отношение «быть симметричным относительно оси Х» выполняется для всех пар точек и Удовлетворяющих условию

3) Отношения на множестве людей: а) «жить в одном городе»; б) «быть моложе»; в) «быть сыном»; Г) «быть знакомым».

Пусть дано отношение R на М. Для любого подмножества естественно определяется отношение R', называемое сужением R на М1, которое получается из R удалением всех пар, содержащих элементы, не принадлежащие М1. ИНаче говоря, Строго говоря, R И R' — Это разные отношения, с разными областями определения. Однако если не возникает разночтений, этот педантизм не соблюдается; например, вполне можно говорить об отношении «быть делителем», не уточняя, задано оно на N Или на каком-либо его подмножестве.

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

Например, для конечного множества {1, 2, 3, 4, 5, 6} матрицы отношений «а», «б», «в» из примера 11, П. 1 приведены в табл. 1а - 1в СОответственно:

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

Поскольку отношения на М задаются подмножествами , для них можно определить те же операции, что и над множествами. Например, отношение «б» из примера 11, П. 1.3 является дополнением отношения «а», отношение £ Является объединением отношений < и равенства.

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

Свойства отношений. Отношение R называется Рефлексивным, если для любого имеет место АRа. Главная диагональ его матрицы содержит только единицы. Отношение R называется антирефлексивным, если ни для какого не выполняется АRа. Главная диагональ его матрицы содержит только нули. Отношения £ и «иметь общий делитель» рефлексивны, отношения < и «быть сыном» — антирефлексивны. Отношение «быть симметричным относительно оси Х» не является ни рефлексивным, ни антирефлексивным: точка плоскости симметрична сама себе, если она лежит на оси Х, и несимметрична сама себе в противном случае.

Отношение R называется Симметричным, если для пары из АRB следует BRа (иначе говоря, для любой пары R выполняется либо в обе стороны, либо не выполняется вообще). Матрица симметричного отношения симметрична относительно главной диагонали: для любых I и J. Отношение R называется Антисимметричным, Если из и следует, что Отношение «быть симметричным относительно оси Х» является симметричным если первая точка симметрична второй, то и вторая симметрична первой. Пример антисимметричного отношения — отношение £: действительно, если И То А = B. Нетрудно убедиться в том, что отношение R симметрично тогда и только тогда, когда

Отношение R называется Транзитивным, если для любых А, B, с ИЗ АRB и АRс следует АRс. Отношения «равенство», £, «жить в одном городе» транзитивны; отношение «быть сыном» нетранзитивно. Отношение «пересекаться», т. Е. «иметь непустое пересечение», заданное на системе множеств, также нетранзитивно. Например, {1, 2} пересекается с {2, 3}, {2, 3} пересекается с {3, 4}, однако {1, 2} и {3, 4} не пересекаются.

Для любого отношения R отношение , называемое Транзитивным замыканием R, определяется следующиХ Образом: АB, если в М существует цепочка из П элементов в которой между соседниМ Элементами выполнено R: еСли R транзитивно, то Действительно, если АRb, То АB (цепочка состоит из двух элемЕНтов А, B), поэтому Еслн же аB, то существует цепочка Но так как R транзитивно, то АКB, поэтому Из включения в обе стороны следует

Транзитивным замыканием отношения «быть сыном» является отношение «быть прямым потомком», являющееся объединением отношений «быть сыном», «быть внуком», «быть правнуком» и т. Д. Транзитивным замыканием отношения «иметь общую стену» для жильцов дома является отношение «жить на одном этаже».

Отношения эквивалентности. Отношение называется Отношением эквивалентности (или просто эквивалентностью), если оно рефлексивно, симметрично и транзитивно.

Пример 12.

1) Отношение равенства Е на любом множестве является отношением эквивалентности. Равенство — это минимальное отношение эквивалентности в том смыслЕ, что при удалении любой пары ИЗ Е (т. е. любой единиЦЫ из диагонали матрицы Е) оно перестает быть рефлексиВНым и, следовательно, уже не является эквивалентностью.

2) Утверждения вида иЛИ состоящие из формул, соединенНЫх знаком равенства, задают бинарное отношение на множестве формул, описывающих суперпозиции элементарных функций (см. пример 10), Это отношение обычНО называется отношением равносильности и определяется следующим образом: формулы равносильны, если они задают одну и ту же функцию. Равносильность, хотя и обозначается знаком =, отличается от отношения равенства Е, так как оно может выполняться для различных формул ВПрочем, можно считать, что знак равенства в таких соотношениях относится не к формулам, а к функциям, которые ими описываются). Отношение Е для формул — это совпадение формул по написанию. Оно называется Графическим равенством.

3) Рассмотрим множество треугольников на плоскости, считая, что треугольник задан, если заданы координаты его вершин. Два треугольника называются конгруэнтными (иногда их называют просто равными), если они при наложении совпадают, т. е. могут быть переведены друг в друга путем некоторого перемещения. Конгруэнтность является отношением эквивалентности на множестве треугольников.

4) Отношение «иметь один и тот же остаток от деления на 7» является эквивалентностью на N. Это отношение выполняется, например, для пар (11, 46), (14, 70) и не выполняется для пар (12, 13), (14, 71).

Пусть на множестве М задано отношение эквивалентности R. ОсуществИМ следующее построение. Выберем элемент и образуем класс (подмножество М) Состоящий из и всех элементов, эквивалентных ; затем выберем элемент и образуем класс , состоящий из и всех элементов, эквивалентных , и т. д. Получится система классов (возможно, бесконечная) такая, что любой элемент из М входит хотя бы в один класс, т. е. Эта система классов обладает следующими свойствами: 1) она образует разбиение, т. е. классы попарно не пересекаются; 2) любые два элемента из одного класса эквивалентны; 3) любые два элемента из разных классов неэквивалентны. Все эти свойства немедленно вытекают из рефлексивности, симметричности и транзитивности R. Действительно, если бы классы, например С1 и С2 пересекались, то они имели бы общий элемент B, эквивалентный и , но тогда из-за транзитивности R было бы , Что противоречит построению С2. Аналогично доказываются другие два свойства.

Построенное разбиение, т. е. система классов называется системой КлаССов эквивалентности по отношению R. Мощность этой системы называется Индексом разбиения. С другой стороны, любое разбиение М на классы определяет некоторое отношение эквивалентности, а именно, отношение «входить в один и тот же класс данного разбиенИЯ».

Пример 13.

1) Все классы эквивалентности по отношению равенства Е состоят из одного элемента.

2) Формулы, описывающие одну и ту же элементарную функцию, находятся в одном классе эквивалентности по отношению равносильности. В этом примере счетны само множество формул, множество классов эквивалентности (т. Е. индекс разбиения) и каждый класс эквивалентности.

3) Разбиение множества треугольников по отношению конгруэнтности имеет континуальный индекс, причем каждый класс также имеет мощность континуум.

4) Разбиение N по отношению «имеТЬ общий остаток от деления на 7» имеет конечный индекс 7 и состоит из 7 счетных классов 0, 7, 14 ...; 1, 8, 15 ...; 2, 9, 16 ...; ...; 6, 13, 20...

Отношения порядка. Отношение называется Отношением нестрогого порядка, если оно рефлексивно, антисимметрично и транзитивно. Отношение называется Отношением строгого порядка, если оно антирефлексивно, антисимметрично и транзитивно. Оба типа отношений называются отношениями порядка. Элементы А, B называются сравнИМыми по отношению порядка R, если выполняется АRb Или BRа. Множество М, на котором задано отношенИЕ порядка, называется полностью упорядоченным, если любые два элемента М сравнимы, и частично упорядоченным в противном случае.

Пример 14.

1) Отношения £ и ³ для чисел являются отношениями нестрогого порядка, отношения < и > — отношением строгого порядка. Оба отношения полностью упорядочивают множества N и R.

2) Определим отношения £ и < на следующим образом: , если , если и хотя бы в одной координате I выполнено Эти отношения определяют частичный порядок на : и (5, 0, 0) не сравнимы.

3) На системе подмножеств множества М отношение включения Задает нестрогий частичный порядок, а отношение строгого включения Ì задает строгий частичныЙ Порядок. Например, {1, 2} Ì {1, 2, 3}, а {1, 2} и {1, 3. 41 не сравнимы.

4) Отношение подчиненности на предприятии задает строгий частичный порядок. В нем несравнимыми являются сотрудники разных отделов.

5) Пусть в списке букв конечного алфавита А порядок букв зафиксирован, т. е. всегда один и тот же, как, например, в русском или латинском алфавите или в алфавите цИФр. Тогда этот список определяет полное упорядочение бУКв, которое назовем отношением предшествования и обозначим ( если предшествует в списке букв). На основе отношения предшествования букв строится отношение предшествования слов, определяемое следующим образом. Пусть даны слова и Тогда , если и только если либо 1) и (B, G, D — некоторые слова, возможно, пустые, и — буквы), либо 2) где B — непустое слово. Это отношение задает полное упорядочение множества всех конечных слов в алфавите А, которое называется Лексикографическим упорядочением слов.

Наиболее известным примером лексикографического упорядочения является упорядочение слов в словарях. Например, лес лето (случай 1 определения: (B = Ле, С т, G пусто, D = о), поэтому слово «лес» расположено в словаре раньше слова «лето»; лес лесть (случай 2 определения: B = Ть).

Если рассматривать числа в позиционных системах счисления (например, в двоичной или десятичной) как слова в алфавите цИФр, то их лексикографическое упорядочение совпадает с обычным, еслИ все сравнимые числа имеют одинаковое число разрядоВ. В общем же случае эти два вИДа упорядочения могут не совпадать: например, 10 < 1073 и 20 < 1073, но 10 1073, а 20 1073. Для того чтобы они совпадали, нужно Выравнять число разрядов у всех сравниваемых чисел, приписывая слева нули. В данном примере при этом получим 0020 1073. Такое выравнивание автоматически происходит при записи целых чисел в ЭВМ.

< Предыдущая		Следующая >