Если отношение порядка обладает еще свойством связности, то говорят, что оно является отношением линейного порядка.

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

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

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

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

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

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

ПРАКТИЧЕСКАЯ РАБОТА. ОТНОШЕНИЯ НА МНОЖЕСТВЕ

Цель. Выяснить на практике свойства, которыми могут обладать отношения: рефлексивности, симметричности, антисимметричности, транзитивности, связности. Раскрыть взаимосвязь между отношением эквивалентности на множестве и разбиением этого множества на классы.

Теоретическая часть

Вопросы к изучению

1. Понятие отношения между элементами одного множества.

2. Способы задания отношений.

3. Свойства бинарных отношений.

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

Основные понятия темы

Ø бинарное отношение на множестве;

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

Ø отношение порядка

Свойства отношений

Ø рефлексивность;

Ø симметричность;

Ø антисимметричность;

Ø транзитивность;

Ø связность

Определения, замечания, выводы

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

Ø Существует взаимосвязь между отношением эквивалентности на множестве Х и разбиением этого множества ни классы.

Практическая часть

Обязательные задания

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

2. На множестве Х={0, 3, 6, 9, 12, 15, 18} задано отношение R. Перечислите пары чисел, связанных этим отношением и постройте его граф, если: а) R – « х больше у в 3 раза»; б) R – « х больше у на 3».

3. На множестве Х = {2, 4, 6, 8} рассматриваются отношения «х = у», «х у» и «х больше у на 2».Какое из приведенных ниже подмножеств множества Х ´ Х задает данные отношения: а) {(4,2),(6,2),(8, 4),(8,6),(2,2),(4,4),(6,6),(8,8)}; б) {(4,2),(6,4),(8, 6)}; в) {(2,2),(4,4),(6,6),(8,8)}.

4. Отношение « х ³ у» рассматривается на множестве Х. Каким будет его график на координатной плоскости, если: а) Х = {2,4,6,8}; б) Х – множество натуральных чисел; в) Х – множество действительных чисел?

5. На множестве отрезков задано отношение «короче». Верно ли, что оно антисимметрично и транзитивно? Рефлексивно ли оно?

6. Какими свойствами обладают следующие отношения, заданные на множестве натуральных чисел: а) «меньше»; б) «меньше на 2»; в) «меньше в 2 раза» ?

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

a

b

c

d

6. Докажите, что отношение R, заданное при помощи графа рефлексивно, антисимметрично и транзитивно.

a

· · b

· c

7. Докажите, что отношение Т, заданное при помощи графа симметрично и транзитивно.

a · · b

· с

8. Сформулируйте условия, при которых отношение свойством рефлексивности не обладает, и докажите, что отношение Т (см. упр. 7) не рефлексивно.

9. Докажите, что отношение Р, граф которого изображен на рисунке, не обладает ни свойством симметричности, ни свойством антисимметричности, ни свойством транзитивности.

а ·

b · · c

10. Какими свойствами обладает отношение, граф которого изображен на рисунке? Является ли оно рефлексивным? Транзитивным?

а

·

b · · c

11. Какие из следующих утверждений истинны: а) Отношение «х больше у на 3» антисимметрично на множестве N, так как из того, что х больше у на 3, не следует, что у больше х на 3; б) Отношение “х больше у на 3” антисимметрично, так как из того, что х больше у на 3, следует. Что у не больше х на 3; в) Отношение “х больше у на 3” антисимметрично, так как из того, что х больше у на 3, следует, что у меньше х на 3.

12. На множестве Х={a, b, c} задано отношение R = { (a,b), (a,a), (b,b), (c,c), (b,a), (b,c), (c,b)}. Какими свойствами оно обладает?

13. На множестве Х= {2, 4, 6, 8, 12}заданы отношения «больше» и «кратно». В чем их сходство и различие?

14. Установите, какое отношение рассматривается в задаче; какие приемы анализа задачи можно использовать:

а) Школьники сделали к карнавалу 15 шапочек для мальчиков, а для девочек в 2 раза больше. Сколько всего карнавальных шапочек они сделали?

б) Второклассники вырезали для елки 26 звездочек, это в 2 раза меньше. Чем снежинок. Сколько всего звездочек и снежинок вырезали второклассники?

17. Объясните, почему отношение равенства отрезков является отношением эквивалентности, а отношение «короче» не является.

18. Х – множество прямых плоскости. Какое из следующих отношений является отношением эквивалентности на этом множестве: а) «х параллельна у»; б) «х перпендикулярна у»; в) «х пересекает у»?

19. На множестве Х = {1,2,3,4,5,6,7,8,9,10} задано отношение «иметь один и тот же остаток при делении на 4». Является ли оно отношением эквивалентности?

20. Можно ли разбить множество Х = {7-3; 2²; 5´2; 60: 6; 1+ 3; 0: 4; 0´10; 4:10-10)} на классы при помощи отношения «иметь равные значения»?

21. На множестве Х = {213, 37, 21, 87, 82} задано отношение Р – «иметь в записи одинаковые цифры». Является ли Р отношением эквивалентности?

22. На множестве целых чисел от 0 до 999 задано отношение К – «иметь в записи одно и то же число цифр». Покажите, что К – отношение эквивалентности. На сколько классов эквивалентности разбивается данное множество при помощи отношения К? Назовите наименьший и наибольший элементы каждого класса.

23. Сколько классов эквивалентности порождает на множестве натуральных чисел отношение «оканчиваться одной и той же цифрой». Назовите по одному представителю каждого класса.

24. Х – множество отрезков. Какие из следующих отношений являются отношениями порядка на этом множестве: а) «х равно у»; б) «х длиннее у»; в) «х длиннее у в 3 раза»?

25. Упорядочивают ли множество натуральных чисел отношения: а) «больше в 2 раза»; б) «больше на 2»; в) «непосредственно следовать за»; г) «х – делитель у»?

26. Отношение Т – «иметь одно и то же число делителей» задано на множестве Х = {1, 2, 4, 6, 7, 8, 10, 11}. Является ли Т отношением эквивалентности? Отношением порядка?

27. Выясните, какие из следующих высказываний истинны, а какие ложны; свой ответ обоснуйте:

а) Отношение «х кратно у» на множестве натуральных чисел рефлексивно и симметрично.

б) Отношение «х кратно у» на множестве натуральных чисел антисимметрично и транзитивно.

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

28. Между множествами существуют отношения равенства, равномощности, «быть подмножеством». Какие из них являются отношениями эквивалентности, а какие отношениями порядка?

29. Решите задачи для младших школьников и укажите свойства отношений, которые были при этом использованы: а) Мальчик составил пирамидку из трех колечек: желтого, красного и зеленого. В каком порядке он расположил колечки, если желтое больше зеленого, а красное меньше зеленого? б) Четверо учащихся получили разные оценки за контрольную работу. Игорь получил оценку выше, чем Петр, Петр ниже, чем Максим, но выше, чем Кирилл. Кто получил самую низкую оценку?

Творческие задания

1. Транзитивно ли отношение, граф которого

2. Показать, что отношение «иметь одинаковые остатки при делении на 3» – эквивалентность.

3. Доказать, что если отношение несимметрично, то оно не может порождать разбиение множества на классы.

4. Доказать, что если отношение нетранзитивно, то оно не может порождать разбиение множества на классы.

5. Множество натуральных чисел разбито на множество однозначных, двузначных, трехзначных и т.д. чисел. Сформулируйте отношение эквивалентности, которому подчинено данное разбиение.