отношение r на множестве х называется рефлексивным если

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

1. Отношение R на множестве X называется рефлексивным, если каждый элемент множества находится в этом отношении с самим собой.

R —рефлексивно на X xRx для любого x€ X

Если отношение R рефлексивно, то в каждой вершине графа имеется петля. Например, отношения равенства и параллельности для отрезков являются рефлексивными, а отношение перпендику­лярности и «длиннее» не являются рефлексивными. Это отражают графы на рисунке 42.

2. Отношение R на множестве X называется симметричным, если из того, что элемент х находится в данном отношении с элементом у, следует, что элемент у находится в этом же отношении с элементом х.

R — симметрично на (хЯу =>у Rx)

3. Отношение R на множестве X называется антисимметричным, если для различных элементов х и у из множества X из того, что элемент х находится в данном отношении с элементом у, следует, что элемент у в этом отношении с элементом х не находится.

R — антисимметрично на Х« (xRy и xy ≠ yRx)

Замечание: черта сверху обозначает отрицание высказывания.

На графе антисимметричного отношения две точки может сое­динять только одна стрелка. Примером такого отношения является отношение «длиннее» для отрезков (рис. 42). Отношения параллель­ности, перпендикулярности и равенства не являются антисиммет­ричными. Существуют отношения, не являющиеся ни симметрич­ными, ни антисимметричными, например отношение «быть братом» (рис. 40).

4. Отношение R на множестве X называется транзитивным, если из того, что элемент х находится в данном отношении с элементом у и элемент у находится в этом лее отношении с элементом z, следует, что элемент х находится в данном отношении с элементом Z

На графах отношений «длиннее», параллельности и равенства на рисунке 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. Какое множество называют упорядоченным?

Источник

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

Отношение R на множестве Х называется рефлексивным, если о каждом элементе множества Х можно сказать, что он находится в отношении R с самим собой: хRх. Если отношение рефлексивно, то в каждой вершине графа имеется петля. И обратно, граф, каждая вершина которого содержит петлю, представляет собой граф рефлексивного отношения.

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

Существуют отношения, не обладающие свойством рефлексивности, например, отношение перпендикулярности отрезков: ab, ba (нет ни одного отрезка, о котором можно сказать, что он перпендикулярен самому себе). Поэтому на графе данного отношения нет ни одной петли.

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

Отношение R на множестве Х называется антирефлексивным, если для любого элемента из множества Х всегда ложно хRх: .

Существуют отношения, не являющиеся ни рефлексивными, ни антирефлексивными. Примером такого отношения может служить отношение «точка х симметрична точке у относительно прямой l», заданное на множестве точек плоскости. Действительно, все точки прямой l симметричны сами себе, а точки, не лежащие на прямой l, себе не симметричны.

Граф симметричного отношения обладает следующей особенностью: вместе с каждой стрелкой, идущей от х к y, граф содержит стрелку, идущую от y к х (рис. 35).

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

Существуют отношения, которые не обладают свойством симметричности.

Действительно, если отрезок х длиннее отрезка у, то отрезок у не может быть длиннее отрезка х. Граф этого отношения обладает особенностью: стрелка, соединяющая вершины, направлена только в одну сторону.

Отношение R называют антисимметричным, если для любых элементов х и y из истинности xRy следует ложность yRx: : xRyyRx.

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

Существуют отношения, которые не обладают ни свойством симметричности, ни свойством антисимметричности.

Отношение R на множестве Х называют транзитивным, если из того, что элемент х находится в отношении R с элементом y, а элемент y находится в отношении R с элементом z, следует, что элемент х находится в отношении R с элементом z: xRy и yRzxRz.

Граф транзитивного отношения с каждой парой стрелок, идущих от х к y и от y к z, содержит стрелку, идущую от х к z.

Свойством транзитивности обладает и отношение «длиннее» на множестве отрезков: если отрезок а длиннее отрезка b, отрезок b длиннее отрезка с, то отрезок а длиннее отрезка с. Отношение «равенства» на множестве отрезков также обладает свойством транзитивности: (а=b, b=с)(а=с).

Существуют отношения, которые не обладают свойством транзитивности. Таким отношением является, например, отношение перпендикулярности: если отрезок а перпендикулярен отрезку b, а отрезок b перпендикулярен отрезку с, то отрезки а и с не перпендикулярны!

Существует еще одно свойство отношений, которое называется свойством связанности, а отношение, обладающее им, называют связанным.

Отношение R на множестве Х называется связанным, если для любых элементов х и y из данного множества выполняется условие: если х и y различны, то либо х находится в отношении R с элементом y, либо элемент y находится в отношении R с элементом х. С помощью символов это определение можно записать так: xy xRy или yRx.

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

На графе связанного отношения любые две вершины соединены стрелкой. Справедливо и обратное утверждение.

Существуют отношения, которые не обладают свойством связанности. Таким отношением, например, является отношение делимости на множестве натуральных чисел: можно назвать такие числа х и y, что ни число х не является делителем числа y, ни число y не является делителем числа х (числа 17 и 11, 3 и 10 и т.д.).

Рассмотрим несколько примеров. На множестве Х= задано отношение «число х кратно числу y». Построим граф данного отношения и сформулируем его свойства.

Про отношение равенства дробей говорят, оно является отношением эквивалентности.

Отношение R на множестве Х называется отношением эквивалентности, если оно одновременно обладает свойством рефлексивности, симметричности и транзитивности.

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

В рассмотренном выше отношении «равенства дробей», множество Х разбилось на три подмножества: <; ; >, <; >, <>. Эти подмножества не пересекаются, а их объединение совпадает с множеством Х, т.е. имеем разбиение множества на классы.

Итак, если на множестве Х задано отношение эквивалентности, то оно порождает разбиение этого множества на попарно непересекающиеся подмножества – классы эквивалентности.

Так, мы установили, что отношению равенства на множестве
Х= <;; ; ; ; > соответствует разбиение этого множества на классы эквивалентности, каждый из которых состоит из равных между собой дробей.

Принцип разбиения множества на классы при помощи некоторого отношения эквивалентности является важным принципом математики. Почему?

Во-первых, эквивалентный – это значит равносильный, взаимозаменяемый. Поэтому элементы одного класса эквивалентности взаимозаменяемы. Так, дроби, оказавшиеся в одном классе эквивалентности <; ; >, неразличимы с точки зрения отношения равенства, и дробь может быть заменена другой, например . И эта замена не изменит результата вычислений.

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

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

Другим важным видом отношений являются отношения порядка. Рассмотрим задачу. На множестве Х=<3, 4, 5, 6, 7, 8, 9, 10> задано отношение «иметь один и тот же остаток при делении на 3». Это отношение порождает разбиение множества Х на классы: в один попадут все числа, при делении которых на 3 получается в остатке 0 (это числа 3, 6, 9). Во второй – числа, при делении которых на 3 в остатке получается 1 (это числа 4, 7, 10). В третий попадут все числа, при делении которых на 3 в остатке получается 2 (это числа 5, 8). Действительно, полученные множества не пересекаются и их объединение совпадает с множеством Х. Следовательно, отношение «иметь один и тот же остаток при делении на 3», заданное на множестве Х, является отношением эквивалентности.

Возьмем еще пример: множество учащихся класса можно упорядочить по росту или возрасту. Заметим, что это отношение обладает свойствами антисимметричности и транзитивности. Или всем известен порядок следования букв в алфавите. Его обеспечивает отношение «следует».

Отношение R на множестве Х называется отношением строгого порядка, если оно одновременно обладает свойствами антисимметричности и транзитивности. Например, отношение «х Просмотров 151 137 Комментариев 0

Источник

Лекция 2. Отношения на множестве, их свойства.

Если множества X и Y совпадают, X = Y, то говорят не о соответствии, а об отношении между элементами множества X.

Бинарные соответствия между X и X называют бинарными отношениями на множестве X.

Например, если X – множество людей, то соответствия «Человек х – друг человека у», «х живет в одном доме с у», «Человек х – отец человека у» являются отношениями между людьми.

Отношение на множестве X задано, если указано множество Г, являющееся подмножеством декартова произведения Х×Х.

Отношения, как и соответствия, принято обозначать буквами R, S, T, Q и др. и писать xRy, xSy и т. д.

Множество X называют областью задания отношения R, а множество Г – графиком отношения R.

Рассмотрим, например, на множестве Х= <1; 2; 3; 4>отношение «х>у». График этого отношения – множество Г=<(2; 1); (3; 1); (3; 2); (4; 1); (4; 2); (4; 3)>, состоящее из всех тех пар (х; у), х€Х, у€Х, для которых х>у.

Способы задания отношения:

1. Перечисление упорядочных пар или графиком Г,

2. Словесным описанием,

3. Ориентированным графом,

4. Графиком в ПДСК (только для числовых множеств),

5. Таблицей (например, график дежурства – задает соответствие между учениками и днями недели),

6. Аналитически или формулой (например, у=х+5).

Чтобы наглядно представить отношение R в множестве X, изобразим точками элементы этого множества, а затем проведем стрелки от х к у для всех пар точек (х; у) таких, что xRy. Полученный чертеж называют графом отношения R, а точки, изображающие элементы множества X, вершинами графа

Построим, например, граф отношения R: «х≤у», заданного на множестве

Х= < 1/2; 3/5;4>. Для этого рисуем диаграмму множества X, изобразив элементы этого множества точками. Затем проводим стрелки от х к у для всех пар (x; у) таких, что х меньше или равент у. Получаем граф отношения «х≤у», заданного на множестве Х= <1>.

Каждое из этих чисел равно самому себе, поэтому для каждой точки х, изображающей элемент множества X, рисуем стрелку, начало и конец которой совпадают с х. Стрелку на графе, у которой начало и конец совпадают, называют петлей. Следовательно, граф отношения R в каждой вершине имеет петли.

Пусть на множестве X задано некоторое отношение R

1. Отношение R называется рефлексивным, если для любого х из множества X истинно xRx. Другими словами, отношение R на множестве X рефлексивно, если каждый элемент х £ X находится в отношении R с самим собой.

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

2. Отношение R называется антирефлексивным, если ни один элемент х из множества X не находится в отношении R с самим собой.

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

Существуют отношения, не являющиеся ни рефлексивными, ни антирефлексивными. Примером такого отношения может служить отношение «Точка х симметрична точке у относительно прямой l», заданное на множестве точек плоскости. Действительно, все точки прямой l симметричны самим себе, а точки, не лежащие на прямой l, себе не симметричны.

3. Отношение R называется симметричным, если для любых элементов х и у из множества X из xRy следует yRx.

Так, симметрично отношение параллельности на множестве прямых плоскости: если прямая х параллельна прямой у, то и прямая у параллельна прямой х.

4. Отношение R называется асимметричным если ни для каких элементов х и у из множества X не может случиться, что одновременно и xRy, и yRx.

Примером асимметричного отношения является отношение

Свойства рефлексивности, симметричности и транзитивности наглядно иллюстрируются при изображении отношений графами. Если отношение R в множестве X рефлексивно, то граф этого отношения в каждой вершине имеет петлю.

Если отношение R симметрично, то граф вместе с каждой стрелкой, идущей из точки х в точку у, должен содержать стрелку, соединяющую те же точки, но идущую в обратном направлении.

Граф транзитивного отношения вместе со стрелками, идущими от х к у и от у к z, должен содержать и стрелку, идущую от х к z.

Отношение эквивалентности. Связь отношения эквивалентности с разбиением множества на классы (классификацией).

Множество X всех студентов пединститута можно разбить на подмножества, состоящие из студентов, обучающихся на одном и том же курсе. Если обучение длится четыре года, то получаем четыре подмножества: студентов первого курса, студентов второго курса, студентов третьего курса и студентов четвертого курса. Никакие два из этих множеств не имеют общих элементов (студент не может сразу учиться и на втором, и на третьем курсе), а объединением этих множеств является множество X всех студентов. Говорят, что X разбито на четыре попарно непересекающихся подмножества Х1 Х2, Х3, Х4. То же множество X можно разбить на непересекающиеся подмножества и другими способами, например, на юношей и девушек, по возрасту, на комсомольцев и не комсомольцев и т. д.

Вообще, можно говорить о разбиении данного множества на попарно непересекающиеся подмножества или классы тогда, когда одновременно выполняются следующие условия:

1. Все подмножества, образующие разбиение, непусты.

2. Любые два таких подмножества не пересекаются.

3. Объединение всех подмножеств есть данное множество.

Так, множество натуральных чисел можно разбить на три подмножества – множество простых чисел, множество составных чисел и множество, состоящее из единицы. Это же множество можно разбить и на два класса – класс четных и класс нечетных натуральных чисел.

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

Разбиение множества на попарно-непересекающиеся подмножества часто производят по некоторому свойству, которое может принимать различные значения. Например, можно производить разбиение на классы по цвету, объединяя в один класс предметы одного и того же цвета. При этом красные предметы попадут в один класс зеленые – в другой, черные – в третий и т. д. Можно сказать, что разбиение производится на основе отношения «х имеет тот же цвет, что и у». Точно так же разбиение студентов по курсам производится на основе отношения «х учится на том же курсе, что и у».

Но не всякое отношение R между элементами множества дает возможность разбить это множество на классы. Нельзя, например, разбить на попарно-непересекающиеся подмножества множество студентов некоторого института при помощи отношения «Студент х знаком со студентом у». Действительно, если х знаком с у, то х и у окажутся в одном подмножестве. Если у знаком с г, то z должен находиться в одном подмножестве с у и, следовательно, с х. Но может случиться, что х не знаком с z. Тогда окажется, что в одном подмножестве есть люди, которые друг с другом не знакомы, а этого не должно быть при разбиении множества по указанному отношению.

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

Если отношение R в множестве X обладает свойствами рефлексивности, симметричности и транзитивности, то его называют отношением эквивалентности.

Выше представлен граф отношения эквивалентности.

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

С каждым таким отношением связано разбиение множества на непересекающиеся подмножества. И это не случайно. Имеет место следующая теорема Для того чтобы отношение R позволяло разбить множество X на классы, необходимо и достаточно, чтобы R было отношением эквивалентности.

Рассмотрим несколько примеров отношений эквивалентности.

1. Отношение «Выражения х и у имеют одинаковые числовые значения» на множестве числовых выражений является отношением эквивалентности, поскольку оно

а) рефлексивно: значение выражения х совпадает со значением выражения х;

б) симметрично: если значение выражения х совпадает со значением выражения у, то и значение выражения у совпадает со значением выражения х;

в) транзитивно: если значение выражения х совпадает со значением выражения у, а значение выражения у совпадает со значением выражения z, то значение выражения х совпадает со значением выражения z.

Множество всех числовых выражений разбивается этим отношением на классы, в каждом из которых находятся выражения, значения которых попарно совпадают. Так, выражения 5+3, 23, 2+2+2+2 находятся в одном классе (их значения равны восьми), а выражения 7–3,22, 16 : 4 – в другом (их значения равны четырем).

2. Во множестве прямых на плоскости отношение параллельности является отношением эквивалентности. Прямые х и у, лежащие в одной плоскости, параллельны, если они либо не пересекаются, либо совпадают. Поэтому отношение параллельности

а) рефлексивно: х\\х для любой прямой х;

б) симметрично: если х\\у, то у\\х;

в) транзитивно: если х\\у и y\\z, то x\\z.

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

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

Отношением порядка называют антисимметричное и транзитивное отношение.

Если отношению порядка присуще еще свойство рефлексивности, то порядок нестрогий.

Если ему присуще свойство антирефлексивности, то порядок строгий.

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

Выясним особенности графа отношения строгого порядка. Отметим, что граф отношения строгого порядка не имеет петель, нет обратных стрелок. Если из х идет стрелка в у, а из у – в z, то из х идет стрелка в z.

Наряду с отношением «х y») в математике рассматривают отношения «х≤y» («х≥у»), представляющие собой объединение отношений «х y» и «х=y»).

Говорят, что «х≤у» является отношением нестрогого порядка.

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

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

Множество X, на котором задано отношение порядка R (строгого или нестрогого), называется частично упорядоченным множеством. Часто говорят также, что в этом случае множество X упорядочено отношением R.

Примером такого множества является множество натуральных чисел по отношению меньше или больше.

Источник