Использование отношений позволяет строить модели взаимосвязей между любыми обьектами в природе.

 

 

Почти каждому мудрому изречению cоответствует противоположное по смыслу при этом не менее мудрое.

Д. Сантаяна

5. Соответствия

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

ЦЕЛИ

Освоив эту главу, студенты должны:

· знать определение и способы задания соответствий;

· знать основные свойства соответствий;

· уметь выполнять операции над соответствиями;

· уметь решать задачи на доказательство тождеств с соответствиями;

· знать понятия функциональности, инъективности, сюръективности, всюду определенности;

· уметь определять и строить взаимно-однозначное соответствие;

· знать определение, способы задания и свойства функции.

5.1. Определение соответствия

Говорят, что между множествами X, Y установлено соответствие, если указано произвольное подмножество G Í X ´ Y, которое обладает некоторыми свойствами. Соответствия обычно обозначают прописными буквами греческого алфавита, например, G, D и т.д. Тогда соответствие (Г) — это тройка множеств Г = < G, X, Y >, первая компонента которой является графиком G, вторая компонента является множеством X и третья — множеством Y.

Г = < G, X, Y >, G Í X ´ Y — определение соответствия.

Множество Х задает область отправления соответствия, а множество Y — область прибытия соответствия.

Существует три способа задания соответствий: теоретический, матричный, графический. Теоретический способ заключается в задании графика соответствия и множеств X и Y.

Для графика соответствия справедливо:

G Í X ´ Y ® G = X ´ Y Ú G Ì X ´Y.

Часто область отправления называют областью определения соответствия (это проекция G на первую ось, пр₁G), а область прибытия - областью значений соответствия (проекция на вторую ось, пр₂G).

При задании матричным способом соответствие представляется в виде матрицы R _г, размером n x m, где строки представляют элементы множества X, столбцы - элементы множества Y, а элемент матрицы r_{i , j} принимает значения:

r_{i , j} = 1 - если существует кортеж < x_i, y_j > Î F;

r_{i , j} = 0, в противном случае.

Таким образом, соответствие можно представить в виде следующей матрицы:

Соответствие, заданное в графическом виде, представлено на рис. 5.1. В этом случае соответствие представляет собой график, вершинами которого являются элементы, принадлежащие множествам X и Y соответствия Г = < X, Y, F >, а кортежи вида < x_i, y_j >, принадлежащие множеству F, представляются на графике соответствия в виде стрелок, направленных от x_i к y_j.

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

Соответствие, график которого F = X ´ Y, называется соответствием с полным графиком и обозначается Г_П. Соответствие, график которого F = Æ, называется соответствием с пустым графиком и обозначается Г _Æ.

Пусть задано соответствие Г= < G, X, Y > и G = {< a, b >}, X = {a}, Y = {b}. Тогда говорят, что элемент (b) соответствует элементу (a). При этом элемент аÎпр₁G, и соответствие Г определено на этом элементе a. Элемент bÎпр₂G и является значением соответствия Г.

Если X = Y, то соответствие Г превращается в отношение. Можно сказать, что отношение является частным случаем соответствия. Все свойства и операции над отношениями можно переносить на соответствия.

ПРИМЕРЫ:

Пример 5.1. Г = < {< a, a >, < b, b >, < c, a >}, X = {a, b, c}, Y = {a, b} >. На рис. 5.2 представлено графическое задание этого соответствия.

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

Пример 5.2. Пусть Г = <G, X, Y>, Х = {1, 2, 3}, Y = {4, 5} G = {<1,4>; <1,5>; <2, 4>; <2,5>; <3,4>; <3,5>}. Тогда пр₁G = {1, 2, 3}, пр₂G = {4, 5}. Как видно, это соответствие является полным на множестве X ´ Y, т.е. G = X ´ Y.

 

Пример 5.3. На предприятии имеется три машины A, B, C. Машина С находится в ремонте. В штате имеется три шофера X, Y, Z, из которых шофер X находится в отпуске. Распределение шоферов по машинам является примером соответствия. Пусть M является областью отправления, а N – областью прибытия соответствия Г = <G, M, N>.

Тогда M = {X, Y, Z }, N = {A, B, C}, а один из возможных способов распределения шоферов по автомашинам задает график G = {<Y, B>, <Z, A>}. В нашем случае G Í M ´ N. На рис. 5.3 показано графическое представление этого соответствия.

Рис. 5.3. Графическое представление соответствия Г = < G, M, N >

Пример 5.4. Выражение <Æ, Æ, Æ> - будет является соответствием.

Отметим следующее, если G Í X ´ Y и G^-1 Í Y ´ X, то если <G, X, Y> — соответствие, то <G^-1, Y, X> является инверсией этого соответствия.

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

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

Объединением соответствий Г = <X, Y, F>и D = <W, Z, P> является соответствие: Г = <X È W, Y È Z, F È P>.

Пересечением соответствий Г и D является соответствие: Г = <X Ç W, Y Ç Z, F Ç P>.

Разностью соответствий Г и D является соответствие: Г = <X \ W, Y \ Z, F \ P>.

Инверсией соответствия Г является соответствие Г^-1, такое, что множество Y является областью отправления соответствия Г^-1; множество X является областью прибытия соответствия Г^-1, а график соответствия F ^-1 является инверсией графика F соответствия Г.

Композицией соответствий Г₁ = <X, Y, F> и Г₂ = <W, Z, P> является соответствие, такое, что его областью отправления является область отправления соответствия Г₁, областью прибытия - область прибытия соответствия Г₂, а графиком - композиция графиков FиP: Г₁ • Г₂ = <X, Z, F • P>.

В случае, если Y Ç W = Æ, то результатом композиции соответствий будет соответствие с пустым графиком.

Соответствие W называется инверсией соответствия Г, если область отправления Г равна области прибытия W и график Г является инверсией графика W.

Четная инверсия оставляет соответствие самим собой, а нечетная — инвертирует. То есть (Г^-1)^-1 = Г, а ((Г^-1)^-1)^-1 = Г^-1. Соответствие Г^-1 = Г тогда и только тогда, когда график соответствия симметричен G = G^-1, а область отправления соответствия совпадает с областью прибытия. Например, Г = <G, X, X>, Х = {1, 2, 3}, G = {< 1, 1 >, < 2, 2 >}. На рис. 5.4 приведено графическое представление этого соответствия.

Рис. 5.4. Графическое представление соответствия

Для соответствия так же, как для отношений и множеств справедлива операция композиции. Композиция соответствий определяется через композицию их графиков. Композиция соответствий не является пустой, если существует хотя бы один элемент y ÎY & y Î Z. Пусть заданы соответствия Г₁ = <G, X, Y>, Г₂ = <H, Z, U>. Тогда Г₁•Г₂ = <G•H, X, U> - определяет композицию двух соответствий.

Например, пусть заданы множества Х = {a, b}, Y = {c, d}, Z = {d,e}, U = <k, l>. Для получения непустого результата композиции соответствий множество Z должно частично или полностью совпадать с множеством Y.

Зададим произвольные графики G = { < a, c >, < b, d > }, и H = { < d,k >, < d,e >, < e,k > }. Тогда композиция графиков G•H = { < b, k >, < b, e > } и композиция соответствий запишется Г₁•Г₂ = < {< b, k >, < b, e >}, X, U >. Графическое представление композиции соответствий Г₁ и Г₂ показано на рис. 5.5.

Рис. 5.5. Пример графического представления композиции соответствий

Для любых трех соответствий существует следующее правило композиции:

(Г₁•Г₂)•Г₃ = Г₁•(Г₂•Г₃).

Докажем это тождество.

1) Докажем необходимость. Предположим, что

<a, b> Î (Г₁•Г₂)•Г₃ ® <a, x> Î Г₁•Г₂ Ù <x, b> Î Г₃ ® <a, x1> Î Г₁ Ù <x₁, x> Î Г₂ Ù <x, b> Î Г₃ ® <a, x₁> Î Г₁ Ù <x₁, b> Î Г₂•Г₃ ® <a, b> Î Г₁•(Г₂•Г₃).

Первая часть доказана.

2) Теперь докажем вторую часть, т.е. достаточность.

Пусть <a, b> Î Г₁•(Г₂•Г₃) ® <a, x> Î Г₁ Ù <x, b> Î Г₂•Г₃ ® <a, x> Î Г₁ Ù <x, z> Î Г₂ Ù <z, b> Î Г₃ ® <a, x> Î Г₁ Ù <x, z> Î Г₂ Ù <z, b> Î Г₃ ® <a, z> Î Г₁•Г₂ Ù <z, b> Î Г₃ ® <a, b> Î (Г₁•Г₂)•Г₃, что и требовалось доказать. Следовательно, тождество справедливо.

ПРИМЕРЫ:

Пример 5.5. Заданы соответствияГ₁ = <X, Y, F>;X = {1, 2, 3}; Y = {a, b, c, d}; F = {<1, a>; <1, c>; <2, b>; <2, c>; <3, d>}; Г₂ = <W, Z, P>; W = {2, 4, 5, 6}; Z = {a, c, d, e}; P = {<2, a>; <2, e>; <4, a>; <4, d>; <5, c>; <5, e>; <6, c>; <6, d>}. Найдем их пересечение, объединение и разность.

Ответ: Пересечение, объединение и разность соответствий Г и D, изображены соответственно на рис. 5.6, а - в.

 

Рис. 5.6, а-в. Результаты операций объединении, пересечения и разности соответствий Г₁ и Г₂

Пример 5.6. Для соответствийГ₁ и Г₂, заданных в предыдущем примере, найти инверсию соответствия Г₂и композицию соответствий Г₁ • Г₂^-1.

Ответ: Инверсия соответствия Г₂ изображена на рис.5.7, а композиция соответствий Г₁ и Г₂^-1 - на рис.5.8.

Рис. 5.7. Результат операции инверсии соответствия Г₂

Рис. 5.8. Результат операции композиции соответствий Г₁ и Г₂^-1

5.3. Понятия образа и прообраза при соответствии

Введем два новых понятия.

Пусть Г = <G, X, Y> и задано множество А Í Х. Тогда образом множества А при соответствии Г называется подмножество тех элементов Y, которые соответствуют элементам из А. Запись Г(А) = { y ÎY/$ x ÎA, < x, y >ÎG} является определением образа множества А при соответствии Г.

Рассмотрим пример. Задано соответствие Г = < G, X, Y >, X = {1, 2, 3}, Y = {a, b, c}, G = {<1, a>, <1, b>, < 2, c >, < 3, b >, < 3, a >} и задано произвольное множество A Í X, A = {1, 3}. Тогда образом данного множества А является Г(А) = {a, b} (рис.5.9).

На графическом языке Г(А) — это множество концов стрелок, выходящих из элементов множества А. Образ множества А можно также определить следующим образом:

Г(А) = пр₂[(A ´ Y) Ç G].

Если Г₁ и Г₂ —произвольные соответствия, то справедливо выражение

(Г₁•Г₂)(А) = Г₂(Г₁(А)).

Рис.5.9. Изображение образа множества А при соответствии Г

Прообразом множества В при соответствии Г = <G, X, Y> называется множество тех элементов области отправления, каждому из которых соответствует какой-нибудь элемент множества В. Г^-1(В) обозначение прообраза. Запись Г^-1(В) = { x ÎX/$ y ÎВ, < x, y >ÎG }} — является определением прообраза множества В при соответствии Г.

Прообраз множества В можно также определить следующим образом:

Г^-1(В) = пр₁[GÇ(X ´ В)].

Следовательно, прообраз на графическом языке представляет собой множество начал стрелок графика G.

Пример 5.7. Пусть задано соответствие Г = < G, X, Y > = <{ < 1, a >, < 1, b >, < 1, c >, < 2, a > }, { 1, 2 }, { a, b, c }>, В Í Y, В = { a, c }. В этом случае прообраз множества В - Г^-1(В) = { 1, 2 } (рис.5.10).

Рис. 5.10. Графическое представление прообраза множества В

Введем понятие сужения и продолжения соответствия. Пусть В — произвольное множество, В Í Х. Тогда сужением соответствия Г на множество В называется соответствие:

Г_B = < GÇ(B ´ Y), X, Y >.

Приведем пример сужения соответствия. Дано Г = < G, X, Y >, X = { 1, 2 }, Y = { a, b, c }, G = { <1, a>, <1, b>, < 1, c >, < 2, b >, < 2, с > }, В = { 1 }. Тогда B ´ Y = { < 1, a >, < 1, b >, < 1, c > } и сужение соответствия на множество B Г_B = <G Ç (B ´ Y), X, Y> = <{ < 1, a >, < 1, b >, < 1, c > }, {1, 2}, {a, b, c}>. Построим это сужение (рис.5.11).

Рис. 5.11. Пример сужения соответствия

Двойственным к понятию сужения является продолжение соответствия. Пусть заданы соответствия Г = <G, X, Y> и W = <H, Z, U>, причем G Í H, Z = X, U = Y. Тогда соответствие W является продолжением соответствия Г. Из этого следует, что произвольный элемент b, соответствующий произвольному элементу a в Г, обязательно соответствует тому же самому элементу в W, но не наоборот.

b ® a.

Пример 5.8. Пусть заданы соответствия Г = < G, X, Y >, X = {1, 2, 3}, Y = {a, b, c, d}, G = {<1, a>, <1, b>, <2, c>, <3, d>} и W = < H, Z, U >, X = {1, 2, 3}, Y = {a, b, c, d}, H = {<1, a>, <1, b>, <2, b>, <2, c>, <3, a>, <3, d>}. В этом случае соответствие W является продолжением соответствия Г. На рис. 5.12 показано соответствие Г, а на рис.5.13 - его продолжение – соответствие W.

Рис. 5.12. Соответствие Г

Рис. 5.13. Соответствие W (Продолжение соответствия Г)

ПРИМЕРЫ:

Пример 5.9. Пусть задано соответствие Г = <X, Y, F>; X = {1, 2, 3}; Y = {a, b, c, d}; F = {<1, a>; <1, c>; <2, b>; <2, c>; <3, d>}. Найти образ элемента 1 Î X и множества А = {1,2} на заданном соответствии.

Ответ: Образом элемента 1 будет множество Г(1) = {a, c}. Образом же множества A является следующее множество элементов: Г(A) = {a, b, c}.

 

Пример 5.10. Для соответствия из предыдущего примера найти прообраз элемента a Î Y и множества B = {a, b, c}.

Ответ: Прообразом элемента a будет множество Г^-1(a) = {1}. Прообразом же множества B = {a, b, c} будет являться множество Г^-1(B) = {1, 2}.

5.4. Доказательства тождеств с соответствиями

Исходя из свойств образа и прообраза произвольного множества при соответствии Г = <X, Y, F>,можно сказать, что будут истинны следующие тождества:

·  Г(A È B) = Г(A) È Г(B);

·  Г(A Ç B) Í Г(A) Ç Г(B);

·  Г(A \ B) Í Г(A) \ Г(B);

·  Г^-1(A È B) = Г^-1(A) È Г^-1(B);

·  Г^-1(A Ç B) Í Г^-1(A) Ç Г^-1(B);

·  Г^-1(A \ B) Í Г^-1(A) \ Г^-1(B).

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

Например, задано соответствие Г = <X, Y, F> и произвольные множества А и В, для которых справедливо условие A Í X, В Í Y. Доказать справедливость тождества:

Г(A È B) = Г(A) È Г(B).

Доказательство: Воспользуемся для доказательства данного тождества методом взаимного включения. Докажем сначала, что Г(A È B) Í Г(A) È Г(B).Предположим, что исходное тождество истинно. Тогда существует элемент y, для которого справедливо следующее высказывание:

yÎГ(A È B) ® yÎпр₂(((A È B) ´ Y) Ç F) ®

(согласно определению образа множества)

($xÎX)(<x, y>Î(((A È B) ´ Y) Ç F)) ®

(согласно свойству операции проектирования)

<x, y>Î((A È B) ´ Y) & <x, y>ÎF ®

(исходя из свойств операции пересечения)

xÎ(A È B) & yÎY & <x, y>ÎF ®

(исходя из свойств прямого произведения множеств)

(xÎA Ú xÎB) & yÎY & <x, y>ÎF ®

(исходя из свойств операции объединения)

xÎA & yÎY & <x, y>ÎF Ú xÎB & yÎY & <x, y>ÎF ®

(согласно закону дистрибутивности)

<x, y>Î(A ´ Y) & <x, y>ÎF Ú <x, y>Î(B ´ Y) & <x, y>ÎF ®

<x, y>Î((A ´ Y) Ç F) Ú <x, y>Î((B ´ Y) Ç F) ®

<x, y>Î[((A ´ Y) Ç F) È ((B ´ Y) Ç F)] ®

yÎпр₂[((A ´ Y) Ç F) È ((B ´ Y) Ç F)] ® yÎГ(A) È Г(B).

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

Теперь докажем справедливость обратного включения:

Г(A) È Г(B) Í Г(A È B).

Допустим, что истинно выражение:

yÎГ(A) È Г(B) ® yÎ Г(A) Ú yÎГ(B) ®

yÎпр₂((A ´ Y) Ç F) Ú yÎпр₂((B ´ Y) Ç F) ®

($x_iÎX)(<x_i, y>Î((A ´ Y) Ç F) Ú ($x_jÎX)(<x_j, y>Î((B ´ Y) Ç F) ®

(поскольку, в общем случае, x_i и x_j не обязательно совпадают))

(<x_i, y>Î(A ´ Y) & <x_i, y>ÎF) Ú (<x_j, y>Î(B ´ Y) & < x_j, y>ÎF) ®

(x_iÎA & yÎY & <x_i, y>ÎF) Ú (x_jÎB & yÎY & < x_j, y>ÎF) ®

((x_iÎA Ú x_jÎB) & yÎY & <x_i, y>ÎF) Ú ((x_iÎA Ú x_jÎB) & yÎY & <x_j, y>ÎF) ®

(согласно закону дистрибутивности)

((xÎ(A È B) & yÎY & <x, y>ÎF) ®

(согласно свойствам операции дизъюнкции для истинности выражения достаточно истинности хотя бы одного из его членов)

<x, y>Î((A È B) ´ Y) & <x, y>ÎF ® <x, y>Î(((A È B) ´ Y) Ç F) ®

yÎпр₂(((A È B) ´ Y) Ç F) ® yÎГ(A È B).

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

Следовательно, исходное тождество справедливо.

5.5. Основные свойства соответствий

Соответствие Г называется функциональным, если его график G функционален. График G называется функциональным, если в нем нет пар с одинаковыми первыми и разными вторыми элементами. Другими словами, из элементов области отправления может выходить не более одной стрелки. На рис. 5.14 - 5.16 приведены примеры функциональных соответсвий и на рис. 5.17 - нефункционального соответствия.

Рис. 5.14. Пример функционального соответствия

Рис. 5.15. Пример функционального соответствия

Рис. 5.16. Пример функционального соответствия

Рис. 5.17. Пример нефункционального соответствия

Следовательно, соответствие Г= <G, X, Y> функционально тогда, когда истинно

("xÎX, "y₁, y₂ÎY) [< x, y₁ >Î G Ù < x, y₂ >Î G ® y₁=y₂].

Соответствие Г называется инъективным, если его график инъективен. График G называется инъективным, если в нем нет пар с разными первыми и одинаковыми вторыми элементами. На рис.5.18, 5.19 приведены примеры инъективных соответствий. На рис.5.20 приведен пример неинъективного соответствия.

Рис. 5.18. Пример инъективного соответствия

Рис. 5.19. Пример инъективного соответствия

Рис. 5.20. Пример неинъективного соответствия

Отметим, что в частном случае инъективные и функциональные графики могут совпадать, например, графики соответствий на рис.5.16 и 5.19.

Соответствие инъективно, когда справедливо:

 ("x₁, x₂ ÎX, "yÎY) [< x₁, y >Î G Ù < x₂, y >Î G ® x₁ = x₂],

Соответствие Г = <G, X, Y> называется всюду определенным, если его область определения совпадает с его областью отправления. Например, Г = < G, X, Y > = < {<1,2>, <3,2>, <4,5>}; {1, 3, 4}; {2, 5}>. Здесь область отправления соответствия X = {1, 3, 4} совпадает с областью определения. На рис. 5.21 приведен пример всюду определенного соответствия.

Рис. 5.21. Пример всюду определенного соответствия

Для всюду определенного соответствия справедливо выражение:

пр₁G = X.

Аналогично можно записать:

("x)($y)[< x, y >ÎG].

Соответствие Г = <G, X, Y> называется сюрьективным, если его область значений совпадает с его областью прибытия. Например, Г = <G, X, Y> = < {<1,b>, <2, a>}; {1, 2, 3}; {a, b}>. Здесь область прибытия соответствия X = {a, b} совпадает с областью значений. На рис. 5.22 приведен пример сюръективного соответствия.

Рис. 5.22. Пример сюръективного соответствия

Для сюръективного соответствия справедливо выражение:

пр₂G = Y.

Аналогично можно записать:

("y)($x)[< x, y >ÎG].

Соответствие Г = <G, X, Y> называется биективным соответствием или биекцией, или взаимооднозначным соответствием, если оно функционально, инъективно, всюду определено и сюрьективно. На рис. 5.23 – 5.25 показаны примеры взаимно-однозначных (биективных) соответствий, а на рис.5.26 – соответствия, не являющиеся биективными.

Рис. 5.23. Пример взаимно-однозначного соответствия

Рис. 5.24. Пример взаимно-однозначного соответствия

             

Рис. 5.25. Пример взаимно-однозначного соответствия

Рис. 5.26. Пример не биективного соответствия

Частным случаем соответствия является понятие отображения. Всюду определенное соответствие называется отображением X в Y и записывается

G: X®Y.

Если в отображении G множества X и Y совпадают, получаем отображение множества Х самого в себя.

G: X®Х.

Приведем пример. Пусть Х = {a₁, a₂, b₁, b₂} — множество, состоящее из двух пар родителей. Обозначим Х₁ = {a_{1-2, 1}, a_{1-2, 2}, b_{1-2, 1}, b_{1-2, 2}, b_{1-2, 3}} — множество детей этих пар родителей, в которое входят как дети пары a, так и дети пары b. Х₂ = {ab_{2-1, 1}, ab_{2-1, 2}} — множество внуков этих родителей. Построив отображения, получим пример генеалогического дерева рис.5.27.

Запишем упорядоченные пары, находящиеся в отношенях на множестве членов этой семьи.

Рис. 5.27. Пример генеалогического дерева для двух пар родителей

Пусть T = {(x, y): x – дедушка y}. Тогда T содержит следующие кортежи: <Саша, Иван>; <Саша, Вера>; <Коля, Иван>; <Коля, Вера>.

Пусть Q = {(x, y): x – брат y}. Тогда Q содержит следующие кортежи: <Боря, Женя>.

Для того чтобы доказать, что между заданными множествами X и Y можно построить взаимно-однозначное соответствие, нужно доказать, что существует такой график G Í X ´ Y, чтобы тройка < G, X, Y > была биекцией.

ПРИМЕРЫ:

Пример 5.11. Привести примеры функционального, нефункционального и антифункционального соответствия.

Решение. Соответствие Г = < X, Y, F > называется функциональным, если образ любого элемента x Î Х - Г(x) содержит не более одного элемента, т.е. график такого соответствия не содержит пар с одинаковыми первыми и разными вторыми элементами. В противном случае соответствие является нефункциональным. В случае, если каждому элементу x Î X соответствует более одного элемента из Y, соответствие называется антифункциональным.

На рис.5.28, а - в даны примеры соответственно функционального, нефункционального и антифункционального соответствия.

      

а                                                      б

в

Рис.5.28. Примеры функционального, нефункционального и антифункционального соответствия

Пример 5.12. Привести примеры инъективного, неинъективного и антиинъективного соответствия.

Решение. Соответствие Г = < X, Y, F > называется инъективным, если прообраз Г^-1(y) любого элемента y Î Y содержит не более одного элемента из X, т.е. график такого соответствия не содержит пар с одинаковыми вторыми и разными первыми элементами.

По аналогии с нефункциональными и антифункциональными соответствиями можем определить понятие неинъективного и антиинъективного соответствия.

На рис.5.29, а - в показаны примеры соответственно инъективного, неинъективного и антиинъективного соответствия.

  

                 а                                                         б

в

Рис. 5.29. Примеры инъективного, неинъективного и антиинъективного соответствия

Пример 5.13. Привести примеры всюду определенного, не всюду определенного, сюръективного и несюръективного соответствия.

Решение. Соответствие Г = < X, Y, F > называется всюду определенным, если для каждого x Î X его образ Г(x) не равен пустому множеству, т.е. в графике такого соответствия из любой вершины x Î X выходит по крайней мере одна стрелка. В противном случае соответствие является не всюду определенным. Соответствие Г = < X, Y, F > называется сюръективным, если для любого y Î Y его прообраз Г^-1(y) не равен пустому множеству, т.е. в графике такого соответствия в любую вершину y Î Y входит хотя бы одна стрелка. В противном случае соответствие называется несюръективным.

Все соответствия, показанные на рис.5.28(а,б,в), 5.29(а,б,в), являются всюду определенными и сюръективными. Примеры не всюду определенного и несюръективного соответствий приведены на рис.5.30, 5.31соответственно.

Рис.5.30. Пример не всюду определенного соответствия

Рис.5.31. Пример не сюръективного соответствия

Пример 5.14. Привести пример взаимно-однозначного соответствия.

Решение: Соответствие называется биективным или взаимнооднозначным, если оно функционально, инъективно, всюду определено и сюръективно. Пример биективного соответствия показан на рис.5.32.

Рис. 5.32. Пример взаимно-однозначного соответствия

Существует много способов установления взаимно-однозначного соответствия. Например, часто употребляемым является лексикографический метод. Он устанавливает соответствие в порядке следования. Тогда для примера показанного на рис. 5.32 получим следующее взаимно-однозначное соответствие:

a ® 1, b ® 2, c ® 3, d ® 4.

Пример 5.15. Задано произвольное множество X = { x ₁, x ₂, x ₃, x ₄, x ₅ }. Привести пример произвольного взаимно-однозначного соответствия на множестве X. Взаимно-однозначное соответствие на одном множестве называется подстановкой.

Ответ: Можем задать на множестве X следующую произвольную подстановку t:

,

то есть x ₁ ® x ₄, x ₂ ® x ₃, x ₃ ® x ₁, x ₄ ® x ₅, x ₅ ® x ₅.

5.6. Функция

Понятие функции ввели Ферма и Декарт. Полное понятие функции привел Леонард Эйлер в XIX веке.

Функция — это функциональное соответствие, т.е. соответствие с функциональным графиком. F = < Ф, X, Y >, Ф — функциональный график.

Функцией из множества X в множество Y называется соответствие, где каждый элемент множества Х связан с единственным элементом множества Y. Другими словами, для каждого xÎX в соответствии существует ровно одна пара вида <x, y>. В графической интерпретации из каждого элемента Х выходит ровно одна стрелка.

Говорят, что функция — это кортеж длины 3, в котором первая компонента является подмножеством прямого декартового произведения второй и третьей компонент и первая компонента — функциональный график.

На рис.5.33 изображена функция из множества X = {a, b, c, d} в множество Y = {1, 2, 3}, состоящая из пар {<a, 1>, <b, 1>, <c, 1>, <d, 3>}.

Рис.5.33. Пример функции из множества Х в множество Y

Выражение для определения функции можно записать в виде

F = < Ф, X, Y >,

где Ф — функциональный график, Ф Í X x Y.

Выражение, обозначающее функцию, иногда записывают так:

 _F

X®Y или F: X®Y.

Другими словами, если имеется некоторый элемент < a, b >ÎF, то говорят, что функция отображает элемент а в элемент b. Или говорят, что значение функции (F(a)) на элементе а равно F(a)=b.

Функция F называется тождественной, если

Ф = DX & X=Y,

где DX – диагональ на области X ´ X.

Функция F называется константной, если существует такой элемент bÎY, что график Ф = X ´ {b}.

Функция F тогда и только тогда всюду определена, когда

("xÎX)[$F(x)].

То есть для любого элемента множества Х всегда существует как минимум одно отображение.

Функция F тогда и только тогда биективна, когда она всюду определена, сюрьективна и инъективна.

Отметим следующее: для функции справедливы операции инверсии и композиции. Композиция функции также будет являться функцией. Для инверсии же существует следущее правило:

Инверсия F^-1 функции F, т.е. F^-1 = <Ф^-1, Y, X> необязательна должна быть функцией. Существует критерий функциональности инверсий.

Инверсия F^-1 функции F тогда и только тогда является функцией, когда функция F — инъективна.

Для любых значений функций F₁ и F₂ справедливо

(F₁•F₂)(x) = F₂(F₁(x)).

Рассмотрим понятие обратной функции. Обратной функцией является функция F^-1.

Отметим 3 основных свойства F^-1.

1. F^-1 является инверсией.

2. F•F^-1 тождествена на пр₁F.

3. F^-1•F тождествена на пр₂F.

Приведем принцип Дирихле. Пусть f: X ® Y – функция, причем X и Y – конечные множества. Принцип Дирихле гласит, что если |X| > |Y|, то по крайней мере одно значение f встретится более одного раза. Неформально, принцип Дирихле можно например записать следующим образом:

Если Х – множество белок, а Y – множество клеток, и |Х| = 12, а |Y| = 11, то 12 белок нельзя посадить в 11 клеток так, чтобы в каждой клетке находилась одна белка.

КОНТРОЛЬНЫЕ ВОПРОСЫ

1. Приведите определение и способы задания соответствия.

2. Как называется и обозначается соответствие Г = (Х, Æ, F)?