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