Отношения эквивалентности и толерантности и их свойства
МИНИСТЕРСТВО ОБРАЗОВАНИЯ РЕСПУБЛИКИ БЕЛАРУСЬ
"Гомельский государственный университет имени Франциска Скорины"
математический факультет
Кафедра алгебры и геометрии
Курсовая работа
"Отношения эквивалентности и толерантности и их свойства"
Гомель 2005
Введение
В обыденной речи мы часто говорим об одинаковости (о равенстве) каких-то объектов (предметов, множеств, абстрактных категорий), не заботясь о надлежащем уточнении смысла, который мы вкладываем в слово "одинаковый". В главе первой попробуем выявить и раскрыть понятие "одинаковости", определим термины "эквивалентность" и "отношение эквивалентности".
Не менее важной является ситуация, когда нам приходится устанавливать сходство объектов. Если одинаковость объектов означает их взаимозаменимость в некоторой ситуации, то сходство – это частичная взаимозаменимость, т.е. возможность взаимной замены с некоторыми (допустимыми в данной ситуации) потерями, с допустимым риском. Во второй главе попробуем раскрыть понятие "толерантности" на базе таких терминов, как "одинаковость" и "сходство" объектов.
А в третьей главе подробнее рассмотрим применение понятий отношений эквивалентности и толерантности в различных областях знаний и практики человека.
Реферат
![]()
Курсовая работа содержит: 41 страница, 3 источника, 1 приложение.
Ключевые слова: отношение эквивалентности, отношение толерантности, одинаковость, сходство, взаимозаменимость, классы эквивалентности, пространство толерантности, классы толерантности, предкласс, базис.
Объект исследования: отношения эквивалентности и толерантности.
Предмет исследования: свойства отношений эквивалентности и толерантности.
Цель работы: используя рекомендуемую литературу рассмотреть понятия отношений эквивалентности и толерантности; рассмотреть приложения этих понятий в различных областях знаний и практики человека.
Методы исследования: методы теории множеств и теории отношений.
Задачами курсовой работы являются: изучить свойства отношений эквивалентности и толерантности и их приложения в конкретных областях знаний.
1. Отношение эквивалентности
1.1 Определение и примеры
1.1.1 Определение
Систему
непустых подмножеств
множества
мы будем называть
разбиением
этого множества,
если
1)
и
2)
при
.
Сами
множества
называются
при этом классами
данного разбиения.
1.1.2 Определение
Отношение
на множестве
называется
эквивалентностью
(или отношением
эквивалентности),
если существует
разбиение
множества
такое, что
соотношение
выполняется
тогда и только
тогда, когда
и
принадлежат
некоторому
общему классу
данного разбиения.
Пусть
– разбиение
множества
.
Определим,
исходя из этого
разбиения,
отношение
на
:
,
если
и
принадлежат
некоторому
общему классу
данного разбиения.
Очевидно, отношение
является
эквивалентностью.
Назовем
отношением
эквивалентности,
соответствующим
исходному
разбиению.
Например,
разбиение
состоит из
подмножеств
множества
,
содержащих
ровно по одному
элементу.
Соответствующее
отношение
эквивалентности
есть отношение
равенства
.
Наконец, если
разбиение
множества
состоит из
одного подмножества,
совпадающего
с самим
,
то соответствующее
отношение
эквивалентности
есть полное
отношение:
любые два элемента
являются
эквивалентными.
Пустое отношение (на непустом множестве!) не является эквивалентностью.
Мы
подошли к
эквивалентности
через понятие
взаимозаменимости.
Но что значит,
что два объекта
и
взанмозамепимы
в данной ситуации?
Это всегда
можно понимать
так, что каждый
из них содержит
всю информацию
о другом объекте,
небезразличную
в данной ситуации.
Это утверждение
означает только
то, что взаимозаменимость
объектов есть
совпадение
признаков,
существенных
в данной ситуации.
Например, пусть мы считаем одинаковыми автомобили, выпущенные в одной и той же серии одним и тем же заводом. Тогда, разобрав один экземпляр "Волги", мы в принципе можем составить комплект рабочих чертежей, который годится для выпуска однотипных "Волг". Однако, изучив один экземпляр "Волги", мы не можем угадать окраску кузова или характер вмятин на бампере у других односерийных экземпляров.
Когда мы выбираем из комплекта одну шахматную фигуру, то мы знаем, куда ее можно поставить в начальной позиции и как ходят, все взаимозаменяемые с ней, т.е. одноименные и одноцветные, фигуры.
Пусть
теперь задано
разбиение
множества
.
Выберем в каждом
множестве
некоторый
содержащийся
в нем элемент
.
Этот элемент
мы будем называть
эталоном для
всякого элемента
,
входящего в
то же множество
.
Мы будем – по
определению
– полагать
выполненным
соотношение
.
Так определенное
отношение
назовем отношением
"быть эталоном".
Легко
видеть, что
эквивалентность
,
соответствующая
исходному
разбиению,
может быть
определена
так:
,
если
и
имеют общий
эталон:
и
.
Ясно, что любое отношение эквивалентности может быть таким образом определено с помощью отношения "быть эталоном" и, наоборот, любое отношение "быть эталоном" определяет некоторую эквивалентность.
Пусть
– отношение
эквивалентности,
а
– такое отношение
"быть эталоном",
что
выполнено в
том и только
том случае,
когда
и
имеют общий
эталон
.
Иначе
говоря,
равносильно
существованию
такого
,
что
и
.
Поскольку
,
это означает,
что
.
Иначе говоря,
эквивалентность
можно алгебраически
выразить через
более простое
отношение "быть
эталоном".
Отношение
на множестве
из
элементов можно
задать графом,
имеющим ровно
стрелок, где
– число классов
эквивалентности:
каждый элемент
соединяется
со своим единственным
эталоном. Граф,
изображающий
отношение
эквивалентности,
состоит из
полных подграфов,
содержащих
по
,
вершин
.
Таким образом,
общее число
ребер в этом
графе равно
.
Рассмотрим
в качестве
множество всех
целых неотрицательных
чисел и возьмем
его разбиение
на множество
четных чисел
и множество
нечетных чисел.
Соответствующее
отношение
эквивалентности
на множестве
целых чисел
обозначается
так:
и читается:
сравнимо с
по модулю 2. В
качестве эталонов
здесь естественно
выбрать 0 – для
четных чисел
и 1 – для нечетных
чисел. Аналогично,
разбивая то
же множество
на
подмножеств
,
где
состоит из всех
чисел, дающих
при делении
на
и остатке
,
мы придем к
отношению
эквивалентности:
,
которое выполняется,
если
и
имеют одинаковый
остаток при
делении на
.
В качестве
эталона в каждом
естественно
выбрать соответствующий
остаток
.
1.2 Формальные свойства эквивалентности
Мы определили выше отношении эквивалентности с помощью разбиений, т.е. фактически задали их некоторой конструкцией. Можно было бы и по-другому определить эквивалентности: можно сформулировать свойства (аксиомы), которые выделяют отношения эквивалентности среди прочих бинарных отношений.
1.2.1 Определение
Отношение
на множестве
называется,
эквивалентностью
(или отношением
эквивалентности),
если оно рефлексивно,
симметрично
и транзитивно.
Мы сейчас дали два независимых определения одного и того же понятия. Теперь нам следует убедиться, что оба определения эквивалентпости равносильны.
Теорема.
Если отношение
на множестве
рефлексивно,
симметрично
и транзитивно,
то существует
разбиение
множества
такое, что
соотношение
выполнено в
тех и только
тех случаях,
когда
и
принадлежат
общему классу
разбиения.
Обратно:
если задано
разбиение
множества
и бинарное
отношение
определено
как "принадлежать
общему классу
разбиения",
то
рефлексивно,
симметрично
и транзитивно.
Доказательство
первой части.
Рассмотрим
рефлексивное,
симметричное
и транзитивное
отношение
на
.
Пусть для любого
множество
состоит из всех
таких элементов
,
для которых
.
Лемма.
Для любых
и
либо
,
либо
.
Доказательство
леммы. Пусть
пересечение
.
Покажем, что
.
Пусть
,
тогда выполнено
и
по самому определению
множеств