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

Поможем в ✍️ написании учебной работы

Имя

Поможем с курсовой, контрольной, дипломной, рефератом, отчетом по практике, научно-исследовательской и любой другой работой

Нажимая кнопку "Продолжить", я принимаю политику конфиденциальности

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

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

математический факультет

Кафедра алгебры и геометрии

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

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

Гомель 2005

Введение

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

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

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

Реферат

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

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

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

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

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

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

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

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

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

Определение

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

1) и

2) при .

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

Определение

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

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

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

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

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

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

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

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

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

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

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

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

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

Определение

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

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

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

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

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

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

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

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

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

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

Теорема

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Таким образом, соотношение выполнено в следующих случаях: 1) , и ; 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.3 (см. ниже) получаем, что отношение – эквивалентность. Из вытекает, что и – эквивалентность. Теорема доказана.

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

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

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

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

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

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

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

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

Лемма

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

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

Лемма

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

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

Из и

Из леммы 1.3.5

Из , , леммы 1.3.5 и того, что любое отношение вида транзитивно,

Подобно тому как доказывается , доказывается

Подобно тому как мы из и вывели , из и выводится

Из и аналогично доказываемого "обратного" включения вытекает . Теорема доказана.

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

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

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

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

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

Далее, применяя распределительный закон получим

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

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

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

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

Теорема

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

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

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

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

Определение

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

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

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

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

Пример

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

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

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

Пример

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

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

Пример

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

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

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

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

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

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

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

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

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

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

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

Лемма

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Определение

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

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

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

Определение

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

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

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

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

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

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

Лемма

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

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

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

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

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

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

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

Лемма

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

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

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

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

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

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

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

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

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

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

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

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

Лемма

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

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

Лемма

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

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

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

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

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

Определение

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

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

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

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

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

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

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

Отметим очевидное включение

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

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

Определение

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

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

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

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

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

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

Лемма. Разиение множества на ядра относительно базиса совпадает с разбиением множества на обычные ядра.

Доказательство. Буквально повторяя доказательство леммы 2.5.1, мы получим, что ядра, определенные по базису – это классы эквивалентности по . Значит, они совпадают с исходными ядрами.

Теорема. Если пространство толерантности имеет конечный базис , то совокупность всех классов толерантности в конечна.

Доказательство. В силу леммы 2.5.2 число ядер конечно, т.е. конечно пространство ядер . Значит, имеет конечное число классов толераитпости. Но так как равносильно , то каждый класс толерантности в есть объединение ядер, образующих соответствующий класс толерантности в . Таким образом, совокупность всех классов толерантности в конечна.

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

Теорема

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

Доказательство. Рассмотрим некоторый класс толерантности . Пусть . По определению класса, для всякого , , а по определению толераптности существует признак такой, что . Тогда 1) ; 2) . Действительно, 1) следует из того, что для всех признаков , a 2) следует из того, что всякий , принадленжащий , толерантен к . Поскольку – произвольный элемент из , по свойству максимальности класса . Отсюда вытекает, что , что доказывает теорему.

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

Теорема

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

Доказательство. По определению толерантности в для всякого любая пара и толерантна. Значит, есть предкласс. Тогда по лемме 2.3.2 получается существует класс . Выберем для каждого один из классов . Очевидно, выбранная совокупность классов удовлетворяет условию 1) из определения 1.4.1. Значит, она содержит некоторый базис .

Следствие. Когда конечно, то существует базис классов толерантности, число классов в котором не превышает количества исходных признаков.

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

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

Теорема

Если выполнено соотношение: , то выполнено и соотношение , т.е. .

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

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

Теорема

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

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

Рассмотрим еще так называемые сопряженные и производные пространства толерантности.

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

Определение. Если совпадает с множеством всех классов, то пространство называется сопряженным к и обозначается (таким образом, ).

Рассмотрим несколько примеров.

В пространстве элемент , содержащий все числа, толерантен ко всем элементам и, стало быть, входит во все классы толерантности. Значит, в пространствe – полное отношение.

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

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

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

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

Определение. Второе сопряженное пространство относительно некоторого базиса в и базиса в называется производным от исходного пространства толерантности .

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

Рассмотрим несколько примеров.

1. Для линейного графа с вершинами производное пространство также есть линейный граф, но с вершинами (см. рис. 4)

2. Для циклического графа с вершинами производное пространство "совпадает" с исходным пространством (см. рис. 5).

3. Та же ситуация для зацепленных циклических графов (см. рис. 6).

4. Для пространства производное пространство состоит из одного элемента.

Теорема

Если – произвольное пространство толерантности, а – произвольный базис в нем, то существует такой базис в сопряженном пространстве и такое инъективное отображение , что при и из следует .

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

Приложение понятий эквивалентности и толерантности в различных областях знаний и практики человека

От сходства к толерантности

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

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

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

Каждый элемент множества несет определенную информацию о похожих на него элементах. Но не всю информацию), как в случае одинаковых элементов. Здесь уже нет дилеммы: "Все или ничего" или "Полная информация – отсутствие информации", Здесь возможны разные степени информации, которую одни элемент содержит относительно другого.

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

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

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

Так же, как переход от расплывчатого понятия "одинаковость" к точно определенному тину отношении сопровождался введением пового термина "эквивалентность", математическое отношение, соответствующее нашему интуитивному представлению о сходстве или неразличимости, получило у Зимана название "толерантность". Иначе говоря, толерантность является экспликацией понятия сходства или неразличимости.

Заключение

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

Литература

1. Шрейдер Ю.А. Равенство, сходство и порядок. – М.:Наука, 1971

2. Бурбаки Н. Теория множеств. – М.:Мир, 1965

3. Общая алгебра. Т. 1./ О.В. Мельников, В.Н. Ремесленников, В.А. Роляньков и др. Под общ. ред. Л.А. Сибриянова. – М.:Наука, 1999 – 592 с.

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

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

математический факультет

Кафедра алгебры и геометрии

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

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

Гомель 2005

Введение

Реферат

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

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

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

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

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

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

Определение

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

1) и

2) при .

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

Определение

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

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

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

Определение

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

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

Теорема

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

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

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

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

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

Теорема

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

Теорема

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

Дата: 2019-07-30, просмотров: 240.

12 3 4 5 6 7 8 Следующая ⇒