Лекции_по_ДМ

Композиция двух соответствий

Пусть Г=(G, А, В) и S=(R, B, C) – соответствия.

Композицией графиков R и G называется график R∘G={(x,z): yB и (x,y)G и (y,z)R}. При этом область значений графика G является областью определения графика R, т.е. пр₂G = пр₁R. Композицией соответствий S и Г называется соответствие S∘Г=(R∘G, А, С).

При этом область прибытия Г является областью отправления S. Иными словами, под композицией понимают последовательное применение двух соответствий: сначала соответствия Г к элементам множества А, а затем соответствия S к значениям Г.

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

Следующие свойства справедливы как для композиции графиков, так и для композиции соответствий с этими графиками. Пусть Г=(G, А, В), S=(R, B, C) и Р=(Т, D, A) – соответствия.

1) (R∘G)^-1= G^‑1∘R^‑1

Доказательство: рассмотрим произвольную пару (z,x)(R∘G)^-1. Тогда по определению обратного графика (x,z)R∘G, и по определению композиции yB и (x,y)G и (y,z)R. Отсюда по определению обратного графика yB и (y,x)G^‑1 и (z,y)R^‑1 или, что то же самое: yB и (z,y)R^‑1 и (y,x)G^‑1. Отсюда по определению композиции следует (z,x)G^‑1∘R^‑1. Аналогично можно показать, что любая пара (z,x) из G^‑1∘R^‑1 принадлежит также и (R∘G)^-1. Отсюда следует: (R∘G)^-1= G^‑1∘R^‑1 .

2) (R∘G) ∘T = R∘ (G∘T)

Доказательство: рассмотрим произвольную пару (x,z)(R∘G) ∘T. Тогда по определению композиции yA и (x,y)T и (y,z)(R∘G), отсюда yA и (x,y)T и tB и (y,t)G и (t,z)R . Последнее равносильно тому, что tB и (yA и (x,y)T и (y,t)G ) и (t,z)R, поэтому tB и (x,t)(G∘T) и (t,z)R, следовательно, (x,z)R∘(G∘T). Аналогично можно показать, что для любой пары (x,z)R∘(G∘T) выполняется также: (x,z)(R∘G) ∘T.

3) (R∘G)(A) = R(G(A))

Доказательство: рассмотрим произвольный элемент z(R∘G)(A), т.е. z является образом некоторого элемента хA или, что то же самое, xA и z=(R∘G)(x) или (x,z)(R∘G). Поэтому xA и yB и (x,y)G и (y,z)R (по определению композиции). Таким образом, z=R(y) и y=G(x) и, следовательно, xA и z=R(G(x)) или zR(G(A)). Далее для завершения доказательства все рассуждения проводим в обратном порядке.

График вида _А={(x,x): xA} называется диагональю АА.

Очевидно, пр₁_А=пр₂_А=А. Соответствие _А=(_А, А, А) называется тождественным соответствием для А. Очевидно, _А^-1=_А, и Г∘_А = _В∘Г = Г, где _В=(_В, В, В) и Г=(G, A, B).

Пример:

Даны множества А={Иван, Жанн, Билл}, В={рус, англ, фр} и C={0, 1, 2}. И графики G={(Иван, рус); (Иван, англ); (Жанн, фр); (Жанн, англ); (Билл, англ)} и R={(рус, 0); (англ, 1); (фр, 2)} соответствий Г=(G, А, В) и S=(R, B, C). Тогда композицией соответствий S и Г будет соответствие S∘Г=(R∘G, А, С) между множествами А и С с графиком R∘G={(Иван, 0); (Иван, 2); (Жанн, 1); (Жанн, 2); (Билл, 2)}

Содержание