Тема: «Отношения эквивалентности и отношения порядка»

Цель занятия:

усвоение таких понятий, как отношение эквивалентности, классы эквивалентности, отношение порядка.

Пояснение к работе

Время выполнения практического задания – 2 часа.

Последовательность выполнения

1. Руководствуясь приведенным теоретическим материалом, ответить на следующие вопросы:

Какими свойствами обладает отношение строгого порядка?

Что называется классом эквивалентности?

Что называется разбиением множества?

2. Дать определение следующих понятий:

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

– отношение строгого порядка;

– отношение частичного порядка;

– отношение линейного порядка.

3. Привести пример разбиения множества.

4. Выполнить задания для аудиторных занятий.

5. Выполнить задания для самостоятельной работы.

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

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

Примеры отношений эквивалентности: 1) отношения равенства, параллельности прямых; 2) отношение между элементами множества всех многоугольников: "иметь одинаковое число сторон"; 3) отношение принадлежности к одной студенческой группе на множестве студентов института – отношение эквивалентности.

Классом эквивалентности, порожденным элементом х, называется подмножество множества Х, состоящее из тех элементов у Î Х, для которых х rу – класс эквивалентности, порожденный элементом х, обозначается через [ х ]:

[ х ] = { у ׀ у Î Х и х rу }.

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

2. Множества подобных друг другу треугольников; в разных классах – треугольники разной формы.

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

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

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

2. Пусть Х – множество студентов института. Тогда разбиением этого множества является, например, совокупность студенческих групп.

Отношения порядка – важный тип бинарных отношений. Отношение строгого порядка – бинарное отношение, являющееся антирефлексивным, антисимметричным и транзитивным. Примерами могут служить отношения "больше", "меньше", "старше" и т. п. Для чисел обычное обозначение – знаки <, >.

Рефлексивное, антисимметричное и транзитивное отношение называется отношением частичного (нестрогого) порядка на множестве Х и обозначается символом £.

Примеры отношений частичного порядка. 1. Отношение х £ у на множестве R есть отношение частичного порядка.

2. Во множестве подмножеств некоторого универсального множества U отношение А Í В есть отношение частичного порядка.

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

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

Примеры отношений линейного порядка. 1. Отношение х £ у на множестве R есть отношение линейного порядка.

2. Во множестве подмножеств некоторого универсального множества U отношение А Í В не является отношением линейного порядка.

Задания

Для аудиторных занятий

1. Перечислить всевозможные отношения линейного порядка на множестве {1, 2, 3, 4}.

2. Доказать, что пересечение отношений эквивалентности на множестве Х есть отношение эквивалентности на этом множестве.

3. Будет ли отношением эквивалентности на множестве действительных чисел отношение x ry, задаваемое равенством x ² + y ² = 25?

4. Будет ли отношением эквивалентности на множестве действительных чисел отношение x r y, задаваемое равенством x = 2 y?

5. Доказать, что если r – частичный порядок, то r ^-1 – также частичный порядок.

6. Доказать, что каждое из следующих отношений является отношением эквивалентности, и найти классы эквивалентности:

а) пусть А = {1, 2, 3}, на множестве Р (А) задано бинарное отношение х rу Û½ х ½= ½ у ½;

б) на множестве N ´ N задано бинарное отношение á a, b ñ r á c, d ñ Û a + d =   b + c;

в) на множестве R: a r b Û a ² = b ²;

г) на множестве R: a r b Û a - b Î Z.

7. На R задано бинарное отношение a r b Û a ² + a = b ² + b. Доказать, что r – отношение эквивалентности. Сколько элементов может содержать класс эквивалентности? Существует ли класс эквивалентности, состоящий из одного элемента?

8. Доказать, что отношение á a, b ñ r á c, d ñ Û a ² + b ² = c ² + d ² является отношением эквивалентности на множестве R × R. Найти классы эквивалентности и изобразить их на координатной плоскости.

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

Для самостоятельной работы

1. Доказать, что если r – отношение эквивалентности, то r ^-1 – также отношение эквивалентности.

2. Доказать, что если r – отношение эквивалентности, то истинны следующие утверждения ([ x ]_r – класс эквивалентности, порожденный элементом х):

а)   х Î[ x ]_r;                        б)   х r y Û [ x ]_r = [ y ]_r.

3. Доказать, что отношение делимости на множестве N является отношением порядка. Является ли это отношение линейным порядком? Является ли отношением порядка отношение делимости на множестве Z?

4. Доказать, что отношение х ry Û x / y Ú х < y на множестве N является линейным порядком.

5. Для каких множеств А множество { В (А), Í} является линейно упорядоченным?

6. Пусть А – не пустое конечное множество. На B (А) рассмотрим отношение X rY Û ç X ç£ ç Y ç. Является ли r отношением порядка?

7. На множестве всех отображений   R в R рассмотреть отношение f rq Û (" x Î R ç f(x) = 1, q(x) = 1). Является ли r отношением порядка?

8. На множестве всех отображений R в R рассмотреть отношение f rq Û { x Î R ç f(x) = 0} Í { x Î R çg(x) = 0}. Является ли r отношением порядка?

9. Доказать, что отношение á a; b ñ r á c; d ñ Û a < c Ú(a = c Ù b £ d) является линейным порядком на множестве Z ´ Z.

10. По аналогии с упражнением 9 определить линейный порядок на множестве А ´ В, если á А, r ₁ ñ и á В, r ₂ñ – линейно упорядоченные множества.

11.  Перечислить всевозможные линейные порядки на множестве  {1, 2}; на множестве {1, 2, 3}. Высказать предположение о числе линейных порядков на множестве из n элементов.

12.  Пусть F – множество всех непустых конечных подмножеств множества N. Какие элементы упорядоченного множества á F, Í ñ являются минимальными? Доказать, что á F, Í ñ не содержит максимальных элементов.

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

14. Доказать:

а) упорядоченное множество содержит не более одного наибольшего (наименьшего) элемента;

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

Литература

1. Белоусов, А. И. Дискретная математика: учебник / А. И. Белоусов. – М.: МГТУ им. Н. Э. Баумана, 2001.  – 744 с.

2. Куликов, Л. Я. Сборник задач по алгебре и теории чисел / Л. Я. Куликов, А. И. Москаленко, А. А Фомин. – М.: Просвещение, 1993. – 288 с.

3. Нефедов, В. Н. Курс дискретной математики: учеб. пособие / В. Н. Нефедов, В. А. Осипова. – М.: Изд-во МАИ, 1992. – 264 с.

 

Практическое занятие № 4