Соответствие в теории множеств

Соотве́тствие (бинарное отношение) между двумя множествами ${\displaystyle A}$ и ${\displaystyle B}$, произвольное подмножество ${\displaystyle R}$ декартова произведения ${\displaystyle A\times B}$. При этом декартовым произведением ${\displaystyle A\times B}$ множеств ${\displaystyle A}$ и ${\displaystyle B}$ называется множество упорядоченных пар ${\displaystyle (a,b),a\in A,b\in B}$.

Если ${\displaystyle a\in A,b\in B}$ и${\displaystyle (a,b)\in R}$, то пишут также ${\displaystyle R(a,b)}$ или ${\displaystyle aRb}$. Если ${\displaystyle R}$ – пустое множество, то соответствие называется пустым, а если ${\displaystyle R=A\times B}$, то соответствие называется полным.

Пусть ${\displaystyle R\subseteq A\times B}$. Областью определения ${\displaystyle DomR}$ называется множество элементов ${\displaystyle a\in A}$, для каждого из которых найдётся хотя бы один элемент ${\displaystyle b\in B}$ такой, что ${\displaystyle aRb}$. Областью значений, или образом, ${\displaystyle ImR}$ соответствия ${\displaystyle R}$ называется множество элементов ${\displaystyle b\in B}$, для каждого из которых найдётся хотя бы один элемент ${\displaystyle a\in A}$ такой, что ${\displaystyle aRb}$. Соответствие ${\displaystyle R}$ называется всюду определённым, если ${\displaystyle DomR=A}$, и сюръективным, если ${\displaystyle ImR=B}$.

Для каждого ${\displaystyle a\in A}$ множество элементов ${\displaystyle b\in B}$ таких, что ${\displaystyle aRb}$ называется образом ${\displaystyle a}$ относительно ${\displaystyle R}$ и обозначается ${\displaystyle imRa}$. Прообразом элемента ${\displaystyle b\in B}$ относительно ${\displaystyle R}$ называется множество элементов ${\displaystyle a\in A}$ таких, что ${\displaystyle aRb}$, он обозначается ${\displaystyle coimRb}$.

Справедливы равенства ${\displaystyle ImR=\bigcup a\in A\,imRa,DomR=\bigcup b\in B\,coimRb}$.

Каждое соответствие однозначно определяет функцию ${\displaystyle a\mapsto imRa}$, которая отображает множество ${\displaystyle A}$ в множество подмножеств ${\displaystyle B}$. Обратно, всякая функция${\displaystyle f}$ из ${\displaystyle A}$ в множество подмножеств ${\displaystyle B}$ определяет некоторое ${\displaystyle {\text{С}}.\ R(f):aR(f)b}$ тогда и только тогда, когда ${\displaystyle b\in f(a)}$.

Указанные сопоставления взаимно однозначны, что позволяет рассматривать соответствия как частично определённые многозначные функции.