Виды отображений. Обратное отображение

При отображении X в Y каждый элемент множества X соответствует одному и только одному элементу из Y. На элементы множества Y ограничений не накладывается. Может случиться, что некоторые элементы множества Y не являются образами ни одного элемента множества X, другие являются образами точно одного элемента множества X, третьи – нескольких или даже бесконечного множества элементов множества X.

Определение. Если каждый элемент множества Y является образом хотя бы одного элемента из X, то такое отображение называют сюръекцией или отображением множества X на множество Y.

На рисунке 12 приведен пример графа такого отображения.

Рис. 12

Заметим, что в множестве Y пришлось взять «меньше» элементов, чем в X. Рассмотрим теперь случай, когда в Y «больше» элементов, чем в X. В этом случае мы получим отображение множества X в множество Y.

Определение. Если каждый элемент множества Y является образом не более одного элемента из X, отображение называют инъекцией.

На рисунках 13 и 14 приведены примеры графов таких отображений.

Возьмем теперь в X и Y «поровну» элементов. Построим графы отображений.

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

Примеры графов таких отображений приведены на рисунках 15 и 16.

П р и м е р. Пусть X – множество пальто в гардеробе, a Y – множество крючков в этом гардеробе. Поставим в соответствие каждому пальто крючок, на котором оно висит.

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

С биекцией связано понятие обратного отображения. Если соответствие R – биекция, обратное соответствие R^-1 тоже биекция, сопоставляющая с каждым элементом из Y точно один элемент из X так, что если xRy, то yR^-1x. Чтобы из графа отображения R получить граф обратного отображения R^-1, достаточно повернуть все стрелки в противоположную сторону.

Эквивалентные множества

Определение. Если существует (хотя бы одно) биективное отображение между множествами X и Y, то говорят, что множество X эквивалентно множеству Y.

Обозначают: Х ~ Y.

Покажем, что отношение эквивалентности множеств обладает свойствами рефлексивности, симметричности и транзитивности. То есть докажем следующие 3 утверждения:

1) для любого множества X имеем Х ~ Х;

2) для любых двух множеств X и Y, если X ~ Y, то Y ~ X;

3) для любых трех множеств X, Y, Z, если X ~ Y и Y ~ Z, то X ~ Z.

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

Докажем теперь второе утверждение. Отношение X ~ Y означает, что существует биективное отображение между элементами этих множеств. Рассмотрим обратное отображение между множествами Y и X, оно тоже будет биективным. Значит, Y ~ X.

Наконец, докажем утверждение 3. Действительно, отношение
Х ~ Y означает, что существует биективное отображение R: X ® Y, а отношение Y ~ Z означает, что существует отображение Q: Y ® Z. Построим отображение F: X ® Z следующим образом: с каждым элементом х Î Х сопоставим элемент z Î Z так, что если у = R(x), то z = Q(y). Это означает, что F(x) = Q(R(x)). Отображение F называется суперпозицией отображения R и Q, обозначается также F = Q R. Совершенно очевидно, что F – биективное отображение. Следовательно, X ~ Z.

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