Соотве́тствие, понятие, распространяющее на случай двух, вообще говоря, различных множеств или однотипных математических структур понятие бинарного отношения. Cоответствие широко используют в математике, а также в различных прикладных областях: теоретическом программировании, теории графов, теории систем, математической лингвистике и так далее.

Соответствием между множествами $A$ и $B$ называют любое подмножество $R$ декартова произведения $A \times B$. Другими словами, соответствие $A$ и $B$ cocтоит из некоторых упорядоченных пар $(a, b)$, где $a \in A$, $b \in B$. Как правило, соответствие обозначают тройкой $(R, A, B)$ и, наряду с записью $(a, b) \in R$, пишут также $a R b$ или $R(a, b)$. Иногда вместо «соответствие» говорят «бинарное отношение» (в широком смысле, не предполагая, что множества $A$ и $B$ совпадают).

Для конечных множеств широко используются матричное и графовое представления соответствия. Пусть в множестве $A$ имеется $n$ элементов, в множестве $B$ имеется $m$ элементов и $(R, A, B)$ – некоторое соответствие. Этому соответствию сопоставляется матрица размером $n \times m$, строки которой помечены элементами из $A$, столбцы – элементами из $B$ и в которой на пересечении $a$-й строки и $b$-го столбца стоит $1$, если $(a, b) \in R$, и $0$ в противном случае. Обратно, каждая $(n \times m)$-матрица, состоящая из нулей и единиц, описывает вполне определённое соответствие между $A$ и $B$. При графовом представлении элементы множеств $A$ и $B$ изображаются точками на плоскости. Обычно эти точки обозначаются теми же буквами, что и соответствующие элементы. Точки $a$ и $b$ соединяются дугой, идущей от $a$ к $b$, если $(a, b) \in R$. Таким образом, соответствие представляется ориентированным графом.

Все соответствия между множествами $A$ и $B$ образуют полную булеву алгебру, нулём которой служит пустое соответствие, а единицей – так называемое полное соответствие, состоящее из всех пар $(a, b)$, $a \in A$, $b \in B$. Пусть $R \subseteq A \times B$.

Множество

$$D_R=\{a \in A \mid \exists b \quad(a, b) \in R\}$$называется областью определения соответствия $R$, а множество

$$B_R=\{b \in B \mid \exists a \quad(a, b) \in R\}$$– областью значений или образом, этого соответствия. Соответствие $R$ всюду определено, если $D_R=A$; соответствие $R$ сюръективно, если $B_R=B$. Для каждого $a \in A$ множество

$$\operatorname{Im}_R a=\{b \in B \mid \quad(a, b) \in R\}$$называется образом элемента $a$ относительно $R$; для каждого $b \in B$ множество

$$\operatorname{Coim}_R b=\{a \in A \mid \quad(a, b) \in R\}$$называется прообразом элемента $b$ относительно $R$. При этом

$$D_R=\cup_{b \in B} \operatorname{Coim}_R b, \quad B_R=\cup_{a \in A} \operatorname{Im}_R a .$$Всякое соответствие $R$ устанавливает соответствие Галуа между подмножествами множества $A$ и подмножествами множества $B$. Именно, каждому подмножеству $X \subseteq A$ сопоставляется подмножество $X^{\prime}=\cap_{a \in X} \operatorname{Im}_R a \subseteq B$. Вместе c дуальным соответствием, которое каждому $Y \subseteq B$ сопоставляет множество $Y^{\prime}=\cap_{b \in Y} \operatorname{Coim}_R b$, соответствие Галуа задаёт на каждом из множеств $A$ и $B$ оператор замыкания.

Инволюция $R^{\#}$ или $R^{-1}$ соответствия $(R, A, B)$ определяется равенством

$$R^{\#}=\{(b, a) \mid(a, b) \in R\}.$$Инволюция устанавливает биекцию между соответствием $(R, A, B)$ и соответствием $(S, B, A)$, которая является изоморфизмом булевых алгебр. Для соответствий $(R, A, B)$ и $(S, B, C)$ произведение, или композиция, определяется равенством

$$(R S, A, C)=\{(a, c) \mid \exists b(a, b) \in R \wedge(b, c) \in S\} .$$Умножение соответствий ассоциативно. Единицами для этого умножения служат диагональные бинарные отношения. Кроме того, $(R S)^{\#}=S^{\#} R^{\#}$ и из $R_1 \subseteq R_2$ следует $R_1^{\#} \subseteq R_2^{\#}$. Поэтому все соответствия между некоторой совокупностью множеств образуют упорядоченную категорию с инволюцией. Умножение и инволюция позволяют выражать свойства соответствий с помощью алгебраических соотношений. Например, соответствие $(R, A, B)$ всюду определено, если $R R^{\#} \supseteq E_A$ ($E_A$ – диагональ множества $A$); соответствие $R$ функционально, то есть является графиком функции из $A$ в $B$, если $R R^{\#} \supseteq E_A$ и $R^{\#} R \subseteq E_B$.

Для всякого соответствия $R$ существуют такие функциональные соответствия $F$ и $G$, что $R=F^{\#} G$. Кроме того, для всякого соответствия $R$ справедливо включение $R \subseteq R R^{\#} R$. Соответствие $R$ называется дифункциональным, если $R=R R^{\#} R$. Всякое дифункциональное соответствие индуцирует на области определения и на образе отношения эквивалентности, фактормножества по которым равномощны. Такое описание справедливо только для дифункциональных соответствий.

Пусть $\mathfrak{A}$ – класс однотипных математических структур, замкнутый относительно конечных декартовых произведений. Под соответствием между структурами $A$ и $B$ из $\mathfrak{A}$ понимают подструктуру $R$ произведения $A \times B$. Так вводятся групповые соответствия, модульные соответствия, кольцевые соответствия и тому подобное. Такие соответствия часто допускают полезные описания своего строения. Пусть, например, $A$ и $B$ – группы и $R$ – подгруппа прямого произведения $A \times B$. Множества

$$K_R=\{a \in A \mid(a, 1) \in R\},\quad I_R=\{b \in B \mid(1, b) \in R\}$$называются ядром и неопределённостью соответствия $R$. При этом $K_R$ – нормальный делитель в $D_R$, $I_R$ – нормальный делитель в $B_R$ и факторгруппы $D_R / K_R$ и $B_R / I_R$ изоморфны. Из этого описания, в частности, следует, что все групповые соответствия дифункциональны.