Отношение эквивалентности на множестве. Разбиение на классы. Отношение эквивалентности. Свойства эквивалентности. Фактор-множество. Классы эквивалентных элементов и их свойства

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

Пусть X - конечное или бесконечное множество. Отношением на X называется правило, по которому «сравниваются» его элементы. Это неформальное определение, но его вполне достаточно для наших целей. Заметим, что для определения отношения мы должны четко задать само множество; другими словами, нам должно быть ясно, какие элементы нужно сравнивать.

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

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

если для всех выполнены следующие свойства:

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

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

Третье - свойство транзитивности. На множестве целых чисел отношения «равно», «меньше, чем», «меньше или равно», - транзитивны. А вот «не равно» этим свойством не обладает. Действительно, и но из этих неравенств не следует Добавим, что симметрично, но не рефлексивно.

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

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

Приведем простой пример. Обозначим символом М множество цветных мячей с отношением эквивалентности «тот же цвет». Класс эквивалентности красного мяча в М состоит из всех красных мячей, содержащихся в М.

Одно из свойств классов эквивалентности настолько важно, что мы назовем его основным принципом классов эквивалентности. Принцип гласит, что любой элемент класса эквивалентности - хороший представитель всего класса. Иначе говоря, зная один элемент из класса эквивалентности, можно немедленно восстановить этот класс полностью. Этот факт бросается в глаза, когда мы имеем дело с множеством М цветных мячей и отношением «тот же цвет». Предположим, Вам говорят, что в картонной коробке находятся все элементы одного класса эквивалентности множества М. Увидев один элемент из этого множества (допустим, это синий мяч), Вы немедленно заключаете, что в коробке лежит класс эквивалентности всех синих мячей М. Проще и быть не может!

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

Докажем это непосредственно из определяющих свойств отношения эквивалентности. Если то, по определению класса эквивалентности, Ввиду симметричности, Но если то и Тогда свойство транзитивности влечет Мы доказали включение: . Похожее рассуждение доказывает обратное включение: Вероятно, это все может показаться несколько педантичным. Но основной принцип - такой источник неразберихи и ошибок, что нам не стоит жалеть усилий на прояснение его точного смысла. Кроме того, полезно осознать, что он непосредственно следует из определения отношения эквивалентности. Кстати о педантичности: вы поняли, что свойство вытекает из рефлексивности?

Основной принцип приводит к важнейшему свойству отношения эквивалентности. Как и раньше, пусть X - множество с отношением эквивалентности тогда

(1) X - объединение своих классов эквивалентности относительно и

(2) два разных класса эквивалентности не могут иметь общего элемента.

Первое утверждение следует из часто упоминаемого факта: класс эквивалентности элемента содержит сам этот элемент. Для доказательства второго предположим, что элементы Так как то по основному принципу Аналогично Так что у. Заметим, что свойства (1) и (2) означают, что множество X разбито на непересекающиеся подмножества, классы эквивалентности. Другими словами, мы имеем дело с разбиением множества

Множество, составленное из классов эквивалентности множества X относительно отношения эквивалентности имеет специальное название: фактормножество X по отношению Отметим, что элементы фактормножества - это подмножества в Поэтому фактормножество не является подмножеством в X, будьте внимательны!

Закончим этот параграф примером, в котором проявляется наконец истинная природа дробей. Из чего состоит дробь? Когда Вы на нее смотрите, то видите два числа, одно из которых (знаменатель) должно быть ненулевым. Конечно, Вы ее, вероятно, воспринимаете как частное. Но если на Вас надавить, Вы можете попытаться выбрать более легкий выход и сказать, что дробь в действительности - пара чисел, одно из которых не равно нулю. Однако, такое определение некорректно.

В математике две пары равны, если они имеют одинаковые первый и второй элементы. Так, пары (2,4) и (1,2) неравны. Но дроби 2/4 и 1/2 равны; так что дроби - не пары чисел.

Что же такое дроби? Это элементы фактормножества! Рассмотрим множество пар целых На стандартном жаргоне Две пары и целых чисел можно теперь называть эквивалентными, если Легко проверить, что это отношение эквивалентности, а дробь - класс эквивалентности множества относительно этого отношения. Следовательно, означает не пару а бесконечное множество всех пар из эквивалентных Итак, множество рациональных чисел - это фактормножество множества по только что определенному отношению эквивалентности.

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

необходимо знать о целом классе эквивалентности. Более того, Вас устроит любой элемент класса.

Итак, Вы можете оперировать с 1/2 как обычно, так же, как если бы это была пара чисел. Вы вспоминаете, что дробь - это класс эквивалентности, только когда (в процессе вычислений) оказывается, что дробь можно сократить. В этот момент вы заменяете одного представителя класса эквивалентности на другой для упрощения вычислений.

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

Часто используют инфиксную форму записи: .

Если отношение определено на множестве, то возможно следующее определение:

Примерами множеств с введёнными на них бинарными отношениями являются графы и частично упорядоченные множества.

Для определены свойства:

Рефлексивность (англ. reflexivity ): ;

Отношение R на множестве Х называется рефлексивным, если о каждом элементе множества Х можно сказать, что он находится в отношении R с самим собой: хRх. Если отношение рефлексивно, то в каждой вершине графа имеется петля. И обратно, граф, каждая вершина которого содержит петлю, представляет собой граф рефлексивного отношения.

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

Антирефлексивность (англ. irreflexivity ): ;

Отношение R на множестве Х называется антирефлексивным , если для любого элемента из множества Х всегда ложно хRх:.

Симметричность (англ. symmetry ): ;

Отношение R на множестве Х называется симметричным , если выполняется условие: из того, что элемент х находится в отношении с элементом y , следует, что и элемент y находится в отношении R с элементом х: xRyyRx .

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

Антисимметричность (англ. antisymmetry ): ;

Отношение R называют антисимметричным , если для любых элементов х и y из истинности xRy следует ложность yRx: : xRyyRx.

Транзитивность (англ. transitivity ): ;

Отношение R на множестве Х называют транзитивным, если из того, что элемент х находится в отношении R с элементом y, а элемент y находится в отношении R с элементом z , следует, что элемент х находится в отношении R с элементом z : xRy и yRzxRz.

Свойством транзитивности обладает и отношение «длиннее» на множестве отрезков: если отрезок а длиннее отрезка b , отрезок b длиннее отрезка с , то отрезок а длиннее отрезка с. Отношение «равенства» на множестве отрезков также обладает свойством транзитивности: (а=b, b=с)(а=с).

Связность (англ. connectivity ): ;

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

Например, свойством связанности обладает отношение «больше» для натуральных чисел: для любых различных чисел х и y можно утверждать, либо x>y, либо y>x.

Ассимметричность (англ. assymetric relation ): .

Выделяются следующие виды отношений:

квазипорядка (англ. quasiorder ) - рефлексивное транзитивное;

эквивалентности (англ. equivalence ) - рефлексивное симметричное транзитивное;

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

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

В рассмотренном выше отношении «равенства дробей», множество Х разбилось на три подмножества: {; ; }, {; }, {}. Эти подмножества не пересекаются, а их объединение совпадает с множеством Х , т.е. имеем разбиение множества на классы.

Итак, если на множестве Х задано отношение эквивалентности, то оно порождает разбиение этого множества на попарно непересекающиеся подмножества – классы эквивалентности.

частичного порядка (англ. partial order ) - рефлексивное антисимметричное транзитивное;

Бинарное отношение на множественазывается отношением частичного порядка (англ. partial order relation

Рефлексивность (англ. reflexivity ): .

Антисимметричность (англ. antisymmetry ): еслии, то.

Транзитивность (англ. transitivity ): еслии, то.

«больше или равно» и «меньше или равно» - нестрогого, причем линейного порядка, но не полного.

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

строгого порядка (англ. strict order ) - антирефлексивное антисимметричное транзитивное;

Бинарное отношение на множественазывается строгим отношением частичного порядка (англ. strict order relation ), если оно обладает следующими свойствами:

Антирефлексивность (англ. irreflexivity ): - не выполняется.

Антисимметричность (англ. antisymmetry ): еслии, то.

Транзитивность : (англ. transitivity ) еслии, то.

На множестве вещественных чисел отношения «больше» и «меньше» являются отношениями строгого порядка

линейного порядка (англ. total order ) - полное антисимметричное транзитивное;

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

Бинарное отношение на множественазывается отношением линейного порядка (англ. total order relation ), если оно является отношением частичного порядка и обладает следующим свойством: либо, либо.

доминирования (англ. dominance ) - антирефлексивное антисимметричное.

толерантности

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

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

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

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

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

Примеры отношений

Примеры рефлексивных отношений : равенство, одновременность, сходство.

Примеры нерефлексивных отношений : «заботиться о», «развлекать», «нервировать».

Примеры транзитивных отношений : «больше», «меньше», «равно», «подобно», «выше», «севернее».

Примеры симметричных отношений : равенство (=), неравенство, отношение эквивалентности, подобия, одновременности, некоторые отношения родства (например, отношение братства).

Примеры антисимметричных отношений : больше, меньше, больше или равно.

Примеры асимметричных отношений : отношение «больше» (>) и «меньше» (<).

Бинарное отношение на множественазывается отношением эквивалентности (англ. equivalence binary relation ), если оно обладает следующими свойствами:

Рефлексивность : .

Симметричность : если, то.

Транзитивность : еслии, то.

Отношение эквивалентности обозначают символом. Запись видачитают как "эквивалентно"

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

Отношение равенства по модулю : на множестве целых чисел.

Отношение параллельности прямых на плоскости.

Отношение подобия фигур на плоскости.

Отношение равносильности на множестве уравнений.

Отношение связности вершин в графе.

Отношение быть одного роста на множестве людей.

Система непустых подмножеств множестваназывается разбиением (англ. partition ) данного множества, если:

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

Если на множестве M задано отношение эквивалентности, то оно порождает разбиение этого множества на классы эквивалентности такое, что:

любые два элемента одного класса находятся в отношении

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

Семейство всех классов эквивалентности множества образует множество, называемое фактор-множеством , или факторизацией множества по отношению, и обозначаемое.

Равенство - классический пример отношения эквивалентности на любом множестве.

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

П р и м е р 1. Пусть на множестве всех целых неотрицательных чисел N 0 = {0, 1, 2, 3, …} задано отношение Р : «числа х и у имеют один и тот же остаток при делении на 3». Докажем, что Р – отношение эквивалентности и определим классы эквивалентности, определяемые этим отношением.

В самом деле:

а) отношение Р – рефлексивно, поскольку любое х Î N 0 имеет при делении на 3 тот же остаток, что х ;

б) Р – симметрично, поскольку для любых х, у Î N 0 , если числа х и у у и х имеют один и и тот же остаток при делении на 3;

в) Р – транзитивно, поскольку для любых трех чисел x, y, z Î N 0, если х и у имеют один и тот же остаток при делении на 3, и у и z имеют один и тот же остаток при делении на 3, то числа х и z имеют один и тот же остаток при делении на 3.

Следовательно, отношение Р : «числа х и у имеют один и тот же остаток при делении на 3» является отношением эквивалентности, и поэтому оно разбивает множество N 0 на классы. Эти классы называются классами вычетов по модулю 3.

– так обозначается класс чисел, дающих при делении на 3 остаток 0, т.е. = {0, 3, 6, 9, 12 …}, или = {3k }, где k Î N 0 .

– так обозначается класс чисел, дающих при делении на 3 остаток 1, т.е. = {1, 4, 7, 10, 13 …}, или = {3k + 1};

– так обозначается класс чисел, дающих при делении на 3 остаток 2, т.е. = {2, 5, 8, 11, 14 …}, или = {3k + 2}.

Итак, отношение Р разбивает множество N 0 на 3 класса, и вообще, можно доказать, что отношение «числа х и у имеют один и тот же остаток при делении на m » разбивает это множество на m классов.

П р и м е р 2. На множестве N – натуральных чисел задано отношение Р следующим образом: (х 1 , у 1) Р (х 2 , у 2) .

Установим, что Р является отношением эквивалентности и определим классы эквивалентности, определяемые этим отношением.

Действительно, это отношение:

а) рефлексивно, поскольку для любых пар (х , у ) имеет место
ху = ух ;

б) симметрично, поскольку для любых двух пар натуральных чисел (х 1 , у 1) и (х 2 , у 2), если х 1 у 2 = у 1 х 2 , то х 2 у 1 = у 2 х 1 ;

в) транзитивно, поскольку для любых трех пар (х 1 , у 1), (х 2 , у 2), (х 3 , у 3), если х 1 у 2 = у 1 х 2 и х 2 у 3 = у 2 х 3 , то х 1 у 2 х 2 у 3 = у 1 х 2 у 2 х 3 , т.е. х 1 у 3 = у 1 х 3 .

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

Например, пары (1, 2), (2, 4), (3, 6) принадлежат одному классу {(1, 2), (2, 4), (3, 6), …}. Можно этот класс определить следующим образом , т.е. как множество пар, эквивалентных паре (1, 2). Обычно эти пары записывают так: и называют дробями, а эквивалентность пар называют равенством дробей. Для упрощения заменяют класс эквивалентности каким-нибудь его элементом (представителем), чаще всего наиболее простым (несократимой дробью), называя его рациональным числом. Такое упрощение допустимо, так как рациональное число, как класс эквивалентности, однозначно определяется любым элементом этого класса, а операции над рациональными числами, как над классами пар, определяются через операции над представителями этих классов таким образом, что результаты этих операций не зависят от выбора представителей.

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

Лекция 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.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

.

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

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

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

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

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

Литература

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

См. также

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

Wikimedia Foundation . 2010 .

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

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

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

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

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

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

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

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

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

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

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

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

Книги

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