Соответствия и бинарные отношения на множествах

Отображение из множества . Отображение из множества или , который отображением сопоставляется элементу и обозначают .

Каждое отображение однозначно определяет множество упорядоченных пар , являющееся подмножеством декартова произведения .

Наоборот, пусть в декартовом произведении , что:

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

Отображение множества при всех может существовать несколько различных элементов множества , называют прообразом элемента при отображении .

Так, прообраз числа при отображении есть множество всех решений уравнения , т.е. множество

Прообраз элемента может быть пустым множеством. Это имеет место, например, для числа при отображении .

Множество всех , таких, что найдется , называют областью значений отображения . Область значений отображения будем обозначать .

Отображение называют инъективным (инъекцией), если каждый элемент из области его значений имеет единственный прообраз, т.е. из следует .

Отображение называют сюръективным (сюръекцией), если его область значений совпадает со всем множеством называют биективным (биекцией), если оно одновременно инъективно и сюръективно.

Таким образом, если отображение биективно, то каждому элементу множества

Пример 1.2. а. Отображение, заданное равенством , есть, как нетрудно показать, биекция множества натуральных чисел на его подмножество .

б. Отображение в. Любая показательная функция , есть биекция множества всех положительных действительных чисел.

г. Функция есть биекция множества .

д. Поворот окружности на заданный угол

Образ и прообраз множества

Пусть задано отображение и — некоторое множество. Множество элементов , таких, что , называют образом множества при отображении . Например, при отображении отрезок является образом множества (отрезка) , равно как и любого объединения отрезков вида (для произвольного целого .

Заметим, что для любого отображения образ всего множества , называют прообразом множества .

Например, для любого действительного числа множество, которое является объединением всех отрезков вида

есть прообраз отрезка при отображении .

Прообраз области значений произвольного отображения совпадает со всем множеством

Частичное отображение и его область определения

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

Во-вторых, можно отказаться от однозначности отображения, полагая, что данному , что , т.е. множество, являющееся прообразом элемента .

Если задано соответствие из по аналогии с обозначением для отображений, понимая при этом, что есть уже не элемент множества из множества упорядоченных пар , таких, что и элементы связаны соответствием , то есть . Указанное множество упорядоченных пар есть подмножество декартова произведения , мы тем самым однозначно определяем некоторое соответствие из

Нетрудно заметить, что графиком соответствия будет как раз множество , а соответствием, отвечающим графику . Поэтому можно отождествить соответствие с его графиком и считать, что соответствие из множества декартова произведения . В частности, при получаем пустое соответствие , а при , совпадающем со всем указанным декартовым произведением, — универсальное соответствие .

При этом будем писать для упорядоченных пар, связанных соответствием .

Используют также термины "частичное мультиотображение" и "частичная многозначная функция".

Пример 1.3. Рассмотрим множество программистов и множество программ . Зададим соответствие

Область определения соответствия из множества

Область значения соответствия — это множество всех вторых компонент упорядоченных пар из

Из определения вытекает, что . Соответствие из .

Сечением соответствия для фиксированного элемента . Можно сказать, что сечение соответствия есть множество всех "образов" элемента Сечением соответствия по множеству будем называть множество

Пример 1.4. Область определения соответствия т из примера 1.3 есть все множество .

Бинарные отношения на множествах

Соответствие из множества , называют бинарным отношением на множестве Пример 1.5. Простейшим примером бинарного отношения является отношение нестрогого неравенства на множестве действительных чисел , для которых справедливо .

Для произвольного бинарного отношения на некотором множестве часто используют запись вместо , говоря при этом об элементах, связанных бинарным отношением . Это согласуется с традиционной формой записи некоторых часто используемых бинарных отношений. Так, пишут , а не . Для таких бинарных отношений употребляют устоявшиеся словосочетания. Например, запись читается так: " ".

Бинарное отношение на множестве , т.е. пар с совпадающими компонентами, называют диагональю множества . Нетрудно понять, что диагональ графа соответствия . В этом случае элементы множеств принадлежит соответствию , то в графе соответствия из кружочка, обозначающего элемент . Для бинарного отношения на конечном множестве

Пример 1.6. а. На рис. 1.1, а изображены график и граф бинарного соответствия из примера 1.3.

б. Пусть . Бинарное отношение на , таких, что . Тогда

Область определения отношения , область значений . График и два варианта графа отношения изображены на рис. 1.1, б.

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

Функциональное соответствие

Соответствие называют функциональным по второй (первой) компоненте, если для любых двух упорядоченных пар и из равенства следует (и из следует ). Функциональность соответствия по второй компоненте означает, что, фиксируя в любой упорядоченной паре, принадлежащей данному соответствию, первую компоненту, мы однозначно определяем и вторую компоненту. Таким образом, мы можем сказать, что соответствие, функциональное по второй компоненте, есть отображение (возможно, частичное).

Поэтому соответствие является отображением из ) и функционально по второй компоненте. Отметим также, что отображение из

Отношения произвольной арности

В заключение обобщим понятие соответствия, определив отношения произвольной арности.

Определение 1.4. Произвольное подмножество называют (п-арным или п-местным) отношением на множествах .

В случае если все множества совпадают, т.е. , говорят об n-арном отношении на множестве — n-арное отношение на множествах и , то говорят об элементах , связанных отношением Замечание 1.3. При . Это не что иное, как соответствие из в , где множества и , вообще говоря, различны.

При получаем введенное ранее бинарное отношение на множестве, т.е. подмножество декартова квадрата ) следует, строго говоря, различать термины "n-арное отношение" и "n-арное отношение на множестве".

Связь между введенными понятиями отношения, соответствия и отображения проиллюстрирована на рис. 1.2.

Пусть n-арное отношение удовлетворяет условию: для любых двух кортежей

из выполнения равенств для любого следует, что и . Тогда отношение называют функциональным по i-й компоненте .

Другими словами, функциональность n-местного отношения по i-й компоненте равносильна условию, что, фиксируя все компоненты, кроме i-й, мы однозначно определяем и i-ю компоненту.

Пример 1.7. а. Представим строку учебного расписания как кортеж вида

Тогда расписание можно рассматривать как секстарное (шестиместное) отношение на соответствующих множествах. Оно будет функционально по первой компоненте, если, конечно, предположить, что два преподавателя или более не проводят одно и то же занятие одновременно в одном и том же месте (хотя, например, на лабораторных работах это возможно). Оно также функционально по третьей компоненте (один преподаватель не может вести одновременно занятия по разным дисциплинам), по четвертой (преподаватель со своей группой не могут находиться в разных аудиториях) и не будет, вообще говоря, функционально по второй, пятой и шестой компонентам.

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