13. Бинарные отношения

---

ВПЕРЁД ⇒

Отношение тождества

⇐ НАЗАД

Формы записи математических операций

---

Бинарные отношения

Определение бинарного отношения

Бинарное (двуместное) отношение на множестве $X$ - любое подмножество множества $X^2$, то есть любое множество упорядоченных пар (двоек), состоящих из элементов $X$.

Обозначение для бинарного отношения

Будем обозначать любое бинарное отношение через $R$ (запоминается легко, как первая буква в слове "relation", которое и переводится как "отношение"). Таким образом, $R$ - бинарное отношение на множестве $X$. Факт того, что упорядоченная пара $⟨y,z⟩$ является элементом бинарного отношения $R$, будем записывать в виде выражения "$⟨y,z⟩\in R$".

Формы записи бинарных отношений

Классическая форма записи бинарных отношений

В классическом виде бинарное отношение записывается как ”$⟨y,z⟩\in R$, $y\in X$, $z\in X$“.

Например, если нас интересует отношение $R$ вида “число слева меньше числа справа”, то мы можем его записать в виде ”$⟨y,z⟩\in <$, $y\in X$, $z\in X$“

Инфиксная форма записи бинарных отношений

Часто отношения записывают в инфиксной форме, то есть в виде ”$yRz$, $y\in X$, $z\in X$“. Это делается с целью упрощения восприятия отношений. Например, если нас интересует отношение $R$ вида “число слева меньше числа справа”, то обычно мы не пишем ”$⟨y,z⟩\in <$, $y\in X$, $z\in X$”, в противоположность этому мы пишем более лаконично: ”$y<z$, $y\in X$, $z\in X$“.

Область определения бинарного отношения

Областью определения бинарного отношения $R$ на множестве $X$ называется множество всех $y\in X$ таких, что $⟨y,z⟩\in R$ хотя бы для какого-нибудь одного $z\in X$. Это можно представить как перебор всех $y\in X$, где для каждого $y$ проверяется существование хотя бы какого-нибудь одного $z\in X$ такого, что $⟨y,z⟩\in R$. Если искомый $z$ существует, то текущий $y$ помещается в целевое множество области определения и перебор продолжается дальше. Здесь стоит сделать упрощение и провести аналогию с функциями, изучаемыми в рамках школьной программы по математике. Позже мы покажем, что функции, которые изучались в рамках школьной программы, на самом деле являются частным случаем более обобщённого определения понятия функции, тесно связанного с понятием отношения. Но это будет чуть позже, а пока дадим пояснение на уровне аналогий из школьной программы. Пусть имеются некоторые переменная $x$ и функция $y=f(x)$. Тогда мы можем переписать наличие подобной функции (подобного отношения) в виде "$⟨x,y⟩\in f$", и это будет означать, что переменные $x$ и $y$ связаны между собой отношением $f$. Также из школьной программы мы уже знаем, что переменная $x$ определена на некоторой области определения, в то время как переменная $y$ определена на некоторой области значений. Таким образом, понятие области определения бинарного отношения $R$ на множестве $X$ является обобщением частного случая понятия области определения аргумента $x$ функции $y=f(x)$.

Множество значений бинарного отношения

Множеством значений бинарного отношения $R$ на множестве $X$ называется множество всех $z\in X$ таких, что $⟨y,z⟩\in R$ хотя бы для какого-нибудь одного $y\in X$. Это можно представить как перебор всех $z\in X$, где для каждого $z$ проверяется существование хотя бы какого-нибудь одного $y\in X$ такого, что $⟨y,z⟩\in R$. Если искомый $y$ существует, то текущий $z$ помещается в целевое множество значений и перебор продолжается дальше. Согласно всё той же аналогии для функций из школьной программы, понятие множества значений бинарного отношения $R$ на множестве $X$ является обобщением частного случая понятия области значений функции $y=f(x)$.

Поле бинарного отношения

Наконец, объединение области определения бинарного отношения $R$ на множестве $X$ и множества значений бинарного отношения $R$ на множестве $X$ называется полем бинарного отношения $R$ на множестве $X$.

Переход от отношений на множестве к отношениям между множествами

Отметим, что в бинарном отношении и область определения бинарного отношения, и множество значений бинарного отношения являются подмножествами множества $X$. То есть про бинарное (да и вообще, про любое $n$-местное) отношение $R$ на множестве $X$ можно говорить как об отношении между множествами, являющимися подмножествами множества $X$. Иными словами, мы можем говорить не “отношение на множестве $X$”, а “отношение между подмножествами множества $X$“.

Пример

Предположим, что у нас имеется множество $X$, являющееся объединением множеств $M$ и $Y$ ($X=M\cup Y$), причём множество $M$ является $n$-кратным декартовым произведением множества $Z$ на себя ($M=Z^n$). Пусть имеется некоторое бинарное отношение $P$ на множестве $X$, областью определения которого является подмножество $M$ множества $X$, а множеством значений которого является подмножество $Y$ множества $X$. Тогда отношение $P$ можно записать в следующем виде:

$⟨a,b⟩\in P$, $a\in M\subseteq X$, $b\in Y\subseteq X$;

$⟨a,b⟩\in P$, $a\in Z^n\subseteq X$, $b\in Y\subseteq X$;

$⟨a,b⟩\in P$, $a\in Z^n$, $b\in Y$.

В приведённом примере мы перешли от рассмотрения отношения $P$ на множестве $X$ к рассмотрению отношения $P$ между множествами $Z^n$ и $Y$.

Обратное отношение

В школе, имея некоторое уравнение (функцию) $у=f(x)$, мы могли путем преобразований свести это уравнение к уравнению (функции) $x=g(y)$, где функция $g(y)$ являлась обратной функцией для функции $f(x)$. Понятие обратной функции, изучаемое в рамках школьной программы по математике, также является частным случаем более обобщённого определения понятия обратной функции, тесно связанного с понятием обратного отношения.

Отношение $R^{-1}$, обратное к $R$, определяется как множество всех упорядоченных пар $⟨y,z⟩$ таких, что $⟨z,y⟩\in R$. Иначе говоря, у нас имеется отношение $⟨z,y⟩\in R$, и из него (путём преобразований) мы получаем отношение $⟨y,z⟩\in R^{-1}$, которое нами называется обратным (к $R$) отношением.

Представленные выше аналогии в виде функций (из школьной программы математики) даются только для упрощения понимания смысла отношений на множествах, ведь в действительности, как показано в описании отношений с n аргументами на множестве, в качестве отношений могут выступать не только функции в их школьном понимании. Например, в качестве примера мы можем рассмотреть отношение “меньше” для любых неотрицательных целых чисел: $y<z$.

Более точным определением отношения “меньше” для любых неотрицательных целых чисел является: $⟨y,z⟩\in <$, $y\in X$, $z\in X$. Областью определения отношения $<$ на множестве $X$ всех неотрицательных целых чисел является само множество $X$. Множеством значений отношения $<$ на множестве $X$ всех неотрицательных целых чисел является множество $X-⟨0⟩$ (не путать множество $⟨0⟩$ с пустым множеством $0$, $⟨0⟩$ означает множество, состоящее из одного элемента - числа $0$), то есть относительное дополнение множеств $X$ и $⟨0⟩$ (разность указанных множеств). Почему это так? Область определения в отношении $<$ связана с элементом $y$, а множество значений - с элементом $z$. Минимальное значение, которое может принимать элемент $y$, равно 0, а минимальное значение, которое может принимать элемент $z$, равно 1, так как в противном случае (при $z=0$) отношение никогда не будет выполняться (это очевидно, если рассмотреть утверждение $0<0$). Если $<$ - это отношение $R$, то обратным ему отношением ($R^{-1}$) является отношение $>$. Преобразовывая выражение "$x<y$" к "$y>x$", мы всё ещё сохраняем корректность самого исходного отношения $⟨y,z⟩\in <$, $y\in X$, $z\in X$.

Основные характериситки бинарных отношений

Отношение $R$ характеризуется не только лишь наличием для него обратного отношения $R^{-1}$. Например, может быть нам интересно знать, сохранится ли отношение, если в нём поменять местами аргументы. Или, быть может, нас интересует, возможно ли один и тот же элемент множества подставить сразу во все аргументы отношения. Для возможности получения ответов на подобные вопросы в рассмотрение вводятся дополнительные характеристики отношений.

Рефлексивность бинарного отношения

Рассмотрим отношение $=$. Что мы можем сказать про это отношение? Оно выполняется для любого элемента множества, подставленного в оба аргумента данного отношения, то есть $⟨z,z⟩\in =$, $z\in X$. Таким образом, можно сказать, что для отношения $=$ (которое обозначим через $R$) выполняется следующее условие: $xRx$ для любого $x$ из поля отношения $R$.

Определение рефлексивности бинарного отношения

Говорят, что бинарное отношение $R$ является рефлексивным, если $xRx$ для любого $x$ из поля отношения $R$.

Таким образом, если в бинарном отношении на множестве $X$ любой элемент $x$ из множества $X$ находится в указанном бинарном отношении с самим с собой, то это означает, что подобное бинарное отношение является рефлексивным.

Симметричность бинарного отношения

Ещё из школьной программы мы знаем, что от перемены мест слагаемых сумма не меняется, то есть варианты суммирования $x+y$ и $y+x$ являются симметричными друг относительно друга.

Определение симметричности бинарного отношения

Говорят, что бинарное отношение $R$ является симметричным, если из $xRy$ следует $yRx$.

Транзитивность бинарного отношения

Снова рассмотрим отношение $=$. Мы знаем, что если $a=b$ и $b=c$, то из этого следует, что $a=c$.

Определение транзитивности бинарного отношения

Говорят, что бинарное отношение $R$ является транзитивным, если из $xRy$ и $yRz$ следует $xRz$.

Эквивалентность бинарного отношения

Определение эквивалентности бинарного отношения

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

Некоторые примеры бинарных отношений

Рассмотрим несколько примеров бинарных отношений и определим, являются ли эти отношения рефлексивными, симметричными, транзитивными или эквивалентными:

• Отношение $⩽$. Поскольку отношение $z⩽z$ выполняется для любого элемента множества $X$, то из этого следует, что отношение $⩽$ является рефлексивным. Также из $z⩽y$ и $y⩽c$ следует $z⩽c$, это означает, что отношение $⩽$ является транзитивным. Однако, мы не всегда можем поменять местами аргументы в этом отношении, например $5⩽10$ мы не можем превратить в $10⩽5$. Из этого следует, что отношение $⩽$ не является симметричным. Таким образом, получаем, что отношение $⩽$ является рефлексивным, транзитивным, но не симметричным.
• Отношение иметь по крайней мере одного общего родителя. В этом отношении двое людей сравниваются на предмет наличия хотя бы одного общего родителя. Сразу уточним, что люди в рассматриваемой паре не обязательно должны быть разными, допустимо сравнение человека с самим собой. Например, можно рассмотреть отношение “я” $R$ “я”, где $R$ - отношение вида иметь по крайней мере одного общего родителя. Мы точно можем сказать, что у обоих “я” в рассматриваемом отношении общим родителем является как папа, так и мама (если, конечно, таковые имеются, предположим, что это так, то есть будем рассматривать полные семьи). Поскольку отношение иметь по крайней мере одного общего родителя в этом случае выполняется, то можем заключить, что это отношение - рефлексивно. Также очевидно, что отношение “я” $R$ “мой брат” будет продолжать выполняться даже в том случае, если в этом отношении поменять местами аргументы (“мой брат” $R$ “я”), то есть это отношение симметрично. Также мы можем сказать, что из отношений “я” $R$ “мой сводный брат (по отцу)” и “мой сводный брат (по отцу)” $R$ “сводная сестра (по матери) моего сводного брата (по отцу)” не следует отношение “я” R “сводная сестра (по матери) моего сводного брата (по отцу)”, то есть это отношение нетранзитивно. Таким образом, можем сказать, что отношение иметь по крайней мере одного общего родителя является рефлексивным, симметричным, но не транзитивным.
• Отношение параллельности между прямыми в плоскости. Из параллельности прямой $a$ самой себе ($a||a$) следует рефлексивность отношения. Если прямая $a$ параллельна прямой $b$ ($a||b$), то, очевидно, что и прямая $b$ параллельна прямой $a$ ($b||a$). Получается, мы можем менять местами аргументы в этом отношении, тогда из этого следует, что данное отношение - симметричное. Если $a||b$ и $b||c$, то $a||c$, иначе говоря, рассматриваемое отношение также яляется транзитивным. Из всего перечисленного следует, что отношение параллельности между прямыми в плоскости представляет собой отношение эквивалентности.

---

ВПЕРЁД ⇒

Отношение тождества

⇐ НАЗАД

Формы записи математических операций

---

Источники

• Э. Мендельсон “Введение в математическую логику”. Глава 0 “Введение” (стр. 7-18).

Категория

Математическая-логика Математическая-логика

Теги

• Логика Логика
• Множество Множество
• Элемент-множества Элемент-множества
• Отношение Отношение
• Пара Пара
• Упорядоченная-пара Упорядоченная-пара
• Упорядоченная-n-ка Упорядоченная-n-ка
• n-местное-отношение n-местное-отношение
• Отношение-с-n-аргументами Отношение-с-n-аргументами
• Бинарное-отношение Бинарное-отношение
• Двуместное-отношение Двуместное-отношение
• Одноместное-отношение Одноместное-отношение
• Обратное-отношение Обратное-отношение
• Рефлексивность Рефлексивность
• Симметричность Симметричность
• Транзитивность Транзитивность
• Эквивалентность Эквивалентность
• Область-определения Область-определения
• Множество-значений Множество-значений
• Поле-отношения Поле-отношения