Определение 2.8. Если , то соответствие называется всюду определенным или полностью определенным (в противном случае соответствие называется частичным).
Определение 2.9 Если , то соответствие называется сюръективным (сюръекцией).
Всюду определённым и сюръективным является соответствие из примера 2.9, поскольку всем поступившим студентам ставится в соответствие группа, в которой он будет проходить обучение. Соответствие из примера 2.6 является только сюръективным, поскольку его область значений совпадает с множеством . Соответсвия из примеров 2.7 и 2.8 не являются ни всюду определёнными ни сюръективными, поскольку их области определения и области значений не совпадают с .
Определение 2.10 Множество всех , соответствующих элементу , называется образом а в В при соответствии G.
Определение 2.11. Множество всех , которым соответствует , называется прообразом b в А при соответствии G.
Пример 2.10. Заданы два множества и и соответствие . Образом элемента «1» в B будет всё множество B, а образом элемента 2 в B будет множество . Прообразом элемента «5» будет множество .
Пример 2.11. Для соответствия из примера 2.7 образом элемента будут элементы и . Пары и поскольку обе эти пары удовлетворяют уравнению, являющимся характеристическим свойством данного соответствия.
Определение 2.12. Если , то образом множества С называется объединение образов всех элементов С.
Определение 2.13. Прообраз множества для любого – это объединение прообразов всех элементов .
Пример 2.12. Образом множества в соответствии (см. пример 2.10) будет являться множество , а прообразом множества будет множество
Определение 2.14. Соответствие называется инъективным (инъекцией), если прообразом любого элемента из является единственный элемент из .
Определение 2.15. Соответствие называется функциональным (однозначным, функцией), если образом любого элемента из является единственный элемент из .
Заметим, что функциональность соответствия ещё не означает его инъективность, и наооборот.
Пример 2.13. Примером функционального, но не инъективного соответствия является соответствие, задаваемое уравнением .
Пример 2.14. Примером инъективного но не функционального соответствия может являться соответствие, где первая компонента каждой пары представляет собой некоторое положительное число, а вторая компонента – любое действительное число, которое при возведении в квадрат даёт первую компоненту.
Если некоторая пара принадлежит некоторому функциональному соответствию то пишут: . В этом случае элемент называется аргументом, а элемент – значением функции. Две функции и называются равными, если областью их определения является одно и то же множество и для любого :
Определение 2.14. Всюду определённое функциональное соответствие называется отображением A в B.
Достаточно часто отображение называют преобразованием множества
Определение 2.15. Функциональное соотвествие , у которого область значений соответствия состоит из одного элемента называется функцией-константой.
Функция типа называется n-местной функцией. В этом случае принято считать, что функция имеет n аргументов: где , , ,…,
Пример 2.15. Сложение, умножение, вычитание и деление являются двухместными функциями на т. е. функциями типа .
Пример 2.16. Таблица выигрышей лотереи задает двухместную не полностью определенную функцию, которая устанавливает соответствие между парами из (серия, номер) и множеством выигрышей.
Определение 2.16. Пусть дано соответствие . Если соответствие таково, что тогда и только тогда, когда , то соответствие называется обратным к и обозначается .
Для обратных соответвтствий существует несколько свойств:
Свойство 1 обратного соответствия. Если некоторое сооответствие является функцией то обратное к нему соответствие инъективно.
Свойство 2 обратного соответствия Если некоторое соответствие сюръективно то обратное к нему отношение всюду определено
Свойство 3 обратного соответствия. Если некоторое сооответствие является инъекцией то обратное к нему соответствие является функцией.
Свойство 4 обратного соответствия. Если некоторое соответствие всюду определено то обратное к нему отношение всюду сюръективно
Определение 2.17. Если соответствие, обратное к функции , является функциональным, то оно называется функцией, обратной к , и обозначается
Так как в обратном соответствии образы и прообразы меняются местами, то для существования функции, обратной к требуется, чтобы каждый элемент из области значений имел единственный прообраз. Это, в свою очередь, означает, что для функции обратная функция существует тогда и только тогда, когда является взаимно однозначным соответствием между своей областью определения и областью значений.
Определение 2.18 Соответствие между и называется взаимно однозначным, или биекцией (иногда пишут 1-1-соответствие), если оно всюду определено, сюръективно, функционально и инъективно
Очевидно, что обратное биекции сооответствие, также является биекцией
Если между конечными множествами А и В существует взаимно однозначное соответствие, то . Действительно, если это не так, то либо , и тогда, поскольку отображение всюду определено, в найдутся два элемента, которым соответствует один и тот же элемент (нарушится инъективность), либо , и тогда, поскольку отображение сюръективно, в найдутся два элемента, соответствующих одному и тому же (нарушится функциональность).
Этот факт, во-первых, позволяет установить равенство мощностей двух множеств, не вычисляя этих мощностей, а во-вторых, часто дает возможность вычислить мощность множества, установив его взаимно однозначное соответствие с множеством, мощность которого известна или легко вычисляется.
Введём теперь строгое определение равномощности двух множеств, а также определение счётного множества.
Определение 2.19. Множества равномощны, если между их элементами можно установить взаимно однозначное соответствие.
Определение 2.20. Множества, равномощные называются счетными.
Определение 2.20 формально определяет тот факт, что множество счётно в том случае, если его элементам могут быть поставлены в соответствие некоторые числа натурального ряда. Необходимо отметить, что тот факт что множество счётно, не означает, что оно конечно. Счётными могут быть и бесконечные множества.
Для соответствий вводятся основные теоретико множественные операции, а также операция композиции
Для сооответствий и объединением этих соответствий является соответствие с областью определений, областью значений и графиком, определяемыми по следующей формуле:
(2.6)
Пересечением соответствий и будет являться соответствие, определяемое следующей формулой
(2.7)
Разностью соответствий и будет являться соответствие, определяемое следующей формулой
(2.8)
Декартовым произведением соответствий называется соответствие:
(2.9)
Дополнением соответствия называется соответствие:
(2.10)
Определение 2.21. Композицией соответствий является соответствие с областью определения, полностью совпадающей с областью определения соответствия , областью значений, полностью совпадающей с областью значений соответствия , и графиком, , определяемым следующим свойством:
(2.11)
Из определения 2.21 и формулы (2.6) вытекает порядок вычисления операции композиции. В том случае, если оба соответствия и функциональны (т.е. являются функциями), часто при определении понятия «композиция соответствий» вместо обозначения , пользуются обозначением , известным по курсу средней школы как обозначение сложной функции.
Перечислим основные свойства композиции соответствий:
Композиция двух соответствий в общем случае некомутативна:
(2.12)
Композиция соответствий ассоциативна
(2.13)
Справедливость операции ассоциативности вытекает из определения операции композиции. Действительно, для трёх сооответствий не имеет значения какую пару сооответствий вычислять первой.
Сооветствие, обратное композиции двух соответствий, равно композиции, обратных к этим двум, соответствий:
(2.14)
Важным частным случаем соответствий являются бинарные отношения.