В повседневной жизни нам постоянно приходится сталкиваться с понятием «отношения». Отношения – один из способов задания взаимосвязей между элементами множества.
Унарные (одноместные) отношения отражают наличие какого-то одного признака R у элементов множества M (например, «быть красным» на множестве шаров в урне).
Бинарные (двуместные) отношения используются для определения взаимо
связей, которыми характеризуются пары элементов во множестве M .
Например, на множестве людей могут быть заданы следующие отношения: «жить в одном городе», «x работает под руководством y », «быть сыном», «быть старше» и т.д. на множестве чисел: «число a больше числа b », «число a является делителем числа b », «числа a и b дают одинаковый остаток при делении на 3».
В прямом произведении , где A - множество студентов какого-либо вуза, B - множество изучаемых предметов, можно выделить большое подмножество упорядоченных пар (a, b) , обладающих свойством: «студент a изучает предмет b ». Построенное подмножество отражает отношение «изучает», возникающее между множествами студентов и предметов. Число примеров можно продолжить
Отношения между двумя объектами являются предметом исследования экономики, географии, биологии, физики, лингвистики, математики и других наук.
Для строгого математического описания любых связей между элементами двух множеств вводится понятие бинарного отношения.
Бинарным отношением между множествами A и B называется подмножество R прямого произведения . В том случае, когда можно просто говорить об отношении R на A .
Пример 1 . Выпишите упорядоченные пары, принадлежащие бинарным отношениям R 1 и R 2 , заданными на множествах A и : , . Подмножество R 1 состоит из пар: . Подмножество .
Область определения R на есть множество всех элементов из A таких, что для некоторых элементов имеем . Иными словами область определения R есть множество всех первых координат упорядоченных пар из R .
Множество значений отношения R на есть множество всех таких, что для некоторых . Другими словами множество значений R есть множество всех вторых координат упорядоченных пар из R .
В примере 1 для R 1 область определения: , множество значений - . Для R 2 область определения: , множество значений: .
Во многих случаях удобно использовать графическое изображение бинарного отношения. Оно осуществляется двумя способами: с помощью точек на плоскости и с помощью стрелок.
В первом случае выбирают две взаимно перпендикулярные линии в качестве горизонтальной и вертикальной осей. На горизонтальной оси откладывают элементы множества A и через каждую точку проводят вертикальную линию. На вертикальной оси откладывают элементы множества B , через каждую точку проводят горизонтальную линию. Точки пересечения горизонтальных и вертикальных линий изображают элементы прямого произведения .
Пример 5 . Пусть , .
Пусть R 1 задано на перечислением упорядоченных пар: . Бинарное отношение R 2 на множестве задано с помощью правила: упорядочена пара , если a делится на b . Тогда R 2 состоит из пар: .
Бинарные отношения, из примера 2, R 1 и R 2 изображены графически на рис. 6 и рис.7.
| | |||||||||||||||||||||||||
Рис. 6 Рис. 7
Чтобы изобразить бинарное отношение с помощью стрелок, слева изображаются точками элементы множества A , справа - множества B . Для каждой пары (a, b) , содержащейся в бинарном отношении R , проводится стрелка от a к b , . Графическое изображение бинарного отношения R 1 , приведенного в примере 6, показано на рис.8.
| Рис.8 |
Бинарные отношения на конечных множествах могут быть заданы матрицами. Предположим, что задано бинарное отношение R между множествами A и B . , .
Строки матрицы нумеруются элементами множества A , а столбцы – элементами множества B . Ячейку матрицы, стоящую на пересечении i - ой строки и j - ого столбца принято обозначать через C ij , а заполняется она следующим образом:
Полученная матрица будет иметь размер .
Пример 6. Пусть задано множество . На множестве задайте списком и матрицей отношение R – «быть строго меньше».
Отношение R как множество содержит все пары элементов (a , b) из M такие, что .
Матрица отношения, построенная по вышеуказанным правилам, имеет следующий вид:
Свойства бинарных отношений:
1. Бинарное отношение R на множестве называетсярефлексивным , если для любого элемента a из M пара (a, a) принадлежит R , т.е. имеет место для любого a из M :
Отношения «жить в одном городе», «учиться в одном вузе», «быть не больше» являются рефлексивными.
2. Бинарное отношение называется антирефлексивным ,если оно не обладает свойством рефлексивности для любых a :
Например, «быть больше», «быть младше» - это антирефлексивные отношения .
3. Бинарное отношение R называется симметричным , если для любых элементов a и b из M из того, что пара (a, b) принадлежит R , , вытекает, что пара (b, a) принадлежит R , т.е.
Симметрична параллельность прямых, т.к. если // , то // . Симметрично отношение «быть равным» на любом множестве или «быть взаимнопростым на N».
Отношение R симметрично тогда и только тогда, когда R=R -1
4. Если для несовпадающих элементов верно отношение , но ложно , то отношение антисимметрично . Можно сказать иначе:
Антисимметричными являются отношения «быть больше», «быть делителем на N», «быть младше».
5. Бинарное отношение R называется транзитивным , если для любых трех элементов из того, что пары (a, b) и (b, c) принадлежат R , следует, что пара (a, c) принадлежит R :
Транзитивны отношения : «быть больше», «быть параллельным», «быть равным» и др.
6. Бинарное отношение R антитранзитивно , если оно не обладает свойством транзитивности.
Например, «быть перпендикулярным» на множестве прямых плоскости ( , , но неверно, что ).
Т.к. бинарное отношение может быть задано не только прямым перечислением пар, но и матрицей, то целесообразно выяснить, какими признаками характеризуется матрица отношения R , если оно: 1) рефлексивно, 2) антирефлексивно, 3)симметрично, 4) антисимметрично, 5) транзитивно.
Пусть R задано на , .R либо выполняется в обе стороны, либо не выполняется вообще. Таким образом, если в матрице стоит единица на пересечении i - ой строки и j - ого столбца, т.е. C ij =1, то она должна стоять и на пересечении j - ой строки и i - ого столбца, т.е. C ji =1, и наоборот, если C ji =1, то C ij =1. Таким образом, матрица симметричного отношения симметрична относительно главной диагонали.
4. R антисимметрично, если из и следует: . Это означает, что в соответствующей матрице ни для каких i , j не выполняется C ij = C ji =1. Таким образом, в матрице антисимметричного отношения отсутствуют единицы, симметричные относительно главной диагонали .
5. Бинарное отношение R на непустом множестве A называется транзитивным если
Вышеприведенное условие должно выполняться для любых элементов матрицы. И, наоборот, если в матрице R имеется хотя бы один элемент C ij =1, для которого данное условие не выполняется, то R не транзитивно.
1. Рефлексивность:
2. Слабая рефлексивность:
3. Сильная рефлексивность:
4. Антирефлексивность:
5. Слабая антирефлексивность:
6. Сильная антирефлексивность:
7. Симметричность:
8. Антисимметричность:
9. Асимметричность:
10. Сильная линейность:
11. Слабая линейность:
12. Транзитивность:
Рефлексивность, свойство бинарных (двуместных, двучленных) отношений, выражающее выполнимость их для пар объектов с совпадающими членами (так сказать, между объектом и его "зеркальным отражением"): отношение R называется рефлексивным, если для любого объекта х из области его определения выполняется xRx. Типичные и наиболее важные примеры рефлексивных отношений: отношения типа равенства (тождества, эквивалентности, подобия и т.п.: любой предмет равен самому себе) и отношения нестрогого порядка (любой предмет не меньше и не больше самого себя). Интуитивные представления о "равенстве" (эквивалентности, подобии и т.п.), очевидным образом наделяющие его свойствами симметричности и транзитивности, "вынуждают" и свойство Р., поскольку последнее свойство следует из первых двух. Поэтому многие употребительные в математике отношения, по определению Р. не обладающие, оказывается естественным доопределить таким образом, чтобы они становились рефлексивными, например, считать, что каждая прямая или плоскость параллельна самой себе, и т.п.
Глава 1. Элементы теории множеств
1.1 Множества
Наиболее простая структура данных, используемая в математике, имеет место в случае, когда между отдельными изолированными данными отсутствуют какие-либо взаимосвязи. Совокупность таких данных представляет собой множество . Понятие множества является неопределяемым понятием. Множество не обладает внутренней структурой. Множество можно представить себе как совокупность элементов, обладающих некоторым общим свойством. Для того чтобы некоторую совокупность элементов можно было назвать множеством, необходимо, чтобы выполнялись следующие условия:
Должно существовать правило, позволяющее определить, принадлежит ли указанный элемент данной совокупности.
Должно существовать правило, позволяющее отличать элементы друг от друга. (Это, в частности, означает, что множество не может содержать двух одинаковых элементов).
Множества обычно обозначаются заглавными латинскими буквами. Если элемент
принадлежит множеству , то это обозначается:Если каждый элемент множества
является также и элементом множества , то говорят, что множество является подмножеством множества :Подмножество
множества называется собственным подмножеством , еслиИспользуя понятие множества можно построить более сложные и содержательные объекты.
1.2 Операции над множествами
Основными операциями над множествами являются объединение , пересечение и разность .
Определение 1 . Объединением
Определение 2 . Пересечением двух множеств называется новое множество
Определение 3 . Разностью двух множеств называется новое множество
Если класс объектов, на которых определяются различные множества обозначить
(Универсум ), то дополнением множества называют разность упорядоченную n-ку , называют мощностью отношения .Замечание. Понятие отношения является очень важным не только с математической точки зрения. Понятие отношения фактически лежит в основе всей реляционной теории баз данных. Как будет показано ниже, отношения являются математическим аналогом таблиц . Сам термин "реляционное представление данных", впервые введенный Коддом , происходит от термина relation , понимаемом именно в смысле этого определения.
Т. к. любое множество можно рассматривать как декартовое произведение степени 1, то любое подмножество, как и любое множество, можно считать отношением степени 1. Это не очень интересный пример, свидетельствующий лишь о том, что термины "отношение степени 1" и "подмножество" являются синонимами. Нетривиальность понятия отношения проявляется, когда степень отношения больше 1. Ключевыми здесь являются два момента:
Во-первых , все элементы отношения есть однотипные кортежи. Однотипность кортежей позволяет считать их аналогами строк в простой таблице, т.е. в такой таблице, в которой все строки состоят из одинакового числа ячеек и в соответствующих ячейках содержатся одинаковые типы данных. Например, отношение, состоящее из трех следующих кортежей { (1, "Иванов", 1000), (2, "Петров", 2000), (3, "Сидоров", 3000) } можно считать таблицей, содержащей данные о сотрудниках и их зарплатах. Такая таблица будет иметь три строки и три колонки, причем в каждой колонке содержатся данные одного типа.
В противоположность этому рассмотрим множество { (1), (1,2), (1, 2,3) }, состоящее из разнотипных числовых кортежей. Это множество не является отношением ни в
, ни в , ни в . Из кортежей, входящих в это множество нельзя составить простую таблицу. Правда, можно считать это множество отношением степени 1 на множестве всех возможных числовых кортежей всех возможных степенейОчевидно, что произвольные бинарные отношения изучать в общем плане не особенно интересно, о них можно сказать очень мало. Однако, если отношения удовлетворяют некоторым дополнительным условиям, относительно них можно делать более содержательные утверждения. В этом разделе мы рассмотрим некоторые из основных свойств бинарных отношений.
- 1. Бинарное отношение на множестве X называется рефлексивным, если для любого элемента aX выполняется условие a:
- (aX) a* a.
Если отношение представлено с помощью графа, то рефлексивность этого отношения означает, что в каждой вершине графа обязательно имеется петля.
Для отношения, заданного с помощью булевой матрицы его рефлексивность равносильна тому, что по главной диагонали этой матрицы (идущей из ее левого верхнего угла в правый нижний) стоят только символы 1.
2. Бинарное отношение на X называется антирефлексивным, если ни для одного aX не выполняется условие a * a:
Обозначим через I x отношение на множестве X, состоящее из пар вида (a, a), где a X:
I x = {(a, a)| a X}.
Отношение Ix обычно называют диагональю множества X или отношением тождества на X.
Очевидно, что отношение на множестве X рефлексивно, если диагональ I x является подмножеством множества:
Отношение антирефлексивно, если диагональ I x и отношение б не имеют ни одного общего элемента:
- 3. Бинарное отношение на множестве X называется симметричным, если из a * b следует b * a:
- (a, bX)(a* b b*a).
Примерами симметричных отношений являются:
отношение перпендикулярности на множестве прямых;
отношение касания на множестве окружностей;
отношение "быть похожим" на множестве людей;
отношение "иметь одинаковый пол" на множестве животных.
Отношение "x брат y" на множестве всех людей не является симметричным. В то же время отношение "x брат y" на множестве мужчин симметричным является.
В графе симметричного отношения для каждой дуги из вершины x в вершину y имеется дуга из y в x. Поэтому симметричные отношения можно представлять графами с неориентированными ребрами. При этом каждая пара ориентированных ребер xy и yx заменяется одним неориентированным ребром.
На рисунке 8 представлено отношение
б= {(a, b), (b, a), (b, c), (c, b), (d, c)}
с помощью ориентированного и неориентированного графов.
Рис. 8.
Матрица симметричного отношения симметрична относительно главной диагонали.
Теорема: Объединение и пересечение любого семейства симметричных отношений снова являются симметричными отношениями.
Определение. Бинарное отношение на множестве X называется антисимметричным, если для любых различных элементов a и b условия a * b и b * a не выполняются одновременно:
(a, bX) (a * b & b* a a = b).
Например, отношение "делится" на множестве натуральных чисел является антисимметричным, так как из a b и b a следует, что a = b. Однако на множестве целых чисел отношение "делится" антисимметричным не является, так как (-2) 2 и 2 (-2), но -22.
Отношения "выше", "тяжелее", "старше" антисимметричны на множестве людей. Отношение "быть сестрой" на множестве всех людей антисимметричным не является.
В графе антисимметричного отношения две различные вершины могут быть соединены не более чем одной дугой.
Определение 3.5. Бинарное отношение a на множестве X называется транзитивным, если для любых трех элементов a, b, c X из a*b и b*c следует a*c:
(a, b, c X) (a* b & b* c a*c).
Примерами транзитивных отношений служат:
отношение "делится" на множестве действительных чисел;
отношение "больше" на множестве действительных чисел;
отношение "старше" на множестве людей игрушек;
отношение "иметь одинаковый цвет" на множестве детских игрушек;
д) отношение "быть потомком" на множестве людей.
Феодальное отношение "быть вассалом" не является транзитивным. Это в частности подчеркивается в некоторых учебниках истории: "вассал моего вассала не мой вассал".
Отношение "быть похожим" на множестве людей не обладает свойством транзитивности.
Для произвольного отношения можно найти минимальное транзитивное отношение такое, что аb. Таким отношением является транзитивное замыкание отношения.
Пример 3.1. Транзитивным замыканием бинарного отношения на множестве людей "быть ребенком" является отношение "быть потомком".
Справедлива теорема.
Теорема 3.2. Для любого отношения транзитивное замыкание равно пересечению всех транзитивных отношений, включающих в качестве подмножества.
Определение 3.6. Бинарное отношение на множестве X называется связным, если для любых двух различных элементов a и b имеет место a*b, либо b*a:
(a, b, c X)(ab a*b b*a).
Примером связного отношения является отношение "больше" на множестве действительных чисел. Отношение "делится" на множестве целых чисел связным не является.
4. Инвариантность отношений
В этом параграфе мы перечислим некоторые случаи, когда те или иные свойства отношений сохраняются при выполнении над ними операций .
Теорема 4.4. Чтобы произведение симметричных отношений было симметрично, необходимо и достаточно, чтобы отношения и коммутировали.
Отношение эквивалентности
Важным видом бинарного отношения является отношение эквивалентности.
Определение 1. Бинарное отношение на множестве X называется отношением эквивалентности на X, если рефлексивно, симметрично и транзитивно.
Отношение эквивалентности часто обозначают символами ~,.
Примерами отношения эквивалентности служат:
отношение тождества I X = {(a, a)|aX} на непустом множестве X;
отношение параллельности на множестве прямых плоскости;
отношение подобия на множестве фигур плоскости;
отношение равносильности на множестве уравнений;
отношение "иметь одинаковые остатки при делении на фиксированное натуральное число m" на множестве целых чисел. Это отношение в математике называют отношением сравнимости по модулю m и обозначают ab (mod m);
отношение "принадлежать одному виду" на множестве животных;
отношение "быть родственниками" на множестве людей;
отношение "быть одного роста" на множестве людей;
отношение "жить в одном доме" на множестве людей.
Отношения "жить на одной улице", "быть похожими" на множестве людей отношениями эквивалентности не являются, так как не обладают свойством транзитивности.
Из перечисленных выше свойств бинарных отношений следует, что пересечение отношений эквивалентности является отношением эквивалентности.
Классы эквивалентности
С отношением эквивалентности тесно связано разбиение множества на классы.
Определение 1. Система непустых подмножеств
{M 1 , M 2 , …}
множества M называется разбиением этого множества, если
Сами множества M 1 , M 2 , … называются при этом классами данного разбиения.
Примерами разбиений служат:
разложение всех многоугольников на группы по числу вершин - треугольники, четырехугольники, пятиугольники и т. д.;
разбиение всех треугольников по свойствам углов (остроугольные, прямоугольные, тупоугольные);
разбиение всех треугольников по свойствам сторон (разносторонние, равнобедренные, равносторонние);
разбиение всех треугольников на классы подобных треугольников;
разбиение множества всех учащихся данной школы по классам.
Широкое применение отношений эквивалентности в современной науке связано с тем, что всякое отношение эквивалентности осуществляет разбиение множества, в котором оно определено, на классы, обычно принимаемые за новые объекты. Другими словами с помощью отношений эквивалентности порождаются новые объекты, понятия.
Так, например, отношение сонаправленности лучей разбивает множество всех лучей плоскости или пространства на классы сонаправленных лучей. Каждый из этих классов лучей называется направлением. Таким образом, интуитивное понятие направления получает точное математическое описание как класс разбиения множества лучей с помощью отношения эквивалентности.
О подобных фигурах обычно говорят, что они имеют одинаковую форму. Но что такое форма геометрической фигуры? Интуитивно ясно, что это то общее, что объединяет подобные фигуры. С помощью отношения эквивалентности удается это интуитивное понятие перевести в точное математическое. Отношение подобия, являясь отношением эквивалентности, разбивает множество фигур на классы подобных фигур. Каждый такой класс можно назвать формой. Тогда выражение "две одинаковые фигуры имеют одинаковую форму" имеет следующий точный смысл "две подобные фигуры принадлежат одной форме".
Отношения эквивалентности встречаются всюду, где осуществляются разбиения множеств на классы. Мы часто пользуемся ими, не замечая этого.
Приведем элементарный пример. Когда дети играют со множеством разноцветных игрушек (например, с блоками Дьенеша) и решают задачу разложить игрушки по цветам, то они пользуются отношением "иметь один цвет". Полученные в результате классы одноцветных фигур воспринимаются детьми как новые понятия: красные, желтые, синие и т. д.
Аналогично в результате решения задачи разложения блоков по форме дети получают классы, каждый из которых воспринимается как форма: прямоугольные, круглые, треугольные и т. д.
Связи между отношениями эквивалентности, определенными на множестве M, и разбиениями множества M на классы описываются в следующих двух теоремах.
Теорема 1 Всякое разбиение непустого множества M на классы определяет (индуцирует) на этом множестве отношение эквивалентности такое, что:
всякие два элемента одного класса находятся в отношении;
всякие два элемента различных классов не находятся в отношении. Доказательство. Пусть имеется некоторое разбиение непустого множества M. Определим бинарное отношение следующим образом: xay(K)(xK&yK).
То есть два элемента x и y aиз множества M связаны отношением в том и только в том случае, если в разбиении найдется такой класс K, которому одновременно принадлежат элементы x и y.
Так определенное отношение, очевидно, рефлексивно и симметрично. Докажем транзитивность отношения. Пусть x*y и x*z. Тогда по определению в существуют классы K 1 и K 2 такие, что x, yK 1 и y, zK 2 . Так как различные классы в разбиении не имеют общих элементов, то K 1 = K 2 , то есть x, z K 1 . Поэтому x*z, что и требовалось доказать.
Теорема 2. Всякое отношение эквивалентности в непустом множестве M порождает разбиение этого множества на классы эквивалентности такое, что всякие два элемента одного класса находятся в отношении;
всякие два элемента различных классов не находятся в отношении.
Доказательство. Пусть б - некоторое отношение эквивалентности на множестве M. Каждому элементу x из поставим в соответствие подмножество [x] множества M, состоящее из всех элементов y, находящихся в отношении с элементом x:
Система подмножеств [x], образует разбиение множества M. Действительно, во-первых, каждое подмножество [x]O, так как в силу рефлексивности отношения x[x].
Во-вторых, два различных подмножества [x] и [y] не имеют общих элементов. Рассуждая от противного, допустим существование элемента z такого, что z[x] и z[y]. Тогда zax и zay. Поэтому для любого элемента a[x] из a* x, z*x и z*y в силу симметричности и транзитивности отношения вытекает a*y, то есть a[y]. Следовательно, [x] [y]. Аналогично получаем, что [y][x]. Полученные два включения влекут равенство [x] = [y], противоречащее предположению о несовпадении подмножеств [x] и [y]. Таким образом, [x]y] = O.
В-третьих, объединение всех подмножеств [x] совпадает со множеством M, ибо для любого элемента xM выполняется условие x[x].
Итак, система подмножеств [x], образует разбиение множества M. Несложно показать, что построенное разбиение удовлетворяет условиям теоремы. Разбиение множества M, обладающее свойствами, указанными в теореме, называется фактор-множеством множества M по отношению и обозначается M/б.
Бинарным отношением на множестве А называется подмножество его квадрата RÍ A 2 . Бинарным отношением между множествами А и В называются подмножество принадлежащее декартовому произведению 2-х множеств: RÍ АхВ.
Если упорядоченная пара (а1, а2) принадлежит отношению R, то говорят что а1 R а2, то есть между элементом а1 и а2 уст-но отношение R.
Областью определения бинарного отношения называется множество элементов а, в котором в принадлежит бинарному отношению: þ R ={a|bÎ aRb}.
Областью значения бинарного отношения называют множество b, в котором а принадлежит бинарному значению:
P R ={b|aÎ aRb } .
Обратное отношение для отношения R называется отношение: R -1 ={(b,a)|(a,b) Î R }.
Отношение можно задать:
- с помощью любого способа задания множеств
- С помощью матрицы бинарного отношения . Матрица бинарного отношения это квадратная матрица R элементы которой определяются следующим образом rij=1, (ai,aj)Î R, 0 – в противном случае.
- С использованием графа . Каждому бинарному отношению можно подставить в соответствие граф G(X,U), содержащий множество вершин Х, и множество ребер U. При этом вершины aj ai соединяются дугой если упорядоченная пара aj ai Î R. Так как отношения являются множеством упорядоченных пар, то для отношения можно определить те же операции, что и для множеств (объединение, пересечение, разность, дополнение, симметрическая разность).
Свойство бинарных отношений:
1) Рефлексивность . Пусть на множестве А задано бинарное отношение R. Бинарное отношение называется рефлексивным, если для любого элемента А упорядоченная пара из этого элемента принадлежит R: для любого A(a,a) Î R. Т.е. бинарное отношение на множестве называется рефлексивным , если всякий элемент этого множества находится в отношении с самим собой.
Матрица рефлексивного отношения на диагонали содержит 1, а граф бинарного отношения имеет петли.
2)Антирефлексивность . Бинарные отношения являются антирефлексивными, если: для любого A(a,a) Ï R.
Матрица антирефлексивного отношения на диагонали содержит 0, а граф не имеет петель.
3)Симметричность. Бинарное отношение на множестве X называется симметричным , если для каждой пары элементов множества выполнение отношения влечёт выполнение отношения . Отношение симметрично, если .
Матрица симметричного бинарного отношения симметрична относительно главной диагонали. В графе все пары вершин соединены 2-мя противоположно направленными дугами.
4) Антисимметричночть . В математике бинарное отношение на множестве X называется антисимметричным , если для каждой пары элементов множества выполнение отношений и влечёт , или, что то же самое, выполнение отношений и возможно только для равных и .
Матрица антисимметричного бинарного отношения не симметрична относительно главной диагонали, в графе отсутствуют противоположно направленные дуги.
5) Транзитивность. Бинарное отношение называют транзитивным, если:
В графе задающего транзитивное бинарное отношение для каждой пары дуг таких, что конец первой совпадает с началом второй, существует дуга, соединяющая начало первой дуги с концом второй.
Специальные бинарные отношения:
1) Отношение Эквивалентности на множестве А это отношение, обладающее свойством рефлекисвности, симметричности и транзитивности. (Отношение равенства, отношение параллельности).
2) Отношения строгого порядка: это бинарное отношение на множестве А, обладающее свойствами антирефлексивности, антисимметричности и транзитивности.
3) Отношения нестрого порядка- бинарные отношения, обладающие свойствами рефлексивности. Антисимметричности и транзитивности.
Отношение, заданное на множестве, может обладать рядом свойств, а именно:
2. Рефлексивность
Определение. Отношение R намножестве Х называется рефлексивным, если каждый элемент х множества Х находится в отношении R с самим собой.
Используя символы, это отношение можно записать в таком виде:
R рефлексивно на Х Û("х Î Х ) х R х
Пример. Отношение равенства на множестве отрезков рефлексивно, т.к. каждый отрезок равен себе самому.
Граф рефлексивного отношения во всех вершинах имеет петли.
2. Антирефлексивность
Определение. Отношение R намножестве Х называется антирефлексивным, если ни один элемент х множества Х не находится в отношении R с самим собой.
R антирефлексивно на Х Û("х Î Х )
Пример. Отношение «прямая х перпендикулярна прямой у » на множестве прямых плоскости антирефлексивно, т.к. ни одна прямая плоскости не перпендикулярна самой себе.
Граф антирефлексивного отношения не содержит ни одной петли.
Заметим, что существуют отношения, не являющиеся ни рефлексивными, ни антирефлексивными. Например, рассмотрим отношение «точка х симметрична точке у » на множестве точек плоскости.
Точка х симметрична точке х – истинно; точка у симметрична точке у – ложно, следовательно, мы не можем утверждать, что все точки плоскости симметричны сами себе, также мы не можем и утверждать, что ни одна точка плоскости не симметрична сама себе.
3. Симметричность
Определение . Отношение R намножестве Х называется симметричным, если из того, что элемент х находится в отношении R с элементом у , следует, что и элемент у находится в отношении R с элементом х .
R симметричнона Х Û("х , у Î Х ) х R у Þ у R х
Пример. Отношение «прямая х пересекает прямую у на множестве прямых плоскости» симметрично, т.к. если прямая х пересекает прямую у , то и прямая у обязательно будет пересекать прямую х .
Граф симметричного отношения вместе с каждой стрелкой из точки х в точку у должен содержать стрелку, соединяющую те же точки, но в обратном направлении.
4. Асимметричность
Определение . Отношение R намножестве Х называется асимметричным, если ни для каких элементов х , у из множества Х не может случиться, что элемент х находится в отношении R с элементом у и элемент у находится в отношении R с элементом х .
R асимметричнона Х Û("х , у Î Х ) х R у Þ
Пример. Отношение «х < у » асимметрично, т.к. ни для какой пары элементов х , у нельзя сказать, что одновременно х < у и у < х .
Граф асимметричного отношения не имеет петель и если две вершины графа соединены стрелкой, то эта стрелка только одна.
5. Антисимметричность
Определение . Отношение R намножестве Х называется антисимметричным, если из того что х находится в отношении с у , а у находится в отношении с х следует, что х = у.
R антисимметричнона Х Û("х , у Î Х ) х R у Ù у R х Þ х = у
Пример. Отношение «х £ у » антисимметрично, т.к. условия х £ у и у £ х одновременно выполняются только тогда, когда х = у.
Граф антисимметричного отношения имеет петли и если две вершины графа соединены стрелкой, то эта стрелка только одна.
6. Транзитивность
Определение . Отношение R намножестве Х называется транзитивным, если для любых элементов х , у , z из множества Х из того, что х находится в отношении с у , а у находится в отношении с z следует, что х находится в отношении с z.
R транзитивнона Х Û("х , у , z Î Х ) х R у Ù у R z Þ х R z
Пример. Отношение «х кратно у » транзитивно, т.к. если первое число кратно второму, а второе кратно третьему, то первое число будет кратно третьему.
Граф транзитивного отношения с каждой парой стрелок от х к у и от у к z содержит стрелку, идущую от х к z.
7. Связность
Определение . Отношение R намножестве Х называется связным, если для любых элементов х , у из множества Х х находится в отношении с у или у находится в отношении с х или х = у .
R связнона Х Û("х , у , z Î Х ) х R у Ú у R z Ú х = у
Другими словами: отношение R намножестве Х называется связным, если для любых различных элементов х , у из множества Х х находится в отношении с у или у находится в отношении с х или х = у .
Пример. Отношение «х < у » связно, т.к. какие бы мы действительные числа не взяли, обязательно одно из них будет больше другого или они равны.
На графе связного отношения все вершины соединены между собой стрелками.
Пример. Проверить, какими свойствами обладает
отношение «х – делитель у », заданное на множестве
Х = {2; 3; 4; 6; 8}.
1) данное отношение рефлексивно, т.к. каждое число из данного множества является делителем самого себя;
2) свойством антирефлексивности данное отношение не обладает;
3) свойство симметричности не выполняется, т.к. например, 2 является делителем числа 4, но 4 делителем числа 2 не является;
4) данное отношение антисимметрично: два числа могут быть одновременно делителями друг друга только в том случае, если эти числа равны;
5) отношение транзитивно, т.к. если одно число является делителем второго, а второе – делителем третьего, то первое число обязательно будет делителем третьего;
6) отношение свойством связности не обладает, т.к. например, числа 2 и 3 на графе стрелкой не соединены, т.к. два различных числа 2 и 3 делителями друг друга не являются.
Таким образом, данное отношение обладает свойствами рефлексивности, асимметричности и транзитивности.
§ 3. Отношение эквивалентности.
Связь отношения эквивалентности с разбиением множества на классы
Определение. Отношение R на множестве Х называется отношением эквивалентности, если оно рефлексивно, симметрично и транзитивно.
Пример. Рассмотрим отношение «х однокурсник у » на множестве студентов педфака. Оно обладает свойствами:
1) рефлексивности, т.к. каждый студент является однокурсником самому себе;
2) симметричности, т.к. если студент х у , то и студент у является однокурсником студента х ;
3) транзитивности, т.к. если студент х - однокурсник у , а студент у – однокурсник z , то студент х будет однокурсником студента z .
Таким образом, данное отношение обладает свойствами рефлексивности, симметричности и транзитивности, а значит, является отношением эквивалентности. При этом множество студентов педфака можно разбить на подмножества, состоящие из студентов, обучающихся на одном курсе. Получаем 5 подмножеств.
Отношением эквивалентности являются также, например, отношение параллельности прямых, отношение равенства фигур. Каждое такое отношение связано с разбиением множества на классы.
Теорема. Если на множестве Х задано отношение эквивалентности, то оно разбивает это множество на попарно непересекающиеся подмножества (классы эквивалентности).
Верно и обратное утверждение: если какое-либо отношение, заданное на множестве Х , порождает разбиение этого множества на классы, то оно является отношением эквивалентности.
Пример. На множестве Х = {1; 2; 3; 4; 5; 6; 7; 8} задано отношение «иметь один и тот же остаток при делении на 3». Является ли оно отношением эквивалентности?
Построим граф данного отношения:
Данное отношение обладает свойствами рефлексивности, симметричности и транзитивности, следовательно, является отношение эквивалентности и разбивает множество Х на классыэквивалентности. В каждом классе эквивалентности будут числа, которые при делении на 3 дают один и тот же остаток: Х 1 = {3; 6}, Х 2 = {1; 4; 7}, Х 3 = {2; 5; 8}.
Считают, что класс эквивалентности определяется любым своим представителем, т.е. произвольным элементом этого класса. Так, класс равных дробей можно задать, указав любую дробь, принадлежащую этому классу.
В начальном курсе математики также встречаются отношения эквивалентности, например, «выражения х и у имеют одинаковые числовые значения», «фигура х равна фигуре у ».