МИНИСТЕРСТВО ОБРАЗОВАНИЯ РЕСПУБЛИКИ БЕЛАРУСЬ
«Гомельский государственный университет имени ФранцискаСкорины»
математический факультет
Кафедра алгебры и геометрии
Курсовая работа
«Отношения эквивалентности и толерантности и их свойства»
Гомель 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)
В этом случае отношения /> и /> мы назовем когерентными.
Легко видеть, что если /> или />, то отношения /> и /> когерентны (надо положить />, />). Таким образом,сравнимость относительно «порядка», задаваемого включением, естьчастный случай когерентности.
Из (2) следует, что для когерентных отношении эквивалентности /> и />: /> и />. Используя определениепрямой суммы и (23), получаем />. Здесь/> и /> – эквивалентности (каксужения эквивалентиостей /> и />), а />, и /> не пересекаются. Потеореме 1.2.3 отсюда следует, что /> естьотношение эквивалентности.
Оказывается, когерентность отношений />,/> является не толькодостаточным, но и необходимым условием для того, чтобы объединение /> эквивалентностей /> и /> было эквивалентностью.
1.3.2 Теорема
Для того чтобы объединение /> эквивалентностсй/> и /> само было отношениемэквивалентности, необходимо и достаточно, чтобы /> и/> были когерентными.
Нам понадобятся некоторые простые свойства разбиений на классыэквивалентности, которые мы сформулируем в виде самостоятельных лемм. Мы будемдалее использовать некоторые словесные сокращения. Если /> – эквивалентность и />, то мы будем говорить, что/> и /> />-эквивалентны.Разбиение, соответствующее эквивалентности />,мы будем называть />-разбиением; />-классами и т.п.
Лемма. Для того чтобы />, необходимо и достаточно,чтобы каждый />-класс содеожался внекотором />-классе.
Действительно, если />, то из /> следует />. Зчачит, множество всех />, />-эквивалентных элементу />, содержится во множествевсех />, />-эквивалентных этому />. Обратный вывод столь жеочевиден.
Для того чтобы /> необходимои достаточно, чтобы каждый />-класс /> содержал любой />-класс />, имеющий с /> непустое пересечение.
Для доказательства необходимости выберем произвольный элемент />. По предыдущей лемме /> целиком содержится внекотором классе />. Но если бы /> был бы отличен от />, то элемент /> был бы сразу в двухклассах />-разбиения, что невозможно.Значит, />. Для доказательствадостаточности нужно только вспомнить, что из /> поусловию вытекает />, и применитьлемму 1.3.1.
Для того чтобы эквивалентности /> и/> были когерентными,необходимо и достаточно, чтобы всякий />-класс/> либо содержался внекотором />-классе />, либо целиком содержаллюбой />-класс />, имеющий с /> непустое пересечение.
Доказательство. Eсли /> и /> когерентны, то />, /> и на />, имеем />, а на /> />. Тогда по лемме 1.3.1 длякаждого класса />, содержащегося в/>, существует такой класс />, что />. По лемме 1.3.2 каждыйкласс />, содержащийся в />, целиком содержит любойкласс />, имеющий с /> непустое пересечение.Поскольку /> и /> не пересекаются, из (1)вытекает, что всякий класс эквивалентности /> содержитсялибо в />, либо в />; значит, наше рассуждениеохватывает все классы.
Проведем доказательство в обратную сторону. Пусть каждый класс /> обладает сформулированнымв лемме 1.2.3 свойством. Обозначим через /> объединениевсех тех классов />, для которыхсуществует такой />, что />, а через /> – объединение остальныхклассов />. Ясно, что />, /> и />, />, где /> и /> – сужения отношений /> и /> на />. Наконец, очевидно, что /> и />, т.е. /> и /> когерентны.
Теперь мы подготовили все необходимое для доказательства теоремы1.3.1. Будем вести доказательство от противного, т.е. предположим, что /> и /> не когерентны. Тогда полемме 1.3.3 существует класс /> и класс/> такиее, что />, но не один из них несодержит другой. Значит, существуетвует />,существует />, существует />. Имеем следующиесоотношения: /> и />, следовательно, /> и />. По транзитивности должнобыло бы быть также />. Однако,соотношения: /> и /> – оба не выполнены, таккак /> не лежит с /> ни в общем />-классе, ни в общем />-классе. Значит,соотношение /> не выполнено. Полученноепротиворечие доказывает теорему.
Замечание. Понятие когерентностиимеет смысл для любых отношений /> и />. Но для эквивалентностейкогерентность отношений /> и /> легко формулируется втерминах классов эквивалентности (лемма 1.3.3).
1.3.4 Лемма
Если /> и /> рефлексивны, то
/> (3)
Доказательство. Если />, то, всилу />, выполнено и соотношение />, т.е. />. Аналогично получается />. Из этих двух включенийследует (3).
Теорема. Для того чтобыобъединение /> эквивалентностей /> и /> само было отношениемэквивалентности, необходимо и достаточно, чтобы
/> (4)
Доказательство. Пусть /> –эквивалентность. По лемме 1.3.4 выполняется (3). Для доказательства (4)остается доказать
/> (5)
Пусть />. Тогда длянекоторого /> имеем /> и />. Следовательно, /> и />. Значит, /> и (5) доказано. Пустьтеперь выполнено (4). Отношение /> симметрично.По (4) тогда симметрично и ортношение />./>. По теореме 1.3.3 (см.ниже) получаем, что отношение /> –эквивалентность. Из (4) вытекает, что и /> –эквивалентность. Теорема доказана.
Условие, при котором произведение /> двухотношений эквивалентности /> и /> само являетсяэквивалентностью, было получено чешским математиком Шиком в 1954 г.
Для того чтобы произведение /> отношенийэквивалентности /> и /> было эквивалентностью,необходимо и достаточно, чтобы /> и /> коммутировали.
Доказательство. Пусть сначала
/> (6)
/> рефлексивно./> симметрично.Транзитивность произведения доказывается так: /> –здесь мы использовали ассоциативный закон для произведения отношений, условие (6),а также транзитивность и рефлексивность отношений /> и/>. Итак />, но это и означаеттранзитивность отношения />,поскольку /> рефлексивно. Пусть теперьпроизведение /> есть эквивалентность.Тогда />.
Легко проверить, что если /> и/> – эквивалентности, то /> и /> также будутэквивалентностями.
Оказывается, операция /> (ееиногда называют, объединением эквивалентностей, имея в виду, что обычноеобъединение эквивалентностей может не быть эквивалентностью) ассоциативна, т.е.является «хорошей» алгебраической операцией.
Для любых транзитивных отношений />,/> и /> справедлив ассоциативныйзакон:
/> (7)
Докажем сначала две леммы.
1.3.5 Лемма
Для любых отношений />, />
/> (8)
/> (9)
(8) вытекает из />. (9)доказывается аналогично.
1.3.5 Лемма
Для любых транзитивных отношений />,/>, /> из /> и /> вытекает />.
Доказательство теоремы 1.3.4. Излеммы 1.3.5
/> (10)
/> (11)
Из (10) и (11)
/> (12)
Из леммы 1.3.5
/> (13)
Из (12), (13), леммы 1.3.5 и того, что любое отношение вида /> транзитивно,
/> (14)
Подобно тому как доказывается (12), доказывается
/> (15)
Подобно тому как мы из (13) и (13) вывели (14), из (14) и (15)выводится
/> (16)
Из (16) и аналогично доказываемого «обратного» включениявытекает (7). Теорема доказана.
Нетрудно убедиться, что для любой эквивалентности />
/> (17)
где /> – диагональноеотношение.
Покажем теперь, что операция /> недает ничего нового:
Если /> и /> – эквивалентности, то
/> (18)
Доказательство. Заметим сначала, что, учитывая лемму 1.3.4, /> Применяя транзитивноезамыкание к обеим частям, ввиду свойства монотонности транзитивного замыканияимеем
/> (19)
Далее, применяя распределительный закон получим
/>(20)
Мы использовали здесь тот факт, что для рефлексивного /> выполнено включение />, а следовательно, />. Запишем теперь выражениедля транзитивного замыкания, используя (20):
/>
Отсюда ясно, что />, т.е.
/> (21)
Сравнивая включения (19) и (21) получим искомое соотношение (18).
Отсюда вытекает следующий результат, также принадлежащий Шику:
1.3.6 Теорема
Если /> и /> – эквивалентности и />, то
/> (22)
В самом деле, по теореме 1.3.3 произведение /> является эквивалентностью,а стало быть отношение /> совпадаетсо своим транзитивным замыканием />. Нотогда из теоремы 1.3.5 следует (22).
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 элементов />,для которых образ /> есть именно этомножество классов толерантности: />. Отсюдаясно, что непустые ядра образуют разбиение, множества /> и тем самым задаютотношение эквивалентности. Мы попробуем разобраться, как это отношение связанос исходной толерантностью.
Пусть задано пространство толерантности />, Далее мы будем обозначатьчерез /> множество всех элементов,толерантных к />. Отношение /> на /> определим условием
/> (23)
Иначе говоря, /> означает,что /> и /> толерантны к одним идем жеэлементам.
Лемма. Для того чтобывыполнялось соотношение />,необходимо и достаточно, чтобы /> и /> лежали в одном и том жеядре />.
Доказательство. Пусть /> и /> принадлежат ядру />. По лемме 2.3.3 множество /> состоит из всех элементов,входящих хотя бы в один из классов /> Но тоже самое справедливо и для множества />, т.е. /> или />. Обратно. Предположим, что/>, и пусть /> принадлежит некоторомуклассу />. Тогда для любого /> будет выполненосоотношение />. В силу (23) выполнено и />. Значит, /> (поскольку /> – максимальный предкласс).Аналогично показывается, что всякий класс, содержащий />, содержит одновременно />. Итак, /> и /> принадлежат одной и той жесовокупности классов, а значит, и общему ядру. Лемма доказана.
Следствие. Отношение /> есть эквивалентность, анепустые ядра сложат для /> классамиэквивалентности.
Отметим очевидное включение
/> (24)
В случае эквивалентности классы не пересекаются и каждое ядросовпадает со своим классом толерантности: />,и, кроме того, для любого /> />.
Заметим, что при обобщении понятия эквивалентности – переходе ктолерантности – понятие класса эквивалентности расщепляется на два разныхпонятия – класс толерантности и ядро.
2.5.2 Определение
Пространство толерантности /> называетсябезъядерным, если каждое ядро состоит не более чем из одного элемента.
Для безъядерных пространств, толерантности основнаяклассификационная теорема (тeopeмa 2.3.1) может быть уточнена так:
Теорема. Пусть /> – безъядерное пространствотолерантности, а /> – множество всехесо классов толерантности. Тогда существует инъективное отображение /> такое, что элементы из /> толерантны в том и толькотом случае, когда толерантны их образы в />.
Для конечных пространств с нетривиальными ядрами можно применитьтот же прием, который был уже использован для задания признакамиэквивалентности. А именно, выберем в каждом ядре свою нумерацию. Сопоставимкаждому элементу /> конечногопространства /> набор номеров />, где /> – те же самые номера, чтои в />3, а /> – номер элемента в своемядре. Ясно, что элемент однозначно определяется целочисленными признаками />, а толерантность парыопределяется совпадением одного из признаков />.
Пусть теперь /> –произвольное прострапсизо толерантности. Обозначим через /> множество его ядер иопределим толераниюсть ядер /> и /> условием: />, если существуютпредставители /> и />, толерантные в />. Так как элементы одногоядра имеют общее множество толерантных с ними элементов, то из />, следует, что для любых /> и /> выполнено />. Мы получили новоепространство />. Можно убедиться, что онобудет безъядерным. Ясно Ясно также, что /> равносильно/>, где /> и /> – содержащие эти элементыядра.
Теперь заметим, что ядра можно было бы определять не с помощьюполного запаса классов, а только с помощью классов, принадлежащих некоторомубазису />. Пусть /> – некоторая совокупностьклассов из базиса />. Ядром /> относительно базиса /> мы назовем совокупностьвсех элементов из />, каждый изкоторых входит во все эти классы и не входит ни в какие другие классы из базиса/>.
Лемма. Разиение множества /> на ядра относительнобазиса /> совпадает с разбиениеммножества /> на обычные ядра.
Доказательство. Буквально повторяя доказательство леммы 2.5.1, мыполучим, что ядра, определенные по базису /> –это классы эквивалентности по />.Значит, они совпадают с исходными ядрами.
Теорема. Если пространство толерантности/> имеет конечный базис />, то совокупность всех классовтолерантности в /> конечна.
Доказательство. В силу леммы 2.5.2 число ядер конечно, т.е.конечно пространство ядер />.Значит, /> имеет конечное числоклассов толераитпости. Но так как /> равносильно/>, то каждый класстолерантности в /> есть объединениеядер, образующих соответствующий класс толерантности в />. Таким образом,совокупность всех классов толерантности в /> конечна.
Обратим внимание, что ни в формулировке теоремы, ни в еедоказательстве не предполагается, что /> конечно.Оно и фактически может быть бесконечным за счет бесконечности ядер.
2.6 Дальнейшее исследование структуры толерантностей
Рассмотрим множество /> и егопокрытие />. Пару /> мы будем далее называть картой.
Произвольная карта /> позволяетввести на множестве /> отношениетолерантности />, определенноеусловием: />, если существует такое />, что одновременно /> и />. Так определеннуютолерантность /> мы назовем толерантностью,порожденную картон />. Очевидно,каждое /> является предклассомпорожденной толерантности />.
Если /> – пространствотолерантности и /> – множество всехклассов толерантности в этом пространстве, то, в силу леммы 2.3.3толерантность, порожденная картой />,совпадает с исходной толерантностью />.Аналогичное утверждение справедливо и для произвольного базиса /> в пространстве />.
Карта /> называется канонической,если каждый элемент /> покрытия /> оказывается классомтолерантности, порожденной исходной картон />.Легко видеть, что если карта /> являетсяканонической, то /> содержитнекоторый базис />, порожденныйтолерантности: />.
На рис. 1 изображена некоторая карта />, а справа система классовпорожденной толерантности (впрочем, в данном случае эта система состоит изодного класса). Этот пример показывает, в частности, существованиенеканонических карт.
Каждая карта /> естественнымобразом приводит к всюду определенному соответствию
/> (25)
которое каждому элементу /> сопоставляетвсе те />, для которых />. Наоборот, если данонекоторое всюду определенное соответствие />,то оно порождает покрытие /> множества/>, состоящее из прообразовэлементов из /> при соответствии />. Таким образом, /> тогда и только тогда,когда существует такое />, что /> есть множество элементовиз />, которым соответствие /> сопоставляет />. Обозначим для дальнейшегопрообраз элемента /> при соответствии/> через />.
По соответствию (25) можно построить отображение,
/> (26)
которое каждому элементу /> сопоставляетнепустое множество элементов />, длякоторых />. С помощью отображении (26)толерантность />, порожденнаяисходной картой />, выражаетсяусловием />, если />. Можно ввести еще иотношение />, определяемое условием: />, если />. />, очевидно, являетсяэквивалентностью.
Посмотрим на примерах, как канонические признаки выражаются черезисходные признаки карты. В примере на рис. 1 Имеем />.
В примере на рис. 2а, изображено соответствие: />, где />, />. Нa рис. 2б изображены классы порожденной толерантности. Легкопроверить, что />, />.
На рис 3 исходная карта уже является канонической. Но если взятьканоническую карту /> с полным наборомклассов толерантности, то получим, что />.Посмотрим далее, каким образом и всегда ли канонические признаки могут бытьвыражены через исходные.
2.6.1 Теорема
Для произвольной карты /> любойкласс порожденной толерантности /> всегдаможет быть выражен через элементы покрытия /> спомощью операций пересечения и объединения.
Доказательство. Рассмотрим некоторый класс толерантности />. Пусть />. По определению класса,для всякого />, />, а по определениютолераптности существует признак /> такой,что />. Тогда 1) />; 2) />. Действительно, 1) следуетиз того, что /> для всех признаков />, a 2) следует из того, что всякий />,принадленжащий />, толерантен к />. Поскольку /> – произвольный элемент из />, по свойствумаксимальности класса />. Отсюдавытекает, что />, что доказываеттеорему.
Подчеркнем, что канонические признаки оправляются через исходныебез перехода к дополнениям. О связи между исходными и каноническими признакамиговорит также.
2.6.2 Теорема
Существует такой базис классов порожденной толерантности, чтокаждый из классов этого базиса содержит некоторое множество />.
Доказательство. По определению толерантности в /> для всякого /> любая пара /> и /> толерантна. Значит, /> есть предкласс. Тогда полемме 2.3.2 получается существует класс />.Выберем для каждого /> один из классов />. Очевидно, выбраннаясовокупность классов удовлетворяет условию 1) из определения 1.4.1. Значит, онасодержит некоторый базис />.
Следствие. Когда /> конечно, то существуетбазис классов толерантности, число классов в котором не превышает количестваисходных признаков.
Рассмотрим исходную карту /> иполученную из нее каноническую карту />, где /> – базис. Как уже былоотмечено, отношения толерантности, издаваемые на множестве обьектов /> обеими картами, совпадают.
Несколько иначе обстоит дело с отношением эквивалентности />, задаваемым на /> с помощью определения,приведенного в начале параграфа. Пусть /> –отношение эквивалентности, заданное исходным множеством признаков />, а /> – отношениеэквивалентности, заданное по (25). Как показывает пример на рис. 1,отношения /> и /> могут и не совпадать. Вобщем, случае справедлива
2.6.3 Теорема
Если выполнено соотношение: />,то выполнено и соотношение />, т.е. />.
Доказательство. Если />, тосовокупности исходных признаков /> и />, выполненных для /> и />, совпадают. Из теоремы2.6.1 вытекает, что для каждого класса толерантности /> и /> одновременно содержатсяили не содержатся в нем. Таким образом, /> и/> имеют одинаковые наборыканонических признаков, т.е. />.Теорема доказана.
Следующая теорема, принадлежащая С.М. Якубович, дает условиятого, что некоторое множество является классом толерантности, т.е. того, чтонекоторый признак является каноническим.
2.6.4 Теорема
Пусть имеется карта />. Для,того чтобы элемент покрытия /> являлсяклассом порожденной толерантности />,необходимо и достаточно, чтобы для любого подмножества />, из /> следоаало бы />.
Доказательство. Сначала предположим, что множество /> не является классомтолерантности. Так как /> являетсяпредклассом, то единственная причина, по которой /> можетне быть классом, состоит в том, что существует />,не входящий в /> и толерантный ковсем элементам />. Значит, длявсякого /> существует множество />, содержащее /> и />. Таким образом, множества /> образуют покрытиемножества />. Но все /> содержат элемент />, не входящий в />. Следовательно,пересечение /> не содержится в />. Итак, мы доказалидостаточность условия, указанною в теореме 2.6.4. Докажем теперь необходимость.Пусть существует такое подмножество />, что />, но />. Значит, существуетэлемент />, не входящий в />, но входящий во все />. Этот элемент толерантенко всем />. Значит, /> не является максимальнымпредклассом, т.е. не является классом толерантности. Теорема доказана.
Рассмотрим еще так называемые сопряженные и производныепространства толерантности.
Пусть /> – произвольноепространство толерантности, и пусть /> –некоторая совокупность классов толерантности. Множество /> естественным образомпревращается в пространство толерантности /> припомощи следующего определения: />, если />.
Определение. Если /> совпадает с множеством /> всех классов, топространство /> называется сопряженнымк /> и обозначается /> (таким образом, />).
Рассмотрим несколько примеров.
В пространстве /> элемент/>, содержащий все числа,толерантен ко всем элементам и, стало быть, входит во все классы толерантности.Значит, в пространствe /> /> – полноеотношение.
На рис. 4 изображен циклический граф из 7 вершин. Классамитолерантности являются «ребра», а толерантны классы, соответствующиесмежным ребрам. Ясно, что для линейного графа из /> вершинсопряженным является линейный граф из /> вершин.
На рис. 5 изображен циклический граф. Сопряженным к немубудет циклический граф из того же числа верин (если количество вершин исходногографа было больше трех).
На рис. 6 изображено пространство толерантности />, состоящее из двух циклов,зацепленных в одной точке. Сопряженное пространство /> состоитиз таких же циклов с более сложным зацеплением. Но сопряженное к последнемупространство /> по существу совпадает сисходным пространством />.
Определение. Пусть /> – базис. Тогдапространство /> называется сопряженнымк />, относительно данногобазиса />.
Определение. Второе сопряженноепространство относительно некоторого базиса /> в/> и базиса /> в /> называется производнымот исходного пространства толерантности />.
Итак, производное пространство толерантности определяется неоднозначно, а с точностью до выбора базисов. Этот произвол исключается, когда /> и /> имеют по единственномубазису.
Рассмотрим несколько примеров.
1. Для линейного графа с /> вершинами/> производное пространствотакже есть линейный граф, но с /> вершинами(см. рис. 4)
2. Для циклического графа с /> вершинами/> производное пространство «совпадает»с исходным пространством (см. рис. 5).
3. Та же ситуация для зацепленных циклических графов (см. рис. 6).
4. Для пространства /> производноепространство /> состоит из одногоэлемента.
2.6.5 Теорема
Если /> – произвольноепространство толерантности, а /> –произвольный базис в нем, то существует такой базис /> всопряженном пространстве /> и такоеинъективное отображение />, чтопри /> и /> из /> следует />.
Доказательство. Обозначим через /> множествоклассов из базиса />, содержащих />. Для любых классов /> и /> из /> имеем />, т.е. />. Итак, множества /> суть предклассы в />. Значит, для всякого /> существует класс в />, для которого />. Зафиксируем для каждого /> некоторый класс /> и множество этих классовобозначим через />. Мы имеемсюръекцию />, которое каждому /> сопоставляет класс />. Покажем, что /> содержит некоторый базис />. Действительно, если />, то существует />, содержащийся в /> и />. Тогда /> и /> содержаться в />, а значит, /> и />. Теперь для каждого /> выберем ровно один элемент/>, для которого />. Множество таких элементовобозначим через />. Ясно, что /> и возникающая при этомсюръекция /> на /> инъективно. Тогда обратноек нему отображение /> инъективноотображает /> на подмножество /> множества />. Поэтому его можнорассматривать как инъективное (но уже в общем случае не сюръективное) отображение.Пусть теперь /> и, /> где /> и /> и />. Тогда существует класс />, содержащий /> и />. Значит, />. Но из /> и /> следует, что />, т.е. />. Теорема доказана.
3. Приложение понятий эквивалентности и толерантности в различныхобластях знаний и практики человека
3.1 От одинаковости к эквивалентности
Возьмем стандартный комплект шахматных фигур. С точки зренияшахматного игрока все белые пешки в нем одинаковы. Расставляя их на шахматнойдоске, шахматист будет выбирать их из коробки в произвольном порядке. Вначальной позиции все они будут поставлены на вторую горизонталь и шахматист небудет размышлять над вопросом, куда ему лучше поставить выбранную наугад пешку.Точно так же любая из черных ладей при расстановке фигур перед игрой может сравным успехом попасть на королевский или ферзевый фланг. Эти ладьи одинаковы.
Но представим себе другую ситуацию: этот же комплект шахмат отданребенку, который играет в солдатики. Для него отдельные пешки могут приобрестииндивидуальность, получить имена и метки. Однако в тот момент, когда этот жемальчик начнет использовать шахматы по прямому назначению, пешки одного цветаопять станут одинаковыми.
Возьмем еще одну ситуацию: шахматные фигуры в процессе игры.Предположим, что шахматист стоит перед выбором: отдать ли противнику пешку,проникшую уже на седьмую горизонталь и грозящую вот-вот превратиться в ферзя,или пешку, мирно стоящую в начальной позиции. Ясно, что (при прочих равныхусловиях) первая пешка гораздо ценней и шахматист уже не считает обе свои пешкиодинаковыми. Правда, в этой ситуации объектами являются не сами по себедеревянные фигурки, а «пешки в данной позиции». В позиции этюдногохарактера каждая пешка играет свою индивидуальную роль, и они, разумеется, неодинаковы для хорошего шахматиста.
Разница здесь того же характера, как между словом русского языка исловом в данном контексте. Например, слова «пешка» и" пешка",хотя и напечатаны разным шрифтом, одинаковы, как слова русского языка. Но вконтекстах «Гроссмейстер эффектно пожертвовал пешку» и «Он былтолько пешкой в чужих руках» это слово имеет разные значения. Иначеговоря, слова одинаковы, а значения различаются.
Аналогично, об одинаковости людей мы можем говорить в различномсмысле. С профессиональной точки зрения продавца готового платья люди, имеющиеодин и тот же пол, рост и размер, неразличимы. Они одинаковы в том смысле, чтоим нужно демонстрировать одни и те же вещи. Впрочем, хороший продавец различаетпокупателей по их вкусам, а хороший портной понимает, что кроме роста и размераесть индивидуальные особенности фигуры. Но для работника склада, который выдаетформу (скажем, штормовые костюмы для альпинистов), существен только размер. Дляпрофессора анатомии малосущественно, на чьем трупе он будет демонстрироватьстудентам устройство человеческих органов. Но уже для профессора психиатрии нетодинаковых больных.
С точки зрения инспектора по кадрам люди с тождественнымианкетными данными одинаковы. Но для научного руководителя лаборатории нетодинаковых и взаимозаменимых сотрудников.
Когда мы приглашаем к себе гостей, то нам совершенно не все равно,кто придет и кого приведет с собой. С точки зрения индивидуальных человеческихвзаимоотношений ни один человек не равен другому. Когда мы говорим о всеобщемравенстве людей, то понимаем под этим в действительности равенство прав передзаконом, равноценность личностей, но не равенство индивидуальностей.
Рассмотрим множество животных. Мы разобьем их на следующие шестьгрупп: 1 – сухопутные млекопитающие, 2 – обитающие в воде, 3 – насекомые, 4 –птицы, 5 – мифические существа, 6 – пресмыкающиеся. Будем считать поопределению животных, входящих в одну группу, одинаковыми. Можно вообразитьситуацию, когда одинаковые в этом смысле животные взаимозаменимы. Например,когда учителю биологии надо показать ученикам представителей разных типов.
Если мы внимательно проанализируем, что общего в употреблениислова «одинаковость» во всех приведенных примерах, то мы увидимследующее.
Во-первых, одинаковость всегда понимается как бинарное отношениена некотором множестве объектов. Во-вторых, содержание этого отношения зависитот ситуации, в которой мы рассматриваем эти объекты, или от наблюдателя,который с выбранной им точки зрения судит об одинаковости объектов. В-третьих,слово «одинаковость» попадает в один синонимический ряд со словом «взаимозаменимость».
Действительно, одинаковость белых пешек или других одноименных иодноцветных фигур состоит в том, что любая из них может заменить другую. Какимбы шрифтом мы не печатали слово в словаре, оно остается таким же словом.Кажется очень естественным предположить, что в данной ситуации взаимозаменяемыте и только те объекты, которые одним и тем же набором формальных признаков,существенных в данной ситуации.
Пусть /> – некотороемножество объектов, в котором некоторые объекты взаимозаменимы. Обозначим через/> множество всех объектов,взаимозаменимых с объектом />.Очевидно, что /> и объединениевсех /> (при всевозможных />) совпадает со всеммножеством />: />.
Предположим, что />. Этозначит, что существует некоторый элемент /> такой,что он одновременно принадлежит /> и />. Значит, /> взаимозаменим с /> и /> взаимозаменим с />. Следовательно, /> взаимозаменим с />, а значит и с любымэлементом из />. Таким образом, />. Симметричным рассуждениемможно показать, что />. Таким образом,встречающиеся в объединении /> множества/> либо целиком совпадают,либо не пересекаются. Проведенное выше рассуждение наводит на мысль, как можнострого определить отношение одинаковости, или взаимозаменимости. В связи с этимобратим внимание на способ употребления слов в математике. До сих пор мы имелидело со словами «одинаковость», «взаимозаменимость». Этислова никак не определялись, а использовались так, как мы привыкли ихупотреблять в обыденной речи. Но с точки зрения математических понятий слово «эквивалентность»является экспликацией (точным определением) понятия одинаковости.
3.2 От сходства к толерантности
Например, две новые «Волги» одного выпуска и цвета сточки зрения покупателя вполне одинаковы и, стало быть, взаимозаменимы. Но две «Волги»разного выпуска (или новая и старая «Волги» одного выпуска) толькопохожи. При отсуствии необходимого выбора одна может заменить другую, еслипокупатель готов согласиться с подобной заменой.
Двое близнецов бывают настолько одинаковыми, что без всякого рискамогут сдавать экзамены друг за друга. Если два студента только похожи, то такаяжульническая проделка, хотя и осуществима, но рискована.
Если для объектов указано только сходство, то невозможно ихразбить на четкие классы так, что внутри класса объекты похожи, а междуобъектами разных классов сходства нет. В случае сходства возникает размытаяситуация без четких границ.
Каждый элемент множества несет определенную информацию о похожихна него элементах. Но не всю информацию), как в случае одинаковых элементов.Здесь уже нет дилеммы: «Все или ничего» или «Полная информация –отсутствие информации», Здесь возможны разные степени информации, которуюодни элемент содержит относительно другого.
Превосходная степень от сходства – неразличимость, а вовсе неодинаковость, как может показаться на первый взгляд. Одинаковость – свойствокачественно иное. Дело в том, чю неразличимые объекты (так же, как и сходные)не разбиваются, вообще говоря, на классы так, чтобы в каждом классе элементы неразличались, а элементы разных классов заведомо различались.
В самом деле. Возьмем множество точек на плоскости. Пусть величина/> лежит ниже порогаразрешимости глаза, т.е. /> – такоерасстояние, при котором точки, находящиеся на этом расстоянии, неразличимызрительно (при выбранном удалении плоскости от наблюдателя). Возьмем теперь /> точек, лежащих на однойпрямой и отстоящих (каждая oт соседних) на расстоянии />.Каждая пара соседних точек неразличима, но если /> достаточновелико, то первая и последняя точки будут отстоять друг от друга на метр изаведомо будут различимы. Разумеется, одинаковость есть частный случаинеразличимости и сходства.
Традиционный подход к изучению сходства или неразличимости состоитв том, чтобы сначала определить меру сходства, а затем исследовать взаимноерасположение сходных объектов. Английский математик Зиман, изучая моделизрительного аппарата, предложил аксиоматическое определение сходства. Тем самымсвойства сходства стало возможным изучать независимо от того, как конкретно онозадано в тон или иной ситуации: расстоянием между объектами, совпадениемкаких-то признаков или субъективным мнением наблюдателя.
Так же, как переход от расплывчатого понятия «одинаковость»к точно определенному тину отношении сопровождался введением пового термина «эквивалентность»,математическое отношение, соответствующее нашему интуитивному представлению осходстве или неразличимости, получило у Зимана название «толерантность».Иначе говоря, толерантность является экспликацией понятия сходства илинеразличимости.
Заключение
В данной курсовой работе были рассмотрены и изучены понятияотношений эквивалентности и толерантности. В главе первой изложена информацияоб отношении эквивалентности: основные определения и связь между ними, свойстваэквивалентности, операции над эквивалентностями, отношения эквивалентности начисловой прямой. В следующей главе содержится основной материал об отношениитолерантности: основные определения и примеры толерантностей, их свойства,установлены операции над толерантностями, раскрыты понятия пространства икласса толерантности. Также установлена связь отношений эквивалентности итолерантности. В последней главе объяснены математические термины «эквивалентность»и «толерантность» с помощью таких привычных для всех слов как «одинаковость»и «сходство». С помощью этих же слов мы установили, в каких областяхзнаний и практики человека нашли свое применение термины «эквивалентность»и «толерантность».
Литература
1. Шрейдер Ю.А. Равенство, сходство и порядок. – М.: Наука,1971
2. Бурбаки Н. Теория множеств. – М.: Мир, 1965
3. Общая алгебра. Т. 1./ О.В. Мельников, В.Н. Ремесленников,В.А. Роляньков и др. Под общ. ред. Л.А. Сибриянова. – М.: Наука, 1999 –592 с.