Специальные бинарные отношения.

 

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

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

Пусть на некотором множестве Х задано отношение эквивалентности r. Выберем элемент х₁ÎХ и образуем класс (подмножество) Х₁, состоящий из х₁ и всех элементов уÎХ, для которых хrу. Затем выберем из Х элемент х₂ÏХ₁ и составим класс Х₂ из элемента х₂ и всех элементов из Х\Х₁ находящихся в отношении r с х₂ и т.д.

Получим систему классов Х₁, Х₂,…,Х_n такую, что любой элемент из множества Х входит в какой –либо из классов этой системы. Эти классы называются классами эквивалентности.

Определение: Классом эквивалентности , образованным (порожденным)элементом х, называется подмножество множества Х, состоящее из элемента х и всех элементов уÎХ, для которых хrу.

Обозначение класса эквивалентности, порожденного элементом х:

[x]={y|yÎX и хrу}.

Примеры:

а)Отношение равенства на множестве целых чисел порождает следующие классы эквивалентности: для любого хÎZ[x]={x}, т.е. каждый класс состоит из одного элемента - числа х.

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

Введем понятие разбиения множества Х.

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

Примеры:

а) Х={1,2,3,4,5}, тогда его разбиение множество {{1,2}, {3,5}, {4}}.

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

Система классов эквивалентности обладает следующими свойствами:

1. Система образует разбиение множества Х.

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

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

Докажем первое свойство: пусть Х₁ и Х₂ пересекаются , тогда существует элемент у такой, что х₁rу (х₁ÎХ₁) и уrх₂ (х₂ÎХ₂), следовательно х₁rх₂, что противоречит условию построения Х₂.

Доказательства 2-го и 3-го свойств аналогичны.

Приведем формулировки теорем о классах эквивалентности.

Теорема1. Пусть r - отношение эквивалентности на множестве Х. Тогда:

1. если хÎХ, то хÎ[x];

2. если {x,y}ÌX и хrу, то [x]=[y], т.е. класс эквивалентности порождается любым своим элементом.

 

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

 

Теорема 2. Любое разбиение множества Х определяет на этом множестве Х отношение эквивалентности r: хrу тогда и только тогда, когда х и у принадлежат одному подмножеству разбиения.

 

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

 

Теорема 3. Любое отношение эквивалентности определяет разбиение множества Х на классы эквивалентности относительно этого отношения.

 

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

Рассмотрим еще один тип специальных бинарных отношений.

Отношение частичного порядка: r называется отношением частичного порядка, если оно рефлексивно, антисимметрично и транзитивно.

Отношение частичного порядка обозначается символом

Пример:

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

б) отношение «АÍВ» - отношение частичного порядка.

Отношение строгого порядка: r называется отношением строгого порядка, если оно антирефлексивно, не симметрично и транзитивно.

Пример:

а) Отношение на множестве действительных чисел «x<y» - антирефлексивно, не симметрично, транзитивно, значит, является отношением строгого порядка на множестве действительных чисел.

б) Схема организации подчинения в учреждениях – отношение строгого порядка (проверьте самостоятельно).

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

Примеры:

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

б) Отношение предшествования на множестве булевых векторов является отношением частичного порядка, но не является отношением линейного порядка, т.к. не все векторы сравнимы.

Множество Х с заданным на нем отношением частичного или линейного порядка называется частично или линейно упорядоченным.

Любое частично упорядоченное множество можно представить в виде схемы. Для введения правила построения схемы введем некоторые понятия.

Пусть Х непустое конечное множество. На этом множестве задано отношение частичного порядка . х у, если ху и х¹ у.

Говорят: у покрывает х, если ху и не существует такого элемента u, что хuу .

Пример: отношение на множестве целых чисел : , т.е. 2 покрывает 1, т.к. 1<2 и не существует целого числа х такого , что 1<x<2.

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

Такие схемы называются диаграммами Хассе.

Примеры:

а) Пусть А={1,2,3}. Рассмотрим отношение быть подмножеством r= {Æ, {1}, {2}, {3}, {1,2}, {1,3}, {2,3}, {1,2,3}}.

 

Диаграмма имеет вид:

 

 

 

б) На множестве Х={1,2,3,4,5,6,7,8} рассмотрим отношение «х£у». Его диаграмма имеет вид.

 

 

 

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

 

в) Дано множество А = {1,2,3,5,6,10,30}. Отношение «быть делителем». У покрывает х, если у делится на х. Диаграмма имеет вид: