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

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

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

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

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

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

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

Гомель 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 – номер элемента в своем классе. Ясно, что если , и , то . Действительно, либо элементы и попали в разные классы – тогда у них различные первые номера; ; либо они различаются номером в классе – тогда . Представим теперь числа и в двоичной системе счисления. Пусть – наибольшее число разрядов у чисел , а – наибольшее число разрядов у чисел . Если некоторое имеет меньше, чем разрядов, то дополним его слева нулями. Так же поступим и со вторыми номерами. Тем самым каждому элементу будет сопоставлен кортеж из двоичных признаков.