68 Глава 2. Бинарные отношения

При n = 2 A2 µ A по определению транзитивности. Предположим, что при некотором n ¡ 1 An¡1 µ A. Из предположения индукции и теоремы 2.11 получим An = An¡1A µ AA

Теорема 2.19 Если отношение A рефлексивно и транзитивно, то

A= A2:

До к а з а т е л ь с т в о . 1. °) Из рефлексивности

[xAy ) xAx ^ xAy] ) A µ A2.

2. °( Из транзитивности [xAy ^ yAy ) xAy] ) A2 µ A. £

2.4Эквивалентность и толерантность

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

Отношение эквивалентности является ма- Эквивалентность тематической абстракцией таких понятий как равенство, одинаковость, взаимозаме-

няемость.

Определение. Отношение A на множестве M называется отношением эквивалентности ( эквивалентностью), если оно рефлексивно, симметрично и транзитивно.

Примеры 2.19.

1. Отношение "равенства” на множестве чисел есть отношение эквивалентности.

2.Для целых чисел “равенство по модулю 2” также является примером эквивалентности.

3."Равенство” чисел в различных системах счисления – эквивалентность. J

Напомним, что покрытие множества M – это семейство

fMiji 2 Ig непустых подмножеств множества M, такое, что

[

M = Mi:

i2I

Если при этом Mi \ Mj = ?; i 6= j, то fMiji 2 Ig – разбиение множества M:

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

Теорема 2.20 Пусть задано разбиение fMiji 2 Ig множества M и бинарное отношение hA; Mi определено как "принадлежать общему классу разбиения”. Тогда A – эквивалентность.

Д о к а з а т е л ь с т в о . Пусть дано разбиение fMiji 2 Ig множества M. Так как M = S Mi, то 8x 2 M ) x 2 Mi, т.е.

i2I

каждый элемент x множества M содержится в некотором классе.

1. Очевидно, соотношение 8x[xAx] выполняется, т.е. A рефлексивно (x и x принадлежат одному классу разбиения).

2. Далее, xAy ) yAx – если пара элементов x; y входит в один класс, то и пара y; x входит в тот же класс, т.е. A симметрично.

3. Пусть теперь выполнены соотношения xAy и yAz. Это значит, что x; y 2 Mi, а y; z 2 Mj. Получили, что Mi \ Mj =6 ?. Это может быть лишь в том случае, когда Mi и Mj совпадают, т.е. это один и тот же класс. Значит,

x; y 2 Mi ^ y; z 2 Mi ) x; z 2 Mi,

т.е. выполняется соотношение xAz. А это означает, что отношение A транзитивно. £

Теорема 2.21 Если отношение hA; Mi – эквивалентность, то существует разбиение fMiji 2 Ig множества M такое, что соотношение xAy выполняется тогда и только тогда, когда x и y принадлежат общему классу разбиения.

Д о к а з а т е л ь с т в о . Пусть отношение hA; Mi рефлексивно, симметрично и транзитивно. Построим для каждого элемента x 2 M подмножество Mx = fzjxAzg.

Лемма Для любых x; y либо Mx = My, либо Mx \ My = ?.

Д о к а з а т е л ь с т в о . Пусть Mx \ My =6 ?. Нужно доказать, что Mx = My.

Пусть z 2 Mx \My, тогда по определению Mx и My должны выполняться соотношения xAz и yAz. Из симметричности A следует zAy, а из транзитивности: xAz ^ zAy ) xAy. Далее, для любого w 2 My выполняется yAw. Из xAy и yAw следует xAw, т.е. w 2 Mx. Это означает, что My µ Mx.

С другой стороны, для любого v 2 Mx выполняется xAv. Из симметричности xAy ) yAx. Из транзитивности

yAx ^ xAv ) yAv, т.е. v 2 My.

Это означает, что Mx µ My. В итоге, Mx = My. £

Из леммы и рефлексивности A следует, что множества вида Mx образуют разбиение множества M. Это разбиение называется соответсвующим данному отношению A. Покажем, что такое разбиение (и классы разбиения) удовлетворяют условиям теоремы.

1. °) Пусть отношение A рефлексивно, симметрично и транзитивно, и пусть для некоторых x; y 2 M выполняется соотношение xAy. Это означает, что y 2 Mx (по определению Mx). Но и x 2 Mx (из рефлексивности xAx отношения A). Следовательно, оба элемента x и y входят в Mx.

2. °( Пусть некоторые элементы u и v содержатся в Mx: u; v 2 Mx. Для доказательства теоремы нужно показать, что выполняется соотношение uAv.

Действительно, из определения Mx следует xAu и xAv. Из симметричности A следует uAx. Из транзитивности A следует: uAx ^ xAv ) uAv. Теорема доказана. £

З а м е ч а н и е 1. Отметим, что доказательство теоремы (2.21) проведено конструктивно. Вначале мы построили подмножества вида Mx = fzjxAzg, соответствующие отношению A, а затем доказали, что они являются классами разбиения.

З а м е ч а н и е 2. Множество является максимальным по некоторому свойству, если оно не содержится во множестве, обладающем этим же свойством. Классы эквивалентности, полученные в теореме 2.21, являются максимальными подмножествами попарно эквивалентных элементов множества

M. I

Мы получили разбиение множества M на подмножества fMiji 2 Ig эквивалентных друг другу элементов – классы эквивалентности. Множество классов эквивалентности по отношению A принято обозначать M=A (читается: фактор-мно- жество множества M по отношению A).

Пусть дано разбиение fMiji 2 Ig множества M. Выберем в каждом подмножестве M некоторый элемент e 2 Mi и назовем его эталоном для всякого x 2 Mi. Отношение eЭx назовем “быть эталоном" или “e – эта-

лон для x”. Тогда отношение эквивалентности £ можно определить так:

соотношение x£y выполняется, если x и y имеют общий эталон e, т.е. eЭx ^ eЭy. Таким образом, отношение эквивалентности можно определить с помощью отношения “быть эталоном” и, наоборот, любое отношение “быть эталоном” определяет некоторую эквивалентность.

Пусть £ – отношение эквивалентности, а Э – такое отношение “быть эталоном”, что x£y выполняется тогда и только тогда, когда x и y имеют общий эталон, т.е. выполнение соотношения x£y равносильно существованию z, такого, что eЭx и eЭy. Так как eЭx есть xЭ¡1e, то можно записать: £ = Э¡1Э, т.е. отношение эквивалентности выражается алгебраически через более простое отношение “быть эталоном”.

Из определения отношения Э “e является эталоном для x” следуют его свойства:

1.8x9e[eЭx] – для всякого элемента x существует эталон e.

2.eЭe – любой эталон есть эталон для самого себя.

3.Эталон единствен, т.е. из e1Эx и e2Эx следует e1 = e2.

Эти свойства можно считать аксиомами отношения “быть эталоном”. Заметим, что эти аксиомы теперь введены безотносительно к разбиению. Покажем теперь, что из аксиом следует определение эталона с помощью разбиения. Для этого сначала по отношению Э построим новое отношение £, определяемое правилом:

x£y, если x; y имеют общий эталон, т.е. если существует такой e, что eЭx и eЭy; при этом £ = Э¡1Э.

Покажем, что £ – отношение эквивалентности.

1.Из свойства 1, у каждого x есть эталон и, следовательно, x£x, т.е. £ рефлексивно.

2.Симметричность £ очевидна: если x; y имеют общий эталон, то и y; x имеют общий эталон.

3.Если x£y и y£z, то это значит, что x; y имеют общий эталон, а y не может иметь эталона, отличного от эталона для z (единственность эталона). Значит, x£z.

Итак, доказано, что £ – отношение эквивалентности. Но тогда по теореме (2.21) существует разбиение fMiji 2 Ig множества M на классы эквивалентности.

Очевидно, что каждый класс эквивалентности состоит из всех элементов, имеющих общий эталон x. По свойству 2 отношения "быть эталоном” xЭx, т.е. x обязательно принадлежит некоторому классу Mi. Таким образом, отношение Э, определенное аксиоматически свойствами 1 – 3, всегда может быть задано разбиением с выбранными представителями (эталонами) в каждом классе.

Пример 2.20. M = fa; b; c; d; e; f; gg;

Э = fhg; ai; hg; ei; hd; bi; hd; ci; hd; fi; hd; di; hg; gig;

£ = Э¡1Э = fha; ai; ha; ei; ha; gi; hb; bi; hb; ci; hb; fi; hb; di; hc; bi; hc; ci; hc; di; hc; fi; hd; bi; hd; ci; hd; di; hd; fi; he; ai; he; ei; he; gi; hf; bi; hf; ci; hf; di; hf; fi;

Графы, представленные на рисунке, соответствуют отношениям эквивалентности и “быть эталоном".