Бинарные отношения.
Пусть A и B – произвольные множества.
Возьмем по одному элементу из каждого множества, a из A, b из B и
запишем их так:
(сначала элемент первого множества, затем элемент второго множества – т.е. нам
важен порядок, в котором берутся элементы). Такой объект будем называть упорядоченной
парой
. Равными
будем считать только те пары, у которых элементы с
одинаковыми номерами равны. =
Декартовым произведением произвольных множеств A и B (обозначается: AB) называется множество, состоящее из всех возможных упорядоченных пар, первый элемент которых принадлежит A, а второй принадлежит B. По определению: AB = { | aA и bB}. Очевидно, что если A≠B, то AB ≠ BA. Декартово произведение множества A само на себя n раз называется декартовой степенью A (обозначается: A n).
Пример 5. Пусть A = {x, y} и B = {1, 2, 3}.
AB = {
BA = {<1, x>, <2, x>, <3, x>, <1, y>, <2, y>, <3, y>}.
AA = A 2 = {
BB = B 2 = {<1, 1>, <1, 2>, <1, 3>, <2, 1>, <2, 2>, <2, 3>, <3, 1>, <3, 2>, <3, 3>}.
Бинарным
отношением
на множестве M называется множество некоторых
упорядоченных пар элементов множества M. Если r – бинарное отношение и пара
Пример 6. Множество {<1, 2>, <2, 2>, <3, 4>, <5, 2>, <2, 4>} является бинарным отношением на множестве {1, 2, 3, 4, 5}.
Пример 7.
Отношение ³ на множестве целых чисел
является бинарным отношением. Это бесконечное множество упорядоченных пар вида
Пример 8.
Отношение равенства на множестве A является бинарным
отношением: I A = {
Поскольку бинарные отношения являются множествами, то к ним применимы операции объединения, пересечения, дополнения и разности.
Областью определения бинарного отношения r называется множество D(r) = { x | существует такое y, что xry }. Областью значений бинарного отношения r называется множество R(r) = { y | существует такое x, что xry }.
Отношением, обратным
к бинарному отношению r Í M 2 , называется бинарное отношение r -1 = {
Композицией
бинарных отношений r 1 и r 2 , заданных на множестве M, называется бинарное отношение r 2 o r 1 = {
Пример 9. Пусть бинарное отношение r
задано на множестве M = {a, b, c, d}, r = {, ,
Пусть r – бинарное отношение на множестве M. Отношение r
называется рефлексивным
, если x r x для любого x Î M. Отношение r называется симметричным
, если вместе
с каждой парой
Укажем критерии выполнения этих свойств.
Бинарное отношение r на множестве M рефлексивно тогда и только тогда, когда I M Í r.
Бинарное отношение r симметрично тогда и только тогда, когда r = r ‑1 .
Бинарное отношение r на множестве M антисимметрично тогда и только тогда, когда r Ç r ‑1 = I M .
Бинарное отношение r транзитивно тогда и только тогда, когда r o r Í r.
Пример 10. Отношение из примера 6 является антисимметричным, но не является симметричным, рефлексивным и транзитивным. Отношение из примера 7 является рефлексивным, антисимметричным и транзитивным, но не является симметричным. Отношение I A обладает всеми четырьмя рассматриваемыми свойствами. Отношения r ‑1 o r и r o r ‑1 являются симметричными, транзитивными, но не являются антисимметричными и рефлексивными.
Отношением эквивалентности на множестве M называется транзитивное, симметричное и рефлексивное на М бинарное отношение.
Отношением частичного порядка на множестве М называется транзитивное, антисимметричное и рефлексивное на М бинарное отношение r.
Пример 11. Отношение из примера 7 является отношением частичного порядка. Отношение I A является отношением эквивалентности и частичного порядка. Отношение параллельности на множестве прямых является отношением эквивалентности.
Рассмотрим отношение «уважать», определенное на множестве всех людей %%M%%. Для полной информации о том, кто кого уважает, составим следующее множество %%R%%. Переберем все пары %%(a, b)%%, где %%a, b%% пробегают множество всех людей. Если %%a%% уважает %%b%%, то пару %%(a,b)%% отнесем к множеству %%R%%, иначе — нет.
Этот список полностью отражает отношение «уважать». Если нужно узнать, уважает ли человек %%a%% человека %%b%%, то просмотрим множество %%R%%. Если пара %%(a, b) \in R%%, то заключаем, что %%a%% уважает %%b%%. В случае %%(a,b) \notin R%% — %%a%% не уважает %%b%%.
Определение
Бинарным отношением , определенным на множестве %%M%%, называется произвольное подмножество %%R%% из декартового произведения %%M^2%%.
Пример
Рассмотрим отношение больше на множестве %%M = \{1, 2\}%%. Тогда
$$ M^2 = \big\{(1, 1), (1,2), (2,1), (2,2)\big\} $$ Из него выбирем все пары %%(a,b)%%, где %%a > b%%. Получим $$ R = \big\{(2,1)\big\} $$
Виды бинарных отношений
Рефлексивное бинарное отношение
рефлексивным , если для любого элемента %%a%% из %%M%%, выполняется условие %%a~R~a%%. $$ \begin{array}{l} \forall a\in M~~a~R~a \text{ или}\\ \forall a\in M~~(a,a) \in R. \end{array} $$
Примеры
- Рассмотрим отношение больше больше рефлексивным? Если да, то каждое число является больше самого себя, что неверно. Поэтому отношение больше не рефлексивно.
- Рассмотрим отношение равно на множестве действительных чисел. Оно является рефлексивным , так как каждое действительное число равно самому себе.
Симметричное бинарное отношение
Бинарное отношение %%R%% на множестве %%M%% называется симметричным , если для любых двух элементов %%a, b%% из %%M%%, из условия %%a~R~b%% следует условие %%b~R~a%%.
$$ \begin{array}{l} \forall a,b\in M~~a~R~b \rightarrow b~R~a \text{ или}\\ \forall a,b\in M~~(a,b) \in R \rightarrow (b,a) \in R. \end{array} $$
Примеры
- Рассмотрим отношение больше на множестве действительных чисел. Является ли отношение больше симметричным? Оно не является симметричным, так как если %%a > b%%, то условие %%b > a%% не выполняется. Поэтому отношение больше не симметрично.
- Пусть %%R%% — отношение, определенное на множестве %%M = \{a,b,c\}%%. При этом %%R = \big\{ (a,b), (b,c), (a,a), (b,a), (c,b)\big\}%%. Для этого отношения имеем %%\forall x,y \in M ~~ (x,y) \in R \rightarrow (y,x) \in R%%. По определению %%R%% симметрично.
Транзитивное бинарное отношение
Бинарное отношение %%R%% на множестве %%M%% называется транзитивным , если для любых элементов %%a, b, c%% из %%M%%, из условий %%a~R~b%% и %%b~R~c%% следует условие %%a~R~c%%.
$$ \begin{array}{l} \forall a,b,c\in M~~a~R~b \land b~R~c \rightarrow a~R~c \text{ или}\\ \forall a,b,c\in M~~(a,b) \in R \land (b,c) \in R \rightarrow (a,c) \in R. \end{array} $$
Пример
Рассмотрим отношение больше на множестве дейтсвительных чисел. Оно является транзитивным , так как для любых элементов выполняется условние %%\forall a,b,c\in M~~a > b \land b > c \rightarrow a > c%%. Так, например, подставив вместо %%a, b%% и %%c%% числа %%2, 1%% и %%0%% соответственно, получим: если %%2 > 1%% и %%1 > 0%%, то %%2 > 0%% — верное утверждение (вспомните импликацию, из истины следует истина).
Антисимметричное бинарное отношение
Бинарное отношение %%R%% на множестве %%M%% называется антисимметричным , если для любых элементов %%a, b%% из %%M%%, из условий %%a~R~b%% и %%b~R~a%% следует условие %%a = b%%.
$$ \begin{array}{l} \forall a,b,c\in M~~a~R~b \land b~R~a \rightarrow a = b \text{ или}\\ \forall a,b\in M~~(a,b) \in R \land (b,a) \in R \rightarrow a = b. \end{array} $$
Пример
Отношение больше или равно на множестве действительных чисел антисимметрично . Действительно, если %%a \geq b%% и %%b \geq a%%, %%a = b%%.
Эквивалентное бинарное отношение
эквивалентности , если оно рефлексивно , симметрично и транзитивно .
Нетрудно проверить, что отношение параллельности на множестве прямых плоскости является отношением эквивалентности.
Отношение частичного порядка
Бинарное отношение %%R%% на множестве %%M%% называется отношением частичного порядка , если оно рефлексивно , антисимметрично и транзитивно .
Отношение больше или равно на множестве действительных чисел является отношением частичного порядка.
Построение отрицаний
Пусть %%R%% — бинарное отношение на множестве %%M%%, и %%P%% — одно из следующих условий:
- отношение %%R%% рефлексивно,
- отношение %%R%% симметрично,
- отношение %%R%% транзитивно,
- отношение %%R%% антисимметрично.
Построим для каждого из них отрицание выполнения условия %%P%%.
Отрицание рефлексивности
По определению %%R%% рефлексивно, если каждый элемент множества %%M%% находится в отношении %%R%% к самому себе, то есть %%\forall a \in M~~a~R~a%%. Тогда рассмотрим отрицание рефлексивности как истинное высказывание %%\overline{\forall a \in M~~a~R~a}%%. Используем равносильность %%\overline{\forall x P(x)} \equiv \exists x \overline {P(x)}%%. В нашем случае получаем %%\forall a \in M~~a~R~a \equiv \exists a\in M~~a~\not\text{R }~a%%, что и нужно.
Аналогично получаем и остальные отрицания. В итоге получаем следующие утверждения:
%%R%% не рефлексивно тогда и только тогда, когда
$$ \exists a \in M~~a~\not R~a $$
%%R%% не симметрично тогда и только тогда, когда
$$ \exists a, b \in M~~ a~R~b \land b~\not R~a $$
%%R%% не транзитивно тогда и только тогда, когда
$$ \exists a, b, c \in M a~R~b \land b~R~c \land a~\not R~c $$
%%R%% не антисимметрично тогда и только тогда, когда
$$ \exists a, b \in M~~ a~R~b \land b~R~a \land a \neq b. $$
Лекция 3.
п.3. Отношения на множествах. Свойства бинарных отношений.
3.1. Бинарные отношения .
Когда говорят о родстве двух людей, например, Сергей и Анна, то подразумевают, что есть некая семья, к членам которой они относятся. Упорядоченная пара (Сергей, Анна) отличается от других упорядоченных пар людей тем, что между Сергеем и Анной есть некое родство (кузина, отец и т. д.).
В математике среди всех упорядоченных пар прямого произведения двух множеств A и B (A ´B ) тоже выделяются «особые» пары в связи с тем, что между их компонентами есть некоторые «родственные» отношения, которых нет у других. В качестве примера рассмотрим множество S студентов какого-нибудь университета и множество K читаемых там курсов. В прямом произведении S ´K можно выделить большое подмножество упорядоченных пар (s , k ), обладающих свойством: студент s слушает курс k . Построенное подмножество отражает отношение «… слушает …», естественно возникающее между множествами студентов и курсов.
Для строгого математического описания любых связей между элементами двух множеств введем понятие бинарного отношения.
Определение 3.1. Бинарным (или двухместным ) отношением r между множествами A и B называется произвольное подмножество A ´B , т. е.
В частности, если A= B (то есть rÍA 2), то говорят, что r есть отношение на множестве A.
Элементы a и b называются компонентами (или координатами ) отношения r.
Замечание. Договоримся, что для обозначения отношений между элементами множеств использовать греческий алфавит : r, t, j, s, w и т. д.
Определение 3.2. Областью определения D r={a | $ b , что a rb } (левая часть). Областью значений бинарного отношения r называется множество R r={b | $ a , что a rb } (правая часть).
Пример 3. 1. Пусть даны два множества A ={1; 3; 5; 7} и B ={2; 4; 6}. Отношение зададим следующим образом t={(x ; y )ÎA ´B | x+ y =9}. Это отношение будет состоять из следующих пар (3; 6), (5; 4) и (7; 2), которые можно записать в виде t={(3; 6), (5; 4), (7;2)}. В данном примере D t={3; 5; 7} и R t= B ={2; 4; 6}.
Пример 3. 2. Отношение равенства на множестве действительных чисел есть множество r={(x ; y ) | x и y – действительные числа и x равно y }. Для этого отношения существует специальное обозначение «=». Область определения совпадает с областью значений и является множеством действительных чисел, D r= R r.
Пример 3. 3. Пусть A – множество товаров в магазине, а B – множество действительных чисел. Тогда j={(x ; y )ÎA ´B | y – цена x } – отношение множеств A и B .
Если обратить внимание на пример 3.1., то можно заметить, что данное отношение было задано сначала в виде t={(x ; y )ÎA ´B | x+ y =9}, а потом записано в виде t={(3; 6), (5;4), (7;2)}. Это говорит о том, что отношения на множествах (или одном множестве) можно задавать различными способами. Рассмотрим способы задания бинарных отношений.
Способы задания отношений:
1) с помощью подходящего предиката;
2) множество упорядоченных пар;
3) в графической форме: пусть A и B – два конечных множества и r – бинарное отношение между ними. Элементы этих множеств изображаем точками на плоскости. Для каждой упорядоченной пары отношения r рисуют стрелку, соединяющую точки, представляющие компоненты пары. Такой объект называется ориентированным графом или орграфом , точки же, изображающие элементы множеств, принято называть вершинами графа .
4) в виде матрицы: пусть A ={a 1, a 2, …, an } и B ={b 1, b 2, …, bm }, r – отношение на A ´B . Матричным представлением r называется матрица M =[mij ] размера n ´m , определенная соотношениями
.
Кстати, матричное представление является представлением отношения в компьютере.
Пример 3. 4. Пусть даны два множества A ={1; 3; 5; 7}и B ={2; 4; 6}. Отношение задано следующим образом t={(x ; y ) | x+ y =9}. Задать данное отношение как множество упорядоченных пар, орграфом, в виде матрицы.
Решение. 1) t={(3; 6), (5; 4), (7; 2)} - есть задание отношения как множества упорядоченных пар;
2) соответствующий ориентированный граф показан на рисунке.
https://pandia.ru/text/78/250/images/image004_92.gif" width="125" height="117">. ,
Пример 3. 5 . Еще в качестве примера можно рассмотреть предложенную Дж. фон Нейманом (1903 – 1957) блок-схему ЭВМ последовательного действия, которая состоит из множества устройств M :
,
где a – устройство ввода, b – арифметическое устройство (процессор), c – устройство управления, d – запоминающее устройство, e – устройство вывода.
Рассмотрим информационный обмен между устройствами mi и mj , которые находятся в отношении r, если из устройства mi поступает информация в устройство mj .
Это бинарное отношение можно задать перечислением всех его 14 упорядоченных пар элементов:
Соответствующий орграф, задающий это бинарное отношение, представлен на рисунке:
Матричное представление этого бинарного отношения имеет вид:
. ,
Для бинарных отношений обычным образом определены теоретико-множественные операции: объединение, пересечение и т. д.
Введем обобщенное понятие отношения.
Определение 3.3. n-местное (n -арное ) отношение r – это подмножество прямого произведения n множеств, то есть множество упорядоченных наборов (кортежей )
rÍA 1´…´An ={(a 1, …, an )| a 1ÎA 1Ù … Ùan ÎAn }
Многоместные отношения удобно задавать с помощью реляционных таблиц . Такое задание соответствует перечислению множества n -к отношения r. Реляционные таблицы широко используются в компьютерной практике в реляционных базах данных . Заметим, что реляционные таблицы нашли применение в повседневной практике. Всевозможные производственные, финансовые, научные и другие отчеты часто имеют форму реляционных таблиц.
Слово «реляционная » происходит от латинского слова relation , которое в переводе на русский язык означает «отношение». Поэтому в литературе для обозначения отношения используют букву R (латинскую) или r (греческую).
Определение 3.4. Пусть rÍA ´B есть отношение на A ´B. Тогда отношение r-1 называется обратным отношением к данному отношению r на A ´B , которое определяется следующим образом:
r-1={(b , a ) | (a , b )Îr}.
Определение 3.5. Пусть r ÍA ´B есть отношение на A ´B, а s ÍB ´C – отношение на B ´C. Композицией отношений s и r называется отношение t ÍA ´C ,которое определяется следующим образом:
t=s◦r= {(a , c )| $ b Î B, что (a , b )Îr и (b , c )Îs}.
Пример 3. 6 . Пусть , и C ={, !, d, à}. И пусть отношение r на A ´B и отношение s на B ´C заданы в виде:
r={(1, x ), (1, y ), (3, x )};
s={(x ,), (x , !), (y , d), (y , à)}.
Найти r-1 и s◦r, r◦s.
Решение. 1) По определению r-1={(x , 1), (y , 1), (x , 3)};
2) Используя определение композиции двух отношений, получаем
s◦r={(1,), (1, !), (1, d), (1, à), (3,), (3, !)},
поскольку из (1, x )Îr и (x ,)Îs следует (1,)Îs◦r;
из (1, x )Îr и (x , !)Îs следует (1, !)Îs◦r;
из (1, y )Îr и (y , d)Îs следует (1, d)Îs◦r;
из (3, x )Îr и (x , !)Îs следует (3, !)Îs◦r.
Теорема 3.1. Для любых бинарных отношений выполняются следующие свойства:
2) ;
3) - ассоциативность композиции.
Доказательство. Свойство 1 очевидно.
Докажем свойство 2. Для доказательства второго свойства покажем, что множества, записанные в левой и правой частях равенства, состоят из одних и тех же элементов. Пусть (a ; b ) Î (s◦r)-1 Û (b ; a ) Î s◦r Û $ c такое, что (b ; c ) Î r и (c ; a ) Î s Û $ c такое, что (c ; b ) Î r-1 и (a ; c ) Î s-1 Û (a ; b ) Î r -1◦s -1.
Свойство 3 доказать самостоятельно.
3.2. Свойства бинарных отношений .
Рассмотрим специальные свойства бинарных отношений на множестве A .
Свойства бинарных отношений.
1. Отношение r на A ´A называется рефлексивным , если (a ,a ) принадлежит r для всех a из A .
2. Отношение r называется антирефлексивным , если из (a ,b )Îr следует a ¹b .
3. Отношение r симметрично , если для a и b , принадлежащих A , из (a ,b )Îr следует, что (b ,a )Îr.
4. Отношение r называется антисимметричным , если для a и b из A , из принадлежности (a ,b ) и (b ,a ) отношению r следует, что a =b .
5. Отношение r транзитивно , если для a , b и c из A из того, что (a ,b )Îr и (b ,c )Îr, следует, что (a ,c )Îr.
Пример 3. 7. Пусть A ={1; 2; 3; 4; 5; 6}. На этом множестве задано отношение rÍA 2, которое имеет вид: r={(1, 1), (2, 2), (3, 3), (4; 4), (5; 5), (6; 6), (1; 2), (1; 4), (2; 1), (2;4), (3;5), (5; 3), (4; 1), (4; 2)}. Какими свойствами обладает данное отношение?
Решение. 1) Это отношение рефлексивно, так как для каждого a ÎA , (a ; a )Îr.
2) Отношение не является антирефлексивным, так как не выполняется условие этого свойства. Например, (2, 2)Îr, но отсюда не следует, что 2¹2.
3) Рассмотрим все возможные случаи, показав, что отношение r является симметричным:
(a , b )Îr | (b , a ) | (b , a )Îr? |
|
4) Данное отношение не является антисимметричным, поскольку (1, 2)Îr и (2,1)Îr, но отсюда не следует, что 1=2.
5) Можно показать, что отношение r транзитивно, используя метод прямого перебора.
(a , b )Îr | (b , c )Îr | (a , c ) | (a , c )Îr? |
|
Как по матрице представления
определить свойства бинарного отношения
1. Рефлексивность: на главной диагонали стоят все единицы, звездочками обозначены нули или единицы.
.
2. Антирефлексивность: на главной диагонали все нули.
3. Симметричность: если .
4. Антисимметричность: все элементы вне главной диагонали равны нулю; на главной диагонали тоже могут быть нули.
.
Операция «*» выполняется по следующему правилу: , где , .
5. Транзитивность: если . Операция «◦» выполняется по обычному правилу умножения, при этом надо учитывать: .
3.3 Отношение эквивалентности. Отношение частичного порядка.
Отношение эквивалентности является формализацией такой ситуации, когда говорят о сходстве (одинаковости) двух элементов множества.
Определение 3.6. Отношение r на A есть отношение эквивалентности , если оно рефлексивно, симметрично и транзитивно. Отношение эквивалентности a rb часто обозначается: a ~ b .
Пример 3. 8 . Отношение равенства на множестве целых чисел есть отношение эквивалентности.
Пример 3. 9 . Отношение «одного роста» есть отношение эквивалентности на множестве людей X .
Пример 3. 1 0 . Пусть ¢ - множество целых чисел. Назовем два числа x и y из ¢ сравнимыми по модулю m (m Î¥) и запишем , если равны остатки этих чисел от деления их на m , т. е. разность (x -y ) делится на m .
Отношение «сравнимых по модулю m целых чисел» есть отношение эквивалентности на множестве целых числе ¢. В самом деле:
это отношение рефлексивно, т. к. для "x ΢ имеем x -x =0, и, следовательно, оно делится на m ;
это отношение симметрично, т. к. если (x -y ) делится на m , то и (y -x ) тоже делится на m ;
это отношение транзитивно, т. к. если (x -y ) делится на m , то для некоторого целого t 1 имеем https://pandia.ru/text/78/250/images/image025_23.gif" width="73" height="24 src=">, отсюда , т. е. (x -z ) делится на m .
Определение 3.7. Отношение r на A есть отношение частичного порядка , если оно рефлексивно, антисимметрично и транзитивно и обозначается символом °.
Частичный порядок важен в тех ситуациях, когда мы хотим как-то охарактеризовать старшинство. Иными словами, решить при каких условиях считать, что один элемент множества превосходит другой.
Пример 3. 11 . Отношение x £y на множестве действительных чисел есть отношение частичного порядка. ,
Пример 3. 1 2 . Во множестве подмножеств некоторого универсального множества U отношение A ÍB есть отношение частичного порядка.
Пример 3. 1 3 . Схема организации подчинения в учреждении есть отношение частичного порядка на множестве должностей.
Прообразом отношения частичного порядка является интуитивное понятие отношения предпочтения (предшествования). Отношение предпочтения выделяет класс задач, которые можно объединить, как задача о проблеме выбора наилучшего объекта .
Формулировка задачи: пусть имеется совокупность объектов A и требуется сравнить их по предпочтительности, т. е. задать отношение предпочтения на множестве A и определить наилучшие объекты.
Отношение предпочтения P , которое можно определить как «aPb , a , b ÎA Û объект a не менее предпочтителен, чем объект b » является по смыслу рефлексивным и антисимметричным (каждый объект не хуже самого себя, и, если объект a не хуже b и b не хуже a , то они одинаковы по предпочтительности). Естественно считать, что отношение P транзитивно (хотя в случае, когда, например, предпочтения обсуждаются группой лиц с противоположными интересами, это свойство может быть нарушено), т. е. P – отношение частичного порядка.
Один из возможных способов решения задачи сравнения объектов по предпочтительности – ранжирование , т. е. упорядочение объектов в соответствии с убыванием их предпочтительности или равноценности. В результате ранжирования мы выделяем «наилучшие» или «наихудшие» с точки зрения отношения предпочтения объекты.
Области применения задачи о проблеме выбора наилучшего объекта: теория принятия решений, прикладная математика, техника, экономика, социология, психология.
Пусть A - множество. Если задано некоторое подмножество его декартового квадрата, другими словами, задано некоторое подмножество упорядоченных пар , где , то говорят, что на множестве A задано бинарное отношение R . Пишут или .В качестве примеров бинарных отношений на числовых множествах можно рассмотреть хорошо известные из арифметики отношения: ,=”,<”,£”,>”,³”.
Бинарное отношение называется:
Рефлексивным, если для любого
Иррефлексивным, если для любого ;
Симметричным, если из следует ;
Антисимметричным, если и следует a=b ;
Транзитивным, если из и следует ;
Отношение,=” рефлексивно, симметрично и транзитивное, отношения,<” и,>” транзитивны и иррефлексивны, отношения,£” и,³”. рефлексивны, антисимметричны и транзитивны. Последние свойства выбираются в качестве определяющих для отношения частичного порядка на множестве A .
Определение. Бинарное отношение R на множестве A называется отношением частичного порядка, если оно рефлексивно, антисимметрично и транзитивно,
Если , то будем считать элемент a предшествующим элементу b и записывать отношение aRb в виде . Если для любых двух элементов имеет место хотя бы одно из отношений или , то частичный порядок называется полным или линейным порядком.
Примером частичного порядка является система множеств, упорядоченных по включению: . Числовые множества с обычным отношением, £” дают примеры линейных порядков.
Обобщением понятия равенства является отношение эквивалентности.
Определение . Бинарное отношение R на множестве A называется отношением эквивалентности, если оно рефлексивно, симметрично и транзитивно.
Отношение эквивалентности разбивает множество A на непересекающиеся подмножества, называемые классами эквивалентности. Если в качестве A рассмотреть множество людей, проживающих в домах некоторого города, то отношение проживания в одном доме будет отношением эквивалентности. Более математическим примером является отношение сравнения по модулю n в множестве целых чисел Z : , если делится на n . При этом Z разбивается на классы , характеризуемые остатками от деления на n . Более общим примером является эквивалентность элементов группы G по подгруппе H : если . Классами эквивалентности здесь являются правые смежные классы по подгруппе H .
Широкий спектр отношений на примере множеств сопровождается большим числом понятий, начиная с их определений и заканчивая аналитическим разбором парадоксов. Разнообразие обсуждаемого в статье понятия на множестве бесконечно. Хотя, когда говорят про двойственные типы, под этим подразумеваются бинарные отношения между несколькими величинами. А также между объектами или высказываниями.
Как правило, бинарные отношения обозначаются символом R, то есть, если xRx для любого значения x из поля R, такое свойство называют рефлексивным, в котором x и х - это принятые объекты мысли, а R служит знаком о том или ином виде взаимосвязи между индивидами. В то же время если выражать xRy® или yRx, то это говорит о состоянии симметрии, где ® - знак импликации, похожий на союз «если..., то...". И, наконец, расшифровка надписи (xRy Ùy Rz) ®xRz расскажет о транзитивной взаимосвязи, причём знак Ù - это конъюнкция.
Бинарное отношение, которое бывает одновременно рефлексивным, симметричным и транзитивным, именуется взаимосвязью эквивалентности. Отношение f - это функция, и из <х, у> Î f и <х, z> Î f вытекает равность y=z. Простая бинарная функция может быть легко применима к двум несложным аргументам, расположенным в определённом порядке, и лишь в данном случае она предоставляет ей значение, направленное этим двум выражениям, взятым в конкретном случае.
Следует говорить, что f отображает x на y,
если f служит функцией с зоной определения x и зоной значений y. Однако когда f экстраполирует x на y, и y Í z, то это приводит к тому, что f показывает x в z. Простой пример: если f(x)=2x справедливо для достоверно любого целого х, то говорят, что f отображает знаковое множество всех известных целых чисел во множество тех же целых, но на этот раз чётных чисел. Как уже упоминалось выше, бинарные отношения, которые одновременно рефлексивны, симметричны и транзитивны, являются взаимосвязями эквивалентности.
Исходя из вышесказанного, взаимосвязи эквивалентности бинарных отношений определяются свойствами:
- рефлексивности - соотношение (M ~ N);
- симметричности - если равность M ~ N, то будет N ~ M;
- транзитивности - если две равности M ~ N и N ~ P, то в результате M ~ P.
Рассмотрим заявленные свойства бинарных отношений подробнее. Рефлексивность - это одна из характеристик некоторых связей, где каждый элемент исследуемого множества пребывает в данной равности сам себе. Например, между числами а=с и а³ с - рефлексивные связи, поскольку всегда а=а, с=с, а³ а, с³ с. В то же время отношение неравенства а>с - антирефлексивно из-за невозможности существования неравенства а>а. Аксиома этого свойства кодируется знаками: aRc® aRa Ù cRc , здесь символ ® означает слово "влечёт" (или "имплицирует"), а знак Ù - выступает союзом "и" (или конъюнкцией). Из этого утверждения следует, что в случае истинности суждения aRc также истинны и выражения aRa и cRc.
Симметричность влечёт за собой наличие отношения и в том случае, если мыслительные объекты поменять местами, то есть при симметричной взаимосвязи перестановка объектов не приводит к трансформации вида "бинарные отношения". Например, связь равенства а=с симметрична по причине эквивалентности отношения с=а; также одинаково и суждение а¹с, так как оно отвечает связи с¹а.
Транзитивное множество - это такое свойство, при котором выполняется следующее требование: у Î х, z Î y ® z Î x, где ® выступает знаком, заменяющим слова: "если..., то...". Вербально читается формула таким образом: «Если у зависит от х, z принадлежит у, то z также зависит от х".