Детская площадка » Блоги мам » Эквивалентные отношения примеры. Отношение эквивалентности

Эквивалентные отношения примеры. Отношение эквивалентности

Связанные определения

Множество всех классов эквивалентности обозначается .

Примеры отношений эквивалентности

Более сложный пример, но совершенно жизненно важный:

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

Таким образом, всевозможные рецепты салатов и коктейлей, ГОСТы и классификаторы также определяют жизненно важные отношения эквивалентности. Отношения эквивалентности заполняют всю нашу жизнь, а не являются абстрактной забавой математиков.

Факторизация отображений

Множество классов эквивалентности, отвечающее отношению эквивалентности , обозначается символом и называется фактор-множеством относительно . При этом сюръективное отображение

называется естественным отображением (или канонической проекцией ) на фактор-множество .

Пусть , - множества, - отображение, тогда бинарное отношение определённое правилом

является отношением эквивалентности на . При этом отображение индуцирует отображение , определяемое правилом

или, что то же самое,

.

При этом получается факторизация отображения на сюръективное отображение и инъективное отображение .

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

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

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

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

Литература

  • А. И. Кострикин , Введение в алгебру. М .: Наука, 1977, 47-51.
  • А. И. Мальцев , Алгебраические системы, М .: Наука, 1970, 23-30.
  • В. В. Иванов , Математический анализ. НГУ, 2009.

См. также

  • Отношение толерантности - ослабленная форма эквивалентности.
  • Эквиваленция - логическая операция.

Wikimedia Foundation . 2010 .

  • Госпитальная пневмония
  • Mitel

Смотреть что такое "Отношение эквивалентности" в других словарях:

    отношение эквивалентности - — Тематики электросвязь, основные понятия EN equivalence relation … Справочник технического переводчика

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

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

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

    ОТНОШЕНИЕ - в логике то, что в отличие от свойства характеризует не отдельный предмет, а пару, тройку и т.д. предметов. Традиционная логика не рассматривала О.; в современной логике О. пропозициональная функция от двух или большего числа переменных. Бинарным … Философская энциклопедия

    Отношение предпочтения - в теории потребления это формальное описание способности потребителя сравнивать (упорядочивать по желательности) разные наборы товаров (потребительские наборы). Чтобы описать отношение предпочтения, не обязательно измерять желательность… … Википедия

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

    отношение - ОТНОШЕНИЕ множество упорядоченных п ок индивидов (где п > 1), т.е. двоек, троек и т.д. Число п называется «местностью», или «арностью», О. и, соответственно, говорят о n местном (п арном) О. Так, например, двуместное О. называют… … Энциклопедия эпистемологии и философии науки

    Отношение - I Отношение философская категория, выражающая характер расположения элементов определённой системы и их взаимозависимости; эмоционально волевая установка личности на что либо, т. е. выражение её позиции; мысленное сопоставление различных… … Большая советская энциклопедия

    Класс эквивалентности - Отношение эквивалентности () на множестве X это бинарное отношение, для которого выполнены следующие условия: Рефлексивность: для любого a в X, Симметричность: если, то, Транзитивность: если … Википедия

Книги

  • Принятие финансовых решений в условиях сравнительной неопределенности: Монография , Баюк О.А.. В монографии разработана и теоретически обоснована новая логическая стратегия принятия решений при выборе между несравнимыми объектами, устанавливающая особое отношение предпочтения и…

ОТНОШЕНИЯ

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

x А, у А отношение Г = {(x,y)| P(x,y)}, P(x,y) какое-то утверждение (предикат).

Если (x,y) Г, то говорят, что х находятся в отношении Г к у .

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

Более строгое определение:

Бинарным отношением называется два множества:

1) несущее множество А,

2) множество пар Г={(x,y)| x A, y A}, являющегося подмножеством квадрата несущего множества.

n-местное отношение, или n-арное (тернарное, кватернарное, …) отношение – это несущее множество А и множества кортежной размерностью n ,являющегося подмножеством множества А n .

Пример тернарного отношения: входить в «тройку игроков».

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

Отношение можно определить также как двухместный предикат предметных переменных х, у , принимающего значение «истина», если (х, у) Г и значение «ложь», если не принадлежит.

Обозначения: (х, у) Г, у = Г(x), у = Гx или просто xГу , например, отношение равенства(х = у) , отношение порядка(х < у) .

Если (х, у) Г , то xГу принимает значение «истина», иначе – «ложь».

Если отношения заданы на дискретном множестве, их можно записывать в виде матрицы

A i , j =

Отношение – частный случай соответствия, для него можно ввести обратные отношения, композицию отношений:

Г -1 ={(y,x)| (x,y) Г}, Г ◦ Δ = {(x,z) | y ((x,y) Г &(y,z Δ))}.

Вводят понятие «единичного элемента» Δ 0 = {(x,x)} – «быть в отношении к самому себе». В матричном представлении это будет - главная диагональ).

Свойства бинарных отношений

1 Рефлексивность – «находиться в отношении к самому себе»

хГх – истина (например, отношения х=x, х≤x, х≥x ).

2 Антирефлексивность - «не быть в отношении к самому себе»

хГx - ложь (например, отношения х≠x, хх ).

Если множество не «рефлексивно», то это еще не значит что оно «антирефлексивно».

3 Симметричность «независимость от того, какой элемент первый, какой второй»

хГу – истина → уГх – истина (например, отношения х=у, х≠у ).

4 Антисимметричность «не превосходить»

(хГу – истина) & (yГх – истина) → (х=у) (например, отношения х≤у, х≥у ).

5 Асимметричность (несимметричность) «превосходить»

хГу – истина → уГх –ложь (например, отношения х<у, х>у ).

6. Транзитивность «передаточность»

(хГу – истина) & (yГz – истина) → (хГz – истина) (например, отношения х=у, х<у, х>у, х≤у, х≥у , отношение х≠у транзитивностью не обладает).

СПЕЦИАЛЬНЫЕ БИНАРНЫЕ ОТНОШЕНИЯ

Рассмотрим «отношение эквивалентности», «отношение нестрогого порядка», «отношение строгого порядка» и «отношение доминирования».

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

Отношением эквивалентности называется рефлексивное (х~x) , симметричное ((х~y)=(y~x)) , транзитивное ((х~у)&(y~z)→(х~z)) отношение.

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

Подмножество элементов, эквивалентных одному элементу, называется классом эквивалентности или смежным классом.

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

Свойства.

Все элементы в классе эквивалентны между собой.

Элементы из разных классов не эквивалентны.

Один элемент может входить только в свой класс.

Все множество можно представить как объединение классов.

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

Индекс разбиения – число классов эквивалентности.

Фактор-множество относительно отношения эквивалентности - это множество всех классов или представителей класса.

Мощность фактора-множества равна индексу разбиения.

Отношения порядка

Отношением порядка называют два вида бинарных отношений.

Отношениемнестрогого порядка называется рефлексивное (х≥x) , антисимметричное ((x≤y)&(y≤x)→ (x=y)) , транзитивное ((х≥у)&(y≥z)→(х≥z)) отношение .

Говорят, что на множестве установлен нестрогий порядок. В понятия ≤ , ≥ вкладывают более широкий смысл: не хуже – не лучше, не раньше – не позже и так далее. В теории множеств пример нестрого порядка - нестрогое включение (быть подмножеством другого множества0.

Отношениемстрогого порядка называется антирефлексивное ((х, антисимметричное ((x, транзитивное

((х>у)&(y отношение .

Говорят, что на множестве установлен строгий порядок. В понятия < , > вкладывают более широкий смысл: хуже – лучше, раньше – позже и так далее. В теории множеств пример строго порядка - строгое включение (быть подмножеством другого множества и при этом не быть равным ему).

Упорядоченные множества

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

Множество действительных или целых чисел: классические примеры упорядоченного множества.

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

Это множество векторов, множество комплексных чисел, множества в теории множеств. В некоторых случаях мы можем говорит «больше – меньше» или «являться надмножеством и подмножеством», но не во всех случаях.

Лекция 22. Отношения эквивалентности и порядка на множестве

1. Отношение эквивалентности. Связь отношения эквивалентности с разбиением множества на классы.

2. Отношение порядка. Строгое и нестрогое отношения порядка, отношение линейного порядка. Упорядоченность множеств.

3. Основные выводы

Рассмотрим на множестве дробей X = {1/2, 1/3, 1/4, 2/4, 2/6, 3/6} отношение равенства. Это отношение:

Рефлексивно, так как всякая дробь равна сама себе;

Симметрично, так как из того, что дробь m /n равна дроби p /q , следует, что дробь p /q равна дроби m /n ;

Транзитивно, так как из того, что дробь m /n равна дроби p /q и дробь p /q равна дроби r /s , следует, что дробь m /n равна дроби r /s .

Про отношение равенства дробей говорят, что оно является отношением эквивалентности .

Определение. Отношение R на множестве X называется отноше­нием эквивалентности, если оно одновременно обладает свойства­ми рефлексивности, симметричности и транзитивности.

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

Почему в математике выделили этот вид отношений? Рассмот­рим отношение равенства дробей, заданное на множестве X = {1/2, 1/3, 1/4, 2/4, 2/6, 3/6} (Рис.106). Видим, что множество разбилось на три подмножества: {1/2, 2/4, 3/6}, {1/3, 2/6}, {1/4}. Эти подмножества не пересекаются, а их объединение совпадает с множест­вом Х, т.е. имеем разбиение множест­ва X на классы. Это не случайно.

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

Так, мы установили, что отношению равенства на множестве дробей {1/2, 1/3, 1/4, 2/4, 2/6, 3/6} соответствует разбиение этого множества на классы эквивалентности, каждый из которых состоит из равных меж­ду собой дробей.

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

Рассмотрим, например, на множестве X = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10} отношение «иметь один и тот же остаток при делении на 3». Оно по­рождает разбиение множества X на классы: в один попадут все числа, при делении которых на 3 получается в остатке 0 (это числа 3, 6, 9), во второй - числа, при делении которых на 3 в остатке получается 1 (это числа 1, 4, 7, 10), и в третий - все числа, при делении которых на 3 в остатке получается 2 (это числа 2, 5, 8). Действительно, полученные подмножества не пересекаются и их объединение совпадает с множе­ством X. Следовательно, отношение «иметь один и тот же остаток при делении на 3», заданное на множестве X, является отношением экви­валентности. Заметим, что утверждение о взаимосвязи отношения эквивалентности и разбиения множества на классы нуждается в доказательстве. Мы его опускаем. Скажем только, что если отношение эквивалентности имеет название, то соответствующее название дается и классам. Например, если на множестве отрезков задается отношение равенства (а оно является отношением эквивалентности), то множест­во отрезков разбивается на классы равных отрезков (см. рис. 99). От­ношению подобия соответствует разбиение множества треугольников на классы подобных треугольников.



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

Принцип разбиения множества на классы при помощи некоторого отношения эквивалентности является важным принципом математи­ки. Почему?

Во-первых , эквивалентный - это значит равносильный, взаимо­заменяемый. Поэтому элементы одного класса эквивалентности взаимозаменяемы. Так, дроби, оказавшиеся в одном классе эквивалентности {1/2, 2/4, 3/6} неразличимы с точки зрения отношения равен­ства, и дробь 3/6 может быть заменена другой, например 1/2. И эта замена не изменит результата вычислений.

Во-вторых , поскольку в классе эквивалентности оказываются эле­менты, неразличимые с точки зрения некоторого отношения, то счи­тают, что класс эквивалентности определяется любым своим предста­вителем, т.е. произвольным элементом этого класса. Так, любой класс равных дробей можно задать, указав любую дробь, принадлежащую этому классу. Определение класса эквивалентности по одному предста­вителю позволяет вместо всех элементов множества изучать совокуп­ность отдельных представителей из классов эквивалентности. Напри­мер, отношение эквивалентности «иметь одинаковое число вершин», заданное на множестве многоугольников, порождает разбиение этого множества на классы треугольников, четырехугольников, пятиугольни­ков и т.д. Свойства, присущие некоторому классу, рассматриваются на одном его представителе.

В-третьих , разбиение множества на классы с помощью отноше­ния эквивалентности используется для введения новых понятий. Например, понятие «пучок прямых» можно определить как то об­щее, что имеют параллельные между собой прямые.

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

Другим важным видом отношений являются отношения порядка.

Определение. Отношение R на множестве X называется отноше­нием порядка, если оно одновременно обладает свойствами анти­симметричности и транзитивности .

Примерами отношений порядка могут служить: отношение «меньше» на множестве натуральных чисел; отношение «короче» на множе­стве отрезков, поскольку они антисимметричны и транзитивны.

Если отношение порядка обладает еще свойством связанности, то говорят, что оно является отношением линейного порядка.

Например, отношение «меньше» на множестве натуральных чисел является отношением линейного порядка, так как обладает свойства­ми антисимметричности, транзитивности и связанности.

Определение. Множество X называется упорядоченным, если на нем задано отношение порядка.

Так, множество N натуральных чисел можно упорядочить, если за­дать на нем отношение «меньше».

Если отношение порядка, заданное на множестве X, обладает свойст­вом связанности, то говорят, что оно линейно упорядочивает множество X.

Например, множество натуральных чисел можно упорядочить и с помощью отношения «меньше», и с помощью отношения «кратно» - оба они являются отношениями порядка. Но отношение «меньше», в отличие от отношения «кратно», обладает еще и свойством связанности. Значит, отношение «меньше» упорядочивает множество на­туральных чисел линейно.

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

Отношение эквивалентности – это отношение, обладающее свойствами рефлексивности, симметричности и транзитивности. Обозначается знаком ~, записьа ~ в означает, что а эквивалентно в .

В соответствии с определением для отношения эквивалентности выполняются свойства:

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

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

Класс эквивалентности , порожденный элементом – множество всех элементов из , вступающих с в отношение эквивалентности. Класс эквивалентности определяется так:

, для
подбираются элементы
, находящиеся в соответствии с элементомх .

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

Фактор-множества множества по отношению эквивалентности φ – множество всех различных классов эквивалентности, обозначаемое А / φ .

Индекс разбиения , порожденный отношением φ – это мощность фактор-множества А / φ .

Пример 2 .11.

а) Отношение равенства
на любом множестве является отношением эквивалентности.

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

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

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

г) Отношение «иметь один и тот же остаток от деления на 9» является эквивалентностью на
. Это отношение выполняетсядля пар (12, 21), (17, 36) и не выполняется для пар (11, 13), (19, 29).

Пусть на множествезадано отношение эквивалентности . Осуществим следующее построение. Выберем элемент
и образуем класс (подмножество), состоящий из; затем выберем элемент
и образуем класс, состоящий изи всех элементов, эквивалентных, и т.д. Получится система классов
(возможно, бесконечная) такая, что любой элемент из входит хотя бы в один класс, то есть
. Эта система классов обладает следующими свойствами:

    она образует разбиение , то есть классы попарно не пересекаются ;

    любые два элемента из одного класса эквивалентны ;

    любые два элемента из разных классов неэквивалентны .

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

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

Пример. 2.12.

а) Все классы эквивалентности по отношению равенства
состоят из одного элемента.

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

в) Разбиение
по отношению «иметь общий остаток от деления на 7» имеет конечный индекс 7 и состоит из 7 счетных классов: 0, 7, 14, …; 2, 9, 16, …; …; 6, 13, 20, …

Похожие статьи