Обратные функции и композиция функций

Отношение эквивалентности

Бинарное отношение называется отношением эквивалентности, если оно одновременно обладает тремя свойствами: рефлексивностью, симметричностью и транзитивностью, то есть если для любых выполняется:

1. ― рефлексивность

2. если , то ― симметричность

3. если и , то ― транзитивность.

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

Непересекающиеся подмножества, на которые разбивается множество А от-

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

Пример. Отношение между целыми числами и , выражаемое равенством целые числа называется отношением сравнения и по модулю и записывается, как . Это отношение является отношением эквивалентности. Действительно,

1. - рефлексивность

2. - симметричность

3. транзитивность

Множество целых чисел разбивается этим отношением на классов

, , , … .

В частности, при , происходит разбиение множества на множество

четных и нечетных чисел, при ― на множество чисел, кратных трем и дающих

при делении на три в остатке 1 и 2.

Отношение порядка

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

Множество , которое обладает отношением порядка, называется упорядоченным.

Рефлексивное отношение порядка называют отношением нестрого порядка и обозначают знаком «».

Антирефлексивное отношение порядка называют отношением строго порядка и обозначают знаком «».

Говорят, что на множестве задано отношение полного (частичного) порядка, если сравнимы все (не все) элементы данного множества.

Множество , на котором установлено отношение полного (частичного) по-

рядка называется вполне (частично) упорядоченным.

Отношение нестрого порядка должно удовлетворять трем условиям: рефлексивности, антисимметричности и транзитивности.

Отношение нестрого порядка есть объединение отношения строгого порядка и отношение тождественности. Каждому отношению порядка на множестве можно поставить в соответствие обратное отношение порядка . Например, отношение больше и меньше на множестве действительных чисел.

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

Пусть – упорядоченное множество с отношением строго порядка . Об упорядоченной паре говорят, что элемент предшествует элементу .

Пусть – вполне упорядоченное множество. Тогда, если для элемента не

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

.

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

Минимальным (максимальным) элементом множества , на котором задано отношение нестрого порядка, называют такой элемент , что для всякого элемента , который сравнивается с , имеет место неравенство .

Например, на множествах целых, рациональных и действительных чисел отношения «» есть отношения нестрого полного порядка, а отношения «» есть отношения строго полного порядка. Отношение «» есть отношение нестрого частичного порядка на множестве (булеан).

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

и пишем .

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

Диаграмма Хассе дает полную информацию об исходном частичном порядке.

Пример. Дано, что отношение «…делитель…» определяет частичный порядок на множестве . Составьте таблицу предшественников и непосредственных предшественников, после чего постройте диаграмму Хассе.

элемент	предшественник	непосредственный предшественник
	нет	нет
	1,2,3	2,3
	1,2,3,6
	1,2,3,6

Рис. 10

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

Всякий частичный порядок на конечном множестве может быть доведен до полного.

В случаях, когда речь идет про множество людей, имеют место отношения доминирования.

Бинарное отношение называют отношением доминирования, если оно антирефлексивно и антисимметрично. Говорят, что доминирует над (), когда в каком либо смысле преобладает над .

Например, если внутри организации существует отношение подчинения, то

для двух членов организации один доминирует над другим, если он им руководит.

Функции

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

Функцией или отображением из множества во множество называется бинарное отношение , при котором каждый элемент множества связан с единственным элементом множества . Другими словами, для каждого существует ровно пара или из того, что и следует .

Функция из в обозначается и .

Если ― функция и , то говорят, что . Элемент называется образом элемента , а элемент называется прообразом элемента .

Если , то пишем ( ― значение функции при значении аргумента ) или (функция ставит в соответствие элементу элемент ).

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

Пример. Определите, какие из следующих отношений между множествами и являются функциями из множества в .

(а) ;

(б) ;

(в) .

Решение.

(а) отношение ― не функция, поскольку элементу соответствует два разных элемента множества : 1 и 2.

(б) отношение является функцией.

(в) последнее отношение не является функцией, так как элементу не соответствует ни одного элемента.

Тождественное отношение является функцией , для которой для всех .

Множество называют областью определения функции и обозначают . А множество ― областью возможных (потенциальных) значений функции.

Если , то множество называют образом множества . Это означает, что множество состоит из образов элементов множества при отображении . Ясно, что .

Образ множества при отображении называется множеством значений данного отображения и обозначается через .

Рассмотрим некоторые важные свойства функций.

Пусть ― функция. Функция будет называться инъективной (инъекцией) или 1-1 функцией, если из того, что следует, что для всех . Это определение логически эквивалентно тому, что

,

т.е. у инъективной функции нет повторяющихся значений. Иными словами, разные входные данные дают различные выходные данные. Если ― инъекция, то пишут

.

Будем называть функцию сюръективной или сюръекцией, или «функцией

на», если множество ее значений совпадает с областью значений. Это означает, что

для каждого найдется такой , что . Будем писать .

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

Существует также классификация отображений по мощности.

Отображение на множество «сюръекция» ― соответствие, при котором каждому элементу множества указан единственный элемент множества , а каждому элементу множества можно указать хотя бы один элемент (т.е. один и больше) множества .

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

Функция называется биективной функцией (взаимно-однозначной функцией) или просто биекцией, если она как инъективна, так и сюръективна.

Если ― биекция между и , то пишут . Простейшим примером биекции есть функция .

Примеры отображений (функций) представлены на рис. 11

Рис. 11

Пример. На рис. 12 графически показаны функции . Функция сюръективна, но не инъективна, инъективна, но не сюрьективна, является биективной, не инъективна и не сюръективна.

Рис. 12

Пример. Биекцией между множеством натуральных чисел и множеством целых чисел является функция , для которой

Обратные функции и композиция функций

Любая функция ― бинарное отношение. Поэтому можно построить

обратное отношение . Если мы снова получим функцию, то исходную функцию

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

Функция состоит из пар вида , где . Если обратима, то обратная функция состоит из пар вида , где . Значит, обратимая функция должна удовлетворять условию: если , то . Другими словами, обратная функция переворачивает действие исходной функции.

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

Примем без доказательства следующую важную теорему.

Теорема. Функция обратима тогда и только года, когда она биективна.

Рассмотрим теперь композиции функций.

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

Сформулируем основные свойства композиции функций в виде предложения.

Предложение. Пусть и . Тогда и

1. Если , то .

2. Если и ― сюръективные функции, то ― сюръекция.

3. Если и ― инъективные функции, то ― инъекция.

4. Если и ― биективные функции, то ― биекция.

5. Если (биекция), то и .

6. Если и ― обратимые функции, то .

Следует отметить, что композиция функций не коммутативна ,

однако подчиняется ассоциативному закону .

Пример. Рассмотрим две функции и . Найти композиции .

Решение. Все четыре новые функции определены на множестве действительных чисел со значениями из этого множества. Тогда

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

Следует отметить, что в некоторых особенно мощных языках, известных как языки функционального программирования, основные операторы определены в терминах функций. Главная особенность таких языков – возможность построения новых, более сложных операторов из основных. Чтобы уметь это делать, необходимо в совершенстве владеть композицией функций.