«Теория систем и системный анализ»

И. Б. Родионов

Лекция 14: Соответствие и функции

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

Соответствием между множествами А и В называется подмножество 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.

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

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

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

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

Отображения и функции

Функцией называется функциональное соответствие. Если функция f устанавливает соответствие между множествами A и В, то говорят, что функция f имеет тип А → B (обозначение f: А → В). Каждому элементу а из своей области определения функция f ставит в соответствие единственный элемент b из области значений. Это обозначается хорошо известной записью f(а) = b. Элемент а называется аргументом функции, b — значением функции на а.

Полностью определенная функция f: А → В называется отображением А в В. Образ А при отображении f обозначается f(А). Если соответствие f при этом сюръективно, т. е. каждый элемент В имеет прообраз в A, то говорят, что имеет место отображение A на B (сюръективное отображение).

Функции f и g равны, если их область определения — одно и то же множество A и для любого а ∈ A f(a) = g(a).

Всякая нумерация счетного множества является его отображением на N. Каждому человеку соответствует множество его знакомых. Если зафиксировать момент времени, то это соответствие будет однозначным и явится отображением множества M людей, живущих в этот момент, в множество подмножеств M.

Пусть дано соответствие G⊆A×В. Если соответствие H⊆B×А таково, что (b, a) ∈ H тогда и только тогда, когда (а, b) ∈ G, то соответствие Н называется обратным к G и обозначается G^-1. Если соответствие, обратное к функции f : А → В, является функциональным, то оно называется функцией, обратной к f, и обозначается f^-1. Так как в обратном соответствии образы и прообразы меняются местами, то для существования функции, обратной к f : A → В, требуется, чтобы каждый элемент b из области значений f имел единственный прообраз. Это в свою очередь означает, что для функции f : А → В обратная функция существует тогда и только тогда, когда f является взаимнооднозначным соответствием между своей областью определения и областью значений.

Пусть даны функции f: А → В и g: B → C. Функция h: А → С называется композицией функций f и g (обозначение f°g), если имеет место равенство h (х) = g (f(x)), где x∈A. Композиция f и g представляет собой последовательное применение функций f и g; g применяется к результату f. Часто говорят, что функция h получена подстановкой f в g. Знак ° аналогично умножению часто опускается.