Например, отношение "больше" асимметрично а>Ь. Матрица асимметричного отношения несимметрична и имеет нули в главной диагонали.

Свойства 3-5 легко распространяются на множество АхА. 6. Транзитивность.

Бинарное отношение на множестве АхА называется транзитивным, если из и ajpa-k следует щра. При распространении на два множества транзитивность отношений между их элементами обеспечивает их композицию.

1.12. БИНАРНОЕ ОТНОШЕНИЕ ЭКВИВАЛЕНТНОСТИ Эквивалентность - строгое математическое обоснование понятий "одинаковость", "неразличимость", обозначаетсяудовлетворяет

следующим свойствам бинарных отношений:

-рефлексивности at pcij ;

-симметричности <z,/xz7- => djpcii;

-транзитивности (atpaj и ajpa/J => atpak.

Эквивалентность позволяет разбить множество А на непересекающиеся подмножества А], А2, Ап,..., Ат, ... Аг, называемые классами эквивалентности.

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

АпС\Ап = 0 при пФт

(1.12)

1К = л

эквивалентности.

На рис. 1.21 показано подробное разбиение.

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

Рис. 1.21. Разбиение множества точек фигуры А на классы эквивалентности

То есть во множестве элементов по какому-либо

признаку можно выделить класс одинаковых (эквивалентных) элементов.

Для доказательства этого положим, что в множестве А есть два класса эквивалентности Ап и Ат, причем ап еАп, ат еАт. По (1.12) имеем

АпГ\Ат = 0, если Ап и Ат неэквивалентны ; А ПА, => А = Ап» есш А ~ Ап •

Пусть Ап и Ат неэквивалентны, что иллюстрируется рис. 1.22,а.

аб

Рис. 1.22. Иллюстрация к доказательству о разбиении множества на классы

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

Доказательство проведем от противного. Допустим, что есть элемент х, который одновременно принадлежит подмножествам Ап и Ат, вэтомслучае, во-первых,

х б А„

ап~х

хеАп х~ а„

а, во-вторых, как это показано на рис. 1.22,

В силу транзитивности эквивалентных отношений

ап~х

а ~ а

пт

V(2

Отсюда получаем, что любой ап еАп в силу своей эквивалентности с ат еАт принадлежит Ат

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

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

Множество классов (AhA2, ...,An} разбиения А, отвечающего отношению эквивалентности р называется фактор-множеством множества А по отношению к р и обозначается А/ р (Aj,A2,...,An}-, сами At называются классами эквивалентности.

В качестве примера рассмотрим отношение сравнения по модулю т на множестве целых положительных чисел r+ , что записывается x=y(mod m) и означает: х сравнимо с у по модулю т

- = к, х ег , у ег , тег, к

т

целое число