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

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

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

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

1) множество A;

2) множество B;

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

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

g = (A, B, G)

Множество A называется о бластью отправления соответствия, множество B – областью прибытия соответствия, G – называется графиком соответствия.

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

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

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

Пусть имеем множества A = {1, 2}, B = {3, 5}. Допустим элементы этих множеств образуют такие пары:

A B = {(1, 3), (1, 5), (2, 3), (2, 5)}.

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

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

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

Перечислим свойства соответствий.

соответствие всюду (полностью) определенно, если пр₁ G = A. Частично определенное соответствие – в противном случае.

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

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

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

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

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

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

Взаимно однозначное соответствие, при котором любой элемент множества 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), ,

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

Пр₂ G = Пр₁ P.

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