Отношения эквивалентности и толерантности и их свойства

МИНИСТЕРСТВО ОБРАЗОВАНИЯ РЕСПУБЛИКИ БЕЛАРУСЬ

" Гомельский государственный университет имени Франциска Скорины"

математический факультет Кафедра алгебры и геометрии

Курсовая работа

" Отношения эквивалентности и толерантности и их свойства"

Гомель 2005

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

Не менее важной является ситуация, когда нам приходится устанавливать сходство объектов. Если одинаковость объектов означает их взаимозаменимость в некоторой ситуации, то сходство — это частичная взаимозаменимость, т. е. возможность взаимной замены с некоторыми (допустимыми в данной ситуации) потерями, с допустимым риском. Во второй главе попробуем раскрыть понятие «толерантности» на базе таких терминов, как «одинаковость» и «сходство» объектов.

А в третьей главе подробнее рассмотрим применение понятий отношений эквивалентности и толерантности в различных областях знаний и практики человека.

Реферат

Курсовая работа содержит: 41 страница, 3 источника, 1 приложение.

Ключевые слова: отношение эквивалентности, отношение толерантности, одинаковость, сходство, взаимозаменимость, классы эквивалентности, пространство толерантности, классы толерантности, предкласс, базис.

Объект исследования: отношения эквивалентности и толерантности.

Предмет исследования: свойства отношений эквивалентности и толерантности.

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

Методы исследования: методы теории множеств и теории отношений.

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

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

1.1 Определение и примеры

1.1.1 Определение

Систему непустых подмножеств множества мы будем называть разбиением этого множества, если

1) и

2) при .

Сами множества называются при этом классами данного разбиения.

1.1.2 Определение

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

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

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

Пустое отношение (на непустом множестве!) не является эквивалентностью.

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

Например, пусть мы считаем одинаковыми автомобили, выпущенные в одной и той же серии одним и тем же заводом. Тогда, разобрав один экземпляр «Волги», мы в принципе можем составить комплект рабочих чертежей, который годится для выпуска однотипных «Волг». Однако, изучив один экземпляр «Волги», мы не можем угадать окраску кузова или характер вмятин на бампере у других односерийных экземпляров.

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

Пусть теперь задано разбиение множества. Выберем в каждом множестве некоторый содержащийся в нем элемент. Этот элемент мы будем называть эталоном для всякого элемента, входящего в то же множество. Мы будем — по определению — полагать выполненным соотношение. Так определенное отношение назовем отношением «быть эталоном» .

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

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

Пусть — отношение эквивалентности, а — такое отношение «быть эталоном», что выполнено в том и только том случае, когда и имеют общий эталон .

Иначе говоря, равносильно существованию такого, что и. Поскольку, это означает, что. Иначе говоря, эквивалентность можно алгебраически выразить через более простое отношение «быть эталоном». Отношение на множестве из элементов можно задать графом, имеющим ровно стрелок, где — число классов эквивалентности: каждый элемент соединяется со своим единственным эталоном. Граф, изображающий отношение эквивалентности, состоит из полных подграфов, содержащих по, вершин. Таким образом, общее число ребер в этом графе равно .

Рассмотрим в качестве множество всех целых неотрицательных чисел и возьмем его разбиение на множество четных чисел и множество нечетных чисел. Соответствующее отношение эквивалентности на множестве целых чисел обозначается так: и читается: сравнимо с по модулю 2. В качестве эталонов здесь естественно выбрать 0 — для четных чисел и 1 — для нечетных чисел. Аналогично, разбивая то же множество на подмножеств, где состоит из всех чисел, дающих при делении на и остатке, мы придем к отношению эквивалентности:, которое выполняется, если и имеют одинаковый остаток при делении на. В качестве эталона в каждом естественно выбрать соответствующий остаток .

1.2 Формальные свойства эквивалентности

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

1.2.1 Определение

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

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

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

Обратно: если задано разбиение множества и бинарное отношение определено как " принадлежать общему классу разбиения" , то рефлексивно, симметрично и транзитивно.

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

Лемма. Для любых и либо , либо .

Доказательство леммы. Пусть пересечение. Покажем, что. Пусть, тогда выполнено и по самому определению множеств и. По симметричности имеем, а по транзитивности из и следует. Возьмем теперь произвольный элемент. По определению. Но из и следует, т. е.. Итак, .

Аналогично показывается, что. Значит. Лемма доказана.

Из леммы и рефлексивности отношения следует, что множества вида образуют разбиение множества. Пусть теперь выполнено соотношение. Это значит, что. Но и, в силу. Следовательно, оба элемента и входят в. Итак, если, то и входят в общий класс разбиения. Наоборот, пусть и. Покажем, что выполнено. Действительно, имеем и. Отсюда по симметричности. По транзитивности из и следует. Первая часть теоремы доказана.

Доказательство второй части. Пусть дано разбиение множества. Так как объединение всех классов разбиения совпадает с, то всякий входит в некоторый класс. Отсюда следует, т. е. отношение рефлексивно. Если и входят в класс, то и входят в тот же класс. Это означает, что из вытекает, т. е. отношение симметрично. Пусть теперь выполнено и. Это означает, что и входят в класс, а и — в класс. Поскольку и, имеют общий элемент,. Значит, и входят в, т. е. выполнено. Итак, отношение транзнтивно, чем и завершается доказательство теоремы.

1.2.2 Теорема

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

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

Для завершении доказательства достаточно заметить, что эквивалентность элементов и означает попадание в общий класс, т. е. совпадение первых номеров (первых признаков).

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

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

Вернемся к обсуждению отношения: «является эталоном для «. Мы уже дали конструктивное определение этого отношения. Из него легко можно получить следующие свойства отношения (быть эталоном):

1) для всякого существует эталон: .

2) Если, то, т. е. любой эталон есть эталон для самого себя.

3) Эталон единствен, т. е. из и следует .

Эти три свойства можно объявить аксиомами отношения «быть эталоном». Покажем, что из них следует определение эталона с помощью разбиения. Для этого сначала по отношению построим новое отношение, определяемое правилом:, если и имеют общий эталон. Иначе говоря, если существует такое, что и. Покажем, что есть отношение эквивалентности. Действительно, по свойству 1) у каждого есть эталон и, стало быть,. Значит, рефлексивно. Симметричность отношения очевидна. Если и, то это значит, что и имеют общий эталон, а не может иметь эталона, отличного от эталона для. Значит, .

Итак, доказано, что есть отношение эквивалентности. Но тогда по теореме 1.2.1 существует разбиение множества на классы эквивалентных друг другу элементов — так называемые классы эквивалентности.

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

Пусть — сюръективное отображение множества на некоторое множество. Рассмотрим на множестве отношение «иметь общий образ» и обозначим это отношение. Иначе говоря,, если. Обозначим через множество всех элементов, имеющих данный образ, т. е. таких, что. Ясно, что, так как любой элемент из имеет образ. Далее, при разных и, , так как иначе элемент, попавший в пересечение, имел бы два разных образа: и. Поскольку сюръективно, для любого. Итак, множества образуют разбиение множества, а отношение есть эквивалентность, соответствующая этому разбиению. Последнее следует из того, что тогда и только тогда, когда и принадлежат общему, множеству .

Множество классов эквивалентности по отношению принято обозначать (читается: фактормножество множества по отношению). Наши рассуждения показывают, что для всякого сюръективного отображения существует отношение эквивалентности на множестве такое, что и могут быть поставлены во взаимно-однозначное соответствие.

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

Рассмотрим частный случай, когда и. Пусть, далее, отображение обладает тем свойством, что, при, или, как говорят в таких случаях, подмножество неподвижно при отображении. Отсюда видно, что сюръективно. Действительно, всякий есть образ по крайней мере самого:. Итак, каждому однозначно сопоставлен некоторый элемент. При этом, если сопоставлен какому-то элементу, то самому сопоставлен он же.

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

Посмотрим теперь, что получится, если отказаться от условии, что определено на всем. Рассмотрим функцию, которая некоторым элементам из сопоставляет единственный образ из. По отображению можно опять-таки построить отношение по правилу:, если. Легко проверить, что будет симметрично и транзитивно. Выберем подмножество, состоящее из тех элементов, на которых определено отображение. Тогда если либо, либо не принадлежат, то заведомо не выполняется. Значит, если не входит в, то также не выполнено. Следовательно, отношение теперь уже не обязано быть рефлексивным.

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

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

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

Прямой суммой отношений и называется отношение. Прямую сумму отношений, мы будем обозначать через .

Таким образом, соотношение выполнено в следующих случаях: 1), и; 2), и ;

1.2.3 Теорема

Если , а отношения и — эквивалентности, то их прямая сумма также является эквивалентностью.

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

Замечание. Из этого доказательства видно, что условие непустоты пересечения работало только при проверке транзитивности. Значит, справедлива.

1.2.4 Теорема

Если отношения и рефлексивны и симметричны (в частности, являются эквивалснтиостями), то их прямая сумма также рефлексивна и симметрична.

Замечание. Если, то каждое из отношений и есть сужение отношения на свою область задания.

1.3 Операции над эквивалентностями

Посмотрим, какие операции над отношениями эквивалентности и при каких условиях дают в результате эквивалентность.

Транзитивное замыкание отношения эквивалентности является отношением эквивалентности.

Отношение, обратное к эквивалентности, является эквивалентностью.

Если и — эквивалентности, то их пересечение также является отношением эквивалентности.

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

Действительно, отношение дает разбиение на два класса и, отношению соответствует разбиение, а отношение дает неполный связный граф.

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

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

Легко видеть, что если или, то отношения и когерентны (надо положить ,). Таким образом, сравнимость относительно «порядка», задаваемого включением, есть частный случай когерентности.

Из следует, что для когерентных отношении эквивалентности и: и. Используя определение прямой суммы и, получаем. Здесь и — эквивалентности (как сужения эквивалентиостей и), а, и не пересекаются. По теореме 1.2.3 отсюда следует, что есть отношение эквивалентности.

Оказывается, когерентность отношений, является не только достаточным, но и необходимым условием для того, чтобы объединение эквивалентностей и было эквивалентностью.

1.3.2 Теорема

Для того чтобы объединение эквивалентностсй и само было отношением эквивалентности, необходимо и достаточно, чтобы и были когерентными.

Нам понадобятся некоторые простые свойства разбиений на классы эквивалентности, которые мы сформулируем в виде самостоятельных лемм. Мы будем далее использовать некоторые словесные сокращения. Если — эквивалентность и, то мы будем говорить, что и -эквивалентны. Разбиение, соответствующее эквивалентности, мы будем называть -разбиением; -классами и т. п.

Лемма. Для того чтобы , необходимо и достаточно, чтобы каждый -класс содеожался в некотором -классе.

Действительно, если, то из следует. Зчачит, множество всех, -эквивалентных элементу, содержится во множестве всех, -эквивалентных этому. Обратный вывод столь же очевиден.

Для того чтобы необходимо и достаточно, чтобы каждый -класс содержал любой -класс , имеющий с непустое пересечение.

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

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

Доказательство. Eсли и когерентны, то, и на, имеем, а на. Тогда по лемме 1.3.1 для каждого класса, содержащегося в, существует такой класс, что. По лемме 1.3.2 каждый класс, содержащийся в, целиком содержит любой класс, имеющий с непустое пересечение. Поскольку и не пересекаются, из вытекает, что всякий класс эквивалентности содержится либо в, либо в; значит, наше рассуждение охватывает все классы.

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

Теперь мы подготовили все необходимое для доказательства теоремы 1.3.1. Будем вести доказательство от противного, т. е. предположим, что и не когерентны. Тогда по лемме 1.3.3 существует класс и класс такиее, что, но не один из них не содержит другой. Значит, существуетвует, существует, существует. Имеем следующие соотношения: и, следовательно, и. По транзитивности должно было бы быть также. Однако, соотношения: и — оба не выполнены, так как не лежит с ни в общемклассе, ни в общемклассе. Значит, соотношение не выполнено. Полученное противоречие доказывает теорему.

Замечание. Понятие когерентности имеет смысл для любых отношений и. Но для эквивалентностей когерентность отношений и легко формулируется в терминах классов эквивалентности (лемма 1.3.3).

1.3.4 Лемма

Если и рефлексивны, то

Доказательство. Если, то, в силу, выполнено и соотношение, т. е.. Аналогично получается. Из этих двух включений следует .

Теорема. Для того чтобы объединение эквивалентностей и само было отношением эквивалентности, необходимо и достаточно, чтобы

Доказательство. Пусть — эквивалентность. По лемме 1.3.4 выполняется. Для доказательства остается доказать Пусть. Тогда для некоторого имеем и. Следовательно, и. Значит, и доказано. Пусть теперь выполнено. Отношение симметрично. По тогда симметрично и ортношение.. По теореме 1.3.3 (см. ниже) получаем, что отношение — эквивалентность. Из вытекает, что и — эквивалентность. Теорема доказана.

Условие, при котором произведение двух отношений эквивалентности и само является эквивалентностью, было получено чешским математиком Шиком в 1954 г.

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

Доказательство. Пусть сначала

рефлексивно. симметрично. Транзитивность произведения доказывается так: — здесь мы использовали ассоциативный закон для произведения отношений, условие, а также транзитивность и рефлексивность отношений и. Итак, но это и означает транзитивность отношения, поскольку рефлексивно. Пусть теперь произведение есть эквивалентность. Тогда .

Легко проверить, что если и — эквивалентности, то и также будут эквивалентностями.

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

Для любых транзитивных отношений , и справедлив ассоциативный закон:

Докажем сначала две леммы.

1.3.5 Лемма

Для любых отношений ,

вытекает из. доказывается аналогично.

1.3.5 Лемма

Для любых транзитивных отношений, , из и вытекает .

Доказательство теоремы 1.3.4. Из леммы 1.3.5

Из и

Из леммы 1.3.5

Из, , леммы 1.3.5 и того, что любое отношение вида транзитивно, Подобно тому как доказывается, доказывается Подобно тому как мы из и вывели, из и выводится Из и аналогично доказываемого «обратного» включения вытекает. Теорема доказана.

Нетрудно убедиться, что для любой эквивалентности

где — диагональное отношение.

Покажем теперь, что операция не дает ничего нового:

Если и — эквивалентности, то

Доказательство. Заметим сначала, что, учитывая лемму 1.3.4, Применяя транзитивное замыкание к обеим частям, ввиду свойства монотонности транзитивного замыкания имеем Далее, применяя распределительный закон получим Мы использовали здесь тот факт, что для рефлексивного выполнено включение, а следовательно,. Запишем теперь выражение для транзитивного замыкания, используя :

Отсюда ясно, что, т. е.

Сравнивая включения и получим искомое соотношение .

Отсюда вытекает следующий результат, также принадлежащий Шику:

1.3.6 Теорема

Если и — эквивалентности и , то

В самом деле, по теореме 1.3.3 произведение является эквивалентностью, а стало быть отношение совпадает со своим транзитивным замыканием. Но тогда из теоремы 1.3.5 следует .

1.4 Отношения эквивалентности на числовой прямой

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

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

1. Рефлексивность. Из того, что для всех, следует, что множество содержит главную диагональ (свойство).

2. Симметричность. Симметричность означает, что если, то и, т. е. что множество симметрично относительно главной диагонали (свойство).

3. Транзитивность. Транзитивность означает, что если и, то и. Точка является четвертой вершиной прямоугольника, три вершины которого находятся в точках и. Заметим, что вершина лежит на биссектрисе координатного угла — главной диагонали координатной плоскости. Поэтому геометрически свойство транзитивности можно сформулировать следующим образом:

Множество на плоскости определяет транзитивное отношение тогда и только тогда, когда для любого прямоугольника, одна вершина которого лежит на главной диагонали, а две соседние с вершины принадлежат , вершина , противоположная , также принадлежит (свойство ).

Замечание. Если отношение является симметричным, то геометрическая формулировка транзитивности несколько упрощается. А именно:

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

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

Заметим, что класс эквивалентности, содержащий точку, есть проекция пересечения множества и прямой на ось ординат.

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

1 Пример. (тривиальный). Множество вся плоскость. Выполнение свойств, , очевидно. Все точки исходной прямой отождествляются, т. е. входят в один класс эквивалентности.

Замечание. Для любого, если множество, определяющее отношение эквивалентности, содержит полосу, то оно совпадает со всей плоскостью. В самом деле, вместе с любой точкой множество содержит все внутренние точки квадрата с вершинами, ,, , т. е. полосу. Ясно, что таким образом свойство «принадлежать «распространяется на все точки плоскости.

2 Пример. (периодичность). Возьмем которое число. Пусть множество состоит из прямых, где — произвольное целое число. Выполнение свойств и очевидно, и если, , то .

3 Пример. «Все константы равны единице, кроме нуля». (Такое утверждение высказал И. М. Гельфанд на одной из своих лекций.) В этом примере множество есть вся плоскость с выброшенными осями координат и добавленным началом координат. Иначе говоря, всегда, кроме случая, и ему симметричного. Если точки, принадлежат, то либо, и тогда, , либо, и тогда и. В обоих случаях .

4 Пример. (Все целые числа равны друг другу.) Множество состоит из главной диагонали и всех точек с целыми координатами.

Очевидно, можно рассматривать и конечные варианты такой эквивалентности типа

5 Пример. (Все числа, не большие единицы по модулю, равны друг другу.) Множество состоит из диагонали и замкнутого единичного квадрата. Очевидно, множество, состоящее из открытого (или полузамкнутого:) квадрата, также дает эквивалентность.

2. Отношение толерантности

2.1 Определения, примеры, свойства

2.1.1 Определение

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

Пример. Множество состоит из четырехбуквенных русских слов — нарицательных существительных в именительном падеже. Будем называть такие слова сходными, если они отличаются не более чем на одну букву. Известная задача «Превращение мухи в слона» в точных терминах формулируется так:

Найти такую последовательность слов, начинающуюся словом «муха» и кончающуюся словом «слон», любые два соседних слова в которой сходны (в смысле только что данного определения).

Приведем решение этой задачи: Муха — мура — тура — тара — кара — каре — кафе — кафр — каюр — каюк — крюк — крок — срок — сток — стон — слон.

2.1.2 Пример

Пусть — натуральное число. Обозначим через — совокупность всех непустых подмножеств множества. Два таких подмножества объявим толерантными, если у них есть хотя бы один общий элемент. Законность такого определения очевидна: рефлексивность и симметричность отношения легко проверяются.

Множество называетсямерным симплексом. Это понятие обобщает понятия отрезка, треугольника и тетраэдра на многомерный случай. Числа интерпретируются как вершины симплекса. Двухэлементные подмножества — как ребра, трехэлементные как плоские грани, -элементные подмножества — какмерные грани. Толерантность граней симплекса означает их геометрическую инцидентность — наличие общих вершин. Число всех элементов из равно .

Множество с заданным на нем отношением толерантности называется пространством толерантности. Таким образом, пространство толерантности есть пара .

2.1.3 Пример

Пусть — произвольное множество. Обозначим через совокупность всех непустых подмножеств множества. Толерантность на задается условием:, если .

Пространство играет роль «универсального» пространства толерантности.

2.1.4 Пример

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

Существует еще один способ задания отношений толерантности. Рассмотрим соответствие. Множество всех образов элемента при соответствии мы обозначим. Отношение на множестве задается условием:, если у элементов и существует образ, т. е. если .

Установим основные свойства отношения :

Отношение всегда симметрично.

Это следует из того, что .

Отношение рефлексивно тогда и только тогда, когда соответствие определено на всем .

В самом деле, в этом и только в этом случае множество .

Если на элементе отношение не рефлексивно (не выполняется или ), то соотношение не выполнено ни для какого , так как .

Если соответствие является функцией, т.е. состоит не более чем из одного элемента (в этом случае равносильно ), то отношение транзитивно.

Действительно, пусть и. Это значит, что и. Следовательно,, т. е. .

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

2.2 Операции над толерантностями

Алгебраические свойства операций над толерантностями сравнительно просты.

2.2.1 Лемма

Если — толерантность, — эквивалентность и , то .

Доказательство получается применением транзитивного замыкания к обеим частям включения .

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

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

Доказательство. Симметрическое произведение толерантностей и всегда будет толерантностью. Симметричность симметризованного произведения следует из того, что: .

Можно ввести еще один вариант симметризованного произведения:. Легко показать, что будет толерантностью, если и — толерантности.

Полезно заметить, что для любого рефлексивного отношения отношения будут толерантностями.

2.3 Классы толерантности

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

Охарактеризуем некоторую совокупность объектов признаками. Возьмем множество всех этих объектов и множество всех возможных признаков. Установим теперь соответствие, сопоставляющее каждому объекту из все те признаки, которыми он обладает. Наоборот, любое соответствие можно интерпретировать как присвоение некоторым объектам (элементам множества) некоторых признаков (элементов из).

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

Покажем, что любое отношение толерантности можно задать таким образом. Более того, существует некоторая каноническая совокупность признаков, которая строится по данному отношению толерантности независимо от способа его конкретного задания.

Отношение толерантности на множестве может быть определено на языке покрытий. (Система множеств называется покрытием множества, если .)

Пусть — всюду определенное соответствие. Сопоставим каждому «признаку» множество всех элементов из, обладающих признаком, т. е. множество. Система всех множеств образует покрытие множества, поскольку любой элемент входит в некоторое. Легко видеть, что тогда и только тогда, когда существует такой признак, что и. Таким образом, толерантность может быть задана так:, если и принадлежат некоторому общему классу покрытия .

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

2.3.1 Определение

Множество называется предклассом в, если любые два его элемента и толерантны, т. е. для них выполнено соотношение: .

Лемма. Для того, чтобы два элемента и были толерантны, необходимо и достаточно, существовал предкласс , содержащий оба этих элемента.

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

2.3.2 Определение

Множество называется классом толерантности в, если есть максимальный предкласс.

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

Лемма. Всякий предкласс содержится хотя бы в одном классе .

Доказательство. Проведем его лишь для случая, когда само множество конечно. Пусть — предкласс. Если — есть класс, то лемма доказана. Если — не класс, то в множестве существует элемент, толерантный ко всякому элементу из. Добавим такой элемент к, т. е. рассмотрим множество. Тогда и снова является предклассом. Либо — класс, либо мы продолжаем дальше этот процесс расширения предкласса до класса. Поскольку множество конечно, то через конечное число шагов наше построение класса закончится.

Следствие. Всякий элемент содержится в некотором классе, т.е. система классов толерантности образует покрытие множества .

Действительно, в силу рефлексивности, и множество, состоящее из одного элемента, образует предкласс.

2.3.3 Лемма

Для того, чтобы два элемента и были толерантны, необходимо и достаточно, чтобы существовал класс, содержащий оба этих элемента.

Все подготовлено к тому, чтобы сформулировать и доказать основную классификационную теорему.

Теорема. Пусть — произвольное пространство толерантности, а — множество всех его классов толерантности. Тогда существует отображение такое, что элементы из толерантны в том и только в том случае, когда толерантны их образы в .

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

Если — конечно, то количество всех его подмножеств конечно и поэтому конечно пространство. Поэтому вместо отображения можно взять отображение, где — число классов толерантности в, которое каждому элементу сопоставляет множество номеров, содержащих его классов: (здесь).

Толерантность элементов и означает, что среди номеров, сопоставленных элементам и согласно, есть хотя бы один общий. Т. е. и имеют общий числовой признак. Рассмотрим всюду определенное соответствие, которое каждому сопоставляет все классы, в которые он входит. Из леммы 2.3.3 следует, что равносильно тому, что у и y имеется общий образ в .

(Л. Кальмар — С. Якубович) Теорема. Произвольное отношение толерантности на множестве можно задать как отношение с помощью некоторого всюду определенного соответствия .

2.4 Классы толерантности в некоторых конкретных пространствах толерантности

Рассмотрим пространство. Это пространство толерантности состоит из множеств номеров вида, где все, причем элементы и толерантны, если они содержат общий номер.

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

2.4.1 Лемма

Множество является классом толерантности.

Так как состоит из всех множеств вида, то число элементов множества равно — число всех подмножеств множества из оставшихся номеров.

Найденных классов достаточно, чтобы задать толерантность в .

Точный смысл этого утверждения состоит в том, что соотношение выполняется тогда и только тогда, когда существует класс содержащий одновременно и. Действительно, если, то и содержат некоторый общий номер, и тем самым входят в класс. Обратное столь же очевидно. Значит, лемма 2.3.3 допускает для пространства уточнение. Для проверки толерантности достаточно ограничиться проверкой вхождения в один из классов. Однако, в кроме есть еще классы толерантности. Так, в множество образует класс. Ясно, что этот класс не совпадает ни с одним, так как не содержит элементов вида .

Определение. Совокупность классов в пространстве толерантности называется базисом, если:

1) для всякой толерантной пары и существует класс, содержащий оба этих элемента: ;

2) удаление из хотя бы одного класса приводит к потере этого свойства, т. е. существует толерантная пара, , для которой является единственным общим классом толерантности в .

Замечание. Произвольная система классов толерантности, обладающая свойством 1) из определения 2.4.1, содержит базис. Чтобы выделить этот базис, достаточно последовательно удалить «лишние» классы. В качестве исходной системы можно выбрать все множество классов. Отсюда следует существование базиса в любом пространстве толерантности.

Теорема. Пусть — произвольное пространство толерантности, а — базис. Тогда существует отображение такое, что элементы из толерантны в том и только в том случае, когда толерантны их образы в .

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

Выше было показано, что в пространстве толерантности набор классов образует базис, не совпадающий с совокупностью всех классов.

Установим одно простое свойство всех классов толерантности в .

2.4.2 Лемма

Если — класс толерантности в , содержащий элемент , то .

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

2.4.3 Лемма

В пространстве существует единственный базис: .

Доказательство. Пусть — базис в. Тогда в нем должен существовать класс, содержащий элемент. По предыдущей лемме таким классом может быть только. Значит, базис должен содержать все классы. Но они уже сами образуют базис, т. е. .

В силу определения базиса толерантность в можно задать только признаками, соответствующими базисным классам .

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

Рассмотрим пространство. Оно состоит из целочисленных кортежей длины, где. Обозначим через множество, состоящее из всех элементов, для которых. Легко проверить, что эти множества образуют классы толерантности. Итак, класс — это совокупность кортежей, у которых фиксированная координата принимает фиксированное значение. Из определения толерантности в сразу следует, что классы образуют базис. Общее количество этих классов равно, а каждый класс содержит элементов.

2.5 Связь отношений эквивалентности и толерантности

Когда отношение толерантности оказывается транзитивным, т. е. превращается в свой частный случай — в отношение эквивалентности, то классы толерантности превращакугся в классы эквивалентности. Так как классы эквивалентности не пересекаются, справедлива

Лемма. Отношение толерантности янлнигся отношением эквивалентности тогда и только тогда, когда классы толерантности не пересекаются друг с другом.

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

2.5.1 Определение

Пусть — пространство толерантности. Множество называется ядром, если существует такая совокупность классов, ,, что есть совокупность всех элементов из, каждый из которых входит во все эти и только эти классы.

Ядра — это прообразы при отображении. Действительно, ядро состоит из всех тex элементов, для которых образ есть именно это множество классов толерантности:. Отсюда ясно, что непустые ядра образуют разбиение, множества и тем самым задают отношение эквивалентности. Мы попробуем разобраться, как это отношение связано с исходной толерантностью.

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

Лемма. Для того чтобы выполнялось соотношение , необходимо и достаточно, чтобы и лежали в одном и том же ядре .

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

Следствие. Отношение есть эквивалентность, а непустые ядра сложат для классами эквивалентности.

Отметим очевидное включение В случае эквивалентности классы не пересекаются и каждое ядро совпадает со своим классом толерантности:, и, кроме того, для любого .

Заметим, что при обобщении понятия эквивалентности — переходе к толерантности — понятие класса эквивалентности расщепляется на два разных понятия — класс толерантности и ядро.

2.5.2 Определение

Пространство толерантности называется безъядерным, если каждое ядро состоит не более чем из одного элемента.

Для безъядерных пространств, толерантности основная классификационная теорема (тeopeмa 2.3.1) может быть уточнена так:

Теорема. Пусть — безъядерное пространство толерантности, а — множество всех есо классов толерантности. Тогда существует инъективное отображение такое, что элементы из толерантны в том и только том случае, когда толерантны их образы в .

Для конечных пространств с нетривиальными ядрами можно применить тот же прием, который был уже использован для задания признаками эквивалентности. А именно, выберем в каждом ядре свою нумерацию. Сопоставим каждому элементу конечного пространства набор номеров, где — те же самые номера, что и в 3, а — номер элемента в своем ядре. Ясно, что элемент однозначно определяется целочисленными признаками, а толерантность пары определяется совпадением одного из признаков .

Пусть теперь — произвольное прострапсизо толерантности. Обозначим через множество его ядер и определим толераниюсть ядер и условием:, если существуют представители и, толерантные в. Так как элементы одного ядра имеют общее множество толерантных с ними элементов, то из, следует, что для любых и выполнено. Мы получили новое пространство. Можно убедиться, что оно будет безъядерным. Ясно Ясно также, что равносильно, где и — содержащие эти элементы ядра.

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