И. Б. Родионов
↑ | Оглавление | ||
← | Лекция 13, «Операции над множествами. Упорядоченное множество» | Задание на курсовую работу | → |
Соответствием между множествами А и В называется подмножество G⊆A×B.
Если (a, b) ∈ G, то говорят, что b соответствует а при соответствии G. Множество np1G называется областью определения соответствия, множество np2G — областью значений соответствия. Если np1G = А, то соответствие называется всюду определенным (в противном случае соответствие называется частичным); если np2G = В, то соответствие называется сюръективным.
Множество всех b ∈ B, соответствующих элементу а ∈ А, называется образом а в В при соответствии G. Множество всех а, которым соответствует b, называется прообразом b в А при соответствии G. Если С ∈ np1G, то образом множества С называется объединение образов всех элементов С. Аналогично определяется прообраз множества D для любого D ⊆ np2G.
Соответствие G называется функциональным (или однозначным), если образом любого элемента из np1G является единственный элемент из np2G. Соответствие G между А и В называется взаимно-однозначным (иногда пишут «1-1-соответствие»), если оно всюду определено, сюръективно, функционально и, кроме того, прообразом любого элемента из np2G является единственный элемент из np1G.
Так, например, англо-русский словарь устанавливает соответствие между множеством английских и русских слов. Это соответствие не является функциональным (так как одному английскому слову, как правило, ставится в соответствие несколько русских слов); кроме того, оно практически никогда не является полностью определенным: всегда можно найти английское слово, не содержащееся в данном словаре.
Позиция на шахматной доске представляет собой взаимно-однозначное соответствие между множеством оставшихся на доске фигур и множеством занятых ими полей.
Различные виды кодирования — кодирование букв азбукой Морзе, представления чисел в различных системах счисления, секретные шифры, входящие и исходящие номера в деловой переписке и другие — являются соответствиями между кодируемыми объектами и присваиваемыми им кодами. Эти соответствия, как правило, обладают всеми свойствами взаимно-однозначного соответствия, кроме, быть может, одного — сюръективности. Единственность образа и прообраза в кодировании гарантирует однозначность шифровки и дешифровки. ∈тсутствие сюръективности означает, что не всякий код имеет смысл, т. е. соответствует какому-либо объекту. Например, кодирование телефонов г. Москвы семизначными номерами не сюръективно, так как некоторые семизначные номера не соответствуют никаким телефонам.
Если между конечными множествами А и В существует взаимно-однозначное соответствие, то |А| = |В|.
Функцией называется функциональное соответствие. Если функция 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. Знак ° аналогично умножению часто опускается.
↑ | Оглавление | ||
← | Лекция 13, «Операции над множествами. Упорядоченное множество» | Задание на курсовую работу | → |
© Виктор Сафронов, 2006–2017
Пользовательское соглашение | RSS | Поддержать проект | Благодарности