Как найти композицию соответствий

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

Поскольку соответствия можно считать множествами, то все операции над множествами (пересечение, объединение, разность, дополнение и т.д.) можно применить и к соответствиям. Заметим, что, говоря о дополнении соответствия из A в B, мы имеем в виду дополнение до универсального соответствия из A в B, т.е. до декартова произведения 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)

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

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

Полезно отметить также, что если f и 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. Сечением соответствия rhocircsigma в точке x будет непустое в силу сделанных предположений множество всех таких упорядоченных пар (x,t)in Atimes C, что xin D(rho), а tinsigma(z) для некоторого zinrho(x). Говоря неформально, нужно перебрать все элементы z из сечения 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. Начнем с элемента I. Имеем

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}.

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

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 и D априори не накладывается никаких органичений. Композиция 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, заданных на множестве A, их композиция rhocircsigma (1.3) как соответствий является бинарным отношением на том же множестве A. В этом случае говорят о композиции бинарных отношений на множестве A.

Композицию 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, такая, что 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) для любого бинарного отношения на множестве A имеет место равенство rhocirc operatorname{id}Acirc rho= rho.

Эти свойства нетрудно доказать методом двух включений. Рассмотрим в качестве примера доказательство свойства 3. Пусть некоторая упорядоченная пара (x,y) принадлежит композиции rhocirc(sigmacuptau). Тогда, согласно (1.3), найдется такой элемент z, что (x,z)inrho и (z,y)insigmacuptau. Последнее означает, что (z,y)insigma или (z,y)intau. Таким образом, для элемента z имеем (x,z)inrho и (z,y)insigma или (x,z)inrho и (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}

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

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

rhocirc (sigmacap tau)subseteq rhocirc sigmacap rhocirctau,,

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

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

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

Соответствие, обратное к соответствию rho subseteq Atimes B, есть соответствие из B в A, обозначаемое 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 на множестве A обратное соответствие есть бинарное отношение на том же множестве. В этом случае говорят о бинарном отношении rho^{-1} на множестве A, обратном к 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 соответствие из B в A в общем случае не является отображением. Действительно, соответствие f^{-1}, обратное к f, состоит из всех упорядоченных пар вида (f(x),x),, xin A. Поскольку в общем случае могут найтись такие два различных элемента x и x', что f(x)= f(x'), то соответствие f^{-1} в общем случае не будет функционально по второй компоненте и поэтому не будет отображением. Если отображение f инъективно, то обратное соответствие есть частичное отображение из B в A. Если отображение f биективно, то обратное соответствие является отображением из B в A, причем имеют место равенства

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

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

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

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

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

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

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 (коротко — C-сужением соответствия rho), а всякое (C,rho(C))-ограничение соответствия rho — строгим сужением соответствия rho на подмножество C (строгим C-сужением соответствия р). C-сужения соответствия rho будем обозначать rhobig|_{C}, а строгое сужение — rhobig|_{circ C} соответственно.

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

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

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

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

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

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

Источник

и
функции

Продолжительность:2 часа (90 мин.)

4.1 Ключевые вопросы

4
Лекция № 3. Соответствия и функции 1

4.1
Ключевые вопросы 1

4.2
Текст лекции 1

4.2.1
Соответствия и их свойства 1

4.2.2
Функция 7

4.2.3
Вопросы для контроля 10

4.2 Текст лекции

4.2.1 Соответствия и их свойства

Соответствие
– способ задания взаимосвязей между
элементами множества. Частными случаями
соответствий являютсяфункции,
отображения, преобразования,
отношения.

Пусть
имеются два множества Аи В.Элементы этих множеств могут сопоставляться
друг другу, образуя пары (a,b). Если способ
сопоставления определен, то говорят,
что между множествамиAиB установлено
соответствие. При этом не обязательно,
чтобы в соответствии участвовали все
элементы множествАи В.

Таким
образом, чтобы задать соответствие надо
задать

–
множество A;

–
множество B;

–
множество
,
определяющее правило соответствия, т.
е. перечисляющее все пары (a,b), для которых
справедливо соответствие.

Записывается
соответствие так

g= (A, B,
G).

–
Множество Aназывается
областью отправления соответствия,

–
множество B–областью
прибытиясоответствия,

– G– называетсяграфикомсоответствия.

Обычно
соответствие обозначается символом
графика соответствия, в нашем случае
обозначим соответствие G.

С
соответствием связаны еще два понятия:

–
область определения соответствияG – элементы
множестваA, участвующие
в соответствии, обозначается эта область
какпр1G
= {а :( a, b)G},
и – область значений соответствияG – элементы
множестваB, участвующие
в соответствии, обозначается она какпр2G
= {b:{а, b)G}
(рис. 4.1 и рис. 4.2 ).

Если
(а, b)G,
то говорят, что«b
соответствуета при соответствииG«. Геометрически
это обозначается стрелками (рис. 4.2).

Пример
1. Пусть имеем множестваA
= {1, 2},B= {3, 5}.

Элементы
этих множеств образуют такие пары

AB= {(1, 3), (1, 5), (2, 3), (2, 5)}.

Из
приведенных пар можно составить несколько
соответствий, например, такие: G1= {(1, 3)}. Для этого соответствия Пр1G1= {1}; Пр2G1= {3}.

G2= {(1, 3), (1, 5)}. Здесь Пр1G2= {1}; Пр2G2= {3, 5}.

Рисунок
4.1 – График соответствия G

Рисунок
4.2 – Геометрическое представление
соответствияG

Свойства
соответствий:

–
соответствиевсюду(полностью)определенно,
еслипр1G=A.

Частично
определенное соответствие – в
противном случае.

–
соответствие
сюръективно, еслипр2G
= В.

Образомэлемента аА
в множествеВ при соответствииG
называется множество всехbВ,
соответствующих элементуаА.

Прообразомэлемента b
в множествеА при соответствииG
называется множество всехаА,
которым соответствуетbВ.

Образом
множества называется объединение образов всех
элементоваС.

Прообразом
множества
называется объединение прообразов
всех элементовb
D.

–
соответствие
называетсяоднозначнымилифункциональным,
если образом любого элементаа из
области определенияпр1Gявляется единственный элементb
из области значенийпр2G.

–
Взаимно однозначноесоответствие,
при котором любой элемент множестваA,
участвующий в соответствии, имеет
единственный образ в множествеB
и наоборот, любой элемент множестваB, участвующий в
соответствии, имеет единственный
прообраз в множествеA,
называетсяинъективным.

–
Соответствие, которое всюду определено,
сюръективно и инъективно называется
биекцией.

Если
между множествами А иВ существует
взаимно однозначное соответствие, то
мощности этих множеств равны, т.е. |А|
= |В|. В таком случае говорят, что
множестваAиВ
равномощны.

Множества,
равномощные множеству натуральных
чисел N, называютсясчетными. Множества, равномощные
множеству вещественных чиселR,
называютсяконтинуальными.

Пусть
дано соответствие

Тогда соответствиеG–1называетсяобратным кG,
еслиG–1
таково, что(b,
а)
G–1тогда и
только тогда, когда (а, b)
G.обратное
соответствие обозначается

g–1= (B,A,
G–1),

где G–1(не всегда).

Геометрически
представление обратного соответствия
получается из обозначения прямого
соответствия заменой направления
стрелок. Отсюда следует, что обратное
соответствие обратного соответствия
будет прямым, т.е.

(g–1)–1=g.

Последовательное
применение двух соответствий называется
композициейсоответствий.

Композиция
соответствий есть операция с тремя
множествами A, B,
C, на которых
определены два соответствия

g= (A, B,
G),,

p= (B, C,P),,

причем
область значений первого соответствия
совпадает с областью определения второго

Пр2G
= Пр1P.

Первое
соответствие определяет для любого
некоторый (возможно не один) элемент.
В соответствии с определением композиции
для этогоbнадо найтипо второму правилу. В результате длянайдем.

Композицию
соответствий gиpобозначаютg(p)
илиgp,
или простоgp.

График
композиции соответствий обозначаютGP.

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

g(p)
= (A,C,GP),GP
.

Операцию
композиции можно распространить и на
большее число (более двух) соответствий.

Композиция
ассоциативна

h(gp)
= (hg)p,

но не коммутативна

gp
pg,

даже если рассматриваются соответствия
элементов на одном множестве.

Пример
2. Англо–русский словарь устанавливает
соответствие между множествами английских
и русских слов. Каковы свойства этого
соответствия?

Данное
соответствие является:

–
не всюду определенным (всегда можно
найти английское слово, не содержащееся
в словаре);

–
не сюръективным (по отношению русских
слов, имеющихся в словаре);

–
не функциональным (одному английскому
слову ставится в соответствие, как
правило, несколько русских);

–
не взаимно однозначным (в силу предыдущего).

Пример
3. ПустьG– множество
всех пар действительных чисел (х, у),
удовлетворяющих соотношению

(х–3)2+(у
– 2)21.

Графически
такое соответствие Gпредставляет собой круг радиуса 1 с
центром в точке (3, 2). Таким образом, кругGзадает соответствие
между множествами действительных чиселR иR
(осью абсцисс и осью ординат, рис.
4.3).

Рисунок
4.3 – Соответствие Gкпримеру 3

Определить,
чему равны

а)
образы и прообразы чисел 2, 3, 4;

б)
образы и прообразы отрезков [2, 3], [2, 4].

Каковы
свойства соответствия G?

а)
Образом числа 2пр1G(на оси абсцисс) при соответствииG(см. рис. 4.3) является единственное число
2пр2G(на оси ординат). Образ числа 3 при
соответствииG есть
множество всех действительных чисел
отрезка [1, 3], а образ числа 4 – число
2.

Прообразом
числа 2пр2G
(на оси ординат) при соответствииG
будет множество всех действительных
чисел отрезка [2, 4]пр1G(на оси абсцисс), прообразом числа 3 при
соответствииG —
число 3, а прообраза числа 4 при
соответствииG не
существует.

б)
Образом множества чисел отрезка [2, 3]
пр1Gявляется объединение всех чисел отрезка
[1, 3]пр2G.
Аналогично, образом отрезка [2, 4]
пр1Gбудет
отрезок [1, 3]пр2Gпри соответствииG.

Прообраз
отрезка [2, 3]пр2Gпри соответствииG
– это отрезок [2, 4]
пр1G, а
прообраз отрезка [2, 4]пр2G– также [2, 4] пр1G.

Если
допустить, что соответствие G
установлено на множестве действительных
чиселR, т.е.,
то оно является:

–
частично определенным, так как

–
не сюръективным, поскольку

–
не функциональным, ибо для любого числа
отрезка [2, 4] = пр1G(кроме чисел 2 и 4) отсутствует единственность
образа;

–
не взаимно однозначным, так как отсутствуют
необходимые условия: Gне является всюду определенным наR,
не сюръективно, не функционально, а
также для любого числа отрезка [1, 3] =пр2G(кроме чисел 1, 3) отсутствует единственность
прообраза.

Если
определить соответствие G[2, 4]х[1, 3], то, очевидно, оно будет всюду
определенным и сюръективным, однако
останется не функциональным и не взаимно
однозначным.

Пример
4.ПустьG– множество
точек прямой линии, удовлетворяющей
соотношению

х
– 2 = у прих, у
0 (рис. 4.4).

Рисунок
4.4 – СоответствиеGкпримеру 4

Каковы свойства соответствия G?

1.
Если соответствие G
задано на множестве действительных
чисел, т.е.,то G:

–
частично определено, так как

пр1G
= [2, )

R;

–
не сюръективно, поскольку

пр2G
=R+ R,

где R+ =
[0,)
– множество всех положительных
действительных чисел с нулем;

–
функционально, ибо любому х из
области определения соответствует
единственный yиз
области значений, т.е. для соответствияG имеет место
единственность образа для любогох пр1G;

–
не взаимно однозначно, так как не
выполняются условия – всюду определенности
и сюръективности.

2.
если соответствиеG задано на множествеR+ с нулем, т.е.,
то соответствиеG:

–
частично определено, так как пp1G = [2,)
ипр1G

R+;

–
сюръективно, поскольку пр2G=R+;

–
функционально;

–
не взаимно однозначно, так как не
выполняется условие – всюду определенности.

3.
При G [2,)хR+
соответствиеG

–
всюду определено;

–
сюръективно;

–
функционально;

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

Пример
5. Пусть множества,
гдеU = {а, b,
с}, иВ3 определены
следующим образом:

– множество всех подмножеств (булеан)
множестваU ={а,
b, с);

В3
– множество всех двоичных векторов
длины 3, т.е.

B3
= A x
A x
A,

где A =
{0, 1}.

Показать,
что между множествами
иВ3 имеет место взаимно
однозначное соответствие.

= {,
{а}, {b}, {с}, {а,
b}, {а, с},
{b, с}, {а, b,
с}};

В
= {(000), (001), (010), (011), (100), (101), (110),
(111)};

для
упрощения обозначений запятые между
компонентами двоичных векторов опущены.

Установим
следующее соответствие G
между множествами изи векторами изВ3:

–
если в множестве из
присутствует элемента, то в
соответствующем ему векторе изВ3
первая компонента равна 1, а если
отсутствует – то 0;

–
если в множестве из
присутствует элементb,
то в соответствующем ему векторе изВ3 вторая
компонента равна 1, а если отсутствует
– то 0;

–
аналогичное соответствие установим
между элементом с в множестве изи значением третьей компоненты вектора
изВ3.

Например,
множеству {b} изсоответствует вектор (010) изВ3,
множеству {а, с} – вектор (101)
и т.д.

Очевидно,
что установленное таким образом
соответствие G является взаимно
однозначным, так как выполняются все
условия для взаимно однозначного
соответствия.

Пример
6. Каковы свойства соответствия между
множествомNнатуральных
чисел и множествомстепеней двойки

Соответствие
G

–
взаимно однозначно;

–
всюду определено, так как пр1G
= N;

–
сюръективно, поскольку пр2G
= ;

–
функционально, так как любому nN
соответствует единственный образ

–
характеризуется единственностью
прообраза, так как для любого
существует единственноеnN.

Источник

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

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

Композиция соответствий. Следуя аналогии с
композицией отображнений, композицией (произведением) соответствий р ⊆ А×В и σ ⊆ В×С называют соответствие

рºσ = {(x, у): (∃ z ∈ B)((x, z)∈р)∧((z, у) ∈ σ)}.     (1.3)

Поясним построение композиции двух соответствий.
Обратимся сначала к отображениям (как частным случаям
соответствий). Пусть заданы отображения (возможно, частичные):
f из А в В и g из В в С. Композиция* fºg определяется
как отображение из А в С, задаваемое формулой у = g(f(x)).
Тем самым задается график отображения fºg, т.е. множество
упорядоченных пар (x, у), таких, что у = g(f(x)). При этом
упорядоченная пара (x, у) будет принадлежать графику
отображения fºg, если и только если найдется элемент z ∈ В, такой, что z = f(x) и у = g(z). Таким образом, график
композиции отображений /ид есть

fºg = {(x, у): (∃z)(z = f(x) и y = g(z))} = {(x, У): У = g(f(x))}.     (1.4)

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

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

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

Вернемся к рассмотрению композиции соответствий рºσ.
Полагая, что область определения D(p) соответствия р не
пуста, возьмем произвольный элемент х ∈ D(p). Пусть сечение
р(х) ⊆ B соответствия p не пусто и найдется такой элемент
z ∈ р(x), что сечение σ(z) ⊆ C также не пусто. Тогда непустое
множество {(x, t): t ∈ σ(z)} будет подмножеством сечения
соответствия роа в точке х. Сечением соответствия роа в точке
х будет непустое в силу сделанных предположений множество
всех таких упорядоченных пар (x, t) ∈ А × С, что х ∈ D(p), a
t ∈ σ(z) для некоторого z ∈ р(х). Говоря неформально,
нужно перебрать все элементы z из сечения р(х). Таким образом,
различие в построении композиции соответствий и
композиции отображений заключается в том, что „промежуточный»
элемент z в общем случае не единственный и каждому
такому элементу также ставится в соответствие не единственный
элемент у ∈ С.

Пример 1.8. Соответствие р возьмем из примера 1.3.
Соответствие σ зададим как соответствие из множества
грамм {n1, n2, n3, n4, n5} в множество заказчиков
программного обеспечения {З1З2З3З4}. Пусть

σ = {(n1,З3), (n1,З4),(n2,З1),(n3,З2),(n4,З4),(n5,З3),

Рассмотрим процесс построения композиции соответствий
р и σ. Начнем с элемента И. Имеем р(И) = {n1, n3,n5}, σ(n1) = {З3,З4},σ(n3) = {З2} и σ(n5) = {З3}. Отсюда получаем

σ(n1)∪σ(n3)∪σ(n5) = {З2,З3,З4} —

сечение композиции по элементу И. Рассуждая аналогично,
получим (р॰σ)(П) = {З1,З4} и (р॰σ)(С) = {З1,З3}.

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

Рис. 1.3. Построение графа композиции

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

К определению композиции соответствий можно подойти с
более общих позиций. Пусть p⊆A×B и σ⊆C×D. При этом
на множества A, B, С и D априори не накладывается
никаких органичений. Композиция р॰σ соответствий р и σ в этом
случае также определяется соотношением (1.3). Чтобы такая
композиция была отлична от пустого соответствия, необходимо
и достаточно выполнение условия R(p)∩D(σ) ≠ ∅. В
частности, р॰σ = ∅ всякий раз, когда В ∩ С = ∅.

Пример 1.9. Рассмотрим соответствие

τ = {(1, а),(2, а),(3,d)}

из множества А = {1,2,3} в множество В = {а, b, d} и
соответствие

φ ={(b,e),(b,f),(c,f)}

из множества С = {b, с, d} в множество D = {е, f}. В данном
случае В ∩ С ≠ ∅, но τ ॰ φ = ∅, поскольку R(τ) = {a, d}, D(φ) = {b,с} и R(τ)∩D(φ)=∅. #

Заметим, что композиция соответствий р ⊆ A × B и σ ⊆ С × D
не коммутативна, т.е. в общем случае рост р ॰ σ ≠ σ ॰ р, поскольку р ॰ σ ⊆ A × D, а σ ॰ р ⊆ C × B.

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

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

Рассмотрим пример построения композиции бинарных
отношений на множестве и покажем, что в общем случае для двух
бинарных отношений τ и φ также имеет место неравенство τ ॰ φ ≠ φ ॰ τ, хотя обе композиции, в отличие от аналогичных
композиций двух произвольных соответствий, заданы на одном
и том же множестве.

Пример 1.10. а. Зададим на множестве А = {1,2,3,4}
бинарные отношения τ = {(x, у): х +1 < у}, φ = {(x,у): |x — y| = 2}
и найдем композицию τ ॰ φ.

Имеем τ(1) = {3,4}, φ(3) = {1} и φ(3) = {2}. Следовательно,
(τ ॰ φ)(1) = φ(3) ∪ φ(4) = {1,2}. Далее τ(1) = {4}, φ(4) = {2} и
(τ ॰ φ)(2) = {2}. Так как τ(3) = τ(4) = ∅, то в итоге получим
τ ॰ φ = {(1, 1), (1, 2), (2, 2)}. Построение композиции
проиллюстрировано на рис. 1.4, а.

Рис. 1.4. Построение композиции

Найдем композицию φ ॰ τ. Поскольку φ(1) = {3}, а τ(3) =
= ∅, то (φ ॰ τ)(1) = ∅. Аналогично φ(2) = {4}, а τ(4) = ∅,
поэтому (φ ॰ τ)(2) = ∅. Далее φ(3) = {1}, τ(1) = {3,4}, поэтому
(φ ॰ τ)(3) = {3,4}, a φ(4) = {2}, τ(2) = {4} и (φ ॰ τ)(4) = {4}.
Построение композиции проиллюстрировано на рис. 1.4, б.

Легко видеть, что τ ॰ φ ≠ φ ॰ τ.

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

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

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

  1. р ॰(σ॰τ) = (р ॰σ)॰τ;
  2. для любого соответствия р имеет место р ॰∅ = ∅॰р = ∅;
  3. р ॰(σ∪τ) = (р ॰σ)∪(р ॰τ);
  4. для любого бинарного отношения на множестве А имеет
    место равенство р ॰ idA = idA॰p = р.

Эти свойства нетрудно доказать методом двух включений.
Рассмотрим в качестве примера доказательство свойства 3.
Пусть некоторая упорядоченная пара (x, у) принадлежит
композиции p ॰ (σ ∪ τ). Тогда, согласно (1.3), найдется такой
элемент z, что (x, z) ∈ р и (z, у) ∈ σ ∪ τ. Последнее означает,
что (z, у) ∈ σ или (z, у) ∈ τ. Таким образом, для элемента z
имеем (x, г) ∈ р и (z, у) ∈ σ или (x, z) ∈ р и (z, у) ∈ τ.
Первая альтернатива имеет место при (x, у) ∈ р ॰ σ, а вторая —
при (x, у) ∈ р ॰ τ, что означает (x, у) ∈ р ॰ σ ∪ р ॰ τ. Тем самым
включение р ॰(σ ∪ τ) ⊆ р ॰ σ ∪ р ॰ τ доказано.

Доказательство включения р ॰ σ ∪ р ॰ τ ⊆ р ॰ (σ ∪ τ) запишем
коротко, используя логическую символику:

(x, у) ∈ р ॰ σ ∪ р ॰ τ ⇒ (∃u)(((x,u)∈р∧((u,y)∈σ))∨(∃v)(((x,v)∈p∧((v,y)∈τ)) ⇒ (∃z)(((x,z)∈p)∧(((z,y)∈σ)∨((z,y)∈τ)))⇒(∃z)(((x,z)∈p∧((z,y)∈σ∪τ))⇒(x,y)∈p॰(σ∪τ).

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

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

р ॰(σ ∪ τ) ⊆ р ॰ σ ∩ р ॰ τ,

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

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

Обратное соответствие. Соответствие, обратное к соответствию р ⊆ А × В, есть соответствие из В в А,
обозначаемое р-1 и равное, по определению, р-1 = {(у, х): (x, у) ∈ р}.

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

τ-1={n1, И),(n2, П),(n2, С),
(n3, И), (n4, П), (n5, И), (n5, С)}.

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

1) (р-1)-1 = р;

2) (р॰σ)-1=σ-1॰р-1.

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

Заметим, что соответствия р॰р-1 и р-1॰р в общем случае
не совпадают. Даже для бинарного отношения р на множестве
А р॰р-1≠р-1॰р, а также р॰р-1≠idA и р-1॰р≠idA.

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

Рис. 1.5. Операции над соответствиями

Если а: A→ В — отображение, то оно является
соответствием. Обратное к а соответствие из В в А в общем случае
не является отображением. Действительно, соответствие f-1,
обратное к f, состоит из всех упорядоченных пар вида (f(x), x),
х∈А. Поскольку в общем случае могут найтись такие два
различных элемента х и x’, что f(x) = f(x’), то соответствие f-1 в
общем случае не будет функционально по второй компоненте и
поэтому не будет отображением. Если отображение f
тивно, то обратное соответствие есть частичное отображение
из В в А. Если отображение f биективно, то обратное
соответствие является отображением из В в А, причем имеют место
равенства

f॰f-1=idA, f-1॰f=idB

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

Ограничение соответствия. Пусть р ⊆ А × В —
соответствие из А в В и С ⊆ A, D ⊆ В. Ограничением
соответствия р на подмножества С и D (или (С, D)-ограничением соответствия р) называется соответствие из С в D
обозначаемое р|C,D) такое, что

(x, у) ∈ р|C,D ⇔ ((x, у) ∈ р) ∧ (х ∈ С) ∧ (у ∈ D).

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

р|C,D=p∩(C×D).

Так, „малый» арксинус, т.е. функция у = arcsinx, есть
ограничение „ большого» арксинуса у — Arcsin x, который является
соответствием на подмножества [—1,1] и [-π/2,π/2].

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

Всякое (С, В)-ограничение соответствия р ⊆ А × В будем
называть сужением соответствия р на подмножество С (коротко — С-сужением соответствия р), а всякое
(С, p(С))-ограничение соответствия р — строгим сужением
соответствия р на подмножество С (строгим С-сужением соответствия р). С-сужения соответствия р будем обозначать р|C, а строгое сужение — р|॰C соответственно.

Полезно заметить, что для любого отображения f: А → В строгое сужение f|॰A есть сюръекция А на f(A). Если,
сверх этого, f является инъекцией, то f|॰A есть биекция А
на f(A). Допуская некоторую вольность речи*, можно
сказать, что любое отображение сюръективно отображает свою
область определения на свою область значений, в частности,
любая инъекция устанавливает взаимно однозначное
соответствие между областью определения и областью значений. Так,
функция у = sinx сюръективно отображает множество ℝ всех
действительных чисел на отрезок [—1,1], а любая
показательная функция биективно отображает ℝ на подмножество всех
положительных действительных чисел.

Для бинарного отношения р ⊆ А2 и любого подмножества
М ⊆ А (М, М)-ограничение бинарного отношения называют ограничением бинарного отношения р на
подмножество М и обозначают р|M. Можно записать р|M = р∩М2.

* Вольность состоит в томб что мы отождествляем функцию а с
функцией f|॰A.

Рассмотрим, например, отношение естественного порядка
≤ на множестве действительных чисел [I]. Тогда отношение
≤|ℤ = {(m, n): m ≤ n; m, n ∈ ℤ} есть ограничение этого
порядка на подмножество целых чисел. Но ни в коем случае нельзя
путать это отношение с ℤ-сужением отношения ≤! Это
последнее состоит из всех таких упорядоченных пар (m, x), что
m ∈ ℤ, x ∈ ℝ и m ≤ x, т.е. вторая компонента пары может быть
произвольным действительным числом, не меньшим заданного
целого m.

Источник

Тема: Множества и отношения. Читаем, комментируем, решаем ДЗ.

Определение множества

Множество — это совокупность элементов, которые объединены отношением
принадлежности. Для любого элемента множества $ A$
можно заключить: $ a in A$
.

Множества бывают конечными (из конечного числа элементов) и безконечными. Конечные
множества могут задаваться перечислением их элементов, например:

$displaystyle A = {1, 2, 3, 4}, B = {$Иванов$displaystyle ,$   Петров$displaystyle ,$   Сидоров$displaystyle }$

Бесконечные множества удобно задавать с помощью коллективизирующего условия:
$ A = { x vertP(x) }$
, где $ P(x)$
принимает значение «истина» или «ложь». Например,

$ A = { x vert kin mathbb{N}, x = 2 k }$
.

Множества считаются равными тогда и только тогда, когда они состоят из одних и тех же
элементов:

Отношение включения — множество $ A$
включается в множество $ B$

, если все элементы
$ A$
принадлежат $ B$
:
$ A subseteq B Leftrightarrow (forall x)(x in A Rightarrowx in B)$
. Тогда
$ A = B Leftrightarrow (A subseteq B) And (B subseteq A)$
.

Порядок элементов в множестве не играет роли, множество не содержит повторяющихся
элементов:
$ {1, 2, 3, 4} = {1, 2, 4, 3} = {1, 1, 2, 3, 4}$
. Не следует путать
множества элементов и множества множеств:

$ {1, 2, 3, 4} neq {{1, 2}, {3, 4}}$
.

Пустое множество не содержит ни одного элемента
$ (forall a) (a notin A)$
. При этом

$ { varnothing } neq varnothing $
.

Существует ли множество, содержащее само себя? Да, рассмотрим пример:

$ Z = { X vert$   X — множество, содержащее не менее трёх элементов$ }$
:

Существует ли множество, не содержащее само себя?
$ Y = { X vert X notin X}$. Это парадокс Рассела.

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

Существуют операции над множествами (получение новых множеств на основе существующих):

Если задано универсальное множество $ U$
, то может быть введена операция

дополнения:
$ overline{A} = U setminus A$.

Указанные операции обладают рядом интересных свойств (см. литературу). Свойства
оформляются в виде тождеств (всегда истинных равенств). Существует несколько способов
доказательства теоретико-множественных тождеств:

  1. метод двух включений;

  2. метод характеристических функций;

  3. метод эквивалентных преобразований.

Операции над множествами могут быть проиллюстрированы на диаграммах
Венна. Например, пересечение множеств может быть представлено как тёмная область на
рисунке 1.

Рис. 1: Диаграмма Венна для пересечения множеств

includegraphics[width=4cm]{venn_and.eps}

Метод двух включений основывается на укзанном выше определении равенства множеств
(
$ A = B Leftrightarrow (A subseteq B) And (B subseteq A)$
). Необходимо доказать две
леммы: если
$ x in A Rightarrow x in B$
и

$ x in B Rightarrow x in A$
. Рассмотрим
пример:

Доказать тождество
$ (A cup B) setminus (A cap B) = (A setminus B) cup (Bsetminus A)$
. Докажем методом двух включений:

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

  • $ (A setminus B) setminus C = A setminus (B setminus C)$
    ;

  • $ (A setminus B) setminus C = (A setminus C) setminus (B setminus C)$
    .

Метод характеристичских функций состоит в сопоставлении каждому множеству $ A$

функции
$ chi_A(x) = left{ begin{array}{l} 1, x in A\ 0, x notin A end{array}right.$
. Тогда функции, соответствующие операциям, будут равны:

Рассмотрим пример доказательства приведённого выше тождества,
$ (A cup B) setminus (A cap B) = (A setminus B) cup (Bsetminus A)$
:

Требуется показать, что
$ chi_{(A cup B) setminus (A cap B)} = chi_{(A setminus B)cup (B setminus A)}$
.

Задания для самоподготовки. Доказать методом характеристических функций и
проиллюстировать результаты на диаграммах Венна:

  • $ (A bigtriangleup B) bigtriangleup C = A bigtriangleup (B bigtriangleup C)$

  • $ A cup (B bigtriangleup C) = (A cup B) bigtriangleup (A cup C)$

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

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

Декартово произведение множеств

Определим множество упорядоченных пар следующим образом:

В общем случае операция декартова произведения некоммутативна:

$ A timesB neq B times A$
. Также эта операция не обладает свойством ассоциативности
$ Atimes (B times C) neq (A times B) times C neq A times B times C$
, действительно,
если
$ a_i in A, b_i in B, c_i in C$
, то
$ (a_i, (b_i, c_i)) neq ((a_i, b_i), c_i) neq(a_i, b_i, c_i)$
.

Графически декатрово произведение можно изобразить в виде квадрата на плоскости (рисунок
2).

Рис. 2: Декартово произведение множеств

includegraphics[width=4cm]{set_product.eps}

Умножение множества на себя называют декартовым квадратом (кубом и т.п.):
$ A^2 = A timesA$
,
$ A^3 = A times A times A$
, …. Декартов квадрат множества всех действительных
чисел
$ mathbb{R}^2$
образует декартову плоскость.

Задания для самоподготовки. Доказать методом двух включений и
проиллюстировать тождества графиком:

  • $ A times (B cup C) = (A times B) cup (A times C)$
    ;

  • $ A times (B setminus C) = (A times B) setminus (A times C)$
    .
Показать, что тождество
$ overline{A times B} = overline{A} times overline{B}$
в общем случае
неверно. Записать верное тождество и доказать его методом двух включений.

Соответствия и операции над ними

Пусть заданы два множества $ A$
и $ B$, соответствием называют некоторое подмножество
их декартова произведения:
$ rho subseteq A times B$
(рисунок 3). Если для пары

$ (x, y) in A times B$
имеет место соответствие,
то
$ (x, y) in rho$
. Это также записывают в виде $ x rho y$
.

Рис. 3: Пример соответствия

includegraphics[width=4cm]{correspond.eps}

Существует несколько способов задания соответствия: перечислением элементов (возможно для
конечных множеств $ A$
и $ B$
), заданием предиката (например,
$ rho = { (x, y) vert x in A, yin B, x < y + 5}$
), и в виде графа, часто соответствие иллюстрируют графиком (рисунок 4).

Рис. 4: Пример задания соответствия графически

includegraphics[width=12cm]{corr_graph.eps}

Для каждого соответствия рассматривают область определения
dom$ , rho = {x vert x in A And (x, y) in rho}$
и область значений
rng$ , rho = {x vert y in B And (x, y) in rho}$
.

Вводится понятие функциональности соответствия. Соответствие функционально по
первой компоненте тогда и только тогда, когда
$ forall (x_1, y_1), (x_2, y_2) in rho:y_1 = y_2 Rightarrow x_1 = x_2$
, другими словами: для каждого $ y$
существует единственный
$ x$
. Аналогично, соответствие функционально по
второй компоненте тогда и только тогда, когда
$ forall (x_1, y_1), (x_2, y_2) in rho:x_1 = x_2 Rightarrow y_1 = y_2$
, или для каждого $ x$
существует единственный $ y$

.

Рис. 5: Пример соответствия, не функционального по 2-ой компоненте

includegraphics[width=4cm]{nf2k.eps}

Отображение из $ A$
в $ B$
(функция) — это соответствие из $ A$
в $ B$
, которое всюду
определено и функционально по второй компоненте.

Соответствие — это множество упорядоченных пар, поэтому все операции над множествами к
ним применимы. Для соответствий вводятся две новые операции: композиция и
обратное соответствие.

Композиция соответствий
$ rho subseteq A times B$
и
$ sigma subseteq B times C$
 —
новое соответствие

$ tau subseteq A times C$
, равное
$ tau = rho circ sigma = { (x,y) vert x in A, y in C, exists z in B: x rho z And z sigma y }$
. Для конечных
соответствий удобно пользоваться графовым представлений соответствий — тогда для
получения композиции достаточно пройти по ребрам графа.

Пример композиции соответствий представлен на рисунке 6 и иллюстрирует
композицию соответствий оценок, полученных студентами, ($ rho$
) и соответствия оценки
получаемой стипендии. Результат композиции в этом случае — соответствие студентов и
выплаты стипендии.

Рис. 6:Пример композиции соответствий

includegraphics[width=14cm]{comp_corr.eps}

Под степенью отношения понимают его композицию с самим собой:

$ rho^2 = rho circrho$
.

Обратное соответствие образуется следующим образом:
$ rho^{-1} subseteq B timesA$
,
$ rho^{-1} = { (x, y) vert (y, x) in rho }$
. При этом
dom$ , rho =$   rng$ , rho^{-1}$

и
rng$ , rho =$   dom$ , rho^{-1}$
.

Композиция и обратное соответствие обладают рядом свойств, которые могут быть доказаны
методом двух включений. Рассмотрим свойство композиции
$ rho circ (sigma cup tau) =rho circ sigma cup rho circ tau$
.

begin{displaymath}begin{array}{l}triangleleftquad mbox{Необходимость:}qu......очность доказывается аналогично}quadtrianglerightend{array}end{displaymath}

Задания для самоподготовки. Доказать тождества для соответствий. Во втором
примере привести контрпример, показывающий, что равенство не может иметь место.

  • $ (rho circ sigma)^{-1} = sigma^{-1} circ rho^{-1}$
    ;

  • $ rho circ (sigma cap tau) subseteq rho circ sigma cap rho circ tau$
    .

Свойства отображений

Отображение называют инъективным, если оно функционально по первой компоненте.

На рисунке 7 показано неинъективное отображение
$ f(x) = x^2$
при
$ A =mathbb{R}$

,
$ B = mathbb{R}^{+}$
. Оно не является инъективным, так как значению $ y = 1$

соответствуют два $ x = 1$
и $ x = -1$
.

Рис. 7: Пример неинъективного отображения

includegraphics[width=6cm]{func_noninj.eps}

Отображение
$ f: A rightarrow B$
называют сюръективным, если область отображения
совпадает с $ B$

.

На рисунке 8 показано несюретивное отображение
$ f(x) = e^x$
при
$ A =mathbb{R}$
,
$ B = mathbb{R}^{+}$
. Оно не является сюръективным, так как область значений
отображения равна

rng$ , f = (0, +infty)$
. Однако, оно инъективно, так как
функионально по первой компоненте.

Рис. 8:
Пример инъективного и несюръективного отображения

includegraphics[width=6cm]{func_nonsur.eps}

Если отображение инъективно и сюръективно, то оно называется биективным. Такое
отображение задаёт взаимо однозначное соответствие между множествами $ A$
и $ B$
.

Пример биекции изображён на рисунке 9: если рассмотреть угол, под
которым расположен луч, то он соответствует точке на действительной прямой и
наоборот. Таким образом, задано биективное отображение интервала $ (0, pi)$

на

$ mathbb{R}$
.

Рис. 9:
Пример биективного отображения

includegraphics[width=10cm]{func_biject.eps}

Бинарные отношения и их свойства

Бинарное отношение (отношение) — соответствие множества самому себе:
$ rhosubseteq A times A$
. Выделим специальное отношение, которое существут для любого
множества $ A$
, называемое диагональю:
$ id_A = { (x, x) vert x in A}$
.

Свойства бинарных отношений:

  1. Отношение называют рефлексивным, если
    $ (forall x in A)((x, x) inrho)$
    . Отношение рефлексивно тогда и только тогда, когда диагональ полностью включается
    в него
    $ id_A subseteq rho$
    . В качестве примера рефлексивного отношения можно привести

    $ rho = { (x, y) vert x = y}$

    .

  2. Отношение называют иррефлексивным, если
    $ (forall x in A)((x, x) notinrho$
    . Отношение иррефлексивно тогда и только тогда, когда диагональ полностью не
    принадлежит ему
    $ id_A cap rho = varnothing$
    . Если отношение не рефлексивно и не
    иррефлексивно, его называют нерефлексивным. Иррефлексивным отношением является

    $ rho = { (x, y) vert x neq y}$
    .

  3. Отношение называют симметричным, если
    $ (forall x, y in A)(x rho yRightarrow y rho x)$
    . При этом график отношения симметричен относительно диагонали,
    при этом отношение совпадает с обратным к нему
    $ rho = rho^{-1}$
    . Примером такого
    отношения является равенство треугольников.

  4. Отношение называют антисимметричным, если
    $ (forall x, y in A)(x rho y Andy rho x Rightarrow x = y)$
    . Если отношение не симметрично и не антисимметрично, его
    называют несимметричным. На графике отношения все симметричные относительно диагонали
    точки будут лежать на самой диагонали

    $ rho cap rho^{-1} subseteq id_A$. Пример
    такого отношения —
    $ x leqslant y$.

  5. Отношение называют транзитивным, если
    $ (forall x, y, z in A)(x rho y Andy rho z Rightarrow x rho z)$. При этом квадрат отношения включается в него самого

    $ rho^2 subseteq rho$
    .

На рисунке 10 показаны примеры отношений с перечисленными свойствами.

Рис. 10:
Графики, иллюстрирующие свойства отношений

includegraphics[width=10cm]{rel_graphs.eps}

Задания для самоподготовки. Для заданного бинарного отношения
$ rho subseteqA^2$
1) построить график; 2) найти $ rho^{-1}$
и $ rho^2$

и построить их графики; 3)
исследовать свойства Р, И, С, А, Т.

  • $ A = {1, 2, 3, 4}, rho = {(1,1), (1, 3)$
    ,
    $ (2, 1), (2, 4)$
    ,
    $ (3, 2), (3,3)$
    ,

    $ (3, 4), (4, 1) }$
    ;

  • $ A = [0, 1], x rho y Leftrightarrow vert x - yvert leqslant 1 / 3$
    ;

  • $ A = [0, 1], x rho y Leftrightarrow y geqslant x + 1/4, x leqslant 1 /2$
    .

Задания для самоподготовки. Для заданного бинарного отношения

$ rho subseteqA^2$
1) найти $ rho^{-1}$
и $ rho^2$
; 2) исследовать свойства Р, И, С, А, Т.

  • $ A = M_{n times n}(mathbb{R}), P rho Q Leftrightarrow p_{i j} leqslantq_{i j}, i, j in {1, dots n}$
    ;

  • $ A = M_{n times n}(mathbb{R}), P rho Q Leftrightarrow det P = det Q$
    ;
  • $ A = M_{n times n}(mathbb{R}), P rho Q Leftrightarrow det P leqslant detQ$
    .

Источник

Как найти композицию отношений

03.05.2021, 17:09. Показов 1693. Ответов 1

Метки нет (Все метки)

Студворк — интернет-сервис помощи студентам

Добрый день, подскажите, как найти композицию отношений здесь.
Пусть на множестве A = {a, b, c} заданы отношения ρ и τ. Найдите композицию отношений τ^(-1)∘ ρ ,
постройте ее граф и определите свойства.
ρ = {(a, a), (b, a), (c, b), (a, c), (c, c)};
τ = {(a, a), (b, b), (b, c), (a, c), (c, c)}.



0



Источник

Понравилась статья? Поделить с друзьями:
  • Как исправить желтый цвет волос после неудачной покраски в домашних условиях
  • Как найти мамины духи
  • Как найти психотерапевта в пензе
  • Как найти лекарство в лесу
  • Как найти общее расстояние между зарядами