Определение 1. Пусть и произвольные множества. Соответствием называется тройка множеств 4 страница

Примеры нетранзитивных отношений: «быть меньше ровно на единицу» (если меньше ровно на единицу , а меньше ровно на единицу , то не меньше ровно на единицу ), «не равно» (если и , то и , вообще говоря, могут и совпадать), «быть отцом» (если отец , а отец , то уже будет дедом ) и т.д.

Вопросы для самоконтроля

1. Может ли одно отношение одновременно быть: а) рефлексивным и асимметричным; б) антирефлексивным и антисимметричным, в) рефлексивным и транзитивным?

2. Определите свойства отношений: а) «быть соотечественником», б) «быть прямым потомком», в) «находиться слева от …».

 

Эквивалентность

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

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

( эквивалентность)

Таким образом, к эквивалентностям относятся такие отношения: «быть однополчанином», «быть членом той же партии, что и …», «быть тезкой», «быть единомышленником», «быть одной веры с …», «иметь тот же остаток при делении на 5», «и много, много других.

Отношение эквивалентности тесно связано с разбиением множества . Эту связь отражает следующая теорема.

Теорема 4. Задание отношения эквивалентности на конечном множестве равносильно разбиению этого множества.

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

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

Следовательно, данное множество { , , …, } подмножеств множества (согласно определению разбиения) есть разбиение последнего. Необходимость доказана.

Достаточность. Пусть теперь задано разбиение { , , …, } множества . Рассмотрим на нем отношение «принадлежать одному и тому же подмножеству». Данное отношение рефлексивно (любой элемент принадлежит тому же подмножеству, в котором сам и находится), симметрично (если принадлежит тому же подмножеству, что и , то и принадлежит тому же подмножеству, что и ) и, наконец, транзитивно (если принадлежит тому же подмножеству, что и , а принадлежит тому же подмножеству, что и , то принадлежит тому же подмножеству, что и ). Следовательно, данное отношение есть эквивалентность. Теорема доказана.

Замечание 1. Данная теорема легко распространяется на случай бесконечного множества . При этом алгоритм построения, описанный в первой части доказательства, будет работать сколь угодно долго, формируя конечное или бесконечное множество { , , …, , …}.

Замечание 2. Формируемые при работе описанного выше алгоритма подмножества , , …, называют классами эквивалентности. Например, отношение «иметь тот же остаток при делении на 5» разобьет множество натуральных чисел на такие пять классов эквивалентности: класс чисел, кратных пяти (числа, остаток которых при делении на 5 равен нулю); класс чисел с остатком при делении на 5, равным 1; класс чисел с остатком при делении на 5, равным 2; класс чисел с остатком, равным 3; класс чисел с остатком, равным 4. Классами эквивалентности отношения «иметь то же социальное происхождение» будут социальные группы: рабочие, служащие, крестьяне и т.д.

Замечание 3. Непересекаемость классов эквивалентности (т.е. условие ) обеспечивает непротиворечивость деления множества на классы (каждый элемент принадлежит не более чем одному классу), а условие говорит о полноте системы этих классов (любой элемент из принадлежит какому-либо классу).

Замечание 4. Данная теорема имеет применение не только в математических науках. Любая научная теория так или иначе, связана с классификацией объектов, составляющих область ее исследований. Для успешного осуществления этой классификации необходимо найти отношение эквивалентности между объектами. Если будет найдено отношение, которое одновременно рефлексивно, симметрично и транзитивно, то оно определит непротиворечивую и полную классификацию изучаемого разнообразия.

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

Вопросы для самоконтроля

1. Какие отношения из нижеследующих являются эквивалентностью? а) «быть того же цвета»; б) «быть кратным тому же числу»; в) «иметь тот же наибольший общий делитель»; г) «иметь хотя бы одно общее свойство».

2. Для приведенных выше отношений эквивалентности определите их классы эквивалентности.

 

Толерантность

 

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

толерантность

В качестве одного из примеров таких отношений, в частности, можно привести отношение «иметь общее», которое еще называют отношением «сходства». Каждый имеет общее с самим собой, что указывает на рефлексивность «сходства». Если имеет общее с , то и имеет общее с , что говорит о свойстве симметричности данного отношения. Однако оно не транзитивно, поскольку из того, что имеет сходство с , а с , вовсе не следует сходство и (они уже могут не иметь ничего общего).

При последовательном переборе некоторой цепочки пар сходных элементов, образующей на графе «сходства» путь из вершины в , между которыми уже нет никакого сходства, происходит постепенное накопление свойств, которыми обладает объект и утрата свойств, присущих объекту . Класс объектов, сходных с , может пересекаться с классом объектов, сходных с . В область их пересечения попадут объекты, сходные одновременно и с , и с .

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

· Классы эквивалентности не пересекаются, а классы толерантности пересекаются.

· Элементы класса эквивалентности попарно эквивалентны, а элементы класса толерантности, в общем и целом, попарно не толерантны.

· Класс эквивалентности представляет собой монолит с совершенно равнозначными элементами, а класс толерантности имеет ядро и оболочку. Ядро содержит один или более элементов. Элемент ядра является тем объектом , который как раз и образует данный класс толерантности . Элементы оболочки представляют довольно пеструю картину, некоторые их пары не толерантны, а сама оболочка не имеет четких границ.

На известной гравюре голландского художника М. К. Эсхера (рис. 5.6) представлены как бы два класса. Верхний класс – птицы (орнитофауна), а нижний класс – рыбы (ихтиофауна).

 

 

Рис. 5.6. Небо и вода (гравюра М. К. Эсхера)

 

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

Ядром нижнего класса является изображение рыбы, находящейся в нижней вершине ромба. По мере подъема в оболочке данного класса происходит обратный процесс – признаки рыбы постепенно начинают утрачиваться, становятся менее четкими, а признаки птицы усиливаются, становятся контрастнее. Однако четкой границы между этими классами провести нельзя. Оболочки классов имеют общую область пересечения. В этой области имеют место изображения как с признаками птицы, так и с признаками рыбы.

Таким образом, утрата свойства транзитивности привела к размыванию границ между классами, исчезла четкая классификация объектов исследования и наука здесь бессильна. Будто сам дьявол сидит в толерантности, размывая границы между противоположностями, устраняя грань между истиной и ложью, добром и злом. Как же бороться с этой толерантностью?

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

Лемма 1. Композиция двух рефлексивных отношений есть рефлексивное отношение.

Доказательство. Пусть отношения и рефлексивны, т.е. и или , где элементы матриц соответственно. Но тогда диагональные элементы двоичной матрицы , соответствующей отношению , согласно (5.11) определятся из выражения , т.е. или , что и требовалось доказать.

Лемма 2. Рефлексивное и симметричное отношение при композиции на себя дает рефлексивное и симметричное отношение, т.е.

.

Доказательство. Рефлексивность отношения следует из леммы 1. Осталось доказать, что оно симметрично. По теореме 1 из симметричности следует , т.е. любая пара из области имеет обратную . Но тогда и любой путь длины 2 в графе, заданном матрицей , также будет иметь обратный . Следовательно, матрица путей длины 2 будет симметрична относительно главной диагонали, но тогда отношение симметрично. Лемма доказана.

Лемма 3. Если отношение рефлексивно, то и ( любое натуральное число) рефлексивно.

Доказательство. Поскольку рефлексивно, то по лемме 1 отношение также рефлексивно. Обозначим , тогда , где и рефлексивны. Поэтому, опять же по лемме 1, рефлексивным отношением будет уже . Так можно доказать, что , и получить, снова используя лемму 1, что . Лемма доказана.

Лемма 4. Если для какого-либо отношения имеет место равенство , то оно транзитивно.

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

Теорема 5. Если отношение рефлексивно, то его область истинности есть подмножество области истинности его композиции на себя, т.е. .

Доказательство. Возьмем произвольный элемент из области . Из свойства рефлексивности отношения следует, что (так же как и ). На графе отношения паре соответствует дуга, выходящая из этой вершины и входящая в нее же. Такие дуги называются петлями. Из того, что , следует, что в графе отношения есть путь длины 2, т.е. пара . Поскольку элемент из области нами был взят произвольно, то по определению подмножества , что и требовалось доказать.

Следствие 1. Аналогично рассуждая, можно получить более общее утверждение .

Следствие 2. Для рефлексивного отношения найдется такое число , где , что .

Доказательство. Из теоремы 5 следует, что в матрице отмечены единицами те пары вершин в графе отношения , минимальная длина пути между компонентами которых не более двух дуг. Аналогично согласно следствию 1 матрица будет определять пары, кратчайший путь между компонентами которых имеет длину, не превышающую . Поэтому, если длина кратчайшего пути между самыми удаленными вершинами графа, то матрица будет являться также матрицей всех путей (путей любой длины) графа. Тогда матрицы путей соответствующих длин никаких других пар, которых бы не было в , содержать не будут и, следовательно, с учетом следствия 1, .

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

Теорема 6. Транзитивное замыкание рефлексивного отношения есть транзитивное и рефлексивное отношение.

Доказательство. По определению 9 транзитивным замыканием отношения является , а т.к. рефлексивно, то на основании следствий 1 и 2 получим . Поскольку , по лемме 3 отношение (следовательно, и ) также рефлексивно. Теперь докажем, что отношение транзитивно, т.е. .

В самом деле, , а (по следствию 2) , откуда следует, что . Из полученного равенства по лемме 4 имеем, что отношение транзитивно, т.е. .