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

Соответствием между множествами А и В называется подмножество G⊆A×B.

Если (a, b) ∈ G, то говорят, что b соответствует а при соответствии G. Множество np₁G называется областью определения соответствия, множество np₂G — областью значений соответствия. Если np₁G = А, то соответствие называется всюду определенным (в противном случае соответствие называется частичным); если np₂G = В, то соответствие называется сюръективным.

Множество всех b ∈ B, соответствующих элементу а ∈ А, называется образом а в В при соответствии G. Множество всех а, которым соответствует b, называется прообразом b в А при соответствии G. Если С ∈ np₁G, то образом множества С называется объединение образов всех элементов С. Аналогично определяется прообраз множества D для любого D ⊆ np₂G.

Соответствие G называется функциональным (или однозначным), если образом любого элемента из np₁G является единственный элемент из np₂G. Соответствие G между А и В называется взаимно-однозначным (иногда пишут «1-1-соответствие»), если оно всюду определено, сюръективно, функционально и, кроме того, прообразом любого элемента из np₂G является единственный элемент из np₁G.

Так, например, англо-русский словарь устанавливает соответствие между множеством английских и русских слов. Это соответствие не является функциональным (так как одному английскому слову, как правило, ставится в соответствие несколько русских слов); кроме того, оно практически никогда не является полностью определенным: всегда можно найти английское слово, не содержащееся в данном словаре.

Позиция на шахматной доске представляет собой взаимно-однозначное соответствие между множеством оставшихся на доске фигур и множеством занятых ими полей.

Различные виды кодирования — кодирование букв азбукой Морзе, представления чисел в различных системах счисления, секретные шифры, входящие и исходящие номера в деловой переписке и другие — являются соответствиями между кодируемыми объектами и присваиваемыми им кодами. Эти соответствия, как правило, обладают всеми свойствами взаимно-однозначного соответствия, кроме, быть может, одного — сюръективности. Единственность образа и прообраза в кодировании гарантирует однозначность шифровки и дешифровки. ∈тсутствие сюръективности означает, что не всякий код имеет смысл, т. е. соответствует какому-либо объекту. Например, кодирование телефонов г. Москвы семизначными номерами не сюръективно, так как некоторые семизначные номера не соответствуют никаким телефонам.

Если между конечными множествами А и В существует взаимно-однозначное соответствие, то |А| = |В|.