отношение x равно y является отношением

Отношение x равно y является отношением

Об отношении можно говорить тогда, когда можно выделить множество объектов, на которых это отношение определено.

Отношением А на множестве М называют подмножество А множества М ´ М. Если входит в А, то обозначают xAy ( Î A). Эта запись читается так: «х находится в отношении А с y».

Такая матрица полностью задает отношение А на множестве М. Прямое произведение М ´ М представлено двадцатью пятью элементами матрицы (табл. 1.2.1).

Элементы теории графов рассмотрим во второй части данного пособия.

1) Отношение А рефлексивно, если оно выполнено между объектом и им самим, т.е. хАх.

2) Если отношение А может выполняться лишь для несовпадающих объектов, то оно антирефлексивно, т.е. из хАу следует, что х ¹ у.

3) Отношение А называется симметричным, если при выполнении хАу выполнено уАх.

Справедлива теорема: если отношение антисимметрично, то оно антирефлексивно.

5) Отношение называется транзитивным, если при выполнении хАу и уАz выполнено хАz.

Примером является отношение «быть больше (меньше)». Так, если х

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

Эквивалентность . Отношение эквивалентности определяется отображением множества Х на множество Y и характеризуется разбиением множества Х на классы.

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

Два элемента множества Х эквивалентны, если они принадлежат одному и тому же классу.

Разбивая множество Х на классы, мы осуществили сюръективное отображение множества всех учащихся Х на множество Y, состоящее из двух элементов у₁= ,у₂= . Причем , .

В то же время составляется каталог по алфавиту, мы осуществляем сюръективное отображение множества всех книг в библиотеке Х на множество букв алфавита Y.

Отношение А на множестве М называется толерантностью, если оно рефлексивно и симметрично.

Так отношение «быть знакомым» соответствует определению толерантности.

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

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

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

Биективное отображение “ f ” упорядоченном множестве Х на упорядоченное множество Y, называют соответствием подобия или подобным соответствием, если оно сохраняет порядок.

Два упорядоченных множества называются подобными, или имеющими один и тот же порядковый тип, если одно из них можно подобно отобразить на другое. Так, два конечных упорядоченных множеств Х и Y, состоящих из одного и того же числа элементов, подобны между собой. Указанные выше биективное отображение между всей числовой прямой и интервалом (а,b) является соответствием подобия и указанные множества подобны (рис. 1.1.9).

Заметим, что подобные множества имеют одну ту же мощность.

Источник

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

Отношение 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.

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

Источник