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

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

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

 

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

 

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

 

 

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

 

 

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

 

 

Гомель 2005

Введение

 

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

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

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

 

 

Реферат

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

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

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

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

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

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

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

 

 

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

 

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

 

Определение

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

1)  и

2)  при .

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

 

Определение

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

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

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

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

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

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

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

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

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

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

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

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

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

 

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

 

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

Определение

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

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

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

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

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

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

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

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

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

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

Теорема

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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