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

Определение. Соответствием φ между множествами %%A%% и %%B%% называется произвольное подмножество их произведения %%A × B%% (т.е. %%φ ⊆ A × B%% ).

Итак, соответствие состоит из упорядоченных пар. Каждая пара %%(a, b) ∈ φ%% указывает, что элементу %%a ∈ A%% соответствует элемент %%b ∈ B%% при данном соответствии %%φ%%.

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

%%φ = \{(1, b), (3, a), (3, c), (4, b)\}%%

Заметим, что некоторым элементам из %%A%% может соответствовать несколько элементов множества %%B%%, а некоторым элементам из %%A%% может не соответствовать ни один элемент множества %%B%% .

Определение. Областью определения соответствия φ называется множество %%Dom\, φ=\{a∈A: \text{ существует элемент } b∈B, \text{ что }(a,b)∈φ\}%% (т.е. это все элементы из %%A%% , которым соответствует хотя бы один элемент из %%B%% ).

Определение. Множеством значений соответствия %%φ%% называют множество %%Im\, φ = \{b ∈ B : \text{ существует элемент }a ∈ A,\text{ что }(a, b) ∈ φ\}%% (т.е. это все элементы из %%B%% , которые соответствуют хотя бы одному элементу из %%A%% ).

Пример 1. Для %%φ%%,изображенного на рис.4, %%Dom\,φ = \{1,3,4\}%% и %%Im\, φ = \{a,b,c\}%%. Для обозначения соответствия %%φ%% между множествами %%A%% и %%B%% будем использовать %%φ:A→B%%.

Опишем некоторые типы соответствий.

Пример 2. Так, соответствие %%φ%% из примера 1 сюръективно, но не всюду определено ( %%2\not ∈ Dom\,φ%% ), не однозначно (так как %%(3, a), (3, c) ∈ φ%% ), не инъективно (так как %%(1, b), (4, b) ∈ φ%% ). Чаще всего мы будем иметь дело с “хорошими” соответствиями — отображениями и биекциями.

Определение. Отображением называется всюду определенное и однозначное соответствие (выполняются свойства 1 и 3). Функцией называют отображение в вещественную прямую (т.е. %%B = \mathbb R%% ).

Определение. Биекцией называют всюду определенное, сюръективное, однозначное и инъективное соответствие (выполняются все свойства 1—4).

Например, квадратичная функция каждому числу %%x ∈ R%% (поэтому она всюду определена) ставит в соответствие одно число %%ax^2 + bx + c%% (она однозначна). Но квадратичная функция не является инъективным соответствием (некоторым pазличным числам она ставит в соответствие одно и то же число). Поэтому это не биекция. С другой стороны, функция %%f(x) = kx + b%% является биекцией при %%k\not= 0%% .

К соответствиям можно применять две операции — рассматривать обратное соответствие и брать композицию соответствий.

Определение. Обратным соответствием к соответствию %%φ ⊆ A × B%% называют %%φ^{−1}%% %% = \{(b,a) : (a,b) ∈ φ\}%%.

Заметим, что %%φ^{−1}%% %% ⊆ B × A %%, поэтому %%φ^{−1}%% — это соответствие уже между %%B%% и %%A%% . На рис. 5 показано обратное соответствие к φ , изображенному на рис. 4. В этом случае %%φ^{−1}%% %% = \{(b, 1), (a, 3), (c, 3), (b, 4)\} %%.

Определение. Композицией соответствий %%φ ⊆ A×B и ψ ⊆ B×C%% называют соответствие %%χ ⊆ A × C%% такое, что %%χ = \{(a, c) : \text{ существует элемент } b ∈ B,\text{ что }(a,b)∈φ\text{ и }(b,c)∈ψ\}%% (обозначается композиция так: %%χ=ψ◦φ%%).

Композиция соответствий, изображенных на рис. 6, является множеством %%ψ◦φ=\{(1,y), (3,x), (4,y)\}%%.