Как найти обратное бинарное отношение - Исправление недочетов и поиск решений вместе с Examum.ru

Операции над соответствиями на множествах

Поскольку соответствия можно считать множествами, то все операции над множествами (пересечение, объединение, разность, дополнение и т.д.) можно применить и к соответствиям. Заметим, что, говоря о дополнении соответствия из в , мы имеем в виду дополнение до универсального соответствия из в , т.е. до декартова произведения Atimes B . Естественно, что и равенство соответствий можно трактовать как равенство множеств.

В то же время на соответствия можно распространить операции, определяемые для отображений. Мы рассмотрим здесь две такие операции.

Композиция соответствии. Следуя аналогии с композицией отображнений, композицией (произведением) соответствий rhosubseteq Atimes B и sigmasubseteq Btimes C называют соответствие

rhocircsigma= bigl{(x,y)colon, (exists zin B)((x,z)inrho)land ((z,y)insigma)bigr}.

(1.3)

Поясним построение композиции двух соответствий. Обратимся сначала к отображениям (как частным случаям соответствий). Пусть заданы отображения (возможно, частичные): из в и из в . Композиция fcirc g определяется как отображение из в , задаваемое формулой y=g(f(x)) . Тем самым задается график отображения fcirc g , т.е. множество упорядоченных пар (x,y) , таких, что . При этом упорядоченная пара (x,y) будет принадлежать графику отображения fcirc g , если и только если найдется элемент zin b , такой, что z=f(x) и y=g(z) . Таким образом, график композиции отображений и есть

fcirc g=bigl{(x,y)colon, (exists z)(z=f(x),, y=g(z))bigr}= bigl{(x,y)colon, y=g(f(x))bigr}.

(1.4)

Необходимо заметить, что запись gcirc f(x) означает g(f(x)) , т.е. отображения в композиции пишутся в порядке, обратном тому, в каком они применяются. Мы же будем везде использовать запись fcirc g , полагая, что fcirc g(x)=g(f(x)) и порядок записи отображений в композиции совпадает с порядком их применения. Это обусловлено тем, что композиция отображений определяется нами как частный случай композиции соответствий, при записи которой естественным оказывается именно такой порядок.

Легко видеть, что (1.4) есть частный случай (1.3). Отметим, что при построении композиции отображений обычно предполагают, что пересечение области значений отображения и области определения отображения не пусто (R(f)cap D(g)ne varnothing) , поскольку в противном случае композиция была бы пуста. Для отображений, не являющихся частичными, R(f)subseteq D(g) , так как D(g)=B . Поэтому в данном случае пересечение R(f)cap D(g) всегда не пусто.

Полезно отметить также, что если и — биекции, то и композиция их тоже будет биекцией.

Вернемся к рассмотрению композиции соответствий rhocircsigma . Полагая, что область определения D(rho) соответствия rho не пуста, возьмем произвольный элемент xin D(rho) . Пусть сечение rho(x)subseteq B соответствия rho не пусто и найдется такой элемент zinrho(x) , что сечение sigma(z)subseteq C также не пусто. Тогда непустое множество {(x,t)colon, tinsigma(z)} будет подмножеством сечения соответствия rhocircsigma в точке . Сечением соответствия в точке будет непустое в силу сделанных предположений множество всех таких упорядоченных пар (x,t)in Atimes C , что xin D(rho) , а tinsigma(z) для некоторого zinrho(x) . Говоря неформально, нужно перебрать все элементы из сечения rho(x) . Таким образом, различие в построении композиции соответствий и композиции отображений заключается в том, что «промежуточный» элемент z в общем случае не единственный и каждому такому элементу также ставится в соответствие не единственный элемент yin C .

Пример 1.8. Соответствие rho возьмем из примера 1.3. Соответствие sigma зададим как соответствие из множества программ ${n_1,n_2 ,n_3, n_4, n_5}$ в множество заказчиков программного обеспечения ${Z_1,Z_2,Z_3,Z_4}$ . Пусть

$sigma=bigl{(n_1,Z_3),, (n_1,Z_4),, (n_2,Z_1),, (n_2,Z_1),, (n_3,Z_2),, (n_4,Z_4),, (n_5,Z_3)bigr}.$

Рассмотрим процесс построения композиции соответствий rho и sigma . Начнем с элемента . Имеем

$rho(I)={n_1,n_3,n_5},quad sigma(n_1)={Z_3,Z_4},quad sigma(n_3)={Z_2},quad sigma(n_5)={Z_5}.$

Отсюда получаем сечение композиции по элементу

$sigma(n_1)cupsigma(n_3)cupsigma(n_5)= {Z_2,Z_3,Z_4}.$

Рассуждая аналогично, получим $(rhocircsigma)(P)={Z_1,Z_4}$ и $(rhocircsigma)(C)={Z_1,Z_3}$ .

Построение графа композиции rhocircsigma проиллюстрировано на рис. 1.3.

Построение графа композиции соответствий

Отметим, что область определения композиции соответствий содержится в области определения первого соответствия, а область значений композиции соответствий — в области значений второго соответствия. Из приведенных рассуждений следует, что для того, чтобы композиция соответствий была отлична от пустого соответствия, необходимо и достаточно, чтобы пересечение области значений первого соответствия и области определения второго соответствия было не пусто.

К определению композиции соответствий можно подойти с более общих позиций. Пусть rho subseteq Atimes B и sigma subseteq Ctimes D . При этом на множества A,,B,,C и априори не накладывается никаких органичений. Композиция rhocircsigma соответствий rho и sigma в этом случае также определяется соотношением (1.3). Чтобы такая композиция была отлична от пустого соответствия, необходимо и достаточно выполнение условия R(rho)cap D(sigma)ne varnothing . В частности, rhocircsigma=varnothing всякий раз, когда Bcap C=varnothing .

Пример 1.9. Рассмотрим соответствие tau={(1,a),(2,a),(3,d)} из множества A={1;2;3} в множество B={a,b,d} и соответствие varphi= {(b,e), (b,f), (c,f)} из множества C={b,c,d} в множество D={e,f} . В данном случае Bcap Cnevarnothing , но taucircvarphi=varnothing , поскольку

R(tau)={a,d},qquad D(varphi)={b,c},qquad R(tau)cap D(varphi)=varnothing.

Заметим, что композиция соответствий rho subseteq Atimes B и sigma subseteq Ctimes D не коммутативна, т.е. в общем случае rhocircsigmane sigmacircrho , поскольку rhocircsigma subseteq Atimes D , а sigmacircrho subseteq Ctimes B .

Композиция бинарного отношения на множестве

Бинарное отношение на множестве является частным случаем соответствия. Для двух бинарных отношении rho и sigma , заданных на множестве , их композиция rhocircsigma (1.3) как соответствий является бинарным отношением на том же множестве . В этом случае говорят о композиции бинарных отношений на множестве .

Композицию rhocircrho бинарного отношения rho на некотором множестве с самим собой называют квадратом бинарного отношения rho и обозначают rho^2 .

Рассмотрим пример построения композиции бинарных отношений на множестве и покажем, что в общем случае для двух бинарных отношений tau и varphi также имеет место неравенство taucircvarphine varphicirctau , хотя обе композиции, в отличие от аналогичных композиций двух произвольных соответствий, заданы на одном и том же множестве.

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

Пример 1.10. а. Зададим на множестве A={1,2,3,4} бинарные отношения tau,,varphi и найдем композицию taucircvarphi , если

tau=bigl{(x,y)colon, x+1<ybigr},quad varphi=bigl{(x,y)colon, |x-y|=2bigr}.

Имеем tau(1)={3;4},~ varphi(3)={1} и varphi(4)={2} . Следовательно, (taucircvarphi)(1)= varphi(3)cupvarphi(4)={1;2} . Далее tau(2)={4},~ varphi(4)={2} и (taucircvarphi)(2)={2} . Так как tau(3)= varphi(4)= varnothing , то в итоге получим taucircvarphi={(1;1),(1;2),(2;2)} . Построение композиции проиллюстрировано на рис. 1.4,а.

Найдем композицию varphicirctau . Поскольку varphi(1)={3} , а tau(3)=varnothing , то (varphicirctau)(1)=varnothing . Аналогично varphi(2)={4} , а tau(4)=varnothing , поэтому (varphicirc tau)(2)= varnothing . Далее varphi(3)={1},~ tau(1)={3;4} , поэтому (varphicirc tau)(3)= {3;4} , а varphi(4)={2},~ tau(2)={4} и (varphicirc tau)(4)= {4} . Построение композиции проиллюстрировано на рис. 1.4,б.

Легко видеть, что taucircvarphinevarphicirctau .

б. Пусть отношение rho на множестве действительных чисел определено как функция y=ax+b . Найдем квадрат этого отношения (линейной функции от одного переменного).

Согласно (1.4), это будет функция , такая, что h(x)=a(ax+b)+c , то есть h(x)=a^2x+(ab+c) . Это тоже линейная функция, но с другими коэффициентами.

Свойства композиции соответствий

Приведем некоторые свойства композиции соответствий:

1) rhocirc(sigmacirctau)= (rhocircsigma)circtau ;
2) для любого соответствия rho имеет место rhocirc varnothing= varnothingcirc tau= varnothing ;
3) rhocirc(sigmacuptau)= (rhocircsigma)cup (rhocirctau) ;
4) для любого бинарного отношения на множестве имеет место равенство rhocirc operatorname{id}Acirc rho= rho .

Эти свойства нетрудно доказать методом двух включений. Рассмотрим в качестве примера доказательство свойства 3. Пусть некоторая упорядоченная пара (x,y) принадлежит композиции rhocirc(sigmacuptau) . Тогда, согласно (1.3), найдется такой элемент , что (x,z)inrho и (z,y)insigmacuptau . Последнее означает, что или (z,y)intau . Таким образом, для элемента имеем и или и . Первая альтернатива имеет место при (x,y)inrhocircsigma , а вторая — при (x,y)inrhocirctau , что означает (x,y)in rhocirc sigmacup rhocirc tau . Тем самым включение rhocirc (sigmacup tau)subseteq rhocirc sigmacup rhocirctau доказано.

Доказательство включения rhocirc sigmacup rhocirctau subseteq rhocirc (sigmacup tau) запишем коротко, используя логическую символику:

$begin{aligned} (x,y)in rhocircsigmacup rhocirctau &Rightarrow (exists u)bigl(((x,u)inrho)land ((u,y)insigma)bigr)lor (exists v)bigl(((x,v)inrho)land ((v,y)intau)bigr) Rightarrow \[2pt] &Rightarrow (exists z)bigl(((x,z)inrho)land (((z,y)insigma)lor ((z,y)intau))bigr) Rightarrow\[2pt] &Rightarrow (exists z)bigl(((x,z)inrho)land ((z,y)insigmacuptau)bigr) Rightarrow\[2pt] &Rightarrow (x,y)in rhocirc (sigmacuptau). end{aligned}$

В данном случае доказательства двух включений не совсем симметричны: элементы и во второй части доказательства не обязаны совпадать.

Замечание 1.4. В тождестве, выражающем свойство 3, нельзя вместо объединения поставить пересечение, так как в этом случае тождество нарушатся. Можно доказать, что сохранится лишь включение

rhocirc (sigmacap tau)subseteq rhocirc sigmacap rhocirctau,,

а обратное включение в общем случае не имеет места.

Анализ свойств 2 и 4 показывает, что роль пустого соответствия аналогична роли нуля при умножении чисел, а диагональ множества играет роль, аналогичную роли единицы, на множестве всех бинарных отношений на .

Обратное соответствие и его свойства

Соответствие, обратное к соответствию rho subseteq Atimes B , есть соответствие из в , обозначаемое $rho^{-1}$ и равное, по определению, $rho^{-1}= {(y,x)colon, (x,y)inrho}$ .

Для соответствия tau из примера 1.3

$tau^{-1}= bigl{(n_1,I),, (n_2,P),, (n_2,C),, (n_3,I),, (n_4,P),, (n_5,I),, (n_5,C)bigr}.$

Обратное соответствие обладает следующими легко проверяемыми свойствами:

1) $(rho^{-1})^{-1}=rho$ ;
2) $(rhocircsigma)^{-1}=sigma^{-1}circrho^{-1}$ .

Для бинарного отношения rho на множестве обратное соответствие есть бинарное отношение на том же множестве. В этом случае говорят о бинарном отношении $rho^{-1}$ на множестве , обратном к rho .

Заметим, что соответствия $rhocircrho^{-1}$ и $rho^{-1}circrho$ в общем случае не совпадают. Даже для бинарного отношения rho на множестве

$Arhocircrho^{-1}ne rho^{-1}circrho$ , а также $rhocirc rho^{-1}ne operatorname{id}A$ и $rho^{-1}circ rhone operatorname{id}A$ .

Например, для бинарного отношения rho={(3;1), (4;1), (4;2)} на множестве A={1;2;3;4} графы самого отношения, обратного отношения $rho^{-1}$ , композиций $rhocircrho^{-1}$ и $rho^{-1}circrho$ представлены на рис. 1.5.

Графы бинарного отношения, обратного отношения и композиций

Если fcolon Ato B — отображение, то оно является соответствием. Обратное к соответствие из в в общем случае не является отображением. Действительно, соответствие $f^{-1}$ , обратное к , состоит из всех упорядоченных пар вида (f(x),x),, xin A . Поскольку в общем случае могут найтись такие два различных элемента и , что f(x)= f(x') , то соответствие $f^{-1}$ в общем случае не будет функционально по второй компоненте и поэтому не будет отображением. Если отображение инъективно, то обратное соответствие есть частичное отображение из в . Если отображение биективно, то обратное соответствие является отображением из в , причем имеют место равенства

$fcirc f^{-1}=operatorname{id}A,,qquad f^{-1}circ f= operatorname{id}B,.$

Отображение $f^{-1}$ в этом случае называют отображением, обратным к .

Ограничение соответствия

Пусть rho subseteq Atimes B — соответствие из в и C subseteq A,~ D subseteq B . Ограничением соответствия rho на подмножества и (или (C,D) -ограничением соответствия rho ) называется соответствие из в , обозначаемое $rhobig|_{C,D}$ , такое, что

$(x,y)in rhobig|_{C,D}~ Leftrightarrow~ bigl((x,y)inrhobigr)land (xin C)land (yin D).$

Таким образом, (C,D) -ограничение соответствия rho есть «то же самое» соответствие rho , но из последнего берутся только упорядоченные пары, первая компонента которых принадлежит подмножеству , а вторая — подмножеству . Можно записать

$rhobig|_{C,D}= rhocap (Ctimes D).$

Так, «малый» арксинус, т.е. функция y=arcsin{x} , есть ограничение «большого» арксинуса y=operatorname{Arcsin}x , который является соответствием на подмножества [-1;1] и $left[-frac{pi}{2};frac{pi}{2}right]$ .

Рассмотрим некоторые важные частные случаи ограничений соответствий (в частности, бинарных отношений и отображений).

Всякое (C,D) -ограничение соответствия rho subseteq Atimes B будем называть сужением соответствия rho на подмножество (коротко — C-сужением соответствия rho ), а всякое (C,rho(C)) -ограничение соответствия rho — строгим сужением соответствия rho на подмножество (строгим C-сужением соответствия р). C-сужения соответствия rho будем обозначать $rhobig|_{C}$ , а строгое сужение — $rhobig|_{circ C}$ соответственно.

Полезно заметить, что для любого отображения fcolon Ato B строгое сужение $fbig|_{circ A}$ есть сюръекция на f(A) . Если, сверх этого, является инъекцией, то $fbig|_{circ A}$ есть биекция на f(A) . Допуская некоторую вольность речи, можно сказать, что любое отображение сюръективно отображает свою область определения на свою область значений, в частности, любая инъекция устанавливает взаимно однозначное соответствие между областью определения и областью значений. Так, функция y=sin{x} сюръективно отображает множество mathbb{R} всех действительных чисел на отрезок [-1;1] , а любая показательная функция биективно отображает на подмножество всех положительных действительных чисел.

Для бинарного отношения rho subseteq A^2 и любого подмножества M subseteq A (M,M)-ограничение бинарного отношения называют ограничением бинарного отношения rho на подмножество и обозначают $rhobig|_{M}$ . Можно записать $rhobig|_{M}=rhocap M^2$ .

Рассмотрим, например, отношение естественного порядка leqslant на множестве действительных чисел. Тогда отношение $leqslantbig|_{mathbb{Z}}= bigl{(m,n)colon, m leqslant n;~ m,ninmathbb{Z}bigr}$ есть ограничение этого порядка на подмножество целых чисел. Но ни в коем случае нельзя путать это отношение с -сужением отношения ! Это последнее состоит из всех таких упорядоченных пар (m,x) , что minmathbb{Z},, xinmathbb{R} и mleqslant x , т.е. вторая компонента пары может быть произвольным действительным числом, не меньшим заданного целого .

Математический форум (помощь с решением задач, обсуждение вопросов по математике).

Кнопка "Поделиться"

Если заметили ошибку, опечатку или есть предложения, напишите в комментариях.

Источник

Обратное отношение в математике — это отношение, взятое в обратном порядке по отношению к данному.

Определение

Пусть на множестве задано бинарное отношение Тогда его обратным называется отношение ${displaystyle R^{-1},}$ построенное следующим образом:

${displaystyle forall x,yin Xquad {bigl (}xR^{-1}y{bigr )}Leftrightarrow {bigl (}yRx{bigr )}.}$

Свойства

Если отношение обладает одним из перечисленных свойств: рефлексивностью, нерефлексивностью, симметрией, антисимметрией, асимметрией, транзитивностью или полнотой, то и обратное отношение ${displaystyle R^{-1}}$ также обладает им.
Если инъективно, сюръективно или функционально, то ${displaystyle R^{-1}}$ , вообще говоря, не обязано обладать таким же свойством.

Примеры

п·о·р Бинарное отношение
между двумя множествами: инъективное · сюръективное · биективное · полное слева · полное справа · функциональное
на множестве: рефлексивное · нерефлексивное · симметричное · антисимметричное · асимметричное · транзитивное · полное · евклидово

Источник

From Wikipedia, the free encyclopedia

In mathematics, the converse relation, or transpose, of a binary relation is the relation that occurs when the order of the elements is switched in the relation. For example, the converse of the relation ‘child of’ is the relation ‘parent of’. In formal terms, if and are sets and is a relation from to then ${displaystyle L^{operatorname {T} }}$ is the relation defined so that ${displaystyle yL^{operatorname {T} }x}$ if and only if In set-builder notation,

${displaystyle L^{operatorname {T} }={(y,x)in Ytimes X:(x,y)in L}.}$

The notation is analogous with that for an inverse function. Although many functions do not have an inverse, every relation does have a unique converse. The unary operation that maps a relation to the converse relation is an involution, so it induces the structure of a semigroup with involution on the binary relations on a set, or, more generally, induces a dagger category on the category of relations as detailed below. As a unary operation, taking the converse (sometimes called conversion or transposition) commutes with the order-related operations of the calculus of relations, that is it commutes with union, intersection, and complement.

Since a relation may be represented by a logical matrix, and the logical matrix of the converse relation is the transpose of the original, the converse relation is also called the transpose relation.^[1] It has also been called the opposite or dual of the original relation,^[2] or the inverse of the original relation,^[3]^[4]^[5] or the reciprocal ${displaystyle L^{circ }}$ of the relation ^[6]

Other notations for the converse relation include ${displaystyle L^{operatorname {C} },L^{-1},{breve {L}},L^{circ },}$ or ${displaystyle L^{vee }.}$

Examples[edit]

For the usual (maybe strict or partial) order relations, the converse is the naively expected «opposite» order, for examples, ${displaystyle {leq ^{operatorname {T} }}={geq },quad {<^{operatorname {T} }}={>}.}$

A relation may be represented by a logical matrix such as

${displaystyle {begin{pmatrix}1&1&1&1\0&1&0&1\0&0&1&0\0&0&0&1end{pmatrix}}.}$

Then the converse relation is represented by its transpose matrix:

${displaystyle {begin{pmatrix}1&0&0&0\1&1&0&0\1&0&1&0\1&1&0&1end{pmatrix}}.}$

The converse of kinship relations are named: « is a child of » has converse « is a parent of «. « is a nephew or niece of » has converse « is an uncle or aunt of «. The relation « is a sibling of » is its own converse, since it is a symmetric relation.

Properties[edit]

In the monoid of binary endorelations on a set (with the binary operation on relations being the composition of relations), the converse relation does not satisfy the definition of an inverse from group theory, that is, if is an arbitrary relation on then ${displaystyle Lcirc L^{operatorname {T} }}$ does not equal the identity relation on in general. The converse relation does satisfy the (weaker) axioms of a semigroup with involution: ${displaystyle left(L^{operatorname {T} }right)^{operatorname {T} }=L}$ and ${displaystyle (Lcirc R)^{operatorname {T} }=R^{operatorname {T} }circ L^{operatorname {T} }.}$ ^[7]

Since one may generally consider relations between different sets (which form a category rather than a monoid, namely the category of relations Rel), in this context the converse relation conforms to the axioms of a dagger category (aka category with involution).^[7] A relation equal to its converse is a symmetric relation; in the language of dagger categories, it is self-adjoint.

Furthermore, the semigroup of endorelations on a set is also a partially ordered structure (with inclusion of relations as sets), and actually an involutive quantale. Similarly, the category of heterogeneous relations, Rel is also an ordered category.^[7]

In the calculus of relations, conversion (the unary operation of taking the converse relation) commutes with other binary operations of union and intersection. Conversion also commutes with unary operation of complementation as well as with taking suprema and infima. Conversion is also compatible with the ordering of relations by inclusion.^[1]

If a relation is reflexive, irreflexive, symmetric, antisymmetric, asymmetric, transitive, connected, trichotomous, a partial order, total order, strict weak order, total preorder (weak order), or an equivalence relation, its converse is too.

Inverses[edit]

If represents the identity relation, then a relation may have an inverse as follows: is called

right-invertible: if there exists a relation called a right inverse of that satisfies
left-invertible: if there exists a relation called a left inverse of that satisfies
invertible: if it is both right-invertible and left-invertible.

For an invertible homogeneous relation all right and left inverses coincide; this unique set is called its inverse and it is denoted by ${displaystyle R^{-1}.}$ In this case, ${displaystyle R^{-1}=R^{operatorname {T} }}$ holds.^[1]^: 79

Converse relation of a function[edit]

A function is invertible if and only if its converse relation is a function, in which case the converse relation is the inverse function.

The converse relation of a function f:Xto Y is the relation ${displaystyle f^{-1}subseteq Ytimes X}$ defined by the ${displaystyle operatorname {graph} ,f^{-1}={(y,x)in Ytimes X:y=f(x)}.}$

This is not necessarily a function: One necessary condition is that be injective, since else $f^{-1}$ is multi-valued. This condition is sufficient for $f^{-1}$ being a partial function, and it is clear that $f^{-1}$ then is a (total) function if and only if is surjective. In that case, meaning if is bijective, $f^{-1}$ may be called the inverse function of

For example, the function has the inverse function ${displaystyle f^{-1}(x)={frac {x}{2}}-1.}$

However, the function has the inverse relation ${displaystyle g^{-1}(x)=pm {sqrt {x}},}$ which is not a function, being multi-valued.

Composition with relation[edit]

Using composition of relations, the converse may be composed with the original relation. For example, the subset relation composed with its converse is always the universal relation:

∀A ∀B ∅ ⊂ A ∩B ⇔ A ⊃ ∅ ⊂ B ⇔ A ⊃ ⊂ B. Similarly,

For U = universe, A ∪ B ⊂ U ⇔ A ⊂ U ⊃ B ⇔ A ⊂ ⊃ B.

Now consider the set membership relation and its converse.

{displaystyle Ani zin BLeftrightarrow zin Acap BLeftrightarrow Acap Bneq emptyset .}

Thus
The opposite composition is the universal relation.

The compositions are used to classify relations according to type: for a relation Q, when the identity relation on the range of Q contains Q^TQ, then Q is called univalent. When the identity relation on the domain of Q is contained in Q Q^T, then Q is called total. When Q is both univalent and total then it is a function. When Q^T is univalent, then Q is termed injective. When Q^T is total, Q is termed surjective.^[8]

If Q is univalent, then QQ^T is an equivalence relation on the domain of Q, see Transitive relation#Related properties.

References[edit]

^ ^a ^b ^c Gunther Schmidt; Thomas Ströhlein (1993). Relations and Graphs: Discrete Mathematics for Computer Scientists. Springer Berlin Heidelberg. pp. 9–10. ISBN 978-3-642-77970-1.
^ Celestina Cotti Ferrero; Giovanni Ferrero (2002). Nearrings: Some Developments Linked to Semigroups and Groups. Kluwer Academic Publishers. p. 3. ISBN 978-1-4613-0267-4.
^ Daniel J. Velleman (2006). How to Prove It: A Structured Approach. Cambridge University Press. p. 173. ISBN 978-1-139-45097-3.
^ Shlomo Sternberg; Lynn Loomis (2014). Advanced Calculus. World Scientific Publishing Company. p. 9. ISBN 978-9814583930.
^ Rosen, Kenneth H. (2017). Handbook of discrete and combinatorial mathematics. Rosen, Kenneth H., Shier, Douglas R., Goddard, Wayne. (Second ed.). Boca Raton, FL. p. 43. ISBN 978-1-315-15648-4. OCLC 994604351.
^ Peter J. Freyd & Andre Scedrov (1990) Categories, Allegories, page 79, North Holland ISBN 0-444-70368-3
^ ^a ^b ^c Joachim Lambek (2001). «Relations Old and New». In Ewa Orłowska; Andrzej Szalas (eds.). Relational Methods for Computer Science Applications. Springer Science & Business Media. pp. 135–146. ISBN 978-3-7908-1365-4.
^ Gunther Schmidt & Michael Winter (2018) Relational Topology, Springer Lecture Notes in Mathematics #2208, page 8, ISBN 978-3-319-74450-6

Halmos, Paul R. (1974), Naive Set Theory, p. 40, ISBN 978-0-387-90092-6

Источник

Если мы хотим
определить такое понятие, как отношение,
мы должны, прежде всего, ввести такое
понятие, как упорядоченная
пара.

Различие между
неупорядоченной парой элементов {a,b}
и упорядоченной парой (a,b)
обычно поясняют на примере сравнения
двух пар элементов. Две неупорядоченные
пары {a,b}={c,d},
если a=b&c=da=c&b=d.
Для упорядоченных пар (a,b)=(c,d)

a=b&c=d.
То есть, в общем случае, для упорядоченных
пар (a,b)(b,a).
Иногда употребляют и такую запись:
R=(a,b)={a,{a,b}}.
Нетрудно догадаться, что существование
множества {a,b}
зависит от того, какое мы выберем a.
Если a,b
– числа, то мы можем описать множество
упорядоченных пар в виде графика,
откладывая по оси абсцисс значения a,
по оси ординат значения b,
для которых существует R=(a,b).

Упорядоченную
пару R
называют двухместным
или бинарным
отношением.
Упорядоченный набор из n
элементов (a₁,
… , a_n)
называют n-местным
отношением или
кортежем.

Элементы для
формирования упорядоченных наборов
мы можем выбирать как из одного множества,
так и из разных. При построении графиков,
которые отображают бинарные отношения
между множествами действительных чисел
X
и Y,
мы используем так называемую декартову
систему координат.

Прямым (декартовым)
произведением двух множеств A
и B
называется множество упорядоченных
пар (a,b),
в которых aA
и bB:
AB={(a,b)|
aA
& bB}.

Степенью множества
A
называется его прямое произведение
само на себя: Aⁿ=A…A
– всего n
раз.

Пользуясь введенным
понятием прямого произведения, можно
определить бинарное отношение как
подмножество
прямого произведения AB:
R=ab={(a,b)R|
RAB}.

Запись ab
обозначает
отношение между элементами a
и b
в общем виде, а запись (a,b)
обозначает конкретную упорядоченную
пару элементов, то есть один элемент
отношения.

Если у нас задан
некоторый универсум U,
то мы можем рассматривать понятия
принадлежности (),
включения (),
и равенства (=), как отношения на B(U)
– множестве всех подмножеств универсума
U.

Способы задания
отношений.
Если отношение содержит небольшое
количество пар (или наборов), его можно
задать, как и множество, перечислением.
Бинарные отношения, как уже говорилось,
могут быть заданы в виде графиков, если
A,B
– числовые множества. В общем случае
отношения могут быть заданы в виде
таблиц или графов. В реляционных базах
данных понятие «кортеж» соответствует
записи в таблице, а поля таблицы с
именами A,B,C,…,
из которых берутся элементы записи,
образуют прямое произведение множеств
ABC…
.

Основные понятия,
связанные с понятием бинарного отношения.

Пусть
R=ab={(a,b)R|
RAB}.
Тогда
существуют:

обратное отношение
R^-1={(b,a)|(a,b)R};

дополнение
отношения R={(a,b)|(a,b)R}=(AB)R;

тождественное
отношение I={(a,a)|aA};

однородное
отношение:
U_R={(a,b)|aA&bA}.

Композиция
отношений.

Пусть заданы два
бинарных отношения: R₁AB
и R₂BC
(говорят так: отношение из A
в B
и отношение из B
в C).

Композицией
отношений
R₁
и R₂называется
отношение R
из A
в C:

R=
R₁
o R₂
={(a,c)|
aA
&
cC
&
bB
: (a,b)

R₁
& (b,c)

R₂}.

Пример.Пусть
A
— множество студентов ФПК, B
– множество специальностей, С –
множество учебных курсов, изучаемых
на этих специальностях. Нам нужно
определить, какие дисциплины будет
изучать каждый конкретный студент ФПК
(что будет включать его приложение к
диплому).

Здесь R₁
AB
– «студент aA
получает специальность bB»,
R₂
BC
– «на специальности bВ
изучается дисциплина cC».
Искомое отношение R
– «студент aA
изучает дисциплину cC»
есть композиция отношений R=
R₁
R₂.
То есть, чтобы студент aA
изучал дисциплину cC
нужно, чтобы он учился на специальности
bB,
что соответствует отношению ab,
и на этой специальности изучалась
данная дисциплина cC,
что соответствует отношению bc.
Значит, для решения задачи нам нужно
выяснить, для каких пар (a,b)
имеются пары (b,c),
и из этих пар составить новые пары
(a,c),
взяв первый элемент из пары (a,b),
а второй элемент – из пары (b,c).

Графически операцию
композиции можно проиллюстрировать
на следующей схеме.

В этой графической
схеме каждой упорядоченной паре
элементов (a,b)
и (b,c)
сопоставлены стрелки из множества А
в множество B
и из множества B
в множество C
соответственно. Искомым парам (a,c)
соответствуют возможные переходы по
стрелкам из множества A
в множество C.

Теперь составим
бинарные таблицы R₁
и R₂для
представленных данной схемой отношений.
Элементы этих таблиц r_ij₍₁₎ и r_jk₍₂₎ соответствуют
отношениям (a_i,b_j)
и (b_j,c_k).
Первая таблица будет содержать |A|
строк и |B|
столбцов, вторая — |B|
строк и |C|
столбцов. Для нашего примера таблицы
будут иметь вид:

1	0	0
0	1	1
1	0	0
0	1	0

1	0	1	1	0	0
0	1	0	0	1	0
0	0	1	0	0	1

R₁

R₂

Одновременное
существование отношений r_ij₍₁₎ и r_jk₍₂₎ соответствует
логическому произведению (конъюнкции)
элементов таблицы r_ij₍₁₎

r_ij₍₂₎,
и значение каждого элемента r_ik
итоговой таблицы R
будет зависеть от того, принимает ли
хотя бы одна из этих элементарных
конъюнкций значение «1», что соответствует
логическому сложению (дизъюнкции). Для
нашего примера r₁₁=(r₁₁₍₁₎r₂₁₍₁₎
r₃₁₍₁₎
r₄₁₍₁₎
)(
r₁₁r₁₂₍₂₎
r₁₃₍₂₎
r₁₄₍₂₎
r₁₅₍₂₎
r₁₆₍₂₎),
и так далее. То есть при i=1,…,|A|,
j=1,…,|B|,
k=1,…,|C|
мы имеем: R=
R₁o
R₂
= R₁
R₂
, где R₁
R₂— логическое
перемножение матриц.

Степенью отношения
Rⁿ
называется композиция отношения R
n
раз с самим собой.

Ядром отношения
RAB
называется композиция R*=
R
o
R^-1.
Ядро отношения является отношением на
A.

9.Однородные
(универсальные) отношения. Примеры
универсальных отношений. Свойства
однородных отношений (рефлексивность,
симметричность, транзитивность).
Отношение эквивалентности и отношение
порядка.

однородным
отношением—
отношение R=
a

b={(a,b)|aA&bA}.

однородное отношение
– это отношение RA².
Однородные
бинарные отношения
– важный тип отношений для многих
приложений информатики и других разделов
дискретной математики, для задач теории
графов. Ребра любого графа задают
однородное бинарное отношение на
множестве его вершин V.
Множество точек на плоскости с заданной
системой координат (X,Y)
– это тоже однородное бинарное отношение,
где A
– множество действительных чисел.

Свойства однородных
отношений.

1. Рефлексивность:

aA
имеет место отношение (a,a).
То есть отношение (a,b)
всегда существует при a=b.
Свойство рефлексивности означает,
что IR.

2.
Антирефлексивность:

aA
имеет место (a,a).
То есть отношение (a,
b)
не существует
ни при каких a=b.
Если для каких-то a=b
отношение существует, а для каких-то
нет, то следует говорить, что отношение
просто не
рефлексивно.

Примеры рефлексивных
отношений
на множестве точек плоскости XY:

1) R={(x,y)
| x=y};

2) R={(x,y)
| |y|<|x|+1};

3) R={(x,y)
| x+y=2k,
k=1,2,…,n}.

3.
Симметричность:

a,bA
(a,b)R

(b,a)R.
Свойство
симметричности означает, что R^-1R.

Симметричными
отношениями на множестве точек плоскости
XY
являются отношения 1) и 3) из приведенных
выше.

4.
Антисимметричность:

a,bA
, ab,
(a,b)R


(b,a)R.
То есть
условие симметричности не
выполняется
ни при каких a,b.
Простейший пример антисимметричного
отношения на XY
– строгое неравенство x<y.

Если для каких-то
ab
симметричность выполняется, а для
каких-то нет, то следует говорить, что
отношение R
просто не
симметрично.
Примером такого отношения является
отношение 2).

5. Транзитивность.

a,b,cA
(a,b)R
& (b,c)R

(a,c)R.
Очень важное свойство отношений.

Свойство
транзитивности можно записать через
степень отношения (композицию отношения
с самим собой): R²
=R
R

R.

Антитранзитивность
обычно не рассматривают, хотя можно и
ее определить так же, как в первых двух
случаях.

Примеры транзитивных
отношений:

1) все три примера,
приведенных выше;

2) x<y
( в том числе и нестрогое неравенство);

3) отношение
вложенности на B(U):
пусть A,B,C

U.
Если A

B
& B

C

A

C.

6.
Полнота
(линейность):

a,bA
, ab


(a,b)R

(b,a)R
.
Полнота
отношения означает, что R

R^-1

I
= U_R.

Свойство полноты,
вообще говоря, довольно редкое. Пример
полного отношения — неравенство xy.

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

Определение 1.
Если однородное отношение RA²:

рефлексивно,
2)симметрично, 3) транзитивно

то оно называется
отношением
эквивалентности. Отношение
эквивалентности часто обозначается
«»,
как и операция эквивалентности в логике.
Множество элементов aA,
для которых выполняется отношение
эквивалентности R,
называется классом
эквивалентности.
Класс эквивалентности будем обозначать
[x]_:

[x]_
= {y
| yA
& yx}.

Из рассмотренных
выше примеров отношениями эквивалентности
являются примеры 1) и 3).

Примером отношения
эквивалентности на B(U)
может служить отношение равномощности
множеств: |A|=|B|.
То есть все подмножества из U
одинаковой мощности образуют класс
эквивалентности.

Определееие 2.
Если однородное отношение RA²:

антисимметрично,
2) транзитивно,

то
оно называется отношением
порядка.
Если отношение при этом еще и
антирефлексивно,
то это отношение
строгого порядка.
Отношение нестрогого порядка может
быть как рефлексивным, так и просто не
рефлексивным.Для обозначения отношения
порядка можно использовать обычный
знак неравенства.Если отношение порядка
не обладает свойством полноты
(линейности), то обычно говорят об
отношении частичного
порядка. В
задачах дискретной математики и
информатики чаще всего встречается
именно этот тип отношений.

Если на множестве
А определено отношение частичного
порядка, то оно называется частично
упорядоченным.
Множество, на котором определено
отношение полного порядка, называется
вполне
упорядоченным.
Например, числовые множества – это
вполне упорядоченные множества.

Теорема.
На всяком конечном, непустом, частично
упорядоченном множестве существует
минимальный
элемент y
| 
xy
y<x.

Вполне упорядоченное
множество содержит только один
минимальный элемент, на частично
упорядоченном множестве их может быть
несколько. Булеан B(U),
— это вполне упорядоченное множество
относительно отношения вложенности
().
Минимальным элементом в этом случае
является пустое множество .

Соседние файлы в предмете [НЕСОРТИРОВАННОЕ]

Источник

Операции над соответствиями на множествах

Композиция бинарного отношения на множестве

Свойства композиции соответствий

Обратное соответствие и его свойства

Ограничение соответствия

Определение

Свойства

Примеры

Examples[edit]

Properties[edit]

Inverses[edit]

Converse relation of a function[edit]

Composition with relation[edit]

See also[edit]

References[edit]