На множестве задано отношение какими свойствами оно обладает
Пусть R — некоторое бинарное отношение на множестве X, а х, у, z любые его элементы. Если элемент х находится в отношении R с элементом у, то пишут xRy.
1. Отношение R на множестве X называется рефлексивным, если каждый элемент множества находится в этом отношении с самим собой.
R —рефлексивно на X <=> xRx для любого x€ X
Если отношение R рефлексивно, то в каждой вершине графа имеется петля. Например, отношения равенства и параллельности для отрезков являются рефлексивными, а отношение перпендикулярности и «длиннее» не являются рефлексивными. Это отражают графы на рисунке 42.
2. Отношение R на множестве X называется симметричным, если из того, что элемент х находится в данном отношении с элементом у, следует, что элемент у находится в этом же отношении с элементом х.
R — симметрично на (хЯу =>у Rx)
Граф симметричного отношения содержит парные стрелки, идущие в противоположных направлениях. Отношения параллельности, перпендикулярности и равенства для отрезков обладают симметричностью, а отношение «длиннее» — не является симметричным (рис. 42).
3. Отношение R на множестве X называется антисимметричным, если для различных элементов х и у из множества X из того, что элемент х находится в данном отношении с элементом у, следует, что элемент у в этом отношении с элементом х не находится.
R — антисимметрично на Х« (xRy и xy ≠ yRx)
Замечание: черта сверху обозначает отрицание высказывания.
На графе антисимметричного отношения две точки может соединять только одна стрелка. Примером такого отношения является отношение «длиннее» для отрезков (рис. 42). Отношения параллельности, перпендикулярности и равенства не являются антисимметричными. Существуют отношения, не являющиеся ни симметричными, ни антисимметричными, например отношение «быть братом» (рис. 40).
4. Отношение R на множестве X называется транзитивным, если из того, что элемент х находится в данном отношении с элементом у и элемент у находится в этом лее отношении с элементом z, следует, что элемент х находится в данном отношении с элементом Z
R — транзитивно на A≠ (xRy и yRz=> xRz)
На графах отношений «длиннее», параллельности и равенства на рисунке 42 можно заметить, что если стрелка идет от первого элемента ко второму и от второго к третьему, то обязательно есть стрелка, идущая от первого элемента к третьему. Эти отношения являются транзитивными. Перпендикулярность отрезков не обладает свойством транзитивности.
Существуют и другие свойства отношений между элементами одного множества, которые мы не рассматриваем.
Одно и то же отношение может обладать несколькими свойствами. Так, например, на множестве отрезков отношение «равно» — рефлексивно, симметрично, транзитивно; отношение «больше» — антисимметрично и транзитивно.
Если отношение на множестве X рефлексивно, симметрично и транзитивно, то оно является отношением эквивалентности на этом множестве. Такие отношения разбивают множество X на классы.
Данные отношения проявляются, например, при выполнении заданий: «Подбери полоски равные по длине и разложи по группам», «Разложи мячи так, чтобы в каждой коробке были мячи одного цвета». Отношения эквивалентности («быть равным по длине», «быть одного цвета») определяют в данном случае разбиение множеств полосок и мячей на классы.
Если отношение на множестве 1 транзитивно и антисимметрично, то оно называется отношением порядка на этом множестве.
Множество с заданным на нем отношением порядка называется упорядоченным множеством.
Например, выполняя задания: «Сравни полоски по ширине и разложи их от самой узкой до самой широкой», «Сравни числа и разложи числовые карточки по порядку», дети упорядочивают элементы множеств полосок и числовых карточек при помощи отношений порядка; «быть шире», «следовать за».
Вообще отношения эквивалентности и порядка играют большую роль в формировании у детей правильных представлений о классификации и упорядочении множеств. Кроме того, встречается много других отношений, которые не являются ни отношениями эквивалентности, ни отношениями порядка.
6. Что такое характеристическое свойство множества?
7. В каких отношениях могут находиться множества? Дайте пояснения каждому случаю и изобразите их при помощи кругов Эйлера.
8. Дайте определение подмножества. Приведите пример множеств, одно из которых является подмножеством другого. Запишите их отношение при помощи символов.
9. Дайте определение равных множеств. Приведите примеры двух равных множеств. Запишите их отношение при помощи символов.
10. Дайте определение пересечения двух множеств и изобразите его при помощи кругов Эйлера для каждого частного случая.
11. Дайте определение объединения двух множеств и изобразите его при помощи кругов Эйлера для каждого частного случая.
12. Дайте определение разности двух множеств и изобразите ее при помощи кругов Эйлера для каждого частного случая.
13. Дайте определение дополнения и изобразите его при помощи кругов Эйлера.
14. Что называется разбиением множества на классы? Назовите условия правильной классификации.
15. Что называется соответствием между двумя множествами? Назовите способы задания соответствий.
16. Какое соответствие называется взаимно однозначным?
17. Какие множества называют равномощными?
18. Какие множества называют равночисленными?
19. Назовите способы задания отношений на множестве.
20. Какое отношение на множестве называют рефлексивным?
21. Какое отношение на множестве называют симметричным?
22. Какое отношение на множестве называют антисимметричным?
23. Какое отношение на множестве называют транзитивным?
24. Дайте определение отношения эквивалентности.
25. Дайте определение отношения порядка.
26. Какое множество называют упорядоченным?
План
1. Свойство рефлексивености
2. Свойство симметричности
3. Свойство транзитивности
Свойства отношений
Мы установили, что бинарное отношение на множестве X представляет собой множество упорядоченных пар элементов, принадлежащих декартову произведению X х Х. Это математическая сущность всякого отношения. Но, как и любые другие понятия, отношения обладают свойствами. Их удалось выделить, изучая различные конкретные отношения. Свойств достаточно много, в нашем курсе мы будем изучать только некоторые.
Рассмотрим на множестве отрезков, представленных на рис. 98, отношения перпендикулярности, равенства и «длиннее». Построим графы этих отношений (рис. 99) и будем их сравнивать. Видим, что граф отношения равенства отличается от двух других наличием петель в каждой его вершине. Эти петли — результат того, что отношение равенства отрезков обладает свойством: любой отрезок равен самому себе. Говорят, что отношение равенства обладает свойством рефлексивности или просто, что оно рефлексивно.
Определение. Отношение R на множестве X называется рефлексивным, если о каждом элементе множества X можно сказать, что он находится в отношении R с самим собой.
Используя символы, это отношение можно записать в таком виде:
R рефлексивно на Х ↔ х R х для любого х € X.
опр.
Если отношение R рефлексивно на множестве X, то в каждой вершине графа данного отношения имеется петля. Справедливо и обратное утверждение: граф, каждая вершина которого имеет петлю, задает отношения, обладающие свойством рефлексивности.
Примеры рефлексивных отношений:
— отношение «кратно» на множестве натуральных чисел (каждое натуральное число кратно самому себе);
— отношение подобия треугольников (каждый треугольник подобен самому себе).
Существуют отношения, которые свойством рефлексивности не обладают. Таким, например, является отношение перпендикулярности на множестве отрезков: нет ни одного отрезка, о котором можно сказать, что он перпендикулярен самому себе. Поэтому на графе отношения перпендикулярности (рис. 99) нет ни одной петли. Не обладает свойством рефлексивности и отношение «длиннее» для отрезков.
Обратим теперь внимание на графы отношений перпендикулярности и равенства отрезков. Они «похожи» тем, что если есть одна стрелка, соединяющая пару элементов, то обязательно есть и другая, соединяющая те же элементы, но идущая в противоположном направлении. Эта особенность графа отражает те свойства, которыми обладают отношения параллельности и равенства отрезков:
— если один отрезок перпендикулярен другому отрезку, то этот «другой» перпендикулярен первому;
— если один отрезок равен другому отрезку, то этот «другой» равен первому.
Про отношения перпендикулярности и равенства отрезков говорят, что они обладают свойством симметричности или просто симметричны.
Определение. Отношение R на множестве X называется симметричным, если выполняется условие: из того, что элемент х находится в отношении R с элементом у, следует, что и элементу находится в отношении R с элементом х.
Используя символы, это отношение можно записать в таком виде:
R симметрично на Х ↔ (х R y →yRx).
опр.
Граф симметричного отношения обладает особенностью: вместе с каждой стрелкой, идущей от х к у, граф содержит и стрелку, идущую от у к x. Справедливо и обратноеутверждение. Граф, содержащий вместе с каждой стрелкой, идущей от x к у, и стрелку, идущую от у к x, является графом симметричного отношения.
В дополнение к рассмотренным двум примерам симметричных отношений присоединим еще такие:
-отношениепараллельности на множестве прямых (если прямая x параллельна прямой у, то и прямая у параллельна прямой х)
-отношение подобия треугольников (если треугольник F подобен треугольнику Р, то треугольник Р подобен треугольнику F).
Существуют отношения, которые свойством симметричности не обладают. Таким, например, является отношение «длиннее» на множестве отрезков. Действительно, если отрезок x длиннее отрезка у, то отрезок у не может быть длиннее отрезка х. Про отношения «длиннее» говорят, что оно обладает свойством антисимметричности или просто антисимметрично.
Определение. Отношение R на множестве X называется антисимметричным, если для различных элементов х и у из множества X выполнено условие: из того, что х находится в отношении R с элементом у, следует, что элемент у в отношении R с элементом х не находится.
Используя символы, это определение можно записать в таком виде:
R симметрично на Х ↔ (х R y ^ x≠y →yRx).
опр.
Граф антисимметричного отношения обладает особенностью: если две вершины графа соединены стрелкой, то эта стрелка только одна. Справедливо и обратное утверждение: граф, вершины которого соединены только одной стрелкой, есть граф антисимметричного отношения.
Кроме отношения «длиннее» на множестве отрезков свойством антисимметричности, например, обладают:
— отношение «больше» для чисел (если х больше у, то у не может
быть больше х);
— отношение «больше на 2» для чисел (если х больше у на 2, то у не может быть больше на 2 числа х),
Существуют отношения, не обладающие ни свойством симметричности, ни свойством антисимметричности. Рассмотрим, например, отношение «быть сестрой» на множестве детей одной семьи. Пусть в семье трое детей: Катя, Маша и Толя. Тогда граф отношения «быть сестрой» будет таким, как на рисунке 100. Он показывает, что данное отношение не обладает ни свойством симметричности, ни свойством антисимметричности.
Рис.100
Обратим внимание еще раз на одну особенность графа отношения «длиннее» (рис. 99). На нем можно заметить: если стрелки проведены от е к а и от а к с, то есть стрелка от е к с; если стрелки приведены от е к b и от b к с, то есть стрелка и от е к с и т.д. Эта особенность графа отражает важное свойство отношения «длиннее»: если первый отрезок длиннее второго, а второй — длиннее третьего, то первый — длиннее третьего. Говорят, что это отношение обладает свойством транзитивности или просто транзитивно.
Определение. Отношение R на множестве X называется транзитивным, если выполняется условие; из того, что элемент х находится в отношении R с элементом у и элемент у находится в отношении R с элементом z, следует, что элемент х находится в отношении К с элементом z .
Используя символы, это определение можно записать в таком виде:
R транзитивно на X ↔ (х R y ^ yRz → xRz).
опр.
Граф транзитивного отношения с каждой парой стрелок, идущих от x к у и у к z, содержит стрелку, идущую от х к z. Справедливо и обратное утверждение.
Кроме отношения «длиннее» на множестве отрезков свойством транзитивности обладает отношение равенства: если отрезок х равен отрезку у и отрезок у равен отрезку z, то отрезок х равен отрезку z, Это свойство отражено и на графе отношения равенства (рис. 99)
Существуют отношения, которые свойством транзитивности не обладают. Таким отношением является, например, отношение перпендикулярности: если отрезок а перпендикулярен отрезку d, а отрезок d перпендикулярен отрезку b, то отрезки а и b не перпендикулярны!
Рассмотрим еще одно свойство отношений, которое называют свойством связанности, а отношение, обладающее им, называют связанным.
Определение. Отношение R на множестве X называется связанным, если для любых элементов х и у из множества X выполняется условие: из того, что х и у различны, следует, что либо х находится в отношении R с элементом у, либо элемент у находится в отношении R с элементом х.
Используя символы, это определение можно записать в таком виде:
R связано на множестве X ↔ (х ≠ у => хRу v уRх).
опр.
Например, свойством связанности обладают отношения «больше» длянатуральных чисел: для любых различных чисел х и у можно утверждать, что либо х > у, либо у > х.
На графе связанного отношения любые две вершины соединены стрелкой. Справедливо и обратное утверждение.
Существуют отношения, которые свойством связанности не обладают. Таким отношением, например, является отношение делимости на множестве натуральных чисел: можно назвать такие числа х и у, что ни число х не является делителем числа у, ни число у не является делителем числа х.
Выделенные свойства позволяют анализировать различные отношения с общих позиций — наличия (или отсутствия) у них тех или иных свойств.
Так, если суммировать все сказанное об отношении равенства, заданном на множестве отрезков (рис. 99), то получается, что оно рефлексивно, симметрично и транзитивно. Отношение «длиннее» на том же множестве отрезков антисимметрично и транзитивно, а отношение перпендикулярности — симметрично, но оно не обладает свойствами рефлексивности и транзитивности. Все эти отношения на заданном множестве отрезков связанными не являются.
Задача 1. Сформулировать свойства отношения R, заданного при помощи графа (рис. 101).
Рис.101
Решение. Отношение R-антисимметрично, так как вершины графа соединяются только одной стрелкой.
Отношение R — транзитивно, так как с парой стрелок, идущих от b к а и от а к с, на графе есть стрелка, идущая от b к с.
Отношение R — связанно, так как любые две вершины соединены стрелкой.
Отношение R свойством рефлексивности не обладает, так как на графе есть вершины, в которых петли нет.
Задача 2. Сформулировать свойства отношения «больше в 2 раза», заданного на множестве натуральных чисел.
Решение. «Больше в 2 раза» — это краткая форма отношения «число х больше числа у в 2 раза». Это отношение антисимметрично, так как выполняется условие: из того, что число х больше числа у в 2 раза, следует, что число y не больше числа x 2 раза.
Данное отношение не обладает свойством рефлексивности, потому что ни про одно число нельзя сказать, что оно больше самого себя в 2 раза.
Заданное отношение не транзитивно, так как из того, что число x больше числа у на 2, а число у больше числа z на 2, следует, что число х не может быть больше числа z на 2.
Это отношение на множестве натуральных чисел свойством связанности не обладает, так как существуют пары таких чисел х и у, что ни число х не больше числа у в два раза, ни число у не больше х в 2 раза. Например, это числа 7 и 3, 5 и 8 и др.
Упражнения
1.Докажите, что отношение R, заданное при помощи графа (рис.102), рефлексивно, антисимметрично и транзитивно.
2.Докажите, что отношение Т, заданное при помощи графа (рис.103), симметрично и транзитивно.
3.Сформулируйте условия, при которых отношение свойством рефлексивности не обладает, и докажите, что отношение Т (см. упр. 2) не рефлексивно.
4. 
Сформулируйте условия, при которых отношение не обладает свойством: а) симметричности; б) антисимметричности; в)транзитивности; г) связанности.
5. 
Докажите, что отношение Р, граф которого изображен на рисунке 104, не обладает ни свойством симметричности, ни свойством антисимметричности, ни свойством транзитивности.
6.Какими свойствами обладает отношение, граф которого изображен на рисунке 105? Является ли оно рефлексивным? Транзитивным?
7.Какие из следующих утверждений истинны:
а) Отношение «x больше у на 3» антисимметрично на множестве N, так как из того, что х больше у на 3, не следует, что у больше х на 3.
б) Отношение «x больше у на 3» антисимметрично, так как из того, что х больше у на 3, следует, что у не больше х на 3.
в) Отношение «х больше у на 3» антисимметрично, так как из того, что х больше у на 3, следует, что у меньше х на 3.
8. На множестве отрезков задано отношение «короче». Верно ли, что оно антисимметрично
и транзитивно? Рефлексивно ли оно?
9. Какими свойствами обладают следующие отношения, заданные на множестве натуральных чисел:
а) «меньше»; б) «меньше на 2»; в) «меньше в 2 раза»?
10. На множестве X ={а, b, с}задано отношение R = {(а, b), (а, а), (b,b), (с, с), (b, а), (b, с), (с, b)}.Какими свойствами оно обладает?
11. На множестве Х= {2,4,6,8, 12} заданы отношения «больше» и «кратно». В чём их сходство и различие?
12.Установите, какое отношение рассматривается в задаче; какие приемы анализа задачи можно использовать:
а) Школьники сделали к карнавалу 15 шапочек для мальчиков, адля девочек в 2 раза больше. Сколько всего карнавальных шапочек они сделали?
б) Второклассники вырезали для елки 26 звездочек, это в 2 раза меньше, чем снежинок. Сколько всего звездочек и снежинок вырезали второклассники?
Бинарное отношение R (RÌA´A=A2), заданное на множестве А называется отношением тождества, если все его элементы (кортежи) имеет вид (а,а), где аÎА и обозначается idA, т.е. . Пары, вида (а,а) называются диагональными, а отношение idA называют диагональным. Вполне понятно, что матрица отношения тождества будет иметь вид единичной матрицы:
Очевидно, что для любого бинарного отношения R, определенного на множестве А, имеет место равенство: *R=R*idA=R.
Бинарное отношение R, заданное на множестве А, называется рефлексивным, если idAÍR, т.е. когда оно включает диагональ.
Примеры:
а. А – множество прямых на плоскости, на котором задано отношение R= «Прямая Х параллельная прямой Y».
Действительно, как известно из элементарной геометрии, две прямые параллельны, если они либо совпадают, либо не имеют ни одной общей точки (нигде не пересекаются). Поскольку прямая Х совпадает сама с собой, то пара (Х,Х) принадлежит данному отношению R, т.е. (Х,Х)Î R.
b. А – множество студентов нашего вуза и на котором задано отношение Р= «студент S ровесник студенту V». Очевидно, что каждый ровесник сам себе, и поэтому (S,S)ÎP.
Бинарное отношение R, заданное на множестве А называется иррефлексивным, если aRa (или (а,а)Î R) не имеет смысла. Или тоже самое можно сформулировать как (а,а)Ï R.
Пример:
а. На числовом множестве D задано отношение R=”<”. Вполне очевидно, что для любых двух чисел х отношение x<x всегда ложно, т.е. все диагональные элементы (х,х) этого отношения на матрице отношений будут равны нулю.
Следует отметить, что иррефлексивные отношения еще называют антиреффлексивным.
Ø Бинарное отношение R, заданное на множестве А называется симметричным, если для пары (а, b) Î А2 из аRb следует bRа (RÍR-1).
Примеры:
а. Прямая А перпендикулярна прямой В в плоскости Z.
b. Студент Х является соседом по парте студента Y.
(Заметим, что приведенные отношения не являются рефлексивными).
Ø Бинарное отношение R, заданное на множестве А называется, антисимметричным, если из и следует, что ( ).
Пример:
а. Отношение включения для множества, т.е. отношение «множество А является подмножеством множества В». И если А Í В и В ÍА, то из аксиомы объемности следует, что А = В.
Ø Бинарное отношение R, заданное на множестве А называется транзитивным, если для любых a, b, c Î A из aRb и bRc следует aRc (R Í R2).
Примеры:
а. Отношения подобия на множестве треугольников;
в. Отношение «быть ровесником», заданное на множестве студентов;
с. Отношение «быть больше (меньше)», заданное на множестве действительных чисел.
Ø Бинарное отношение R, заданное на множестве А называется отношением эквивалентности (или просто эквивалентностью), если для любых элементов a, b, c Î A выполняются следующие свойства:
— рефлексивность: aRa (idA Í R);
— симметричность: aRb Þ bRa (R Í R-1);
— транзитивность: aRb и bRc Þ aRc (R2 Í R).
Примеры:
а. Отношение равенства “=” на любом множестве является отношением эквивалентности (рефлексивность: а=а; симметричность: a=bÞb=a; транзитивность: (a=b и b=c) Þ a=c).
b.Отношение R={(1, 1), (1, 2), (1, 3), (2, 2), (2, 2), (2, 1), (2, 3), (3, 3), (3, 2), (3, 1)} является отношением эквивалентности, так как оно рефлексивно: «(а){(a, a) Î R}; симметрично: (a, b) R (b, a) ÎR; транзитивно: ((a, b) и (b, c) ÎR Þ (a, c) Î R, где a, b –числа, принимающие значения 1, 2, 3. Например, транзитивность (1, 2) Î R и (2, 3) Î R влечет (1, 3) Î R. Отметим, что в этом примере R=R-1.
с. Отношение “быть на одном курсе” на множестве студентов факультета;
d. Отношение “иметь одинаковый остаток при делении на 3” на множестве
натуральных чисел;
e. Отношение параллельности на множестве прямых плоскости.
d. Отношение подобия на множестве треугольников и т.п.
Считается, что термин “отношение эквивалентности” применяется только в случае, если выполняются следующие три условия:
Ø Каждый элемент эквивалентен самому себе;
Ø Высказывание, что два элемента являются эквивалентными, не требует уточнения, какой из элементов рассматривается первым, а какой вторым;
Ø Два элемента, эквивалентные третьему, эквивалентны между собой.
Для обозначения эквивалентности иногда применяют символ ”~”1.
Тогда общее определение отношения эквивалентности получим, записав три вышеприведенные условия в виде следующих соотношений:
а~а (рефлексивность);
а~bÞb~a (симметричность);
а~b и b~c Þa~c (транзитивность).
Отношение эквивалентности, заданное на множестве А, тесно связано с разбиением множества на классы. Эта определяется следующим утверждением:
Лемма: «Всякое отношение эквивалентности, определенное на множестве А, задает разбиение множества на классы».
Доказательство:
Пусть на множестве А задано отношение эквивалентности «~». Выполним следующее построение. Выберем элемент а1ÎА и образуем класс (подмножество А) А1, состоящий из элемента а1 и всех элементов, эквивалентных а1; затем выберем элемент а2ÏА1 и образуем класс А2, состоящий из а2 и всех элементов, эквивалентных а2 и т.д. получится система классов А1, А2….(возможно бесконечная) такая, что любой элемент из А входит в один класс. Вполне очевидно, что полученная система классов обладает свойствами:
Ø Аi=А;
Ø
Ø .
Построенное разбиение, т.е. система классов, называется системой классов эквивалентности по отношению R.
С другой стороны, любое разбиение А на классы определяет некоторое отношение эквивалентности, а именно, отношение “входить в один и тот же класс данного разбиения”, что утверждается следующей леммой:
Лемма: «Всякое разбиение множества А на классы задает на множестве А отношение эквивалентности»
Доказательство:
Пусть a, b Î A и aRb Û a и b лежат в одном классе разбиения. Тогда для любого а Î К aRa, т.е данное отношение рефлексивно.
Пусть К – некоторый класс разбиения, и a, b Î К. Тогда и b, a Î K, т.е. aRb Þ bRa, что доказывает симметричность отношения элементов данного класса.
Из aRb и bRc следует, что a, b, c Î K. Следовательно aRc что доказывает транзитивность отношения элементов данного класса.
Таким образом доказано, что элементы, определяющие класс разбиения, связаны отношением эквивалентности.
Пример. Разбиение множества натуральных чисел N={1, 2, ….} по отношению “иметь общий остаток от деления на 7” состоит из 7 бесконечных (счетных) классов: первый класс –{0, 7, 14, 21,….} (остаток 0), второй класс –{1, 8, 15, 22,…} (остаток 1), третий класс –{2, 9, 16,….} (остаток 2) ……, седьмой класс – {6, 13, 20, 27,….} (остаток 6).
Пример 5. Отношение “проживание в одном доме” в множестве жителей России образует разбиение населения России.
Множество классов эквивалентности множества А образует фактормножество множества А по отношению эквивалентности и обозначается А|~.
Системой представителей некоторого отношения эквивалентности ~ называется множество, содержащее по одному элементу из каждого класса эквивалентности.
Пример. Пусть на плоскости определена декартова система координат и координаты обозначаются через х и у. Будем говорить, что две точки М1 и М2 эквивалентны, если их абсциссы равны: М1~М2Ûх1=х2.
Класс эквивалентности – прямая, параллельная оси ординат. Фактормножества образованы прямыми на плоскости, параллельными оси ординат. Система представителей может определена точками, лежащими на оси абсцисс, т.е. точками с координатами (х, 0), хÎR.
Другими примерами отношения эквивалентности могут служить равенство и подобие фигур, логические утверждения, выражаемые с помощью оборотов “иметь такое же”, “быть таким же”.