Пример как решать бинарный множества транзитивность симметричность. Бинарное отношение
Рассмотрим отношение «уважать», определенное на множестве всех людей %%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. $$
Определение . Бинарным отношением R называется подмножество пар (a,b)∈R декартова произведения A×B, т. е. R⊆A×B . При этом множество A называют областью определения отношения R, множество B – областью значений.
Обозначение: aRb (т. е. a и b находятся в отношении R). /
Замечание : если A = B , то говорят, что R есть отношение на множестве A .
Способы задания бинарных отношений
1. Списком (перечислением пар), для которых это отношение выполняется.
2. Матрицей. Бинарному отношению R ∈ A × A , где A = (a 1 , a 2 ,..., a n), соответствует квадратная матрица порядка n , в которой элемент c ij , стоящий на пересечении i-й строки и j-го столбца, равен 1, если между a i и a j имеет место отношение R , или 0, если оно отсутствует:
Свойства отношений
Пусть R – отношение на множестве A, R ∈ A×A . Тогда отношение R:
рефлексивно, если Ɐ a ∈ A: a R a (главная диагональ матрицы рефлексивного отношения содержит только единицы);
антирефлексивно, если Ɐ a ∈ A: a R a (главная диагональ матрицы рефле сивного отношения содержит только нули);
симметрично, если Ɐ a , b ∈ A: a R b ⇒ b R a (матрица такого отношения симметрична относительно главной диагонали, т.е. c ij c ji);
антисимметрично, если Ɐ a, b ∈ A: a R b & b R a ⇒ a = b (в матрице такого отношения отсутствуют единицы, симметричные относительно главной диагонали);
транзитивно, если Ɐ a, b, c ∈ A: a R b & b R c ⇒ a R c (в матрице такого отношения должно выполняться условие: если в i-й строке стоит единица, например в j-ой координате (столбце) строки, т. е. c ij = 1 , то всем единицам в j-ой строке (пусть этим единицам соответствуют k е координаты такие, что, c jk = 1) должны соответствовать единицы в i-й строке в тех же k-х координатах, т. е. c ik = 1 (и, может быть, ещё и в других координатах).
Задача 3.1. Определите свойства отношения R – «быть делителем», заданного на множестве натуральных чисел.
Решение.
отношение R = {(a,b):a делитель b}:
рефлексивно, не антирефлексивно, так как любое число делит само себя без остатка: a/a = 1 для всех a∈N ;
не симметрично, антисимметрично, например, 2 делитель 4, но 4 не является делителем 2;
транзитивно,таккакесли b/a ∈ N и c/b ∈ N, то c/a = b/a ⋅ c/b ∈ N, например, если 6/3 = 2∈N и 18/6 = 3∈N, то 18/3 = 18/6⋅6/3 = 6∈N.
Задача 3.2.
Определите свойства отношения R – «быть братом», заданного на множестве людей.
Решение.
Отношение R = {(a,b):a - брат b}:
не рефлексивно, антирефлексивно из-за очевидного отсутствия aRa для всех a;
не симметрично, так как в общем случае между братом a и сестрой b имеет место aRb , но не bRa ;
не антисимметрично, так как если a и b –братья, то aRb и bRa, но a≠b;
транзитивно, если называть братьями людей, имеющих общих родителей (отца и мать).
Задача 3.3. Определите свойства отношения R – «быть начальником», заданного на множестве элементов структуры
Решение.
Отношение R = {(a,b) : a - начальник b}:
- не рефлексивно, антирефлексивно, если в конкретной интерпретации не имеет смысла;
- не симметрично, антисимметрично, так как для всех a≠b не выполняется одновременно aRb и bRa;
- транзитивно, так как если a начальник b и b начальник c , то a начальник c .
Определите свойства отношения R i , заданного на множестве M i матрицей, если:
- R 1 «иметь один и тот же остаток от деления на 5»; M 1 множество натуральных чисел.
- R 2 «быть равным»; M 2 множество натуральных чисел.
- R 3 «жить в одном городе»; M 3 множество людей.
- R 4 «быть знакомым»; M 4 множество людей.
- R 5 {(a,b):(a-b) - чётное; M 5 множество чисел {1,2,3,4,5,6,7,8,9}.
- R 6 {(a,b):(a+b) - чётное; M 6 множество чисел {1,2,3,4,5,6,7,8,9}.
- R 7 {(a,b):(a+1) - делитель (a+b)} ; M 7 - множество {1,2,3,4,5,6,7,8,9}.
- R 8 {(a,b):a - делитель (a+b),a≠1}; M 8 - множество натуральных чисел.
- R 9 «быть сестрой»; M 9 - множество людей.
- R 10 «быть дочерью»; M 10 - множество людей.
Операции над бинарными отношениями
Пусть R 1 , R 1 есть отношения, заданные на множестве A .
объединение R 1 ∪ R 2: R 1 ∪ R 2 = {(a,b) : (a,b) ∈ R 1 или (a,b) ∈ R 2 } ;
пересечение R 1 ∩ R 2: R 1 ∩ R 2 = {(a,b) : (a,b) ∈ R 1 и (a,b) ∈ R 2 } ;
разность R 1 \ R 2: R 1 \ R 2 = {(a,b) : (a,b) ∈ R 1 и (a,b) ∉ R 2 } ;
универсальное отношение U: = {(a;b)/a ∈ A & b ∈ A}. ;
дополнение R 1 U \ R 1 , где U = A × A;
тождественное отношение I: = {(a;a) / a ∈ A};
обратное отношение R -11 : R -11 = {(a,b) : (b,a) ∈ R 1 };
композиция R 1 º R 2: R 1 º R 2: = {(a,b) / a ∈ A&b ∈ B& ∃ c ∈ C: aR 1 c & c R 2 b}, где R 1 ⊂ A × C и R 2 ⊂ C × B;
Определение. Степенью отношения R на множестве A называется его композиция с самим собой.
Обозначение: 
Определение . Если R ⊂ A × B , то R º R -1 называется ядром отношения R .
Теорема 3.1. Пусть R ⊂ A × A – отношение, заданное на множестве A .
- R рефлексивно тогда и только тогда, (далее используется знак ⇔) когда I ⊂ R.
- R симметрично ⇔ R = R -1 .
- R транзитивно ⇔ R º R ⊂ R
- R антисимметрично ⇔ R ⌒ R -1 ⊂ I .
- R антирефлексивно ⇔ R ⌒ I = ∅ .
Задача 3.4 . Пусть R - отношение между множествами {1,2,3} и {1,2,3,4}, заданное перечислением пар: R = {(1,1), (2,3), (2,4), (3,1), (3,4)}. Кроме того, S - отношение между множествами S = {(1,1), (1,2), (2,1), (3,1), (4,2)}. Вычислите R -1 , S -1 и S º R. Проверьте, что (S º R) -1 = R -1 , S -1 .
Решение.
R -1 = {(1,1), (1,3), (3,2), (4,2), (4,3)};
S -1 = {(1,1), (1,2), (1,3), (2,1), (2,4)};
S º R = {(1,1), (1,2), (2,1), (2,2), (3,1), (3,2)};
(S º R) -1 = {(1,1), (1,2), (1,3), (2,1), (2,2), (2,3)};
R -1 º S -1 = {(1,1), (1,2), (1,3), (2 ,1), (2,2), (2,3)} = (S º R) -1 .
Задача 3.5 . Пусть R отношение «...родитель...», а S отношение «...брат...» на множестве всех людей. Дайте краткое словесное описание отношениям:
R -1 , S -1 , R º S, S -1 º R -1 и R º R.
Решение.
R -1 - отношение«...ребёнок...»;
S -1 - отношение«...брат или сестра...»;
R º S - отношение «...родитель...»;
S -1 º R -1 - отношение «...ребёнок...»
R º R - отношение «...бабушка или дедушка...»
Задачи для самостоятельного решения
1) Пусть R - отношение «...отец...», а S - отношение «...сестра...» на множестве всех людей. Дайте словесное описание отношениям:
R -1 , S -1 , R º S, S -1 º R -1 , R º R.
2) Пусть R - отношение «...брат...», а S - отношение «...мать...» на множестве всех людей. Дайте словесное описание отношениям:
R -1 , S -1 , S º R, R -1 º S -1 , S º S.
3) Пусть R - отношение «...дед...», а S - отношение «...сын...» на множестве всех людей. Дайте словесное описание отношениям:
4) Пусть R - отношение «...дочь...», а S - отношение «...бабушка...» на множе- стве всех людей. Дайте словесное описание отношениям:
5) Пусть R - отношение «...племянница...», а S - отношение «...отец...» на множестве всех людей. Дайте словесное описание отношениям:
R -1 , S -1 , S º R, R -1 º S -1 , R º R.
6) Пусть R - отношение «сестра...», а S - отношение «мать...» на множестве всех людей. Дайте словесное описание отношениям:
R -1 , S -1 , R º S, S -1 º R -1 , S º S.
7) Пусть R - отношение «...мать...», а S - отношение «...сестра...» на множе- стве всех людей. Дайте словесное описание отношениям:
R -1 , S1, R º S, S1 º R1, S º S.
8) Пусть R - отношение «...сын...», а S - отношение «...дед...» на множестве всех людей. Дайте словесное описание отношениям:
R -1 , S -1 , S º R, R -1 º S -1 , R º R.
9) Пусть R - отношение «...сестра...», а S - отношение «...отец...» на множе- стве всех людей. Дайте словесное описание отношениям:
R -1 , S -1 , R º S, S -1 º R -1 , S º S.
10) Пусть R - отношение «...мать...», а S - отношение «...брат...» на множестве всех людей. Дайте словесное описание отношениям:
R -1 , S -1 , S º R, R -1 º S -1 , R º R.
Пусть 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 также зависит от х".
Бинарные отношения.
Пусть A и B – произвольные множества.
Возьмем по одному элементу из каждого множества, a из A, b из B и
запишем их так:
Декартовым
произведением
произвольных множеств A и B (обозначается: AB)
называется множество, состоящее из всех возможных упорядоченных пар, первый
элемент которых принадлежит A, а второй принадлежит B. По определению: AB = {
Пример 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 является отношением эквивалентности и частичного порядка. Отношение параллельности на множестве прямых является отношением эквивалентности.
