3.5. Соответствия и функции

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

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

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

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

Пример 3.8.

1. Круг G радиуса 1 с центром в точке (3.2) (рис. 3.4), т.е. множество пар действительных чисел {x,y}, удовлетворяющих соотношению (х – 3)²+ +(у – 2)² £ 1, задает соответствие между R и R (осью абсцисс и осью ординат). Образом числа 4 при этом соответствии является единственное число 2, образом числа 3 является отрезок [1, 3] оси ординат; этот же отрезок [1, 3] является образом отрезка [2, 4] оси абсцисс, который, в свою очередь, служит прообразом числа 2. Данное соответствие не является функциональным. Примером функционального соответствия между действительными числами на том же рис. 3.4 служит дуга AВС.

Еще раз напомним, что для задания соответствия надо указать не только множество G, но и множества А и В, т. е. указать, подмножеством какого прямого произведения является G. В данном примере тот же круг G₁ задает и другое соответствие: между отрезком [2, 4] и отрезком [1, З]. При этом по некоторым свойствам соответствия G₁ Í R² и G₁ Í [2, 4]´[1, 3] отличаются: второе соответствие в отличие от первого всюду определено и сюръективно. Учитывая эти соотношения, можно определять соответствие как тройку множеств (G, А, В). Тогда не пришлось бы оговариваться, что один круг может задавать два соответствия, это и так было бы ясно из различия троек (G₁, R, R) и (G₁,[2,4], [1, 3]). Однако такие оговорки приходится делать редко: либо множества А и В ясны из контекста, либо различия в их выборе не влияют на исследуемые свойства соответствия. Поэтому «определение через тройку множеств» далее использоваться не будет.

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

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

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

5. Множество векторов вида (n, 2^n-1), где n Î N, задает взаимно однозначное соответствие между множеством N натуральных чисел и множеством M₂n степеней двойки.