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

ЛИЧНЫЙ КАБИНЕТ 

 

Здравствуйте гость!

 

Логин:

Пароль:

 

Запомнить

 

 

Забыли пароль? Регистрация

Повышение уникальности

Предлагаем нашим посетителям воспользоваться бесплатным программным обеспечением «StudentHelp», которое позволит вам всего за несколько минут, выполнить повышение уникальности любого файла в формате MS Word. После такого повышения уникальности, ваша работа легко пройдете проверку в системах антиплагиат вуз, antiplagiat.ru, etxt.ru или advego.ru. Программа «StudentHelp» работает по уникальной технологии и при повышении уникальности не вставляет в текст скрытых символов, и даже если препод скопирует текст в блокнот – не увидит ни каких отличий от текста в Word файле.

Результат поиска


Наименование:


Курсовик Эквивалентность, ее формальные свойства и операции над отношениями. Доказательство основных теорем, лемм. Отношения эквивалентности на числовой прямой. Характерные свойства толерантности. Применение эквивалентности и толерантности в сферах различных наук.

Информация:

Тип работы: Курсовик. Предмет: Математика. Добавлен: 20.09.2009. Сдан: 2009. Уникальность по antiplagiat.ru: --.

Описание (план):


МИНИСТЕРСТВО ОБРАЗОВАНИЯ РЕСПУБЛИКИ БЕЛАРУСЬ
"Гомельский государственный университет имени Франциска Скорины"
математический факультет
Кафедра алгебры и геометрии
Курсовая работа
"Отношения эквивалентности и толерантности и их свойства"
Гомель 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.3 отсюда следует, что есть отношение эквивалентности.
Оказывается, когерентность отношений , является не только достаточным, но и необходимым условием для того, чтобы объединение эквивалентностей и было эквивалентностью.
1.3.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.4 выполняется . Для доказательства остается доказать
Пусть . Тогда для некоторого имеем и . Следовательно, и . Значит, и доказано. Пусть теперь выполнено . Отношение симметрично. По тогда симметрично и ортношение . . По теореме 1.3.3 (см. ниже) получаем, что отношение - эквивалентность. Из вытекает, что и - эквивалентность. Теорема доказана.
Условие, при котором произведение двух отношений эквивалентности и само является эквивалентностью, было получено чешским математиком Шиком в 1954 г.
Для того чтобы произведение отношений эквивалентности и было эквивалентностью, необходимо и достаточно, чтобы и коммутировали.
Доказательство. Пусть сначала
рефлексивно. симметрично. Транзитивность произведения доказывается так: - здесь мы использовали ассоциативный закон для произведения отношений, условие , а также транзитивность и рефлексивность отношений и . Итак , но это и означает транзитивность отношения , поскольку рефлексивно. Пусть теперь произведение есть эквивалентность. Тогда .
Легко проверить, что если и - эквивалентности, то и также будут эквивалентностями.
Оказывается, операция (ее иногда называют, объединением эквивалентностей, имея в виду, что обычное объединение эквивалентностей может не быть эквивалентностью) ассоциативна, т.е. является "хорошей" алгебраической операцией.
Для любых транзитивных отношений , и справедлив ассоциативный закон:
Докажем сначала две леммы.
1.3.5 Лемма
Для любых отношений ,
вытекает из . доказывается аналогично.
1.3.5 Лемма
Для любых транзитивных отношений , , из и вытекает .
Доказательство теоремы 1.3.4. Из леммы 1.3.5
Из и
Из леммы 1.3.5
Из , , леммы 1.3.5 и того, что любое отношение вида транзитивно,
Подобно тому как доказывается , доказывается
Подобно тому как мы из и вывели , из и выводится
Из и аналогично доказываемого "обратного" включения вытекает . Теорема доказана.
Нетрудно убедиться, что для любой эквивалентности
где - диагональное отношение.
Покажем теперь, что операция не дает ничего нового:
Если и - эквивалентности, то
Доказательство. Заметим сначала, что, учитывая лемму 1.3.4, Применяя транзитивное замыкание к обеим частям, ввиду свойства монотонности транзитивного замыкания имеем
Далее, применяя распределительный закон получим
Мы использовали здесь тот факт, что для рефлексивного выполнено включение , а следовательно, . Запишем теперь выражение для транзитивного замыкания, используя :
Отсюда ясно, что , т.е.
Сравнивая включения и получим искомое соотношение .
Отсюда вытекает следующий результат, также принадлежащий Шику:
1.3.6 Теорема
Если и - эквивалентности и , то
В самом деле, по теореме 1.3.3 произведение является эквивалентностью, а стало быть отношение совпадает со своим транзитивным замыканием . Но тогда из теоремы 1.3.5 следует .
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 Лемма
Если - толерантность, - эквивалентность и , то .
Доказательство получается применением транзитивного замыкания к обеим частям включения .
Смысл этой леммы в том, что транзитивное замыкание отношения толерантности есть минимальная эквивалентность, включающая эту толерантность.
Теорема. Для того, чтобы произведение отношений толерантности и было толерантностью, необходимо и достаточно, чтобы и коммутировали. В этом случае .
Доказательство. Симметрическое произведение толерантностей и всегда будет толерантностью. Симметричность симметризованного произведения следует из того, что: .
Можно вве и т.д.................


Перейти к полному тексту работы



Смотреть похожие работы


* Примечание. Уникальность работы указана на дату публикации, текущее значение может отличаться от указанного.